Contents  Introduction  Basic Board  Representations  Bit Boards  Transposition  Tables  Generating Hash  Keys for Chess  Boards  History Tables  Pre-processing  move generation  Printable version     The Series  Getting Started  Data Structures  Move Generation  Basic Search  Advanced Search  Evaluation  Functions

Pre-processing move generation

Move generation (i.e., deciding which moves are legal given a specific position) is, with position evaluation, the most computationally expensive part of chess programming.  Therefore, a bit of pre-processing in this area can go a long way towards speeding up the entire game.

The scheme presented by Jean Goulet in his 1984 thesis Data Structures for Chess (McGill University) is a personal favorite.  In a nutshell:

• For move generation purposes, piece color is irrelevant except for pawns which move in opposite directions.
• There are 64 x 5 = 320 combinations of major piece and square from which to move, 48 squares on which a black pawn can be located (they can never retreat to the back rank, and they get promoted as soon as they reach the eight rank), and 48 where a white pawn can be located.
• Let us define a "ray" of moves as a sequence of moves by a piece, from a certain square, in the same direction.  For example, all queen moves towards the "north" of the board from square H3 make up a ray.
• For each piece on each square, there are a certain number of rays along which movement might be possible.  For example, a king in the middle of the board may be able to move in 8 different directions, while a bishop trapped in a corner only has one ray of escape possible.
• Prior to the game, compute a database of all rays for all pieces on all squares, assuming an empty board (i.e., movement is limited only by the edges and not by other pieces).
• When you generate moves for a piece on a square, scan each of its rays until you either reach the end of the ray or hit a piece.  If it is an enemy piece, this last move is a capture.  If it is a friendly piece, this last move is impossible.

With a properly designed database, move generation is reduced to a simple, mostly linear lookup; it requires virtually no computation at all.  And the entire thing holds within a few dozen kilobytes; mere chump change compared to the transposition table!

All of the techniques described above (bit boards, history, transposition table, pre-processed move database) will be illustrated in my own chess program, to be posted when I finish writing this series.  Next month, I will examine move generation in more detail.

François Dominic Laramée, June 2000