Approximating Maxmin Strategies in Imperfect Recall Games Using A-loss Recall Property

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F18%3A00318608" target="_blank" >RIV/68407700:21230/18:00318608 - isvavai.cz</a>

Result on the web

<a href="https://www.sciencedirect.com/science/article/pii/S0888613X17304097" target="_blank" >https://www.sciencedirect.com/science/article/pii/S0888613X17304097</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ijar.2017.11.010" target="_blank" >10.1016/j.ijar.2017.11.010</a>

Result language

angličtina

Original language name

Approximating Maxmin Strategies in Imperfect Recall Games Using A-loss Recall Property

Original language description

Extensive-form games with imperfect recall are an important model of dynamic games where the players are allowed to forget previously known information. Often, imperfect recall games result from an abstraction algorithm that simplifies a large game with perfect recall. Solving imperfect recall games is known to be a hard problem, and thus it is useful to search for a subclass of imperfect recall games which offers sufficient memory savings while being efficiently solvable. The abstraction process can then be guided to result in a game from this class. We focus on a subclass of imperfect recall games called A-loss recall games. First, we provide a complete picture of the complexity of solving imperfect recall and A-loss recall games. We show that the A-loss recall property allows us to compute a best response in polynomial time (computing a best response is NP-hard in imperfect recall games). This allows us to create a practical algorithm for approximating maxmin strategies in two-player games where the maximizing player has imperfect recall and the minimizing player has A-loss recall. This algorithm is capable of solving some games with up to 5⋅109 states in approximately 1 hour. Finally, we demonstrate that the use of imperfect recall abstraction can reduce the size of the strategy representation to as low as 0.03% of the size of the strategy representation in the original perfect recall game without sacrificing the quality of the maxmin strategy obtained by solving this abstraction.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

20201 - Electrical and electronic engineering

Project

<a href="/en/project/GA15-23235S" target="_blank" >GA15-23235S: Abstractions and Extensive-Form Games with Imperfect Recall</a><br>

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2018

Confidentiality

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

Name of the periodical

International Journal of Approximate Reasoning

ISSN

0888-613X

e-ISSN

1873-4731

Volume of the periodical

93

Issue of the periodical within the volume

February

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

37

Pages from-to

290-326

UT code for WoS article

000424721400017

EID of the result in the Scopus database

2-s2.0-85037089484