Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search

Abstract

📜 Abstract

Monte-Carlo evaluation consists in estimating a position by averaging the outcome of several random continuations, and can serve as an evaluation function at the leaves of a min-max tree. This paper presents a new framework to combine tree search with Monte-Carlo evaluation, that does not separate between a min-max phase and a Monte-Carlo phase. Instead of backing-up the min-max value close to the root, and the average value at some depth, a more general backup operator is defined that progressively changes from averaging to min-max as the number of simulations grows. This approach provides a fine-grained control of the tree growth, at the level of individual simulations, and allows efficient selectivity methods. This algorithm was implemented in a 9 × 9 Go-playing program, Crazy Stone, that won the 10th KGS computer-Go tournament.

Description

✨ Summary

The paper presents an anytime Monte-Carlo tree-search framework in which repeated random game simulations both evaluate positions and incrementally expand a search tree. Rather than separating a conventional min-max search from a Monte-Carlo evaluation phase, the method uses a backup operator that gradually shifts from averaging simulation outcomes toward a max-like estimate as simulation counts increase.

Its selectivity mechanism allocates simulations according to each move’s estimated probability of outperforming the current best move. Unlike irreversible progressive pruning, every move retains a nonzero urgency, which helps preserve moves whose apparent value may improve after deeper search. The method also introduces uncertainty estimates with deliberately inflated variance for rarely explored nodes, encouraging continued exploration of under-sampled alternatives.

The principal backup method, called “Mix,” combines the mean value with a robust-max estimate based on the move receiving the most simulations. The combination is tuned empirically using self-play positions. Experiments report that the mean backup tends to underestimate node values, the ordinary maximum tends to overestimate them, and the mixed operator provides lower error across the tested simulation budgets. The resulting Crazy Stone program performed strongly on 9×9 Go, winning the 10th KGS computer-Go tournament and defeating Indigo in a 100-game match, although it remained weaker than GNU Go under the reported conditions and showed tactical weaknesses in deep sequences.

The paper became an early foundational reference for Monte-Carlo Tree Search. A widely cited 2012 survey identifies Coulom’s work as combining Monte-Carlo evaluation with tree-based search and credits it with coining the term “Monte Carlo tree search.” (lamsade.dauphine.fr) The AlphaGo research paper later cited this work directly among the antecedents of its search approach, while demonstrating the broader practical importance of neural-network-guided MCTS in computer Go. (storage.googleapis.com)