Continual Depth-limited Responses for Computing Counter-strategies in Sequential Games

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F24%3A00377050" target="_blank" >RIV/68407700:21230/24:00377050 - isvavai.cz</a>

Result on the web

<a href="https://www.ifaamas.org/Proceedings/aamas2024/pdfs/p2393.pdf" target="_blank" >https://www.ifaamas.org/Proceedings/aamas2024/pdfs/p2393.pdf</a>

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Continual Depth-limited Responses for Computing Counter-strategies in Sequential Games

Original language description

In zero-sum games, the optimal strategy is well-defined by the Nash equilibrium. However, it is overly conservative when playing against suboptimal opponents and it can not exploit their weaknesses. Limited look-ahead game solving in imperfect-information games allows superhuman play in massive real-world games such as Poker, Liar's Dice, and Scotland Yard. However, since they approximate Nash equilibrium, they tend to only win slightly against weak opponents. We propose theoretically sound methods combining limited look-ahead solving with an opponent model, in order to 1) approximate a best response in large games or 2) compute a robust response with control over the robustness of the response. Both methods can compute the response in real time to previously unseen strategies. We present theoretical guarantees of our methods. We show that existing robust response methods do not work combined with limited look-ahead solving of the shelf, and we propose a novel solution for the issue. Our algorithm performs significantly better than multiple baselines in smaller games and outperforms state-of-the-art methods against SlumBot.

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

2024

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 23rd International Conference on Autonomous Agents and Multiagent Systems

ISBN

—

ISSN

1548-8403

e-ISSN

1558-2914

Number of pages

3

Pages from-to

2393-2395

Publisher name

IFAAMAS

Place of publication

County of Richland

Event location

Auckland

Event date

May 6, 2024

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—