Monte Carlo Tree Search in Simultaneous Move Games with Applications to Goofspiel

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F14%3A00223904" target="_blank" >RIV/68407700:21230/14:00223904 - isvavai.cz</a>

Výsledek na webu

<a href="http://link.springer.com/chapter/10.1007/978-3-319-05428-5_3" target="_blank" >http://link.springer.com/chapter/10.1007/978-3-319-05428-5_3</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-05428-5_3" target="_blank" >10.1007/978-3-319-05428-5_3</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Monte Carlo Tree Search in Simultaneous Move Games with Applications to Goofspiel

Popis výsledku v původním jazyce

Monte Carlo Tree Search (MCTS) has become a widely popular sampled-based search algorithm for two-player games with perfect information. When actions are chosen simultaneously, players may need to mix between their strategies. In this paper, we discuss the adaptation of MCTS to simultaneous move games. We introduce a new algorithm, Online Outcome Sampling (OOS), that approaches a Nash equilibrium strategy over time. We compare both head-to-head performance and exploitability of several MCTS variants inGoofspiel. We show that regret matching and OOS perform best and that all variants produce less exploitable strategies than UCT.

Název v anglickém jazyce

Monte Carlo Tree Search in Simultaneous Move Games with Applications to Goofspiel

Popis výsledku anglicky

Monte Carlo Tree Search (MCTS) has become a widely popular sampled-based search algorithm for two-player games with perfect information. When actions are chosen simultaneously, players may need to mix between their strategies. In this paper, we discuss the adaptation of MCTS to simultaneous move games. We introduce a new algorithm, Online Outcome Sampling (OOS), that approaches a Nash equilibrium strategy over time. We compare both head-to-head performance and exploitability of several MCTS variants inGoofspiel. We show that regret matching and OOS perform best and that all variants produce less exploitable strategies than UCT.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GAP202%2F12%2F2054" target="_blank" >GAP202/12/2054: Bezpečnostní hry v extenzivní formě</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2014

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Computer Games

ISBN

978-3-319-05427-8

ISSN

1865-0929

e-ISSN

—

Počet stran výsledku

16

Strana od-do

28-43

Název nakladatele

Springer International Publishing AG

Místo vydání

Cham

Místo konání akce

Beijing

Datum konání akce

3. 8. 2013

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—