The move generator scans the board and returns a list of all presumably legal moves for a particular player.
I use the word presumably, because to save time in the move generator, certain illegal moves are returned - moves which would leave the king in check. The final legality of the move is tested when the move is applied so the check testing occurs here.

The move list

The move list is stored in a global area of memory. Because we will be calling the move generator during a recursive search, we need to keep a list of moves for each depth that we are currently searching. I do this using a set of pointers into the global movelist, one for each depth. When a move is added to the list of moves for the current depth, the move pointer for the next depth is increased so that to scan the move list for moves generated for a particular depth we can loop from the move pointer for the depth to the move pointer for the next depth.

Scanning the board

A simple loop is made of all the squares on the board, and we see if the square contains a piece for the current player. If it does, we then take the following action:

Pawn

The following tests are made

If the square immediately in front of the pawn is empty, add this square as a possible move

If the square diagonally in front of the pawn is an oppenent piece, or the en passant square, add this square as a possible capture move

If the move ends up on an end rank, we add each possible promotion move

If the pawn is on it's starting rank, and the square in front of the pawn and the square in front of that are empty, we add the square two in front as a possible move.

Knight

For each of the possible eight L shaped moves which do not fall off the edge of the board, if the destination square is empty or an opponent piece we add this move

King

For each of the possible eight single steps which do not fall off the edge of the board, if the destination square is empty or an opponet piece, we add this move

For each of the castling moves, if the castle is available (ie the flag is set in the castle flags for the current player), and all squares between the king and the rook are empty, we add the castle move

Sliding Pieces: Rook, Bishop, Queen

Sliding moves are a little different, we set a test position to the piece's square and then iterate the possible directions that the piece can move.
For each direction, we advance the test square in the appropriate direction and if it's empty or an opponent piece we add the move.
If the test square is now off the edge of the board, or an oppoent piece we stop testing the direction, reset the test position to the starting position and try the next direction, otherwise we continue testing the direction.

A Note on Directions

I use an array of directions, which holds the offset from one sqaure to the next in a particular direction, to simplify direction testing.
The direction array holds the offsets {left,right,up,down,left-up,right-up,right-down,left-down,up,down,right,left}
I use another two arrays to hold the start and end directions for each of the sliding pieces, ie for a bishop we check direction 4 to direction 7.
You may notice that the direction array holds twelve directions, rather than eight: the last four are the directions at right angles to the first four, used for knight moves. We move two sqaures in one direction, then one square in the corresponding right-angled direction.
I thought about adding four, rather than two extra rank/files to the board so that knight testing could be a simple iteration of a set of knight offsets, but decided that it would be simpler to just test each step in a knight's move individually for 'falling off the board'. This complicates the knights movement generator a little bit, but simplifies the board arrays (and helpfully makes the square numbers decimal which is more intuitive).

Back to: The User Interface

Show Topic: The Program

Next Page: The Move Applier