What is a bitboard?

Well, I don’t know where that year went. I didn’t mean to leave it so long between the last post and this one but life happens! I’ll try not to leave it so long this time…

So now we have our implementation of move generation using an 0x88 board. It works but we’ve made no attempt to optimise it for speed. Now we have two choices:

  • Analyse the performance of the 0x88 board move generation and attempt to optimise it making it as fast as possible
  • Reimplement the move generation using a ‘bitboard’ to compare the relative speed.

Ideally we would perform both of the above so we can compare an optimised 0x88 board against an optimised bitboard but as well as looking at performance I’m interested in looking at the complexity of implementing a bitboard based move generator as well as performing the optimisation. So, we’re going to throw away the current 0x88 board code we’ve looked at and see how to write it all over again using a bitboard.

Now, I’ve read a number of descriptions of what a bitboard is and how they can be implemented along with some ideas on optimisation. I’ve deliberately steered away from looking at anyone else’s implementation though because I want to see what I can come up with on my own.

If you take the name “bitboard” literally then what have you got? An entire chess board state stored as single bits in an array? Well, that won’t work will it. If you have one bit per square then how do you know what piece is in each square? How do you know what side it is? How do you know if castling or en-passant is available? No, the idea of a bitboard is (at least as far as I’m thinking) that you use bit arrays for storing information that can be easily optimised using bit operations.

Consider the white pawns in their opening position. All eight of them on the second rank. When we want to work out the valid moves from the opening position we know the pawns can all move forward one or two places. How do we do this with an 0x88 board?

Well, here’s a naiive implementation:

The implementation literally iterates through every cell on the board looking for white pawns then stores potential moves for each pawn. OK, there are very simple ways to make this more efficient. In fact, our previous code was more efficient than this. However it will still end up in a loop for each pawn.

Now let’s look at an implementation using a bitboard.

Hmm… There are a few things to explain here. The first is the representation of the bitboard itself. The first line above defines a BITBOARD as a uint64_t. Basically, the entire board representation is stored in a 64 bit number; 64 bits for 64 cells in a chess board.

As I said previously though you cannot store then entire state of a chess board in a single bitboard; 1-bit per cell is not enough to store all the information we need. So, we’ve got a function that returns a bitboard representation of all the white pawns on the board. Where a white pawn stands a bit is set. Where a cell is empty or contains a piece that is not a white pawn the bit is clear. The board is arranged as following in the 64-bit number:

MSB is the most significant bit, LSB is the least significant bit. You can see all the bits on rank 2 are set indicating where the white pawns live. If we rearrange the above putting each block of 8 bits on top of each other then we get this:

You can see how the above matches the cells on a chessboard.

So how does this help us? Looking again at the valid moves for these pawns starting from the opening position then we know the pawns can all move forward one or two places. We need to shift all the 1’s in the board above up by one or two rows. How do we do that with a bitwise operation? We shift the bits by the number of cells in a row multiplied by the number of rows; 8 * 1 or 8 * 2.

So looking at the flat representation the shift does the following:

So it’s easy to see that shifting the board left by 8 bits moves all the pieces on the board up by a row. This is a very efficient way to generate this type of move and removes the need to iterate over the cells of the board for each piece, as long as the get_white_pawns() function does not need to perform the iteration.

That brings us onto the representation of the board itself. We’ve seen that we cannot represent the whole chess board with a single bitboard so how do we represent it efficiently? How about this?

OK, I don’t see any bitboards in there but let’s go with it. How do we implement get_white_pawns() using the above?

Oh dear. That’s just what we wanted to avoid – iterating through all the pieces in order to locate/move the white pawns. Instead of doing this, how about we store the positions of the white pawns in our BOARD structure? And while we’re at it, let’s store the black pawns too. We’ll put them in an array of 2, one for white one for black.

This means our function is simplified to this:

In fact, we can probably just lose the function altogether and just access the structure member directly.

This all looks much more efficient. However, there is one catch; We need to remember to keep the pawn bitboards consistent with the pieces array in the structure. Whenever we move a piece we need to update board.pieces[] but we also need to check if it is a white/black pawn and updated the relevant bitboard. Is this more efficient that just iterating through all the pieces in the board? We’ll see.

Move Generation: Castling

Let’s finish this off so we can get to the more interesting bitboard code and some optimisation.

The last piece of the move puzzle is castling. Here is the code.

