|
One Move At A Time
Sophisticated chess programs since at least CHESS 4.5 have adopted the opposite strategy: generate a few moves at a time, search them, and if a cutoff can be caused, there will be no need to generate the rest of the moves.
A combination of factors has made this technique popular:
- Search does not require much memory. Programs of the 1970's had to make do with small transposition tables and could ill afford pre-processed move generation data structures, limiting the usefulness of the complete generation scheme described above.
- Move generation is more complicated in chess than in most other games, with castling, en passant pawn captures, and different rules for each piece type to contend with.
- Very often, a refutation (i.e., a move that will cause a cutoff) is a capture. For example, if Player A leaves a queen "en prise", the opponent will quickly grab it and wreck A's game. Since there are usually few possible captures in a position, and since generating captures separately is relatively easy, computing captures is often enough to trigger a cutoff at little expense.
- Captures are usually one of the few (if not the only) type of move examined during quiescence search (which will be discussed in a later article), so generating them separately is doubly useful.
Therefore, many programs will generate captures first, often starting with those of highly valuable pieces, and look for a quick cutoff. A number of techniques have been developed to speed up piece-meal move generation, most of them involving bitboards:
- CHESS 4.5 maintains two sets of 64 bitboards, with one bitboard per square on the board. One contains the squares attacked by the piece, if any, located on that square; the other is the transpose, containing all squares occupied by pieces attacking that square. Therefore, if the program is looking for moves that would capture Black's queen, it looks for its position in the basic bitboard database, uses these new data structures to identify the pieces which attack the queen's position, and only generates moves for these pieces.
- Maintaining these "attack bitboards" after each move requires some rather involved technical wizardry, but a tool called a rotated bitboard can accelerate the work significantly. The best discussion of rotated bitboards I have seen was written by James F. Swafford, and can be found on the web at http://sr5.xoom.com/_XMCM/jswaff/chessprg/rotated.htm
|
Unite 2010
