Piece Movement Part 2: Magic Bitboards

The Problem With Sliding Pieces

The last post went over lookup tables for non-sliding pieces. This works for non-sliding pieces (Pawn, King, Knight) because their moves are consistent, meaning they dont rely on the other pieces position.

The Bishop, Rook, and Queen's moves rely on other pieces as they can be blocked from moving any further. For example, to know if a Queen can move from a4 to a2 we first need to know if any pieces are on a3 incase it's blocked.

There are a LOT of different board states that we would need to take into consideration if we were to create a simple lookup table for this. Instead we need to find a way to make the combination of possible blocker pieces along the possible moves for the piece an index for an array. This is where we use magic bitboards.

What is a Magic Bitboard?

A magic bitboard is a technique used to map which squares are occupied along a sliding pieces movement path to a specific index in a pre-calculated attack lookup table. It relies on a magic number to perform hashing in order to condense the index size. Here is the process

index = (occupancyBitboard * magicNummber) >> shift;

• occupancyBitboard - A bitboard of pieces currently on the path of a sliding piece

• magicNumber - A specific 64-bit number that makes the occupancy bits denser

• Shift - We need to shift the result to get the correct, small, index

Why use Magic Bitboards?

Without magic bitboard, you would need to calculate the moves every time you need them. This would require looping in each direction (4 for the bishop or rook, 8 for the queen) until you hit a blocker or the edge of the board, every time we want to move a sliding piece. Doing this is slower than using magic bitboards. Magic bitboards cut down the move time into just a simple lookup, just like a lookup table from the last post.

How it works

1) Define a mask of all squares the piece can potentially go to excluding the edges of the board. Dont take into account any pieces on the board just yet. You do not need to take into account the last square of the board as it doesnt matter if a piece is there or not, it cannot block any moves as no more squares are beyond that squre.

2) Make a way to generate every possible variation of pieces that could be in that mask. This will be a lot, the GIF just shows a few.

3) Get the magic number that, when multiplied, makes a unique index for every unique attack pattern. Here is a list of these that I used.

You will also need the shifts, which you can find here. Both the shifts, and the magic numbers are part of my chess engine github repo, look in there if you're stuck with anything.

Here is some code I wrote as an example.

//get blocker mask
ulong occupancy = allPiecesBitboard & rookMasks[27];

//use the magic number and shift to find the index
int index = (int)((occupancy * rookMagics[27]) >> rookShifts[27]);

//look up the pre-calculated attack bitboard
ulong attacks = rookTable[27][index];

I used for loops in each direction to get the attack bitboards and then storing the output. This works just fine, however, there are much faster ways to go about this including PEXT which is a hardware optimisation on modern systems that replaces the magic number multiplication and shift step, but just in one CPU instruction.

The Trade Off

Magic bitboards do require more memory usage than calculating the moves whenever you need them. This is nearly never an issue, however, as the memory required is typically less than 5MB. It's just something to be aware of.

As the calculations are done at start up, the programs start up time will be a bit slower. This for me wasn't noticeable.