Contents  The Dilemma  Forward Pruning  Generating All  Moves Up-Front  One Move  At A Time  Ordering Moves  My Choice  Printable version     The Series  Getting Started  Data Structures  Move Generation  Basic Search  Advanced Search  Evaluation  Functions

Last month, I finished Part II of this series by introducing a data structure which pre-processes and stores most of the work related to chess move generation.  This time, I will return to the topic in more detail, examining the two major move generation strategies and explaining how to choose between them for a given application.

The Dilemma

No matter how you slice it, chess is a complicated game, especially for a computer.

In any given situation, a player may have 30 or more legal moves to choose from, some good, some suicidal.  For trained humans, it is easy to characterize the majority of these moves as foolish or pointless: even beginners learn that they had better come up with a solid plan before leaving their queen in a position where she can be captured, and masters know (more through instinctive pattern matching than by conscious effort) which 1-2 moves are likely to be the strongest in the position.

However, coding this information (especially the unconscious type!) into a computer has proven spectacularly difficult, and the strongest programs (except, to some extent, Hans Berliner's Hitech and its siblings) have given up on this approach, instead relying on "brute force": if you can analyze all possible moves fast enough and predict their consequences far enough down the road, it doesn't matter whether or not you start with a clear idea of what you are trying to accomplish, because you'll discover a good move eventually.  Therefore, move generation and search should be made as fast as possible, so as to minimize the loss of effort required by the brute force method.

Search will be discussed in Parts IV and V of this series; this month, we will concentrate on move generation.  Historically, three major strategies have been used in this area:

• Selective generation: Examine the board, come up with a small number of "likely" moves and discard everything else.
• Incremental generation: Generate a few moves, hoping that one will prove so good or so bad that search along the current line of play can be terminated before generating the others.
• Complete generation: Generate all moves, hoping that the transposition table (discussed in Part II) will contain relevant information on one of them and that there will be no need to search anything at all.

Selective generation (and its associated search technique, called forward pruning) have all but disappeared since the mid 1970's.  As for the other two, they represent two sides of the same coin, trading off effort in move generation vs search.  In games where move generation is easy and/or there are lots of ways to transpose into the same positions (i.e., Othello and GoMoku), complete generation may be most efficient, while in games where move generation rules are complicated, incremental generation will usually work faster.  Both strategies are sound and viable, however.

Next : Forward Pruning