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 Early Days: Forward Pruning

In 1949 (yes, really), Claude Shannon described two ways to build a chess-playing algorithm:

• Look at all possible moves, and all the possible moves resulting from each, recursively.
• Only examine the "best" moves, as determined from a detailed analysis of a position, and then only the "best" replies to each, recursively.

At first, the second alternative seemed more likely to succeed.  After all, this is how human players do it, and it seems logical to assume that looking at only a few moves at each node will be faster than looking at all of them.  Unfortunately, the results disproved the theory: programs using selective search just didn't play very well.  At best, they achieved low to mid-level club player ratings, often committing humiliating blunders at the worst possible time.  Beating a world champion (or even playing reasonably well on a consistent basis) was beyond their reach.

The problem is that, for a "best move generator" to be any good, it has to be almost perfect.  Suppose that a program is equipped with a function that looks for the 5 best moves in a position, and that the objective best move is among those 5 at least 95% of the time.  (That, by the way, is a big assumption.)  This means that the probability that the generator's list will always contain the best choice at all times, during a 40-move game, is less than 13%.  Even a god-like generator with 99% accuracy will blunder at least once in about a third of its games, while a more reasonable 90%-accurate function will play an entire game without messing up less than 1.5% of the time!

In the mid 1970's, the legendary Northwestern team of Slate and Atkin decided to do away with the complicated best-move generator; it turned out that the time they saved in avoiding costly analysis during move generation was enough to cover the added expense of a full-width search (i.e., examining all possible moves).  To all intents and purposes, this discovery buried forward pruning for good.

Botvinnik's work
An extreme example of a forward pruning algorithm was developed in the Soviet Union, in the 1970's and early 1980's, under the tutelage of former World chess champion Mikhail Botvinnik.  Botvinnik was convinced that the only way for a computer to ever play grandmaster-level chess was to play like a grandmaster, i.e., examine only a few moves, but in great depth and detail.  His program seeked to identify and implement the sort of high-level plans and patterns which a world-class player might come up with during a game.  While it led to some fascinating books, revealing insights into the master's mind which only Botvinnik could provide, this work unfortunately did not reach its lofty goals.

Next : Generating All Moves Up-Front