Extended Futility Pruning

TL;DRAbstract

This chapter presents a new selective forward-pruning technique for alpha-beta based game-tree search in computer chess. Extended futility pruning applies the futility idea to pre-frontier nodes (remaining depth = 2). It cuts complete branches of the search tree at pre-frontier nodes according to solely static criteria at the respective nodes. Thus, the new scheme performs static forward pruning. Its pruning style resembles that of normal futility pruning at frontier nodes (remaining depth = 1). Although extended futility pruning is theoretically unsound, extensive experiments with 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 by additional 5%–1

Chat with Paper

AI Agents for this Paper