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.

 

0x88 Board

In this post we’ll start looking at my reference chess board implementation. Remember, I want to keep this simple and maybe not spend too much time thinking about optimisation or even optimisable code. This is just a learning experience that will ease the future development of a much more efficient version.

The simplest implementation would seem to be just to define a structure that describes the contents of a square (I call them ‘cells’ in my code) and then define an array of 8×8 of these or simply:

These could be arrange any way you please but it makes sense that cells[0] is A1, cells [1] is A2, cells[8] is B1, etc.

However, a slightly larger, more complicated board array actually makes a lot of the chess rules engine code much easier. Therefore for this implementation I’m going to be using the common 0x88 board format. Much has been written about this format so I’m not going to duplicate it in my words here but basically the board is laid out as in the diagram below:

88board

What you’ll notices is that the indices for the cells follow a simple pattern; all indices for a particular file share the same low nibble and all indices for a particular rank share the same high nibble. Further, the top bit of each nibble is clear for all valid cells so we can easily check whether an index is valid using the following C code:

So now we can declare some structures that represent the data in a cell and create the board array.

 

Now we have our board structure we can start writing some functions.

Starting with a simple one just to clear all pieces from the board:

And here’s a useful function for debugging that prints an ASCII representation of the board:

Notice that the function above uses a macro ‘CELL_INDEX’ to convert from file and rank to an index. I’ve generated a number of useful macros like this:

And finally for now, a very scrappy, partial implementation of a FEN string parser just so I’m able to populate the board.

Putting all this together with a simple main() function containing the following code results in an 0x88 board that can be printed to the screen.

board_output