This article presents a new selective pruning technique for alpha-beta based game-tree search in computer chess. Extended futility pruning builds on ideas of both deep razoring and normal futility pruning at frontier nodes (depth = 1). It cuts complete branches of the search tree at pre-frontier nodes (depth = 2) according to solely static criteria at the respective nodes and thus performs true forward pruning.

Although extended futility pruning is theoretically unsound, extensive experiments with our master-strength chess program DARKTHOUGHT show that it works markedly well in practice. Even at fixed search depths, extended futility pruning exhibits hardly any loss of tactical strength while shrinking the search trees by 10%-20% on average as compared with normal futility pruning. Furthermore, extended futility pruning combines nicely with a conservatively limited variation of razoring that reduces the search trees at fixed search depths > 10 plies by additional 5%-15% on average. Last but not least, the presented pruning schemes scale very well with search depth and reap ever more benefits at higher depths.

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