Re:Magic Bitboards: Finding all valid bishop moves in a 64-b...
by ZirconiumX on Wednesday April 18, 2018 @02:53AM
(#16865235)
Something interesting to note is the variety of ideas based on this. What you see there is "plain" magic bitboards, where the right-shift is constant and used to index a two-dimensional array.
That's rather wasteful, because the centre squares need only around 2^5 occupancies, which is why "fancy" magic bitboards exist.
In these, the right-shift is variable, and the occupancy calculation is added to a table of offsets to get the output, shrinking the tables from about 2MB to 800KiB for even the "easy" right-shift amounts.
So the question is whether we can find smaller magic numbers[1]. Niklas Fiekas has found a trick[2] that helps reduce the brute-force search space for magics, but it's still not trivial to solve.
That's rather wasteful, because the centre squares need only around 2^5 occupancies, which is why "fancy" magic bitboards exist. In these, the right-shift is variable, and the occupancy calculation is added to a table of offsets to get the output, shrinking the tables from about 2MB to 800KiB for even the "easy" right-shift amounts.
So the question is whether we can find smaller magic numbers[1]. Niklas Fiekas has found a trick[2] that helps reduce the brute-force search space for magics, but it's still not trivial to solve.
[1]: http://chessprogramming.wikispaces.com/Best%20Magics%20so%20... [2]: http://www.talkchess.com/forum/viewtopic.php?t=65187
I could also make a write-up of Hyperbola Quintessence, which I think is a fantastic bit of bit-twiddling, if someone is interested.