
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
Type
Communication / ConférenceDate
2012Conference title
AAAI 2012Conference date
2012-07Conference city
TorontoConference country
CanadaBook title
Proceedings of the Twenty-Sixth AAAI Conference on Artificial IntelligenceBook author
Selman, Bart; Hoffmann, JörgPublisher
AAAI Press
ISBN
978-1-57735-568-7
Pages
7
Metadata
Show full item recordAbstract (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 theoryRelated items
Showing items related by title and author.
-
Cazenave, Tristan; Saffidine, Abdallah; Schofield, Michael John; Thielscher, Michael (2016) Communication / Conférence
-
Li, Junkang; Cazenave, Tristan; Zanuttini, Bruno; Ventos, Veronique (2022) Communication / Conférence
-
Saffidine, Abdallah; Cazenave, Tristan (2012) Communication / Conférence
-
Saffidine, Abdallah (2012) Communication / Conférence
-
Saffidine, Abdallah; Jamain, Florian; Bonnet, Édouard (2013) Communication / Conférence