Search Parameterization

As mentioned in the introduction, one important design principle of DARKTHOUGHT is configurability without loss of efficiency. To this end, it contains a large collection of source-code switches that allow for the quick and easy generation of versatile search ``personalities''. Descriptions of the most interesting parameters and their effects follow below.

Search Algorithm.
Beside standard PVS/NegaScout, DARKTHOUGHT can run pure fail-soft alpha-beta (FAB) and a mixture of both that uses PVS until reaching a configurable depth where it switches to FAB. Viable values for the depth threshold range from 1 to 4.

Null-Move Search.
Generally regarded as both a curse and a blessing of microcomputer-based chess programs, the realm of null-move pruning provides ample opportunities for many improvements (e.g. by parameter fine-tuning). In DARKTHOUGHT, null moves may be layered (i.e. disabled in either the upper or lower parts of the search tree up to a predefined depth threshold), made non-recursive or even switched off completely. The first DARKTHOUGHT delayed null moves until depths  <= 5 after Don Dailey (of SOCRATES and STARSOCRATES fame) enthused about this scheme during the 8th WCCC in Hong Kong, 1995.

Like many other chess programs, DARKTHOUGHT currently uses a depth-reduction factor of 2 for null-move searches. But other values (especially depth-adaptive ones in combination with various material thresholds for disabling the null move in endgames) are constantly experimented with. The same holds for depth and score margin of the deep-search extension which default to 2 and the value of 3 Pawns respectively.

Transposition-Table Access.
DARKTHOUGHT performs multiple probes in the transposition table because experiments conducted by Peter in 1993 showed the superiority thereof as compared to multiple tables (see [16] for an independent confirmation). The number of probes per access is a redefinable parameter normally set to 4.

The depth up to which DARKTHOUGHT accesses the transposition table can be configured independently for read and write operations. Setting both to one ply below the quiescence horizon currently produces the best overall results.

Extension Heuristics.
All extensions may individually be layered or completely turned off. Check extensions can be disabled if the piece material of the checking side falls below a certain threshold (e.g. less than two pieces). The depth up to which checking moves are followed unconditionally is modifiable, too, yet normally set to the frontier as this combines well with futility pruning and capture-only quiescence.

Data Structures.
Because most computers exhibit different behaviour as for memory performance and cache sensitivity, DARKTHOUGHT contains distinct implementations of many data structures accessed during the search. First and foremost, you may choose between a single global board modified by corresponding make/unmake-move operations and stacked local boards that require no unmake after but copying prior to the make-move operation during node expansion. Similarly, stacked local move lists as opposed to a single global move list may be selected. Although they feature much higher memory consumption, the localized data structures will simplify any future parallelization attempts. Last but not least, there exist several variations of history tables with the piece-to-square formulation [210] used by default.

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