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

My Choice

For my chess program, I have chosen to generate all moves at the same time.  These are only some of the reasons why:

• I intend to use the program as a basis for several other games, most of which have no direct counterparts to chess captures.
• I have plenty of memory to play with.
• The code required to implement this technique is simpler to write and to understand; you will thank me when you see it.
• There are several freeware programs that implement piece-meal move generation; the curious reader should look at Crafty, for example, as well as James Swafford's Galahad.

While overall performance may be slightly less stellar than otherwise, my program (written in Java, no less) wouldn't exactly provide a challenge to Deep Blue even in the best case, so I won't feel too bad!

Next Month

Now, we are ready to delve into the brains of a chess-playing program, with search techniques.  This is such a large topic that it will require two articles.  We will begin with the basic search algorithms common to all games, before continuing with new developments and chess-specific optimizations in the next installment.
 

François Dominic Laramée, July 2000