# Watch the Unobserved: A Simple Approach to Parallelizing Monte Carlo Tree Search

arXiv: https://arxiv.org/abs/1810.11755 · HTML: https://mlsanity.com/paper/1810.11755/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Oct 2018.

## Built on by (most cited first, 13 of 13)

- [Efficient Adaptation in Mixed-Motive Environments via Hierarchical Opponent Modeling and Planning](https://mlsanity.com/paper/2406.08002/) (2024)
- [Fast Monte Carlo Tree Diffusion: 100x Speedup via Parallel Sparse Planning](https://mlsanity.com/paper/2506.09498/) (2025)
- [Batch Monte Carlo Tree Search](https://mlsanity.com/paper/2104.04278/) (2021)
- [Learning to design without prior data: Discovering generalizable design strategies using deep learning and tree search](https://mlsanity.com/paper/2211.15068/) (2022)
- [MCTS-GEB: Monte Carlo Tree Search is a Good E-graph Builder](https://mlsanity.com/paper/2303.04651/) (2023)
- [SPO: Sequential Monte Carlo Policy Optimisation](https://mlsanity.com/paper/2402.07963/) (2024)
- [Twice Sequential Monte Carlo for Tree Search](https://mlsanity.com/paper/2511.14220/) (2025)
- [MCBlock: Boosting Neural Radiance Field Training Speed by MCTS-based Dynamic-Resolution Ray Sampling](https://mlsanity.com/paper/2504.09878/) (2025)
- [A Three-Level Alignment Framework for Large-Scale 3D Retrieval and Controlled 4D Generation](https://mlsanity.com/paper/2512.22294/) (2025)
- [RetroReasoner: A Reasoning LLM for Strategic Retrosynthesis Prediction](https://mlsanity.com/paper/2603.12666/) (2026)
- [Adaptive Parallel Monte Carlo Tree Search for Efficient Test-time Compute Scaling](https://mlsanity.com/paper/2604.00510/) (2026)
- [AgonAlpha: Autonomous Alpha Discovery via Prompt Economy and Scalable Agentic Search](https://mlsanity.com/paper/2608.11250/) (2026)
- [AutoSR: Automatic Symbolic Regression by Searching Research States](https://mlsanity.com/paper/2608.16876/) (2026)

## Abstract (arXiv)

Monte Carlo Tree Search (MCTS) algorithms have achieved great success on many challenging benchmarks (e.g., Computer Go). However, they generally require a large number of rollouts, making their applications costly. Furthermore, it is also extremely challenging to parallelize MCTS due to its inherent sequential nature: each rollout heavily relies on the statistics (e.g., node visitation counts) estimated from previous simulations to achieve an effective exploration-exploitation tradeoff. In spite of these difficulties, we develop an algorithm, WU-UCT, to effectively parallelize MCTS, which achieves linear speedup and exhibits only limited performance loss with an increasing number of workers. The key idea in WU-UCT is a set of statistics that we introduce to track the number of on-going yet incomplete simulation queries (named as unobserved samples). These statistics are used to modify the UCT tree policy in the selection steps in a principled manner to retain effective exploration-exploitation tradeoff when we parallelize the most time-consuming expansion and simulation steps. Experiments on a proprietary benchmark and the Atari Game benchmark demonstrate the linear speedup and the superior performance of WU-UCT comparing to existing techniques.