Thumbnail

Combining UCT and Nested Monte-Carlo Search for Single-Player General Game Playing

Méhat, Jean; Cazenave, Tristan (2010), Combining UCT and Nested Monte-Carlo Search for Single-Player General Game Playing, IEEE Transactions on Computational Intelligence and AI in Games, 2, 4, p. 271-277. http://dx.doi.org/10.1109/TCIAIG.2010.2088123

View/Open
Type
Article accepté pour publication ou publié
Date
2010
Journal name
IEEE Transactions on Computational Intelligence and AI in Games
Volume
2
Number
4
Publisher
IEEE
Pages
271-277
Publication identifier
Metadata
Show full item record
Author(s)
Méhat, Jean
Cazenave, Tristan
Abstract (EN)
Monte-Carlo tree search has recently been very successful for game playing particularly for games where the evaluation of a state is difficult to compute, such as Go or General Games. We compare Nested Monte-Carlo Search (NMC), Upper Confidence bounds for Trees (UCT-T), UCT with transposition tables (UCT+T) and a simple combination of NMC and UCT+T (MAX) on single-player games of the past GGP competitions. We show that transposition tables improve UCT and that MAX is the best of these four algorithms. Using UCT+T, the program Ary won the 2009 GGP competition. MAX and NMC are slight improvements over this 2009 version.
Subjects / Keywords
Nested Monte-Carlo Search; Single-player games; General Game Playing; UCT