Last-Branch and Speculative Pruning Algorithms for Maxn

Abstract

Previous work in pruning algorithms for maxn multi-player game trees has produced shallow pruning and alpha-beta branch-and-bound pruning. The effectiveness of these algorithms is dependant as much on the range of terminal values found in the game tree as on the ordering of nodes. We introduce last-branch and speculative pruning techniques which can prune any constantsum multi-player game tree. Their effectiveness depends only on node-ordering within the game tree. As b grows large, these algorithms will, in the best case, reduce the branching factor of a nplayer game from b to b(n-1)/n. In Chinese Checkers these methods reduce average expansions at depth 6 from 1.2 million to 100k nodes, and in Hearts and Spades they increase the average search depth by 1-3 ply.