Why calculate magic numbers for bitboards rather than using the blocker bitboard as a key?

Question

I am modifying my chess engine to use a bitboard based approach to board representation instead of the current mailbox approach.

I've read much about using magic bitboards to retrieve bitboards of legal moves.

The approach is summed up in this Chess SE post (Understanding magic bitboard) with the following pseudocode

bbBlockers = bbAllPieces & occupancyMaskRook[C3]

databaseIndex = (int)((bbBlockers * magicNumberRook[C3]) >> rookMagicShifts[C3])

bbMoveSquares = magicMovesRook[C3][databaseIndex] & ~bbFriendlyPieces

I am comfortable with how this works. However, I am not sure why we bother with the magic numbers. Essentially, multiplying the blocker bitboard by the magic number for a given square gives us a key which we then use to look up the moves bitboard.

Why can't we just use the integer value of the blockers bitboard as the key instead since it is just a 64 bit value?

Going back to the pseudo-code above it would be as follows:

bbBlockers = bbAllPieces & occupancyMaskRook[C3]
      
bbMoveSquares = rookMoves[C3][bbBlockers] & ~bbFriendlyPieces

Which indicates that removing magic numbers would reduce the number of operations needed.

Also, looking at the numbers involved for rooks we have 64 possible squares and a maximum of 4096 (2¹²) which gives us 262,144 dictionary entries. Each entry is 16 bytes (8 for the key and 8 for the payload) so we only need to store 4,194,304 bytes (roughly 4MiB) so the storage requirements aren't huge. The values for bishops will be less so I'm not sure that this is a justification for avoiding the approach.

I could just be missing a key point so I hope someone can help clarify things for me.

Answer 1

Basically, what you're missing is that while there may only be 64*2¹² possible different blocker values to consider, those values are spread out across almost the entire 64-bit number range, which is far too large to use as an index into an array (as that would require the array to have a capacity of 2⁶⁴ slots). So those blocker bitboards need to be transformed into some other number that can be used to index into a reasonably sized array.

A traditional, general purpose hashmap could do this, but the algorithms used by them are built to spread similar values far apart in order to minimize collisions. However, in the case of magic bitboards, we know that there are many different blocker boards that will map into the same attack board, and our ideal state would be that the hashing algorithm will map all of the blockers that yield the same attacks into the same index in the table.

The magic numbers involved with magic bitboards are meant to push all of the relevant bits from the blocker board into the same few bits so that we can then use just those bits from the result as the key into our table of attack boards. In the ideal state for rook moves, we would only need 12 bits, which would reduce the total size of the array from 2⁶⁴ down to 2¹² possible indexes.

Essentially, the blocker board values need to be hashed in some way in order to be useable as a key into a dictionary. Given that fact, we may as well use a purpose-built hashing algorithm that is able to make efficient use of our resources.

This site's explanation is what made this click with me.

Answer 2

I tested both approaches.

Using the dictionary as detailed above does work and is conceptually easy to understand.

Using magic number also works and seems to be much faster - for example, on my test machine it completes Perft tests between 30% and 50% quicker than the dictionary approach. It is however more complex in its approach and requires some initialisation code to set up the magic numbers.

This means that, as with many things, it is a trade-off between simplicity and speed.

As far as I can tell, the reason for the difference is that the dictionary approach hashes my 64 bit key to a 32 bit hash behind the scenes. I believe that this hashing is much more CPU intensive than the multiplication, two list look ups and one bitwise shift needed when using magic numbers.