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
TypeCommunication / Conférence
Conference titleAAAI 2012
Book titleProceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence
Book authorSelman, Bart; Hoffmann, Jörg
MetadataShow full item record
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 / Keywordsmulti-agent environment; Monte Carlo Tree Search; stacked matrix games; perfect information; game theory
Showing items related by title and author.
Computer Games: 6th Workshop, CGW 2017, Held in Conjunction with the 26th International Conference on Artificial Intelligence, IJCAI 2017 Cazenave, Tristan; Winands, Mark H.M.; Saffidine, Abdallah (2018) Ouvrage