Sequential Halving Applied to Trees

Tristan Cazenave

TL;DR

This paper introduces SHOT, a novel Monte Carlo Tree Search (MCTS) algorithm that adapts the "Sequential Halving" bandit strategy. SHOT significantly reduces memory usage and computation time compared to the standard UCT algorithm, while achieving superior performance in games like Nogo, and it's also parameter-free and easily parallelizable.

What Problem Does This Paper Address?

Monte Carlo Tree Search (MCTS) is a powerful technique for decision-making in complex domains like games. The most common MCTS algorithm is UCT (Upper Confidence bounds applied to Trees), which relies on a specific formula to balance exploration and exploitation. However, UCT can be computationally expensive, requiring significant memory and time, and often needs careful parameter tuning. This paper addresses the need for a more efficient, memory-light, and user-friendly MCTS algorithm that can still achieve state-of-the-art performance.

Methods

The core innovation of SHOT is its adaptation of the "Sequential Halving" algorithm, originally designed for multi-armed bandits, to the tree search problem. Unlike UCT, which incrementally expands the search tree and uses a fixed formula for move selection, SHOT takes a different approach:

  • Budget Allocation: SHOT allocates a fixed budget of "playouts" (simulated game outcomes) to moves. It starts by considering all possible moves at a node and, in each round, allocates a portion of the budget to sample these moves.
  • Progressive Pruning: After each round, SHOT identifies the best-performing moves based on their empirical averages and discards the worst half. This progressively narrows down the search space.
  • Parameter-Free: A key advantage is that SHOT does not require tuning parameters like UCT's exploration constant.
  • Memory Efficiency: SHOT creates tree nodes only when a certain number of playouts have been performed for a move, leading to significantly fewer nodes being stored compared to UCT, which often creates a node for every simulated playout.
  • Handling Re-visits: When SHOT revisits a node with an increased budget, it intelligently re-allocates playouts by considering the previously used budget and the new total budget, ensuring efficient use of resources.

Datasets

The paper evaluates SHOT on the game of Nogo, a misere version of Go where capturing a string results in a loss. Experiments were conducted on 9x9 and 19x19 board sizes. No new datasets were introduced; the evaluation was performed by playing games against itself and comparing performance against UCT.

Key Insights and Ideas

  • Bandit Strategies for Trees: The paper demonstrates that successful bandit strategies like Sequential Halving can be effectively adapted to tree search problems, offering a powerful alternative to traditional UCT.
  • Efficiency Through Pruning: The aggressive pruning strategy of Sequential Halving, by eliminating weaker moves early, leads to substantial reductions in computation time and memory usage.
  • Parameter-Free Advantage: The absence of tuning parameters makes SHOT much easier to deploy and use, removing a significant hurdle often associated with MCTS algorithms.
  • Memory Savings are Dramatic: The memory reduction achieved by SHOT is substantial, making it suitable for scenarios where memory is a critical constraint.
  • SHOT's Robustness: SHOT's performance improves with increased playouts, and it outperforms UCT at equal time settings, suggesting its effectiveness across different resource allocations.

Key Results

  • Performance: SHOT consistently outperforms UCT in Nogo, achieving higher win rates, especially at equal time settings. For example, in 19x19 Nogo, SHOT achieved a 100.0% win rate against UCT.
  • Speed: SHOT is significantly faster than UCT. For 10,000 playouts, SHOT takes half the time of UCT, and for 500,000 playouts, it takes approximately three times less time.
  • Memory: SHOT dramatically reduces memory consumption. For 9x9 Nogo, memory usage is reduced by a factor of twenty-five, and for 19x19 Nogo, by a factor of forty, compared to UCT.
  • Scalability: Both SHOT and UCT scale well with increasing numbers of playouts, but SHOT does so more efficiently.

Limitations and Future Work

  • Monte Carlo Resistant Games: The authors acknowledge that SHOT might struggle with "Monte Carlo resistant" games where increasing playouts can lead to worse results, as it eliminates moves from consideration and may not revise estimates as effectively as UCT in such scenarios.
  • Future Work: The authors suggest several avenues for future research, including:
  • Parallelizing SHOT on multi-core machines and clusters.
  • Applying SHOT to other games and problems.
  • Adapting other MCTS improvements to the SHOT framework.
  • Investigating alternative memory-saving strategies and reallocation strategies for budgets.

Summary updated

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.
BibTeX
@article{cazenave2015sequential,
  author = {Tristan Cazenave},
  title = {{Sequential Halving Applied to Trees}},
  journal = {IEEE Trans. Comput. Intell. AI Games},
  year = {2015},
  url = {https://openreview.net/forum?id=kPSeyWV1sv},
}
Figure