Algorithms for Playing Massive Imperfect-Information Games
Project goals
Game theory is a formal framework that allows computing optimal behavior in situations where multiple agents interact in a shared environment. The computational branch of the field provides algorithms for approximating optimal strategies applicable in competitive real-world problems (e.g., physical or cyber security), recreational games (e.g., poker, computer games), or safety-critical robust optimization (e.g., healthcare, autonomous driving). While there was considerable progress in this field in recent years, the existing algorithms applicable in large games either pose very particular assumptions on problem structure, which severely limits their applicability (e.g., an abundance of available information, finite horizon), or lack any performance guarantees. In this project, we aim to develop novel theory and algorithms that will allow guaranteed convergence to optimal strategies in large imperfect-information games with more general information structure, longer horizon, and weaker assumptions on opponent’s rationality than previously possible.
Keywords
Imperfect-information gamessequential decision makingdepth-limited solvingbounded rationalityreinforcement learning
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
SGA0202200004
Main participants
České vysoké učení technické v Praze / Fakulta elektrotechnická
Contest type
VS - Public tender
Contract ID
22-26655S
Alternative language
Project name in Czech
Algoritmy pro hraní masivních her s neúplnou informací
Annotation in Czech
Teorie her je vědní obor který umožňuje nalézt optimální chování v interakcích vícero agentů. Výpočetní odnož teorie her pak přichází s algoritmy, které aproximují optimální chování v množství důležitých aplikací jako reálné konflikty (např. fyzická a kybernetická bezpečnost), rekreační hry (např. poker či počítačové hry) nebo optimalizační problémy vyžadující důraz na bezpečnost (např. zdravotnictví či autonomní vozidla). Podobor který se zabývá řešením velkých her s neúplnou informací sice nedávno zaznamenal značné pokroky, současné algoritmy pro tyto hry však stále trpí řadou omezení. Současné algoritmy totiž buď vyžadují velmi specifické předpoklady (jako velké množství veřejné informace, což omezuje jejich uplatnitelnost) nebo nenabízejí žádné teoretické záruky (což omezuje jejich spolehlivost). Cílem navrhovaného projektu je tedy vyvinout teorii velkých her s neúplnou informací a navrhnout algoritmy které budou zaručeně konvergovat k optimálnímu řešení ve výrazně více hrách (co do jejich délky, předpokladů na racionalitu protivníka a struktury informace ve hře) než doposud.
Scientific branches
R&D category
ZV - Basic research
OECD FORD - main branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
OECD FORD - secondary branch
—
OECD FORD - another secondary branch
—
AF - Documentation, librarianship, work with information
BC - Theory and management systems
BD - Information theory
IN - Informatics
Solution timeline
Realization period - beginning
Jan 1, 2022
Realization period - end
Dec 31, 2024
Project status
—
Latest support payment
Feb 29, 2024
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
CEP25-GA0-GA-R
Data delivery date
Mar 12, 2025
Finance
Total approved costs
9,747 thou. CZK
Public financial support
9,747 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
9 747 CZK thou.
Public support
9 747 CZK thou.
100%
Provider
Czech Science Foundation
OECD FORD
Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Solution period
01. 01. 2022 - 31. 12. 2024