Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== 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:

<code>
I = ((T & O) * M) >> S
</code>

<WRAP info>
**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: <code>
I = ((T[P] & O) * M[P]) >> S[P]
</code>
    * 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 **<nowiki>((T & O) * M) >> S</nowiki>** 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.

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

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

<code>
┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │   │   │   │ k │   │ R │
└───┴───┴───┴───┴───┴───┴───┴───┘
</code>


<WRAP info>
**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: <code>
reachable_squares = lookup[P][board]
</code>

  * This will result in a lookup table containing: <code>
8 * 2^8 = 2048 entries
</code>

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

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

</WRAP>

----

===== Build a Lookup Table =====

<code cpp>
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' : '')
}
</code>

<WRAP info>
**NOTE:**  The table is storing all possible positions of the Rook piece and each possible board (from 00000000 to 11111111).
</WRAP>