This basically checks for availability of castling by looking at the castling_availability flags in the board structure then checks to see if the conditions are right for castling.

The conditions that are checked are:

  1. Ensure the squares that the king and rook pass through are empty
  2. Ensure that the king is not in check in any of the squares it passes through or ends up in

In order to check that the king is not in check in any of the squares we call the is_cell_range_attacked() function.

This works by making a dummy move to each of the squares being checked then generates moves for all enemy pieces to see if they attack the piece on the square being checked.

That concludes the move generation code for the 0x88 board. Next time we’ll throw together a simple perft function to check that the move generation code is working correctly and give us an idea of the performance.

Move Generation: Other Pieces

Last time we looked at the pawn moves in detail which resulted in a fair amount of code due to all the special cases required by pawn moves (en-passant, double moves, can only capture diagonally). This time we will cover the moves of all the other pieces.

With the exception of castling, none of the other pieces have any ‘special’ moves or rules so we can handle them by using an offset table. The table contains a set of values for each piece, one for each possible direction the piece can move. To move the piece in a particular direction by one step you just add the value to the current cell location.

For example, looking at the values for the rook offset table:

This is a bit more obvious if we show the values for each direction on a chess board where CELLS_PER_RANK is 16 for an 0x88 board:

rook_moves

So, to go up 1 rank (go North) we add 16 to the current cell. To go down 1 rank we add -16 to the current cell.

This works well for the king as we can specify the offsets for all 8 directions it can move and that fully describes the possible locations for the king. But how do we handle sliding pieces that move until they bump into another piece or the edge of the board? Simple – we just keep adding the offset for the current direction in a loop until we reach a stopping condition:

Putting this all together we can write the get_valid_moves_table() function that handles the moves for all non-pawn pieces, sliding and otherwise.

The function is called with the cell_index containing the piece to find the valid moves for, a pointer to the relevant piece offset table and a flag that specifies whether the pieces is sliding (single == FALSE) or not (single == TRUE).

Looking back at the get_valid_moves() function we can see how we have now defined the moves for all the pieces with the exception of castling which we will cover next time.

 

Making a Move

Now we have our board representation we need a way to make and unmake moves. As before, this is going to be a very naive implementation that is more about readability than efficiency.

We’ll start with the interface. We need two functions. One for making a move and one for undoing the last move.

So, what do we store in the move structure?

Not a lot! We just need to keep track for the cell a piece is moving from and where it is going to along with the piece a pawn that reaches the end should be promoted to. One important thing to note here is that the move/unmove code assumes that all moves are valid; it performs no validity checking whatsoever.

So let’s start to implement the move function. The most obvious thing we have to do is to move the piece. Recall from the last post that we created a global variable holding the board state – the move function will directly update this state.

If only it was that simple! We have a number of other things to consider when moving pieces:

  • Capturing en-passant
  • Castling
  • Promotion

Let’s deal with these in order.

En-Passant

The move function needs to perform three functions related to en-passant:

  1. For any other move the current en-passant cell needs to be cleared.
  2. If a pawn is advanced two places then the board structure needs to be updated to keep track of the en-passant cell
  3. If a pawn moves to the current en-passant cell then the enemy pawn needs to be removed from it’s cell

Here are 1 and 2.

And 3.

Castling

Castling is another special case with two functions.

  1. If the board indicates castling is available and the king is moved to a castling destination then the rook needs to also be moved
  2. Moving the king or either rook removes castling ability

This gets a bit messy (and could easily be improved – remember this is not the final code…)

Yuck! Magic numbers. I’ll fix them later. This is a lot of code but it’s fairly straightforward. If the king is being moved from it’s home position to a castling location then move the rook as well. We don’t need to check for castling availability because we assume that the move being passed to us is valid.

Removing castling availability is straightforward.

More magic numbers… We don’t need to check whether the piece we are moving is the king or a rook as if it is not then the castling availability will have already been removed so we will not be changing any state.

Pawn Promotion

Finally we have pawn promotion. This one is easy.

That completes the move function. So how do we undo a move? In the interests of keeping this simple we are going to add a new field to the CHESS_MOVE structure.

We’ve added the ‘board’ member. Before we make a move we will copy the entire board state into this member then we can just copy it back when we undo the move. So, at the start of the move function we add this:

This leaves us with the simple task of implementing the unmove function:

Well, that’s it for this instalment. Next we’ll start taking a look at the code required to generate all the legal moves from a starting position.