Home▸AI & Machine Learning▸Monte Carlo Tree Search — Game AI

🌳 Monte Carlo Tree Search — Game AI

Watch MCTS grow a search tree over a simple game by repeating four phases — selection with UCB1, expansion, random rollout, and backpropagation — converging on strong moves without a full game-tree search.

AI & Machine Learning2DAdvanced60 FPS

About Monte Carlo Tree Search

Monte Carlo Tree Search (MCTS) is an algorithm for finding strong moves in sequential decision problems, such as board games, by incrementally building a search tree through repeated random sampling. Each iteration performs four phases: selection, which walks down the tree from the root using the UCB1 formula — winRate + C·√(ln(parentVisits)/childVisits) — to balance exploiting known-good moves against exploring under-visited ones; expansion, which adds one new node for an untried move; rollout, which plays uniformly random moves to a terminal state; and backpropagation, which updates visit and win statistics along the path back to the root. Because MCTS estimates position values from simulation outcomes rather than a hand-crafted heuristic, it scales well to games with enormous branching factors, such as Go, where exhaustive minimax search is computationally infeasible. This property made MCTS the backbone of DeepMind's AlphaGo and, combined with deep neural networks replacing random rollouts, AlphaZero — systems that surpassed human expertise in Go, chess, and shogi.

Frequently Asked Questions

What are the four phases of Monte Carlo Tree Search?

MCTS repeats four phases each iteration: selection, which descends the tree using UCB1 to pick promising children; expansion, which adds a new child node for an untried move; rollout (simulation), which plays random moves to a terminal outcome; and backpropagation, which updates visit and win counts for every node on the path back to the root. Repeating this thousands of times grows an asymmetric tree focused on strong lines of play.

What is UCB1 and how does it balance exploration and exploitation?

UCB1 (Upper Confidence Bound 1) scores each child node as winRate + C·√(ln(parentVisits)/childVisits). The win-rate term favours moves that have performed well (exploitation), while the square-root term grows larger for children with few visits (exploration), pulling the search back to under-sampled branches. The constant C = √2 balances the two terms for rewards scaled between 0 and 1.

Why is a random rollout sufficient without a hand-crafted evaluation function?

A single random rollout is noisy, but averaged over many simulations, rollout outcomes give an unbiased statistical estimate of a position's true win probability. This lets MCTS evaluate positions in games where designing an accurate heuristic evaluation function — as minimax requires — would be difficult or impossible, such as Go's vast and pattern-dependent board states.

Where is MCTS used in real-world game AI?

MCTS is the core search algorithm behind DeepMind's AlphaGo, which defeated top human Go players in 2016, and its successor AlphaZero, which mastered Go, chess, and shogi from self-play. In these systems, MCTS's random rollouts were replaced with a trained neural network's value and policy estimates, but the selection-expansion-backpropagation structure of the tree search remained.

⚙ Under the hood

Monte Carlo Tree SearchGame AIUCB1Reinforcement learningCanvas 2D

2D · HTML5 Canvas 2D · 60 FPS target · runs fully client-side, no install