Thumbnail

Sequential Halving Applied to Trees

Cazenave, Tristan (2015), Sequential Halving Applied to Trees, IEEE Transactions on Computational Intelligence and AI in Games, 7, 1, p. 102-105. 10.1109/TCIAIG.2014.2317737

View/Open
Type
Article accepté pour publication ou publié
Date
2015
Journal name
IEEE Transactions on Computational Intelligence and AI in Games
Volume
7
Number
1
Publisher
IEEE
Pages
102-105
Publication identifier
Metadata
Show full item record
Author(s)
Cazenave, Tristan
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
Monte Carlo tree search (MCTS) is state of the art for multiple games and problems. The base algorithm currently used for MCTS is UCT. We propose an alternative MCTS algorithm: sequential halving applied to Trees (SHOT). It has multiple advantages over UCT: it spends less time in the tree, it uses less memory, it is parameter free, at equal time settings it beats UCT for a complex combinatorial game and it can be efficiently parallelized.
Subjects / Keywords
UCT; Monte Carlo Tree Search; Sequential Halving; Nogo; Sequential halving applied to trees (SHOT)