Refining subgames in large imperfect information games

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10329244" target="_blank" >RIV/00216208:11320/16:10329244 - isvavai.cz</a>

Result on the web

<a href="http://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12102/11636" target="_blank" >http://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12102/11636</a>

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Refining subgames in large imperfect information games

Original language description

The leading approach to solving large imperfect information games is to pre-calculate an approximate solution using a simplified abstraction of the full game; that solution is then used to play the original, full-scale game. The abstraction step is necessitated by the size of the game tree. However, as the original game progresses, the remaining portion of the tree (the subgame) becomes smaller. An appealing idea is to use the simplified abstraction to play the early parts of the game and then, once the subgame becomes tractable, to calculate a solution using a finer-grained abstraction in real time, creating a combined final strategy. While this approach is straightforward for perfect information games, it is a much more complex problem for imperfect information games. If the subgame is solved locally, the opponent can alter his play in prior to this subgame to exploit our combined strategy. To prevent this, we introduce the notion of subgame margin, a simple value with appealing properties. If any best response reaches the subgame, the improvement of exploitability of the combined strategy is (at least) proportional to the subgame margin. This motivates subgame refinements resulting in large positive margins. Unfortunately, current techniques either neglect subgame margin (potentially leading to a large negative subgame margin and drastically more exploitable strategies), or guarantee only non-negative subgame margin (possibly producing the original, unrefined strategy, even if much stronger strategies are possible). Our technique remedies this problem by maximizing the subgame margin and is guaranteed to find the optimal solution. We evaluate our technique using one of the top participants of the AAAI-14 Computer Poker Competition, the leading playground for agents in imperfect information settings.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

IN - Informatics

OECD FORD branch

—

Project

<a href="/en/project/GA13-10660S" target="_blank" >GA13-10660S: Interval methods for optimization problems</a><br>

Continuities

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

Publication year

2016

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 Thirtieth AAAI Conference on Artificial Intelligence

ISBN

978-1-57735-661-5

ISSN

2159-5399

e-ISSN

—

Number of pages

7

Pages from-to

572-578

Publisher name

AAAI Press

Place of publication

Palo Alto, California

Event location

Hyatt Regency Phoenix

Event date

Feb 12, 2016

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—