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.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">