Differences

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

--- chess:programming:magic_bitboards:calculate_magic_numbers [2021/10/27 22:27] – peter
+++ chess:programming:magic_bitboards:calculate_magic_numbers [2021/10/28 00:00] (current) – [Determine Magic Numbers] peter
@@ Line 1: / Line 1: @@
 ====== Chess - Programming - Magic BitBoards - Calculate Magic Numbers ======
-To start off, the following functions are needed:
+The following functions are needed:
 <code cpp>
@@ Line 23: / Line 23: @@
 /* Example, Rook on e4:
  *
- *    The blocker mask        A blocker board         The move board
+ *    Blocker Mask            Blocker Board           Move Board
+ *    ------------            -------------           ----------
  *    0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0
  *    0 0 0 0 1 0 0 0         0 0 0 0 1 0 0 0         0 0 0 0 0 0 0 0
@@ Line 39: / Line 40: @@
   * The edge squares do not need to be a part of that, because the piece cannot move further past that square anyway.
-  * The number of 1s in this BitBoard determine how large of a lookup table is needed for this piece & square combination.
+  * The number of 1s in this BitBoard determine how large of a lookup table is needed for this Piece & Square combination.
   * In this case, there are 10 ones, so there are 2^10 (1024) possible permutations of pieces that can block an e4 rook.
@@ Line 46: / Line 47: @@
   * In this example, there are pieces on b4, c4, e2, e5, and e7.
-  * These are enemy and friendly pieces.
+  * These pieces are both enemy and friendly pieces.
-  * A Blocker Board is always a subset of the blocker mask (it need not show pieces on other squares.
+  * A Blocker Board is always a subset of the blocker mask (it need not show pieces on other squares).
     * blockers = occupancy & blockermask.
-The **Move Board** is the resulting available moves for your piece, for a given Blocker Board.
+The **Move Board** is the resulting available moves for the Piece, for a given Blocker Board.
-  * This includes possible captures for this piece.
+  * This includes possible captures for this Piece.
     * This also includes capturing own pieces (but these can easily be removed by doing an AND with a NOT of own piece locations).
 </WRAP>
+----
+===== Generate a Blocker Mask for all squares =====
+A Blocker Mask is needed to be generated for all squares, for both the Rook and Bishop.
+<WRAP info>
+**NOTE:**  Blocker Masks for the Queen moves do not need to be generated as the Queen moves can make use of the same Rook and Bishop masks.
+</WRAP>
+----
+===== Generate all possible Blocker Boards for all squares =====
+A Blocker Board is needed to be generate for each square, for both the Rook and Bishop.
+<WRAP info>
+**NOTE:**  As the Blocker Boards are being generated, the resulting Move Boards should also be generated.
+  * Store all of this stuff in arrays for later use.
+</WRAP>
+----
+===== Determine Magic Numbers =====
+For each Square/Piece combo try random 64-bit numbers and see if they are magic.
+Magic numbers can be confirmed by this formula:
+<code cpp>
+magical_index = ((blockerboard*magic) >> (64-bits));
+</code>
+<WRAP info>
+**NOTE:**  This will create a magical index from 0..2^bits (0..1024 in the case of the e4 rook).
+  * **magic** is the random 64-bit number.
+    * At this time this is done by trial-and-error, as no known formula to provide a perfect solution.
+      * It is just luck/probability that a number is found that happens to calculate unique indices for unique MoveBoards.
+    * Ideally no gaps should be between each index, i.e. a perfect hash.
+  * This should result in 64 magic rook numbers and 64 magic bishop numbers.
+    * The index returned by the magic formula is always an integer less than the total number of BlockerBoards.
+  * These indexes will be used to determine where to store each BlockerBoards corresponding MoveBoard within an array.
+    * The MoveBoard are just stored at the index calculated by these pre-programmed good magics.
+  * While this example of the Rook at e4 has 1024 BlockerBoards, each of which has a corresponding MoveBoard, you may end up storing less than 1024 MoveBoards.
+    * For two different BlockerBoards that have the same MoveBoard, the magic could calculate two different indices or it could calculate the same index for both.
+    * As long as the MoveBoards are the same, it is okay for the index to collide.
+</WRAP>
+<WRAP important>
+**WARNING:**
+  * For a certain Piece/Square, if two blocker boards ever generate the same Magical Index but these two blocker boards have different move boards, then this is a conflict, which means the Magic is bad and another one should be tried.
+</WRAP>
+----
+===== Using the Magics at Program Startup =====
+All of the Blocker Masks, Blocker Boards, and Move Boards should be initialized.
+<WRAP info>
+**NOTE:**  The index returned by the magic formula is always an integer less than the total number of BlockerBoards (BB).
+  * Each BB has a corresponding MoveBoard (MB).
+  * When searching for magics, each MB is being calculated  with a slow algorithm and storing the MB at the index calculated by the candidate magic number.
+  * At engine startup, the MBs are recalculated with the slow algorithm and then they are just stored at the index calculated by your pre-programmed good magics.
+</WRAP>
+----
+===== Using the Magics during a game =====
+The program can efficiently look up Move Boards for Bishops and Rooks on any square (and thus also Queens).
+The code for that will look something like this:
+<code cpp>
+// Retrieves the Move Board for the given square and occupancy board.
+uint64_t magic_move_rook(int8_t square, uint64_t occupancy)
+{
+  // Remove occupants that are not in the Blocker Mask for this square.
+  occupancy &= Rook.blockmask[square];
+  // Calculate the magic move index.
+  int index = (occupancy*Rook.magic[square]) >> (64-Rook.bits[square]);
+  // Return the pre-calculated move board.
+  return Rook.moveboard[square][index];
+}
+</code>
+<WRAP info>
+**NOTE:**
+  * **index** points to the right spot in the moveboard array.
+</WRAP>
+----