Value functions for depth-limited solving in zero-sum imperfect-information games

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F23%3A00364334" target="_blank" >RIV/68407700:21230/23:00364334 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1016/j.artint.2022.103805" target="_blank" >https://doi.org/10.1016/j.artint.2022.103805</a>

DOI - Digital Object Identifier

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

Result language

angličtina

Original language name

Value functions for depth-limited solving in zero-sum imperfect-information games

Original language description

We provide a formal definition of depth-limited games together with an accessible and rigorous explanation of the underlying concepts, both of which were previously missing in imperfect-information games. The definition works for an arbitrary (perfect recall) extensive-form game and is not tied to any specific game-solving algorithm. Moreover, this framework unifies and significantly extends three approaches to depth-limited solving that previously existed in extensive-form games and multiagent reinforcement learning but were not known to be compatible. A key ingredient of these depth-limited games is value functions. Focusing on two-player zero-sum imperfect-information games, we show how to obtain optimal value functions and prove that public information provides both necessary and sufficient context for computing them. We provide a domain-independent encoding of the domains that allows for approximating value functions even by simple feed-forward neural networks, which are then able to generalize to unseen parts of the game. We use the resulting value network to implement a depth-limited version of counterfactual regret minimization. In three distinct domains, we show that the algorithm's exploitability is roughly linearly dependent on the value network's quality and that it is not difficult to train a value network with which depth-limited CFR's performance is as good as that of CFR with access to the full game.

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

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

2023

Confidentiality

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

Name of the periodical

Artificial Intelligence

ISSN

0004-3702

e-ISSN

1872-7921

Volume of the periodical

314

Issue of the periodical within the volume

103805

Country of publishing house

GB - UNITED KINGDOM

Number of pages

51

Pages from-to

—

UT code for WoS article

000886552700002

EID of the result in the Scopus database

2-s2.0-85140295902