This is an old revision of the document!

Chess - Programming - Magic BitBoards

Magic BitBoard Principle

The basic principle is:

Isolate the squares that a given piece may reach from a given position, without taking board occupancy into account. This gives us a 64-bit bitmask of potential target squares. Let's call it T (for Target).
Perform a bitwise AND of T with the bitmask of occupied squares on the board. Let's call the latter O (for Occupied).
Multiply the result by a magic value M and shift the result to the right by a magic amount S. This gives us I (for Index).
Use I as an index in a lookup table to retrieve the bitmask of squares that can actually be reached with this configuration.

To sum it up:

I = ((T & O) * M) >> S

NOTE:

Reachable_squares = lookup[I]

T, M, S and lookup are all pre-computed and depend on the position of the piece (P = 0 … 63).
So, a more accurate formula would be:
```
I = ((T[P] & O) * M[P]) >> S[P]
```
- reachable_squares = lookup[P][I]

The purpose of step #3 is to transform the 64-bit value T & O into a much smaller one, so that a table of a reasonable size can be used.

What we get by computing ¹⁾

¹⁾

T & O) * M) » S is essentially a random sequence of bits, and we want to map each of these sequences to a unique bitmask of reachable target squares.

The 'magic' part in this algorithm is to determine the M and S values that will produce a collision-free lookup table as small as possible.
This is a Perfect Hash Function problem.
However, no perfect hashing has been found for magic bitboards so far, which means that the lookup tables in use typically contain many unused 'holes'.
Most of the time, they are built by running an extensive brute-force search.

</WRAP>

===== Example ===== The Rook can move any amount of positions horizontally but cannot jump over the King.

┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │ R │   │   │ k │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘ 
  7   6   5   4   3   2   1   0

How to verify that the following is an illegal move, because the Rook cannot jump over the King?

┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │   │   │   │ k │   │ R │
└───┴───┴───┴───┴───┴───┴───┴───┘

NOTE: It is not possible to determine valid moves for sliding pieces by using only bitwise operations.

Bitwise operations and pre-computed lookup tables will be needed.

Here, the position of the piece is in [0 … 7] and the occupancy bitmask is in [0x00 … 0xFF] (as it is 8-bit wide).

Therefore, it is entirely feasible to build a direct lookup table based on the position and the current board without applying the magic part.

This would be:
```
reachable_squares = lookup[P][board]
```

This will result in a lookup table containing:
```
8 * 2^8 = 2048 entries
```

Obviously we cannot do that for chess, as it would contain:
```
64 * 2^64 = 1,180,591,620,717,411,303,424 entries
```

Hence the need for the magic multiply and shift operations to store the data in a more compact manner.

===== Build a lookup table =====

int xPos = 2;               // Position of the 'K' piece.
UINT64 board = 1 << xPos,   // Initial board.
lookup = [];                // Lookup table.
 
void buildLookup() 
{
  int i, pos, msk;
 
  // Iterate on all possible positions.
  for(pos=0; pos<8; pos++) 
  {
    // Iterate on all possible occupancy masks.
    for(lookup[pos] = [], msk=0; msk<0x100; msk++) 
    {
      lookup[pos][msk] = 0;
 
      // Compute valid moves to the left.
      for(i=pos+1; i<8 && !(msk & (1<<i)); i++) 
      {
        lookup[pos][msk] |= 1 << i;
      }
 
      // Compute valid moves to the right.
      for(i=pos-1; i>=0 && !(msk & (1<<i)); i--) 
      {
        lookup[pos][msk] |= 1 << i;
      }
    }
  }
}
 
 
void update() 
{
  // Get valid target squares from the lookup table.
  var target = lookup[xPos][board];
 
  // Redraw board
  for(var n=0; n<8; n++) 
  {
    if(n != xPos) 
    {
      $('td').eq(7 - n)
      .html(board & (1 << n) ? 'O' : '')
      .toggleClass('reachable', !!(target & (1 << n)));
    }
  }
}
 
 
void moveTo(int pos) 
{
  var n = 7 - pos);
  n != xPos && (board ^= 1 << n);
  update();
}
 
 
buildLookup();
update();