Our chess program DARKTHOUGHT relied on extended futility pruning with a cutoff margin of 6 Pawns during the 15th ICCA World Microcomputer Chess Championship (WMCC) in October 1997. DARKTHOUGHT finished the championship on a shared 4th place among 34 strong participants. Hence, the new pruning scheme already inaugurated its practical value with a successful real-life performance under tough tournament conditions.
In our quantitative experiments with all 2180 postions from the test suites ``Encyclopedia of Chess Middlegames'' (ECM, 879 positions), ``Win at Chess'' (WAC, 300 positions), and ``1001 Winning Chess Sacrifices'' (WCS, 1001 positions) extended futility pruning performed equally well. The version of DARKTHOUGHT used for the experiments was mostly identical with the one described in our article ``How DARKTHOUGHT plays chess'' [96].
DARKTHOUGHT is a fast yet sophisticated alpha-beta searcher using
PVS/NEGASCOUT [51,174] with
state-of-the-art enhancements like normal futility pruning, 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], 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]. Therefore, the program
already generated very slim search trees without the new pruning scheme
while routinely reaching search depths of 11-13 plies in normal
middlegame positions at tournament time-controls.1.5
Even at fixed search depths, extended futility pruning exhibits hardly any loss of tactical strength when extd futil margin = 6 * pawn val. Yet it shrinks the search trees by additional 10%-20% in comparison with our state-of-the-art implementation of normal futility pruning. Table 1.1 gives the according performance data as obtained by searching all 2180 positions of the ECM, WAC, and WCS test suites to fixed depths of 8, 10, and 12 plies with the 1997 WMCC version of DARKTHOUGHT (see Appendix 1.3.8 for a detailed description of the exact experimental setup). The data shows that extended futility pruning scales nicely with higher search depths. The overall relative savings as counted in number of nodes visited increase from 12% at a fixed search depth of 8 plies to 21% at a fixed search depth of 12 plies. Simultaneously, the already extremely low quota of less overall solutions further decreases from 0.8% at a fixed search depth of 8 plies to 0.3% at a fixed search depth of 12 plies.
The preserved tactical strength clearly distinguishes extended futility pruning from pure razoring. As for our own experience, pure razoring greatly suffers from tactical misconceptions that often tend to delay critical findings for some search plies which in turn causes gross blunders with inacceptable frequency. Moreover, our new scheme may even be easier to implement than pure razoring.
Nodes