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