Sequential Halving Applied to Trees
Tristan Cazenave · IEEE Transactions on Computational Intelligence and AI in Games · 2014
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.