The Beauty of Bitboards

I really am enjoying coding Maverick using bitboards.  Yesterday I stumbled across a neat way to handle en-passant move generation.

moves = (((board->piecelist[piece] << 7) >> 16 * to_move) & B8H1) & (board->occupied[opponent] | board->ep_square);

The term “board->ep_square” is a bitboard holding the en-passant target capture square.  The last “or” instruction fools the move generation routine into thinking there is piece at this target square.  This means en-passant moves are then handled the same as all other pawn captures (über-cool!!).

Writing Color Blind Chess Code

Back in 1999 I created the first version of Monarch in Delphi.  At that time I wondered just how fast the Delphi code would be.  Would it be able to compete with the then rapidly improving C compilers.  So I wanted my code to be as fast as possible.  While the debate over brute force vs. selective search in computer chess was all but over, I believe a hangover from those times was an industry-wide obsession with speed.  For example, there were still some engines coded purely in assembler (Fritz, Rebel, M-Chess and Genius).  So I wasn’t alone in my “need-for-speed”.  One of the ways I thought I could squeeze out a little extra speed by writing code which is specific for white and black e.g. a white move generator and a black move generator.  Of course it was a nightmare to maintain.  When I found a bug in one part of the code I needed to change it in another part of the code (if I remembered) – a veritable nightmare!!

I believe Fabian Letouzey can take the credit for shifting my mindset away from trying to create ultra-optimized code at all cost.  Back in 2004 I was gobsmacked when I first saw the clarity of Fabian’s code.  And the resulting engine, Fruit 1.0, was strong.  As a result there was a significant shift in computer chess, away from over optimizing and towards clarity and bug free code.

So in Maverick I’m attempting to make the code as clear as possible.  To this end, one of the aims is to write color-blind code i.e. wherever possible try to have one routine which accomplishes the task for both white and black.  An obvious task is move generation, and pawn move generation in particular.  I’ve managed to accomplish this using the following code.  There were some helpful hints from this thread on CCC (I went with H. G. Muller‘s approach):

int forward = 8 - 16 * to_move;
moves = (((board->piecelist[piece] << 8) >> 16 * to_move) & ~(board->all_pieces));

So the left shift by 8 occurs for both white and black pawn, and the right shift is for black only pawn since (16 * t_move) will be zero when to_move is white.  It all works nicely!  Also worth noting – there are no bits lost by the first shift since there are never any pawns on the 8th rank – beautiful!!

All I need to do now is generate castling moves and e-p captures and the basic move generator will be complete!

More Work on Magic Move Data Structures

I spent a couple of hours translating some of my Delphi code into “C”.  Everything seems to be working well.  Hopefully I should be able to start generating moves soon.  Based on my past experience, once you get to the stage where you can make and unmake moves the pace of development picks up; it starts to get interesting and the addictive nature of computer chess programming sucks you in.

I’m certainly enjoying the Microsoft Visual C++ Express IDE.  It’s a well put together system – and it seems super stable.

Generating Magic Multipliers

I finally cracked the process needed to generate magic multipliers.  I didn’t find it trivial.  Here are necessary steps:

1. Create Combination Table:

When generating magic moves the first step is to logically AND the board with the relevant square’s mask.  Let’s use the rook on e5 in the diagram below as an example:

Board with pieces

The mask used is as follows (we’ll call this the AND_MASK):


Note the edge squares are not part of the mask. The reason is simple.  For example, if the rook can move to e2 it can always attack, protect or move  to e1.  This trick also reduced the bits in the mask; an important point as we’ll see in a moment.

So the bitboard after the AND operation only has one bit set, corresponding to the black pawn on f5.  We’ll call this the AND_RESULT.  In this case it look like this:


After the magic operation this will provide a look-up to the possible attacking moves of the rook.  We’ll call this the ROOK_ATTACKS.  In this case it is the following bitboard:


There are a couple of things to note:

  • If g5 was set in the AND_RESULT we’d still have the same ROOK_ATTACKS
  • There are (2 to the power BitCount) possible AND_RESULTs, where BitCount is the number of bits set in the AND_MASK.

So now we need to create a list of all the possible AND_RESULTs as well the corresponding ROOK_ATTACKS.  Once again this isn’t trivial.  How do you create all of the possible permutation of the AND_RESULT?  The key is a little function which take as inputs the AND_MASK and the index you’d like to create (the index being between zero and 2 ^ BitCount).  Here’s the Delphi code I used:

