Table of Contents

Chess - Programming - Magic BitBoards - Magic BitBoard Principle

Magic BitBoard Principle

The basic principle is:

  1. 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).
  2. Perform a bitwise AND of T with the bitmask of occupied squares on the board. Let's call the latter O (for Occupied).
  3. 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).
  4. 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).