# Monte Carlo Tree Search for Asymmetric Trees

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

## Key facts

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

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

- [Qubit Routing using Graph Neural Network aided Monte Carlo Tree Search](https://mlsanity.com/paper/2104.01992/) (2021)
- [Improving Robustness of AlphaZero Algorithms to Test-Time Environment Changes](https://mlsanity.com/paper/2509.04317/) (2025)
- [A Three-Level Alignment Framework for Large-Scale 3D Retrieval and Controlled 4D Generation](https://mlsanity.com/paper/2512.22294/) (2025)
- [Learning to Play: Reinforcement Learning and Games](https://mlsanity.com/paper/2610.17391/) (2026)

## Abstract (arXiv)

We present an extension of Monte Carlo Tree Search (MCTS) that strongly increases its efficiency for trees with asymmetry and/or loops. Asymmetric termination of search trees introduces a type of uncertainty for which the standard upper confidence bound (UCB) formula does not account. Our first algorithm (MCTS-T), which assumes a non-stochastic environment, backs-up tree structure uncertainty and leverages it for exploration in a modified UCB formula. Results show vastly improved efficiency in a well-known asymmetric domain in which MCTS performs arbitrarily bad. Next, we connect the ideas about asymmetric termination to the presence of loops in the tree, where the same state appears multiple times in a single trace. An extension to our algorithm (MCTS-T+), which in addition to non-stochasticity assumes full state observability, further increases search efficiency for domains with loops as well. Benchmark testing on a set of OpenAI Gym and Atari 2600 games indicates that our algorithms always perform better than or at least equivalent to standard MCTS, and could be first-choice tree search algorithms for non-stochastic, fully-observable environments.