Magic bitboards

Magic bitboards are a relatively recent development used in most modern chess engines. They are a bit difficult to understand though. Bitboards use an integer (usually a 64-bit unsigned) to store 64 individual boolean values. For chess they are perfect, because a single integer can story information about the entire board. For example, an integer could store information about which squares contain a white piece.

Bitboards have been used for a while, but one of the problems is looping over the board. One has to find the next set bit in a bitboard. Modern processors have instructions for finding the highest (or lowest) set bit, but this usually requires processor dependent inline assembly. Earlier chess engines used a combination of logical AND’s with lookup tables. For example (bitboard & 0xFF) quickly determines whether the lowest 8 bits contain at least a 1. A 256 byte lookup table contains the pre-computed position of the lowest bit.

A faster way is using magic bitboards. We’ll skip the mathematical details for now, but the idea is to multiply sparse bitboards (bitboards with a low number of 1’s) by a ‘magic’ constant. This constant is chosen, such that the information about the bit pattern is shifted to the highest bits of the result value. Shifting this to the right results in a small unique value that can be used to index a lookup table.

As an example, here’s how to compute the index of the lowest bit of a bitboard:

The ‘b&-b’ trick isolates the lowest bits, the multiplication gives a unique 6-bit value in the highest 6 bits for all 64-bit integers with a single bit set. More details about the mathematics of magic bitboards in a later post.


Leave a Reply

Your email address will not be published. Required fields are marked *