Differences

This shows you the differences between two versions of the page.

--- chess:programming:magic_bitboards:magic_bitboard_principle [2021/10/27 22:13] – created peter
+++ chess:programming:magic_bitboards:magic_bitboard_principle [2021/10/27 22:14] (current) – peter
@@ Line 1: / Line 1: @@
 ====== 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 │   │   │
+└───┴───┴───┴───┴───┴───┴───┴───┘
+   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>
+* 2^8 = 2048 entries
+</code>
+  * Obviously we cannot do that for chess, as it would contain: <code>
+* 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>