An Algorithm for Constructing and Solving Imperfect Recall Abstractions of Large Extensive-Form Games

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

An Algorithm for Constructing and Solving Imperfect Recall Abstractions of Large Extensive-Form Games

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

An Algorithm for Constructing and Solving Imperfect Recall Abstractions of Large Extensive-Form Games

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA15-23235S" target="_blank" >GA15-23235S: Abstrakce a extenzivní hry s nedokonalou pamětí</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2017

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the International Joint Conference on Artificial Intelligence

ISBN

978-0-9992411-0-3

ISSN

—

e-ISSN

1045-0823

Počet stran výsledku

7

Strana od-do

936-942

Název nakladatele

Association for the Advancement of Artificial Intelligence (AAAI)

Místo vydání

Palo Alto, California

Místo konání akce

Melbourne

Datum konání akce

19. 8. 2017

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—