Search Engine

DARKTHOUGHT is a sophisticated alpha-beta searcher using PVS/NEGASCOUT [51,174] with state-of-the-art enhancements like aggressive futility pruning [95,182], internal iterative deepening [7,184], dynamic move ordering (history+killer heuristic) [3,76,180,183,191], recursive null-move pruning [20,62,77], selective extensions [7,17], interior-node recognizers [94,190], and an extended transposition table [161,191]. On average, all enhancements taken together reduce the effective branching factor of DARKTHOUGHT to 2-3 and its search-tree size to roughly 55% of that of the according minimal tree [124]. These observations are consistent with reports by other researchers [17,216].

At the top level DARKTHOUGHT employs lazy alpha bounding and iterative deepening with an aspiration window of half a Pawn [127,191]. In contrast to plain alpha bounding [182], the lazy scheme delays the complete resolution of both new best moves and fail highs up to the next iteration. Top-level alpha bounding often saves some effort while at the same time searching new best moves one ply deeper than usual. If the top-level search is unstable or if the final score lies far below the score of the previous move, DARKTHOUGHT extends the duration of the current search up to threefold when playing in tournament mode.

The full-width search of variable depth is backed by a ``most valuable victim / least valuable aggressor (MVV/LVA)'' style quiescence [32] that triggers the static leaf-node evaluations and follows capturing moves only. In order to work well such half-blind quiescence needs deep full-width searches as executed by DARKTHOUGHT which routinely reaches 11-13 plies in standard middlegame positions within a minute. Due to its high search depths and wealth of extensions, DARKTHOUGHT does not switch off null moves until one side has no more pieces (i.e., it still performs null-move pruning if both sides have just a single minor piece plus Pawns). Our overall experience of numerous matches and test-suite runs suggests that the positive effects of largely increased full-width depth strongly outweigh the zugzwang-related negative ones. At least for tournament play, early discovery of deep pawn breakthroughs and related tactical tricks seems to be much more important than accurate zugzwang detection in endgames with major or minor pieces on both sides.


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