Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Chess - Programming - Magic BitBoards - Calculate Magic Numbers ======

The following functions are needed:

<code cpp>
uint64_t blockermask_rook   (int square);
uint64_t blockermask_bishop (int square);
uint64_t moveboard_rook     (int square, uint64_t blockerboard);
uint64_t moveboard_bishop   (int square, uint64_t blockerboard);
uint64_t blockerboard       (int index, uint64_t blockermask);
</code>

<WRAP info>
**NOTE:**  These functions do not need to be particularly fast, because they will only be used when looking for magic numbers; and once at program startup before the magic numbers are used.

  * Therefore any technique can be used in these functions.

</WRAP>

----

<code>
/* Example, Rook on e4:
 *  
 *    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 
 *    0 0 0 0 1 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 1 0 0 0 
 *    0 1 1 1 0 1 1 0         0 1 1 0 0 0 0 0         0 0 1 1 0 1 1 1 
 *    0 0 0 0 1 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 1 0 0 0         0 0 0 0 1 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 
 */
</code>

<WRAP info>
The **Blocker Mask** is all of the squares that can be occupied and block a piece from moving further.

  * 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.
  * In this case, there are 10 ones, so there are 2^10 (1024) possible permutations of pieces that can block an e4 rook.


The **Blocker Board** is __one__ of these permutations.

  * 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).
    * blockers = occupancy & blockermask.

The **Move Board** is the resulting available moves for the Piece, for a given Blocker Board.

  * 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>

----