DocumentCode
81383
Title
Sequential Halving Applied to Trees
Author
Cazenave, Tristan
Author_Institution
LAMSADE, Univ. Paris-Dauphine, Paris, France
Volume
7
Issue
1
fYear
2015
fDate
Mar-15
Firstpage
102
Lastpage
105
Abstract
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.
Keywords
Monte Carlo methods; game theory; trees (mathematics); MCTS algorithm; Monte Carlo tree search; SHOT; combinatorial game; sequential halving applied to trees; Algorithm design and analysis; Games; Indexes; Memory management; Monte Carlo methods; Random access memory; Search problems; Monte Carlo tree search; Nogo; UCT; sequential halving; sequential halving applied to trees (SHOT);
fLanguage
English
Journal_Title
Computational Intelligence and AI in Games, IEEE Transactions on
Publisher
ieee
ISSN
1943-068X
Type
jour
DOI
10.1109/TCIAIG.2014.2317737
Filename
6799192
Link To Document