An Algorithm for Constructing and Solving Imperfect Recall Abstractions of Large Extensive-Form Games
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F17%3A00315393" target="_blank" >RIV/68407700:21230/17:00315393 - isvavai.cz</a>
Result on the web
<a href="https://www.ijcai.org/proceedings/2017/130" target="_blank" >https://www.ijcai.org/proceedings/2017/130</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.24963/ijcai.2017/130" target="_blank" >10.24963/ijcai.2017/130</a>
Alternative languages
Result language
angličtina
Original language name
An Algorithm for Constructing and Solving Imperfect Recall Abstractions of Large Extensive-Form Games
Original language description
We solve large two-player zero-sum extensive-form games with perfect recall. We propose a new algorithm based on fictitious play that significantly reduces memory requirements for storing average strategies. The key feature is exploiting imperfect recall abstractions while preserving the convergence rate and guarantees of fictitious play applied directly to the perfect recall game. The algorithm creates a coarse imperfect recall abstraction of the perfect recall game and automatically refines its information set structure only where the imperfect recall might cause problems. Experimental evaluation shows that our novel algorithm is able to solve a simplified poker game with 7.10^5 information sets using an abstracted game with only 1.8% of information sets of the original game. Additional experiments on poker and randomly generated games suggest that the relative size of the abstraction decreases as the size of the solved games increases.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA15-23235S" target="_blank" >GA15-23235S: Abstractions and Extensive-Form Games with Imperfect Recall</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the International Joint Conference on Artificial Intelligence
ISBN
978-0-9992411-0-3
ISSN
—
e-ISSN
1045-0823
Number of pages
7
Pages from-to
936-942
Publisher name
Association for the Advancement of Artificial Intelligence (AAAI)
Place of publication
Palo Alto, California
Event location
Melbourne
Event date
Aug 19, 2017
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—