Solving Endgames in Large Imperfect-Information Games such as Poker
| Thesis title in Czech: | Řešení koncovek ve velkých hrách s neúplnou informací jako je např. Poker |
|---|---|
| Thesis title in English: | Solving Endgames in Large Imperfect-Information Games such as Poker |
| Key words: | algoritmická teorie her, hry s neúplnou informací, Nashovo equilibrium, podhra, koncovka, counterfactual regret minimization, Poker |
| English key words: | algorithmic game theory, imperfect-information games, Nash equilibrium, subgame, endgame, counterfactual regret minimization, Poker |
| Academic year of topic announcement: | 2014/2015 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | prof. Mgr. Milan Hladík, Ph.D. |
| Author: | Mgr. Karel Ha - assigned and confirmed by the Study Dept. |
| Date of registration: | 30.05.2014 |
| Date of assignment: | 30.05.2014 |
| Confirmed by Study dept. on: | 06.06.2014 |
| Date and time of defence: | 13.09.2016 09:00 |
| Date of electronic submission: | 28.07.2016 |
| Date of submission of printed version: | 28.07.2016 |
| Date of proceeded defence: | 13.09.2016 |
| Opponents: | Mgr. Branislav Bošanský |
| Guidelines |
| Ř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. |
| References |
| 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. |
| Preliminary scope of work in English |
| 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. |