Node Expansion

DARKTHOUGHT implements a standard node-expansion procedure whose structure probably does not differ much from that of other chess programs. It executes the following successive steps as suggested by several authors and excellently summarized in [141,144].

The letters in parantheses behind each step explain where in the search tree it is actually applied: F means ``frontier'' (depth = 1), L ``lower part'' (depth  <= 0), and U ``upper part'' (depth  >= 1) where depth denotes ply distance from the quiescence horizon. The last node expansion step achieves good move ordering by arranging the sequence of recursive search calls as listed below.

1.
Hashed move from transposition table (L/U),

2.
capture moves in MVV/LVA order (L/U),

3.
killer moves (U),

4.
history moves (U),

5.
statically pre-sorted remaining moves (U).

This ordering scheme enjoys wide-spread use in computer chess because it represents the best currently known according to many independent researchers. An unintended yet nice side effect thereof is that it also saves precious memory bandwidth because it does not require the creation of a move list prior to history-move selection.

In contrast to most other chess programs, DARKTHOUGHT uses a single node-expansion routine to handle both full-width and quiescence-search nodes. Because of better code reuse (see above lists of steps), a single node expansion routine can be made smaller than two separate ones and it is much easier to reconfigure. The complexity of the implementation, however, increases considerably as compared to the solution with two separate routines.



Created by Ernst A. Heinz, Thu Dec 16 23:28:11 EST 1999