0x88 Perft

Now the 0x88 board move generator is complete we can check if it generates the correct moves by implementing a perft function.

The perft function counts all valid moves to a certain depth from the current board position. This count can be checked against a table of known results to see if the move generator is behaving correctly.

The perft function is split into two parts. The perft() function initialises a timer and the counter and calls the recursive perft_s() function to generate the results which it then prints along with the time taken to calculate the result.

The perft_s() function is very simple. It starts by generating all pseudo valid moves for the current board layout.

It then iterates through the moves and ensures that making the move does not result in leaving the king in check – this turns the pseudo legal moves into actual legal moves.

If we’ve reached maximum depth then we count the move at this point. If not at maximum depth then we recursively call the perft_s() function to make all the moves for the opposition with the new board layout.

To use the perft() function I just populated the main() function with some test code.

I added the run_perft() function to provide a neater output when calculating to multiple depths. The main() function defines a fen string for the starting position then calculates the perft results at multiple depths (in the case above, from perft(1) to perft(6)).

This results in the following output.perft

Checking this against the results from the chessprogramming wiki here we can see that the move generator is working correctly, at least for the initial position.

I have been through all the perft positions in the wiki and the move generator creates the correct results for each one.

That concludes the 0x88 board move generator. Next we will start looking at a bitboard implementation to see how much of a speed improvement we can achieve.

 

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.

 

Move Generation: pawns

Now we have the ability to make and unmake moves it’s time to generate the list of valid moves from the current board position.

For this implementation, like the rest of the code so far, I’m going for simplicity. Therefore this will be a pseudo-valid move generator. It will quite happily generate moves that will leave the king in check. We’ll need to check for this when making the move and filter the invalid moves out at this stage.

The valid moves are going to be stored in an array of CHESS_MOVE structures which we defined in the last entry as:

For each board position there is a maximum number of moves that can be played. So instead of dynamically allocating and reallocating the move list as we add valid moves, I just pass an array that is guaranteed to be big enough.

So, how big should it be? Well, let’s imagine that every pawn has been promoted to a queen and can move to the maximum amount of squares a queen can move to (impossible, I know but it doesn’t matter if we over estimate). That’s 8 * 28. Add that to the maximum moves available to each other piece (Rook : 14, Knight 8, Bishop : 14, King : 8, Queen : 28) and you end up with 332. We can define this in our code:

Now we can just generate an array containing this many CHESS_MOVE instances and we can guarantee we will not overflow it. We haven’t taken promotions, en-passant captures or castling in our maximum move count but we have easily over-estimated so we will not be overflowing our array.

So now we have our array, we can pass it to the function that generates the moves, along with an integer that is initialised to zero that keeps track of how many valid moves we’ve added to the array.

This function looks for all valid moves from a single cell. To generate all valid moves for a position the caller needs to iterate through all cells populated by pieces of the side to move. Each piece type is handled by calling a function that generates the moves for the individual piece.

Let’s take a look at how the pawn moves are generated.

This is fairly self explanatory albeit a bit long winded. There are a couple of things that maybe require further explanation.

Firstly, if the destination rank is 2 (for white) or 5 (for black) after the pawn has moved then it is an initial pawn move. Therefore we add an extra move advancing the pawn one step further if the cell is empty. This handles the initial pawn double move.

Secondly when a pawn advances or captures we check whether we have reached the end rank. If so we add the move multiple times to represent the possible pawn promotions.

Lastly we check to see if the pawn can move diagonally to the board en-passant cell and if so we add a move to represent this.

Note the use of the macros to populate the moves. This is just to save some typing. Here they are:

Next time we’ll take a look at the moves for all the other pieces.