In 1949 (yes, really), Claude Shannon described two ways to build a chess-playing algorithm: Both strategies are sound and viable, however.

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.

As for the other two, they represent two sides of the same coin, trading off effort in move generation vs search. Selective generation (and its associated search technique, called forward pruning) have all but disappeared since the mid 1970's. 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.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.Selective generation: Examine the board, come up with a small number of 'likely' moves and discard everything else.Historically, three major strategies have been used in this area: Search will be discussed in Parts IV and V of this series this month, we will concentrate on move generation.

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. 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. 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. In any given situation, a player may have 30 or more legal moves to choose from, some good, some suicidal.

No matter how you slice it, chess is a complicated game, especially for a computer. 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. 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.

Algorithm for chess program