Differences

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

--- chess:programming:magic_bitboards [2021/10/27 15:09] – peter
+++ chess:programming:magic_bitboards [2021/10/30 13:12] (current) – peter
@@ Line 1: / Line 1: @@
 ====== Chess - Programming - Magic BitBoards ======
-===== Magic BitBoard Principle =====
+Magic BitBoards are an efficient way to take a position and obtain the legal moves for a sliding piece.
-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>
+The occupancy bits for a specific piece on a specific square can be multiplied against a "magic" number, and then shifted, to obtain an index in a per-initialized attack table.
 ----
-===== Example =====
+[[Chess:Programming:Magic BitBoards:Calculate Magic Numbers|Calculate Magic Numbers]]
-The Rook can move any amount of positions horizontally but cannot jump over the King.
+[[Chess:Programming:Magic BitBoards:Magic BitBoard Principle|Magic BitBoard Principle]]
-<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 =====
+===== References =====
-<code cpp>
-int xPos = 2;               // Position of the 'K' 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.
+https://stackoverflow.com/questions/7365562/de-bruijn-like-sequence-for-2n-1-how-is-it-constructed
-  int target = lookup[xPos][board];
-  // return (!target & (1 << pos));
+https://www.stmintz.com/ccc/index.php?id=306404
-  int n =7-pos;
-  n != xPos && (board ^= 1 << n);
-}
-</code>