function TMagicGenerator.IndexTo64(AndMask: TBitboard; Index: integer): TBitboard;
i, n, b: integer;
a: TBitboard;
result := 0;
a := AndMask;
n := PopCount(a);
for i := 0 to n − 1 do
b := BSF_Reset(a);
if IsBitSet(i, index) then
SetBit(b, result);

This loops through all of the bits set in AndMask.  Each bit has an index (in this case “i” which runs form 0 to n-1) and a position (in this case “b” which is between 0 and 63).  If index also has the “i” bit set then the “b” bit is also set in the result.  It’s worth spending a couple of minutes getting your head around this.  As I said it’s not trivial but nevertheless core to the whole approach. 

The function BSF_Reset(a) returns the position of the first set bit and resets that bit.  The other functions are self explanatory.

Once we have this function we can create a list of all the possible AND_RESULTS and their corresponding ROOK_ATTACKS.

 procedure TMagicGenerator.CreateAllRookMasks(b: Tbitboard; square: integer);
n: integer;
i: integer;
AndMask, AttackMask: TBitboard;
n := PopCount(b);
Setlength(AndAttackMask, Round(Power(2, n)));
for i := 0 to High(AndAttackMask) do
AndAttackMask[i].AndMask := IndexTo64(b, i);
AndAttackMask[i].AttackMask := CreateRookAttacks(square, AndAttackMask[i].AndMask);

2. Test Candidate Magic Multipliers:

For a magic to be valid one of two condition must be met:

  • The magic must map each AND_RESULT to a unique position in a look-up table


  • The magic must map the AND_RESULTS to a position with the same ROOK_ATTACKS

This can be accomplished by:

  1. Creating the look-up table
  2. Setting all values to zero
  3. Looping through all AND_RESULT transforming them into a look-up table index
  4. Check to see if the look-up table already contains a ROOK_ATTACK
  5. If it does have a ROOK_ATTACK already stored then it must be the same as the one corresponding to the AND_RESULT – if it isn’t the magic is not valid
  6. The magic is valid if this sequence can be completed for all possible AND_RESULTs

The code I used for this is here:
function TMagicGenerator.MagicWorks(xMagic: uint64): boolean;
i: integer;
b: uint64;
// Zero Test table
for i := 0 to High(MagicTable) do
MagicTable[i] := 0;
// Test each possible mask
result := true;
i := High(AndAttackMask);
b := (AndAttackMask[i].AndMask * xMagic) shr (64 - RookBitCount);
if MagicTable[b] = 0 then
MagicTable[b] := AndAttackMask[i].AttackMask
else if MagicTable[b] <> AndAttackMask[i].AttackMask then
result := false;
until (result = false) or (i < 0); end; procedure TMagicGenerator.FindRookMagics(Trials: integer); var i, n: Integer; Square: integer; xMagic: uint64; RookMask: TBitboard; begin SetLength(MagicTable, Round(Power(2, RookBitCount))); // Initialize for Square := 0 to 63 do begin if assigned(fOnNewSquare) then fOnNewSquare(self, square); RookMask := CreateRookMask(Square); CreateAllRookMasks(RookMask, Square); for i := 0 to Trials do begin if (i and 1023) = 0 then Application.ProcessMessages; // Find a candidate magic repeat xMagic := SparseRandom64;
until BitCount(xMagic) > 6;
// Does Candidate work
if MagicWorks(xMagic) then
if assigned(fOnFoundMagic) then
fOnFoundMagic(self, Square, xMagic);
if i > Trials then
if assigned(fOnSquareFail) then
fOnSquareFail(self, Square);

Note the random magic number seems to work best with a sparse 64 bit integer.

What I’ve outlined is the simplest form of magic bitboard with a fixed shift.  One nice aspect of magic move generation is it’s a stand-alone part of the chess engine.  So any improvements to the approach (e.g. more compact look-up tables) can be added later.

A couple of resource I found helpful were Looking for Magic and Rival Chess’ Page

Automatic Tuning of a Chess Evaluation Function

I’ve taken a little detour over the past week to look at Population Based Incremental Tuning.  This was something which Thomas Petzke brought to my attention.  You can read his take here:

It’s an interesting approach.  After some investigation I’ve decide to add some form of automated tuning to Maverick’s chess position evaluation function.  I think PBIL seems to hold some promise.

