Alpha-Beta Pruning for Games with Simultaneous Moves
Abstract
Alpha-Beta pruning is one of the most powerful and fundamental MiniMax search improvements. It was designed for sequential two-player zero-sum perfect information games. In this paper we introduce an Alpha-Beta-like sound pruning method for the more general class of “stacked matrix games” that allow for simultaneous moves by both players. This is accomplished by maintaining upper and lower bounds for achievable payoffs in states with simultaneous actions and dominated action pruning based on the feasibility of certain linear programs. Empirical data shows considerable savings in terms of expanded nodes compared to naive depth-first move computation without pruning.
Cite
Text
Saffidine et al. "Alpha-Beta Pruning for Games with Simultaneous Moves." AAAI Conference on Artificial Intelligence, 2012. doi:10.1609/AAAI.V26I1.8148Markdown
[Saffidine et al. "Alpha-Beta Pruning for Games with Simultaneous Moves." AAAI Conference on Artificial Intelligence, 2012.](https://mlanthology.org/aaai/2012/saffidine2012aaai-alpha/) doi:10.1609/AAAI.V26I1.8148BibTeX
@inproceedings{saffidine2012aaai-alpha,
title = {{Alpha-Beta Pruning for Games with Simultaneous Moves}},
author = {Saffidine, Abdallah and Finnsson, Hilmar and Buro, Michael},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2012},
pages = {556-562},
doi = {10.1609/AAAI.V26I1.8148},
url = {https://mlanthology.org/aaai/2012/saffidine2012aaai-alpha/}
}