Solving Endgames in Large Imperfect-Information Games such as Poker

• Název práce v češtině: Řešení koncovek ve velkých hrách s neúplnou informací jako je např. Poker
• Název v anglickém jazyce: Solving Endgames in Large Imperfect-Information Games such as Poker
• Klíčová slova: algoritmická teorie her, hry s neúplnou informací, Nashovo equilibrium, podhra, koncovka, counterfactual regret minimization, Poker
• Klíčová slova anglicky: algorithmic game theory, imperfect-information games, Nash equilibrium, subgame, endgame, counterfactual regret minimization, Poker
• Akademický rok vypsání: 2014/2015
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: prof. Mgr. Milan Hladík, Ph.D.
• Řešitel: Mgr. Karel Ha - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 30.05.2014
• Datum zadání: 30.05.2014
• Datum potvrzení stud. oddělením: 06.06.2014
• Datum a čas obhajoby: 13.09.2016 09:00
• Datum odevzdání elektronické podoby: 28.07.2016
• Datum odevzdání tištěné podoby: 28.07.2016
• Datum proběhlé obhajoby: 13.09.2016
• Oponenti: Mgr. Branislav Bošanský

Zásady pro vypracování

Řešení koncovek pro hry s neúplnou informací je principelně velmi odlišné od řešení koncovek pro hry s úplnou informací. Zatímco v případě úplné informace lze snadno řešit jednotlivé podstromy herního stromu nezávisle, tento postup není v případě neúplné informace možný. Dosavední přístupy pro hry s neúplnou informací nemají teoretické záruky optimality pro výslednou strategii.
Tato práce se má zaměřit na nové možnosti řešení koncovek pro hry s neúplnou informací, které by měly zachovat jisté garance pro výslednou strategii.

Seznam odborné literatury

Neil Burch and Michael Bowling. CFR-D: Solving Imperfect Information Games Using Decomposition. preprint arXiv:1303.4441, 2013.
Sam Ganzfried and Tuomas Sandholm. Improving Performance in Imperfect-Information Games with Large State and Action Spaces by Solving Endgames. Computer Poker and Imperfect Information Workshop at the Twenty-Seventh AAAI Conference on Artificial Intelligence, 2013.
David Paul Schnizlein. State translation in no-limit poker. Master thesis, University of Alberta, 2009.

Předběžná náplň práce v anglickém jazyce

Solving endgames in games with perfect information is relatively straightforward. This is not the case for the games with imperfect information. Current techniques have no guarantee for the worst-case performance of the final strategy. This thesis deals with new approaches of endgame solving of imperfect information games, providing a bounds on the worst-case performance of the final strategy.