Pawn Captures

The next moves we need to consider for pawns are captures. Now we all know that pawns can only capture diagonally. In fact, they can only move diagonally if they are able to catch an enemy piece. How can we model this with a bitboard?

The white pawns bitboard looks like this. We’ll draw it laid out as a board for now.

In order to check for valid captures we need to move the pawns forwards diagonally in both directions. This is easy to achieve with bitboards again using the shift operator. Instead of shifting by 8 to move directly forwards we will shift by 7 to capture to the right and 9 to capture to the left.

But there’s a problem with this. What happens to the pawn on the A file when we capture to the left using the shift? It gets moved onto the 4th rank!

There is an easy solution to this. It is never valid for an A file pawn to capture to the left so we can just mask these out before performing the shift.

Likewise we need to the same for the capture to the right, masking out the H file pawns.

So now we’ve generated bitboards for the potential moves we need to check which ones are valid. To do this we need to mask out any move that doesn’t result in our pawn taking an opposing piece. Where do we find a bitboard of opposing pieces? We have to store it in our BOARD structure.

Like with the pawns, we store two bitboards – one for each side. These need to be updated along with pieces, all and pawns for every move on the board to keep them all in synch.

Now we simply need to bitwise ‘and’ the opposing side with our potential captures to see which ones actually result in a capture:

What is left is bitboards for capture_left and capture_right containing bits set only where a diagonal move would capture an enemy piece.

Let’s add this to our move generation function.

Bitboard: Moving Pawns

We’ve seen in the previous part how to actually move some pawns. This is fine for the opening position because we know that all the white pawns can move one or two spaces forwards – there are definitely no pieces in the way preventing this. How can we apply this later in the game though where the pawns are not all on one rank and might be blocked by other pieces?

The answer lies with more bitboards. A pawn bitboard is all very well on it’s own for generating candidate moves for the pawns but in order to validate the moves we need some more information.

Consider a white pawn sitting on C2, blocked in by white’s own knight. We’ll ignore all the other pieces for now and assume the board is empty except for these two pieces.

What does the white pawn bitboard contain?

Notice the single, solitary bit set on the second rank. There is no sign of the knight in this representation. So, if we want to generate the moves for the pawn we can start by shifting the board left by 8 to advance the pawn:

Perfect. Our pawn has moved forward a rank. But there’s a problem isn’t there? We’ve just moved the pawn onto the cell containing the knight. The bitboard has no idea the knight is there. We’ve generated a move for the pawn but not a valid move.

So how do we validate the move? We could iterate through the moved pawns bitboard and for every moved pawn we could see if a piece exists on the cell:

This isn’t bad but again requires us to spend CPU cycles iterating through the bits of the bitboard. There is a more efficient way of doing that which we will see later but, like the last time we removed the need for an iteration we can solve this with another bitboard. But what bitboard? What we need is something that can efficiently tell us where every piece on the chess board is.

Like the pawns bitboards we need to update this new bitboard every time a piece is moved. We set a bit in the bitboard if any piece resides in the relevant cell and clear it when a piece moves out of the cell. So, going back to our knight and our pawn in their original positions, the ‘all’ bitboard will contain the following:

Using a bit of bitwise magic we can move the pawn as before but then validate the move by checking it against the ‘all’ board.

How does this work? Let’s take a look at the bits.

If you perform a bitwise ‘and’ of white pawns << 8 and ~board.all you get this:



Everything is zero in the resulting bitboard indicating there are no valid moves. That’s the result we wanted.

We can take this a stage further and look at pawn double-moves too. Consider this board:

We have the same pawn/knight as before but in addition we have a pawn on the E file that can make a valid double move and a pawn on the G file that can move once but not twice. The white pawns bitboard looks like this:

The ‘all’ bitboard looks like this:

If we now calculate the shifted pawn bitboard for a single move then and it with ~board.all like before we get this:

Note there are only two pawns left thanks to the knight we looked at before. There are two valid single pawn moves. Now let’s try to move forward again by shifting by another 8 bits.

Now and this with ~board.all again and you get:

Just one pawn left – one pawn which can make a valid double move.

Let’s put this into code. We will start writing a function that calculates all the valid moves for a given position and start implementing it with the pawn moves we’ve just looked at. The function will not be complete yet as we need to do something with the bitboards of valid moves that we generated however it is a start.

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.