• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
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
Alpha-Beta%20Pruning%20for%20Games%20with%20Simultaneous%20Moves.pdf (250.9Kb)
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

Related items

Showing items related by title and author.

  • Thumbnail
    Nested Monte Carlo Search for Two-Player Games 
    Cazenave, Tristan; Saffidine, Abdallah; Schofield, Michael John; Thielscher, Michael (2016) Communication / Conférence
  • Thumbnail
    Generalisation of alpha-beta search for AND-OR graphs with partially ordered values 
    Li, Junkang; Cazenave, Tristan; Zanuttini, Bruno; Ventos, Veronique (2022) Communication / Conférence
  • Thumbnail
    A General Multi-Agent Modal Logic K Framework for Game Tree Search 
    Saffidine, Abdallah; Cazenave, Tristan (2012) Communication / Conférence
  • Thumbnail
    General Game Playing and the Game Description Language 
    Saffidine, Abdallah (2012) Communication / Conférence
  • Thumbnail
    On the complexity of trick-taking card games 
    Saffidine, Abdallah; Jamain, Florian; Bonnet, Édouard (2013) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo