Differences

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

--- chess:programming:magic_bitboards [2021/10/27 14:45] – 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:
+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.
-  - 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:
+[[Chess:Programming:Magic BitBoards:Calculate Magic Numbers|Calculate Magic Numbers]]
-<code>
+[[Chess:Programming:Magic BitBoards:Magic BitBoard Principle|Magic BitBoard Principle]]
-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 ((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.
-</WRAP>
 ----
-===== Example =====
+===== References =====
-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:**  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.
+https://stackoverflow.com/questions/7365562/de-bruijn-like-sequence-for-2n-1-how-is-it-constructed
-</WRAP>
+https://www.stmintz.com/ccc/index.php?id=306404