Last-Branch and Speculative Pruning Algorithms for Maxn
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.
@inproceedings{ijcai2003p98,
title = {Last-Branch and Speculative Pruning Algorithms for Maxn},
author = {Sturtevant, Nathan R.},
booktitle = {Proceedings of the Eighteenth International Joint Conference on
Artificial Intelligence, {IJCAI-03}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Georg Gottlob},
pages = {669--677},
year = {2003},
url = {https://ijcai.org/proceedings/2003/98},
}
TY - CPAPER TI - Last-Branch and Speculative Pruning Algorithms for Maxn AU - Sturtevant, Nathan R. T2 - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03 PB - International Joint Conferences on Artificial Intelligence PY - 2003 SP - 669 EP - 677 UR - https://ijcai.org/proceedings/2003/98 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
