Show simple item record

Alpha-Beta Pruning for Games with Simultaneous Moves

dc.contributor.authorBuro, Michael
dc.contributor.authorFinnsson, Hilmar
dc.contributor.authorSaffidine, Abdallah
dc.date.accessioned2012-06-20T10:12:03Z
dc.date.available2012-06-20T10:12:03Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/9510
dc.language.isoenen
dc.subjectmulti-agent environmenten
dc.subjectMonte Carlo Tree Searchen
dc.subjectstacked matrix gamesen
dc.subjectperfect informationen
dc.subjectgame theoryen
dc.subject.ddc519en
dc.subject.classificationjelC15en
dc.titleAlpha-Beta Pruning for Games with Simultaneous Movesen
dc.typeCommunication / Conférence
dc.contributor.editoruniversityotherUniversity of Alberta;Canada
dc.contributor.editoruniversityotherReykjavík University;Islande
dc.description.abstractenAlpha-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.en
dc.identifier.citationpages7en
dc.relation.ispartoftitleProceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence
dc.relation.ispartofeditorSelman, Bart
dc.relation.ispartofeditorHoffmann, Jörg
dc.relation.ispartofpublnameAAAI Press
dc.relation.ispartofdate2012
dc.description.sponsorshipprivateouien
dc.subject.ddclabelProbabilités et mathématiques appliquéesen
dc.relation.ispartofisbn978-1-57735-568-7
dc.relation.conftitleAAAI 2012en
dc.relation.confdate2012-07
dc.relation.confcityTorontoen
dc.relation.confcountryCanadaen


Files in this item

Thumbnail
Name:
Alpha-Beta%20Pruning%20for%20G ...
Size:
250.9Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record