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

Generating All Moves Up-Front

Once forward pruning is eliminated from consideration, the most straightforward way to implement full-width searching consists of:

• Finding all of the legal moves available in a position.
• Ordering them in some way, hopefully speeding up search by picking an advantageous order.
• Searching them all one at a time, until all moves have been examined or a cutoff occurs.

Early programs, for example Sargon, did this by scanning the board one square at a time, looking for pieces of the moving side, and computing possible move destinations on the fly.  Memory being at a premium, the expenditure of CPU time required to re-compute these moves every time was a necessary evil.

These days, a pre-processed data structure like the one I described last month can avoid a considerable amount of computation and code complexity, at the cost of a few dozens of Kbytes.  When this super-fast move generation is combined with transposition tables, an added bonus may fall into the programmer's lap: if even one of the moves has already been searched before, and if its evaluation (as retrieved from the table) is such that it triggers a cutoff, there will be no need to search any of the moves at all!  Obviously, the larger the transposition table, and the higher the probability of a transposition given the rules of the game, the bigger the average payoff.

Not only is this technique conceptually simple, it is also the most "universal": while there are easy ways to segregate chess moves into different categories (i.e., captures and non-captures), other games like Othello do not provide such convenient tools to work with.  Therefore, if you intend your program to play more than one game, you should probably pick this technique instead of the one described in the next section.

Next : One Move at a Time