Abstractions and Extensive-Form Games with Imperfect Recall
Project goals
Non-cooperative game theory provides mathematical models of behavior of rational agents in competitive scenarios. We focus on the problem of solving finite strictly competitive extensive-form games with imperfect information, for which current state-of-the-art algorithms have only limited scalability. A promising approach for solving large extensive-form games is to transform the game into a smaller abstracted game, solve this abstracted game, and translate the abstracted strategies back into the original game. This approach is often used in specific domains, however, a generalization to all extensive-form games is not known. Moreover, a more compact abstracted game may belong into a different class of games (termed games with imperfect recall) that are much harder to solve than typically solved games with perfect recall. This project aims to solve this problem by designing domain-independent methods for finding abstractions with guaranteed quality of optimal abstracted strategies, and designing algorithms for computing guaranteed strategies in abstracted games of imperfect recall.
Keywords
computational game theoryextensive-form gamesimperfect recallzero-sum games
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 19 (SGA0201500001)
Main participants
České vysoké učení technické v Praze / Fakulta elektrotechnická
Contest type
VS - Public tender
Contract ID
15-23235S
Alternative language
Project name in Czech
Abstrakce a extenzivní hry s nedokonalou pamětí
Annotation in Czech
Nekooperativní teorie her poskytuje matematické modely chování racionálních agentů v kompetitivních situacích. V projektu se zaměřujeme na problém řešení končených, striktně kompetitivních sekvenčních (extenzivních) her s neúplnou informací. Tyto hry lze řešit pomocí několika algoritmů, které však mají limitovanou škálovatelnost. Slibnou metodou pro řešení velkých extenzivních her je transformace hry na menší abstrahovanou hru, vyřešení této abstrahované hry, a následně aplikování nalezených abstrahovaných strategií v původní hře. I když je tato metoda často používána v praxi, doménově nezávislá metodologie využitelná pro všechny extenzivní hry chybí. Navíc, kompaktní abstrahovaná hra může patřit do specifické podtřídy extenzivních her (zvané hry s nedokonalou pamětí), řešení kterých je výpočetně náročnější. Tento projekt chce proto navrhnout doménově nezávislé algoritmy pro nacházení abstrahovaných her, řešením kterých nalezneme strategie s garantovanou kvalitou v původní hře a také navrhnout algoritmy pro výpočet garantovaných strategií v hrách s nedokonalou pamětí.
Scientific branches
Completed project evaluation
Provider evaluation
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Project results evaluation
The project brought both theoretical and practical (algorithms) results in the area of games with imperfect information. The results were presented/published at the prestigious AI conferences and journals and they are partially also behind the well-known DeepStack Poker playing program. Financial resources were used appropriately and according to rules.
Solution timeline
Realization period - beginning
Jan 1, 2015
Realization period - end
Dec 31, 2017
Project status
U - Finished project
Latest support payment
Apr 5, 2017
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP18-GA0-GA-U/02:1
Data delivery date
May 4, 2018
Finance
Total approved costs
4,235 thou. CZK
Public financial support
4,235 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
4 235 CZK thou.
Public support
4 235 CZK thou.
100%
Provider
Czech Science Foundation
CEP
IN - Informatics
Solution period
01. 01. 2015 - 31. 12. 2017