Extended Futility Pruning

Abstract

This article presents a new selective pruning technique for alpha-beta based game-tree search in computer chess, called extended futility pruning. It builds on ideas of both razoring and normal futility pruning at frontier nodes (depth = 1), and it cuts complete branches of the search tree at pre-frontier nodes (depth = 2) according to solely static criteria at the respective nodes. Hence, extended futility pruning 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 to 20 percent on average as compared with normal futility pruning.

Moreover, extended futility pruning combines nicely with a conservatively limited variation of razoring. It reduces the search trees at fixed search depths of more than 10 plies by an additional 5 to 15 percent on average. Finally, we have observed that the presented pruning schemes scale very well with the search depth, and reap ever more benefits at higher depths.