Thumbnail

Alpha-Beta Pruning for Games with Simultaneous Moves

Buro, Michael; Finnsson, Hilmar; Saffidine, Abdallah (2012), Alpha-Beta Pruning for Games with Simultaneous Moves, in Selman, Bart; Hoffmann, Jörg, Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, AAAI Press, p. 7

View/Open
Type
Communication / Conférence
Date
2012
Conference title
AAAI 2012
Conference date
2012-07
Conference city
Toronto
Conference country
Canada
Book title
Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence
Book author
Selman, Bart; Hoffmann, Jörg
Publisher
AAAI Press
ISBN
978-1-57735-568-7
Pages
7
Metadata
Show full item record
Author(s)
Buro, Michael
Finnsson, Hilmar
Saffidine, Abdallah
Abstract (EN)
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 and computation time compared to naive depth-first move computation without pruning.
Subjects / Keywords
multi-agent environment; Monte Carlo Tree Search; stacked matrix games; perfect information; game theory
JEL
C15 - Statistical Simulation Methods: General