Differences

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

--- chess:programming:magic_bitboards [2021/10/27 14:38] – created 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).
+===== References =====
-  * 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.
+https://stackoverflow.com/questions/7365562/de-bruijn-like-sequence-for-2n-1-how-is-it-constructed
-  * 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.
+https://www.stmintz.com/ccc/index.php?id=306404
-  * 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>