Differences

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

--- chess:programming:magic_bitboards:calculate_magic_numbers [2021/10/27 22:57] – [Chess - Programming - Magic BitBoards - Calculate Magic Numbers] peter
+++ chess:programming:magic_bitboards:calculate_magic_numbers [2021/10/28 00:00] (current) – [Determine Magic Numbers] peter
@@ Line 40: / 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 48: / Line 48: @@
   * In this example, there are pieces on b4, c4, e2, e5, and e7.
   * 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).
@@ Line 60: / Line 60: @@
 ----
-====== Generate a Blocker Mask for all squares ======
+===== Generate a Blocker Mask for all squares =====
-A Blocker Mask is needing to be generated for all squares, for both the Rook and Bishop.
+A Blocker Mask is needed to be generated for all squares, for both the Rook and Bishop.
 <WRAP info>
@@ Line 70: / Line 70: @@
 ----
-====== Generate all possible Blocker Boards for all squares ======
+===== 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.
@@ Line 83: / Line 83: @@
 ----
-====== Determine Magic Numbers ======
+===== Determine Magic Numbers =====
 For each Square/Piece combo try random 64-bit numbers and see if they are magic.
@@ Line 90: / Line 90: @@
 <code cpp>
-return ((blockerboard*magic) >> (64-bits));
+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>
@@ Line 103: / Line 116: @@
 **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 found.
+  * 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>
@@ Line 113: / Line 126: @@
 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>
 ----
@@ Line 124: / Line 146: @@
 <code cpp>
 // Retrieves the Move Board for the given square and occupancy board.
-uint64_t magic_move_rook  (int8_t square, uint64_t occupancy)
+uint64_t magic_move_rook(int8_t square, uint64_t occupancy)
 {
   // Remove occupants that are not in the Blocker Mask for this square.
@@ Line 136: / Line 158: @@
 }
 </code>
+<WRAP info>
+**NOTE:**
+  * **index** points to the right spot in the moveboard array.
+</WRAP>
 ----