How Monte Carlo Tree Search Powers AlphaGo and Beyond: A Deep Dive

2016 AlphaGo beat Lee Sedol, sparking worldwide interest in Monte Carlo Tree Search (MCTS), a statistical simulation‑based heuristic search algorithm.

Basic Principles of Monte Carlo Tree Search

MCTS evaluates each possible choice via random simulations, constructing a decision tree.

It consists of four steps: Selection, Expansion, Simulation, and Backpropagation.

Selection

The goal of the selection step is to find the most promising node in the current tree. It uses the Upper Confidence Bound (UCB) formula:

UCB = (average reward) + C * sqrt(ln(parent visits) / node visits)

where the average reward reflects past performance, and the exploration term (controlled by constant C) encourages trying less‑explored nodes.

average reward of the node

C is a constant balancing exploration and exploitation

parent visits is the number of times the parent node has been visited

node visits is the number of times the node itself has been visited

Maximizing the UCB value selects the optimal node.

Expansion

When a leaf node is selected and not fully expanded, one or more child nodes are added, growing the search tree and covering more of the search space.

Simulation

Starting from the newly expanded node, a complete random simulation is performed until a terminal state is reached; the result evaluates the node’s potential value.

Backpropagation

The simulation result is back‑propagated up the path to the root, updating statistics of each visited node and edge, thereby improving future search quality.

Through repeated application of these steps, MCTS continuously refines the decision tree, enhancing search efficiency and accuracy.

Application in AlphaGo

AlphaGo uses an enhanced MCTS combined with deep neural networks and reinforcement learning.

Two networks are employed: a Policy Network that guides the selection step, and a Value Network that evaluates leaf nodes, replacing traditional random simulations.

By integrating these networks, AlphaGo can search and evaluate board states more efficiently, achieving superhuman performance.

Other Domains

MCTS is also applied in many complex decision and optimization problems:

Robot path planning – finding optimal routes in dynamic environments.

Autonomous driving – real‑time decision making to predict and choose safe maneuvers.

Financial investment – simulating portfolios to assess potential returns and risks.

Bioinformatics – protein folding and drug design by exploring molecular structures.

Overall, Monte Carlo Tree Search is a versatile heuristic algorithm that, by combining statistical simulation with decision‑tree construction, serves a wide range of fields requiring sophisticated decision making.