Chess - Programming - Magic BitBoards - Magic BitBoard Principle

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.

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 = 5;               // Position of the 'Rook' piece.
UINT64 board = 1 << xPos,   // Initial board.
UINT 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++) 
    {
      // Initialize to zero.
      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;
      }
    }
  }
}
 
 
bool isReachable(int pos)
{
  // TODO.
 
  // Get valid target squares from the lookup table.
  int target = lookup[xPos][board];
 
  // return (!target & (1 << pos));
 
  int n =7-pos;  // Need to work backwards.
 
  // Check if pos is valid and reachable.
  if (n != xPos && (board ^= 1 << n))
    return true
  else
    return false;
 
  // Reachable = (target & (1 << n)).
  //if ((board & (1 << n) ? 'O' : '')
}

NOTE: The table is storing all possible positions of the Rook piece and each possible board (from 00000000 to 11111111).

Wiki

Table of Contents

Chess - Programming - Magic BitBoards - Magic BitBoard Principle

Magic BitBoard Principle

Example

Build a Lookup Table