---
title: "Last-Branch and Speculative Pruning Algorithms for Maxn"
authors:
  - "Nathan R. Sturtevant"
doi: ""
url: "https://ijcai.org/proceedings/2003/98"
pdf: "https://ijcai.org/proceedings/2003/0098.pdf"
venue: "Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence"
year: 2003
pages: "669-677"
track: ""
keywords:
---

# Last-Branch and Speculative Pruning Algorithms for Maxn

Nathan R. Sturtevant

*Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence*, pages 669-677.

## Abstract

Previous work in pruning algorithms for max" 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 <• -• >t •_ In Chinese Checkers these methods reduce average expansions at depth 6 from 1.2 million to lOOk nodes, and in Hearts and Spades they increase the average search depth by 1-3 ply.