Contents  Games of Perfect  Information  What We Need  Board  Representations  Move Generation  Search Techniques  Evaluation  Printable version     The Series  Getting Started  Data Structures  Move Generation  Basic Search  Advanced Search  Evaluation  Functions

Move Generation

The rules of the game determine which moves (if any) the side to play is allowed to make.  In some games, it is easy to look at the board and determine the legal moves: for example, in tic-tac-toe, any empty square is a legal move.  For chess, however, things are more complicated: each piece has its own movement rules, pawns capture diagonally and move along a file, it is illegal to leave a king in check, and the "en passant" captures, pawn promotions and castling moves require very specific conditions to be legal.

In fact, it turns out that move generation is one of the most computationally expensive and complicated aspects of chess programming.  Fortunately, the rules of the game allow quite a bit of pre-processing, and I will describe a set of data structures which can speed up move generation significantly.

Part III of this series covers this topic.

Next : Search Techniques