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: 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.