Sound Algorithms in Imperfect Information Games
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F21%3A00355540" target="_blank" >RIV/68407700:21230/21:00355540 - isvavai.cz</a>
Result on the web
<a href="https://www.ifaamas.org/Proceedings/aamas2021/pdfs/p1674.pdf" target="_blank" >https://www.ifaamas.org/Proceedings/aamas2021/pdfs/p1674.pdf</a>
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Sound Algorithms in Imperfect Information Games
Original language description
Search has played a fundamental role in computer game research since the very beginning. And while online search has been commonly used in perfect information games such as Chess and Go, online search methods for imperfect information games have only been introduced relatively recently. This paper addresses the question of what is a sound online algorithm in an imperfect information setting of two-player zero-sum games? We argue that the fixedstrategy definitions of exploitability and epsilon-Nash equilibria are ill suited to measure the worst-case performance of an online algorithm. We thus formalize epsilon-soundness, a concept that connects the worst-case performance of an online algorithm to the performance of an epsilon-Nash equilibrium. Our definition of soundness and the consistency hierarchy finally provide appropriate tools to analyze online algorithms in repeated imperfect information games. We thus inspect some of the previous online algorithms in a new light, bringing new insights into their worst case performance guarantees.
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/GJ18-27483Y" target="_blank" >GJ18-27483Y: Online Solution Methods for Imperfect-Information Games</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2021
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
AAMAS '21: 20th International Conference on Autonomous Agents and Multiagent Systems, Virtual Event, United Kingdom, May 3-7, 2021
ISBN
978-1-7138-3262-1
ISSN
1548-8403
e-ISSN
—
Number of pages
3
Pages from-to
1662-1664
Publisher name
ACM
Place of publication
New York
Event location
virtual
Event date
May 3, 2021
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—