Original title: Vyhodonocení abstrakcií určených pre extenzívne hry s aplikáciou v pokeri
Translated title: Evaluating public state space abstractions in extensive form games with an application in poker
Authors: Moravčík, Matej ; Hladík, Milan (advisor) ; Zimmermann, Karel (referee)
Document type: Master’s theses
Year: 2014
Language: eng
Abstract: [eng] [cze]
Efficient algorithms exist for finding optimal strategies in extensive-form games. However human scale problems, such as poker, are typically so large that computation of these strategies remain infeasible with current technology. State space abstraction techniques allow us to derive a smaller abstract game, in which an optimal strategy can be computed and then used in the real game. This thesis introduces state of the art abstraction techniques. Most of these techniques do not deal with public information. We present a new automatic public state space abstraction technique. We examine the quality of this technique in the domain of poker. Our experimental results show that the new technique brings significant performance improvement. Powered by TCPDF (www.tcpdf.org) Poznáme efektívne techniky na výpočet optimálnej stratégie pre hry v rozšírenej forme. Niektoré problémy, napríklad poker, sú stále omnoho väčšie, ako sú tieto techniky schopné zvládnuť. Riešením je vytvoriť abstrakciu hry, ktorá je menšia ako pôvodná hra. V tejto abstrakcii už dokážeme nájsť optimálnu stratégiu. Túto stratégiu môžeme potom využiť v originálnej hre. V tejto práci opisujeme techniky, ktoré sa na tvorbu abstrakcií aktuálne používajú. Väčšina z nich neberie osobite v úvahu informácie, ktoré sú viditeľné pre všetkých hráčov v hre. My sme na tento účel vyvinuli vlastnú techniku a otestovali sme ju v pokeri. Naše experimentálne výsledky ukázali, že nová technika priniesla značné zlepšenie oproti doteraz používaným technikám. Powered by TCPDF (www.tcpdf.org)
Keywords: Automatic abstraction technique; Extensive form games; Nash equilibrium; Public information; State space abstraction; Abstrakcia hry; Hry v rozšírenej forme; Nashovo equilibrium; Poker

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/62938

Permalink: http://www.nusl.cz/ntk/nusl-332088


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses