Title :
Sequential Halving Applied to Trees
Author :
Cazenave, Tristan
Author_Institution :
LAMSADE, Univ. Paris-Dauphine, Paris, France
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);
Journal_Title :
Computational Intelligence and AI in Games, IEEE Transactions on
DOI :
10.1109/TCIAIG.2014.2317737
