Automated construction of bounded-loss imperfect-recall abstractions in extensive-form games

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F20%3A00345737" target="_blank" >RIV/68407700:21230/20:00345737 - isvavai.cz</a>

Result on the web

<a href="https://www.ijcai.org/Proceedings/2020/0701.pdf" target="_blank" >https://www.ijcai.org/Proceedings/2020/0701.pdf</a>

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Automated construction of bounded-loss imperfect-recall abstractions in extensive-form games

Original language description

Information abstraction is one of the methods for tackling large extensive-form games (EFGs). Removing some information available to players reduces the memory required for computing and storing strategies. We present novel domain-independent abstraction methods for creating very coarse abstractions of EFGs that still compute strategies that are (near) optimal in the original game. First, the methods start with an arbitrary abstraction of the original game (domain-specific or the coarsest possible). Next, they iteratively detect which information is required in the abstract game so that a (near) optimal strategy in the original game can be found and include this information into the abstract game. Moreover, the methods are able to exploit imperfect-recall abstractions where players can even forget the history of their own actions. We present two algorithms that follow these steps - FPIRA, based on fictitious play, and CFR+IRA, based on counterfactual regret minimization. The experimental evaluation confirms that our methods can closely approximate Nash equilibrium of large games using abstraction with only 0.9% of information sets of the original game.

Czech name

—

Czech description

—

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)

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

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

Publication year

2020

Confidentiality

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

Article name in the collection

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence

ISBN

978-0-9992411-6-5

ISSN

—

e-ISSN

—

Number of pages

5

Pages from-to

5030-5034

Publisher name

International Joint Conferences on Artificial Intelligence Organization

Place of publication

—

Event location

Yokohama

Event date

Jul 11, 2020

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—