Monte Carlo tree search

• 1. Introduction

  ›

  Monte Carlo tree search is the algorithm that, in October 2015, powered the first computer program to beat a professional human Go player without handicaps on a full-sized board. That program was AlphaGo, built by Google DeepMind, and its victory was not just a milestone for the game of Go. It was a milestone for machine learning itself. But AlphaGo did not emerge from nowhere. The technique underneath it had been quietly developing for decades, tracing its roots to randomized methods from the 1940s. How does a search algorithm built on random game simulations outthink some of the strongest minds in the world? That question opens onto a deeper one: what makes a decision genuinely hard, and how do you write software that handles it?

• 2. Random Roots

  ›

  The Monte Carlo method dates back to the 1940s, when researchers first used random sampling to tackle deterministic problems that resisted conventional solution. The name is a reference to the famous casino in Monaco, evoking the role of chance in computation. Decades passed before anyone thought to apply this idea systematically to board games. In his 1987 PhD thesis, Bruce Abramson combined minimax search with what he called an expected-outcome model, replacing the usual static evaluation functions with random game playouts run all the way to the end. Abramson described his model as precise, accurate, easily estimable, efficiently calculable, and domain-independent. He tested it on tic-tac-toe, then on machine-generated evaluation functions for Othello and chess. Two years later, in 1989, W. Ertel, J. Schumann, and C. Suttner applied related methods to automated theorem proving, cutting through the exponential search times that had frustrated uninformed algorithms like breadth-first and depth-first search. Then in 1992, B. Brugmann used the approach for the first time in a Go-playing program, planting the technique in the game that would later become its most celebrated arena.

• 3. The UCT Breakthrough

  ›

  In 2002, Chang and colleagues proposed what they called Adaptive Multi-stage Sampling, or AMS, for Markov decision processes. AMS was the first algorithm to explore the idea of balancing exploration and exploitation when building simulated trees, and it became the direct seed for what would follow. Four years later, in 2006, three separate developments arrived almost simultaneously. Remi Coulom formally described applying the Monte Carlo method to game-tree search and coined the name Monte Carlo tree search. Levente Kocsis and Csaba Szepesvar developed the UCT algorithm, which stands for Upper Confidence bounds applied to Trees. And S. Gelly and colleagues implemented UCT in a Go-playing program called MoGo. UCT is built on a formula originally derived by Auer, Cesa-Bianchi, and Fischer, and it resolves a central tension in any search: exploit moves that have already proven strong, but keep exploring moves that have been tried only rarely. By 2008, MoGo had reached dan, or master level, in 9x9 Go. The Fuego program was winning against strong amateur players in the same format. The Zen program, in January 2012, won 3:1 against an amateur 2-dan player on the full 19x19 board.

• 4. How the Search Works

  ›

  Each cycle of Monte Carlo tree search follows four steps, repeating as long as time allows. Selection begins at the root of the game tree, which represents the current position, and descends by choosing child nodes until it reaches a leaf, meaning a position from which no simulation has yet been run. Expansion then creates one or more child nodes from that leaf, representing legal moves from that position. Simulation runs a complete random playout from the chosen child, playing moves at random until the game ends in a win, loss, or draw. Backpropagation carries the result back up the tree, updating every node along the path. Each node tracks the ratio of wins to total playouts for the player it represents. If white loses a simulation, every node along the selection path increments its simulation count, but only the black nodes are credited with wins. Draws split the credit, adding 0.5 to the win tally for both sides. After all available time is used, the algorithm selects whichever move has accumulated the most simulations, not necessarily the highest win rate, as its final answer.

• 5. Strengths and Trap States

  ›

  One of MCTS's most practical advantages over older algorithms like alpha-beta pruning is that it requires no explicit evaluation function. A program only needs to know the rules of the game: the legal moves from any position and the conditions that end it. This makes MCTS useful for games without a well-developed theory, and for general game-playing systems. The game tree it builds is asymmetric, concentrating growth on the most promising branches and achieving strong results in games with a high branching factor, where classical algorithms bog down. The weakness is the flip side of this selectivity. Moves that look superficially strong can lead to a subtle loss many steps later, and MCTS may never explore that line deeply enough to catch it. These positions are sometimes called trap states. It is believed that this vulnerability played a role in AlphaGo's loss in its fourth game against Lee Sedol during the March 2016 five-game match, a match AlphaGo ultimately won 4-1 and after which it was awarded an honorary 9-dan ranking in 19x19 Go.

• 6. Improvements and Reach

  ›

  Researchers have layered many refinements onto the basic algorithm. Playouts can be light, using purely random moves, or heavy, guided by heuristics drawn from previous playouts or expert knowledge. In Go programs, for instance, certain patterns of stones on the board influence the probability of moving into a particular area. One counterintuitive finding is that playing suboptimally during simulations sometimes makes the overall program stronger. A technique called RAVE, for Rapid Action Value Estimation, accelerates learning in games where the same position can be reached through different move orderings, such as placement games where a stone put down early has the same value regardless of what happened before it. D. Silver proposed one formula for RAVE that defines the balance between RAVE-derived and standard win statistics. MCTS also runs well in parallel: playouts can be distributed across multiple threads or processes, either by running many playouts simultaneously from a single leaf, building separate game trees in parallel and combining their root-level conclusions, or sharing a single tree with careful synchronization. This scalability made MCTS a natural fit when DeepMind combined it with deep neural networks to build AlphaGo, and when its successor AlphaZero replaced the simulation step entirely with a neural-network evaluation, extending the approach to Chess and Shogi.