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:

// Find index of lowest bit in a bitboard
final long MAGIC = 0x021bb2bf47316a4fL; 

const unsigned int lowBitTable[64] =
{
    0,  1,  2,  7,  3, 44,  8, 34,
    4, 55, 20, 45, 40,  9, 35, 58,
    5, 32, 53, 56, 51, 21, 46, 23,                     
   41, 17, 48, 10, 36, 13, 59, 25,                     
   63,  6, 43, 33, 54, 19, 39, 57,                     
   31, 52, 50, 22, 16, 47, 12, 24,                     
   62, 42, 18, 38, 30, 49, 15, 11,                     
   61, 37, 29, 14, 60, 28, 27, 26
};

int lowBitIndex(long b)
{
    return lowBitTable[(int)(((b&-b)*MAGIC) >>> 58)];
}

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 *