Bitboards Magic Number Research

I’ve quite happy with the global list of possible move.  Now I need to turn my attention to move generation.  For the pieces which don’t slide (i.e. pawns, knight and kings) this is trivial.  For sliding pieces I’m going to use the “new kid on the algorithmic block” – Magic Bitboards.  I’m in the process of going over Pradu Kannan’s 2007 paper.  I need to think about how I will generate my magic multipliers.  At this stage I’m not sure if I’ll do it in Delphi or C.  I also think a fixed shift seem to be sensible (from simplicity).

Are There 65,884 Legal Chess Moves?

I’ve finished creating the global move list.  This list contains all legal chess moves (e.g. one move might be white bishop on g2 captures black queen on d5).  It would seem there are 65,884 possible legal moves!  Does anyone know if this is indeed correct?

EDIT: It looks like my first attempt was off.  After more debugging I have 43,764 possible moves!

Refining the Piece Index Values

I’ve been thinking about the piece index values.  The original set had all of the pieces in a random list.  I think there is an advantage in having the following piece index values:

#define WHITE 0
#define BLACK 1

#define KNIGHT 1
#define BISHOP 2
#define ROOK 3
#define QUEEN 4
#define PAWN 5
#define KING 6

#define BLANK 0
#define WHITEROOK 3
#define WHITEQUEEN 4
#define WHITEPAWN 5
#define WHITEKING 6

#define BLACKROOK 10
#define BLACKQUEEN 11
#define BLACKPAWN 12
#define BLACKKING 13

With these values note the following:

You can detect the color easily with a simple (piece >>> 3).  This isn’t a big deal.

Since the king has the highest index of all piece, I can find any move in the global move table using the following code:

move = global_move_list[from][to][piece] + captured_piece

or for promoting a pawn:

move = global_move_list[from][to][piece] + captured_piece + (4 * promote_to)

That’s neat!

One of the weakness of bitboards is it is sometimes difficult to see which piece is occupying a particular square.  In a pure bitboard only structure you’d need to loop through all the piece bitboards until you find the relevant one.  This sounds cumbersome.  So I think I’ll also need to add a square[64] array to the board structure. This will simply hold the index of the piece occupying the square.

I think Maverick is going to fly!

Global Move List

In the first version of Monarch I used an Exhaustive Global List of Chess Moves.  This is a list of about (from memory), 47k moves which collectively describe all possible moves on the chess board.  So an example of one move might be white Bishop on b2 takes black Rook on e5.  This will be one of the moves in the table.  I think this approach may well work well with Magic Bitboards – so I intend to implement it in Maverick.  The main advantage is you can store move specific information in the move’s record (e.g. the changes in hash value).  Also generating moves is just a matter of storing a pointer to the move in question.  Obviously the downside is the memory used to store the table and the negative impact on the cache.

This structure was first popularized by Gnu Chess 3.  Subsequent engines which have used a similar approach are Ferret by Bruce Moreland and Diep by Vincent Diepeveen.

So my first task is to classify every possible move into “move types”.  This will be used in switch statements to make and unmake moves quickly.  Here’s my first pass:

// Types of Moves
#define MOVE_CASTLE 0
#define MOVE_PAWN_PUSH1 1
#define MOVE_PAWN_PUSH2 2
#define MOVE_PxPAWN 3
#define MOVE_PxPIECE 4
#define MOVE_PxP_EP 5
#define MOVE_PIECExPAWN 10
#define MOVE_KING_MOVE 11
#define MOVE_KINGxPIECE 12
#define MOVE_KINGxPAWN 13

 Now I need to think about generating the Global Move List!

When Will Maverick be “Launched”?

I see over on CCC Pawel Koziol has launched Rodent 1.0. Big Congrats! I was intrigued by Pawel’s “launch criteria” (i.e. 1.0 status).  He says he would only go to “1.0” status when Rodent beat Fruit 2.1 in a 100 game match.  This is an interesting criteria for launching a chess engine!

It got me thinking!

So here’s what I’m going to do for Maverick.  The first version, Maverick 0.1 will be launched only when it beats Monarch 1.7 over a 100 game match.  Version 0.2 will be launched when Maverick reaches 2100 ELO, version 0.3 at 2200 ELO, version 0.4 at 2300 ELO, version 0.5 at 2400 ELO and finally 1.0 at 2500 ELO (i.e. Grandmaster level!).