Chess - Programming - Magic BitBoards - Calculate Magic Numbers

Chess - Programming - Magic BitBoards - Calculate Magic Numbers

The following functions are needed:

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);

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.

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

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).

Generate a Blocker Mask for all squares

A Blocker Mask is needed to be generated for all squares, for both the Rook and Bishop.

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.

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.

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.

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:

magical_index = ((blockerboard*magic) >> (64-bits));

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.

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.

Using the Magics at Program Startup

All of the Blocker Masks, Blocker Boards, and Move Boards should be initialized.

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.

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:

// 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];
}

NOTE:

index points to the right spot in the moveboard array.