Search code examples
algorithm2d-gameschessbitboard

Not understanding how the bitboard technique works for chess boards

My brain is smoking trying to understand the mechanics of this bitboard technique. In order to make it simple, lets imagine that, instead of chess and a lot of complex piece movements, we have a game with only two pieces and one a row of 8 positions. One piece is a triangle and the other is a circle, like this:

┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │ ▲ │   │   │ ● │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘

The triangle can move like a rook. Any amount of positions horizontally but cannot jump over the circle.

Now imagine that the user moves the triangle to the last position, like this:

┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │   │   │   │ ● │   │ ▲ │
└───┴───┴───┴───┴───┴───┴───┴───┘

For this example the triangle move bitboard is

1 1 0 1 1 1 1 1

and the circle position mask is 

0 0 0 0 0 1 0 0

Obviously the move is illegal, because the triangle cannot jump over the circle but how the software can check if the move is legal using the magic bitboard technique?

Solution

  • You are right that it's not possible to determine valid moves for sliding pieces by using only bitwise operations. You'll need bitwise operations and precomputed lookup tables.

    The Chess case

    Most recent chess engines are using the technique known as Magic Bitboards.

    The implementations vary, but the basic principle is always the same:

    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
reachable_squares = lookup[I]

    T, M, S and lookup are all precomputed 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. As noticed by Bo Persson in the comments, 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.

    Your test case

    Now going back to your example:

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

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

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

    We'd have:

    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.

    Below is a JS snippet to illustrate that method. Click on the board to toggle the enemy pieces.

    var xPos = 5,          // position of the 'X' piece
    board = 1 << xPos, // initial board
    lookup = [];       // lookup table

function buildLookup() {
  var 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;
      }
    }
  }
}

function 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)));
    }
  }
}

$('td').eq(7 - xPos).html('X');

$('td').click(function() {
  var n = 7 - $('td').index($(this));
  n != xPos && (board ^= 1 << n);
  update();
});

buildLookup();
update();
    td { width:16px;border:1px solid #777;text-align:center;cursor:pointer }
.reachable { background-color:#8f8 }
    <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<table>
  <tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
</table>