Sliding move generation using magic bitboard

It's good that we can assume magic bitboard functions are available, but in general bitboard move generation functions can accept any technique that produces a bitboard that gives the possible squares to move to. Say RookMoves is such a function, then you would populate the move list as follows: 

UInt64 pieceBitboard = Bitboard[SideToMove | Piece.Rook];
UInt64 targetBitboard = ~Bitboard[SideToMove | Piece.All];

while (pieceBitboard != 0) {
   Int32 from = Bit.Pop(ref pieceBitboard);
   UInt64 moveBitboard = targetBitboard & RookMoves(from, OccupiedBitboard);

   while (moveBitboard != 0) {
       Int32 to = Bit.Pop(ref moveBitboard);
       moveList[index++] = Move.Create(this, from, to);
   }
}

where Bit.Pop(ref x) returns the least significant bit in x while simultaneously "popping" (removing) it from x.

To validate a move (I'm interpreting this as confirming move validity), you would either check to see if the move is in the move list, or perform the move and see whether it leaves you in check. Of course, you might need to check whether it obeys the movement rules for the piece but that is trivial. 

if ((RookRays[move.From] & Bit.At[move.To]) == 0)
   return false;

Int32 side = SideToMove;
position.Make(move);
Boolean valid = position.InCheck(side);
position.Unmake(move);

return valid;

Simply put, magic bitboards are an efficient way to take a position and obtain the legal moves for a sliding piece.

First, you need to find some magic numbers. Some of the code you write to find the magic numbers will also be re-used when you use the magic numbers.

To start off, you need to write 5 functions. These don't need to be particularly fast, because you will only use them when looking for magic numbers and once at program startup before you use your magic numbers. You can use any old technique in these functions.

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

So you may be asking yourself, da f%q are a blocker mask, move board, and blocker board? Well, I just made the terms up, but here's what I mean by them:

/* Example, Rook on e4:
 *  
 *    The blocker mask        A blocker board         The 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 your piece from moving further. The edge squares don't need to be a part of that, because your piece can't move further past that square anyway. The number of 1's in this bitboard determine how large of a lookup table you need 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 are enemy and friendly pieces. A blocker board is always a subset of the blocker mask (it needn't show pieces on other squares (e.g., blockers = occupancy & blockermask;)).

The move board is the resulting available moves for your piece, for a given blocker board. This includes possible captures for your piece. Note that it also includes capturing your own pieces (but you can just AND it with a NOT of your own piece locations to remove those).

So, basically you need to generate the blocker mask on all squares, for both the rook and bishop. And you also need to generate all possible blocker boards on each square, for both the rook and bishop. As you generate the blocker boards, you should also generate the resulting move boards. Store all of this stuff in arrays for later use.

Now that you have that done, for each square/piece combo you try random 64 bit numbers and see if they're magic. You'll know if they're magic by using the magic formula, return ((blockerboard*magic) >> (64-bits));, which will create a magical index from 0..2^bits (0..1024 in the case of the e4 rook). 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 muggle number, and you should try a new one.

Once you get that down, you'll have 64 magic rook numbers and 64 magic bishop numbers. To use them, at program startup you will initialize all of the blocker masks, blocker boards, and move boards. And now your 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 aren't 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];
}

Tags:

Chess

Bitboard

Recent Posts