Thumbnail

Alpha-Beta Pruning for Games with Simultaneous Moves

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

Voir/Ouvrir
Type
Communication / Conférence
Date
2012
Titre du colloque
AAAI 2012
Date du colloque
2012-07
Ville du colloque
Toronto
Pays du colloque
Canada
Titre de l'ouvrage
Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence
Auteurs de l’ouvrage
Selman, Bart; Hoffmann, Jörg
Éditeur
AAAI Press
Isbn
978-1-57735-568-7
Pages
7
Métadonnées
Afficher la notice complète
Auteur(s)
Buro, Michael
Finnsson, Hilmar
Saffidine, Abdallah
Résumé (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.
Mots-clés
multi-agent environment; Monte Carlo Tree Search; stacked matrix games; perfect information; game theory
JEL
C15 - Statistical Simulation Methods: General