Understanding the Monte Carlo Tree Search for game AI

Game playing has always been a proving ground for computer science. From the early checkers programs of the 1950s to the chess engines that defeated world champions, each generation of algorithms has stretched the boundary of what machines can plan ahead. Monte Carlo Tree Search, often shortened to MCTS, belongs to a newer family of techniques that tackle games through sampling rather than exhaustive enumeration. It turned out to be the ingredient that lifted computer Go from a stubborn puzzle into a discipline conquered by neural networks.

The algorithm rose to worldwide attention during the 2016 matches between AlphaGo and top-ranked human Go players. Behind the headlines, MCTS had been quietly maturing in academic circles for years, with key research at Australian universities and the University of Alberta. Today, the same loop of selection, expansion, simulation, and backpropagation powers board game bots, real-time strategy heuristics, and planning tools used by logistics teams across Sydney, Melbourne, and beyond.

Where the method came from

Monte Carlo Tree Search grew out of two traditions. The first was the older Monte Carlo method, which trades deterministic guarantees for statistical approximation by running many random trials. The second was classical game tree search, including minimax and alpha-beta pruning, which had driven engines for chess and checkers. Researchers in the early 2000s noticed that for games with vast branching factors, such as Go with its 19 by 19 grid, brute force tree search simply would not fit in any reasonable amount of memory.

Rémi Coulom's 2006 work on Crazy Stone and parallel groups exploring Upper Confidence bounds applied to Trees, or UCT, brought the pieces together. Around the same time, computer scientists at the University of Adelaide and other Australian institutions ran experiments that fed ideas from bandit problems into game tree search. The breakthrough was treating each node as an independent multi-armed bandit. That framing let the algorithm balance promising moves against unfamiliar ones, and produced results that were both stronger and more general than anything that came before.

The four phases that make up a single iteration

Every pass through the algorithm follows the same four-step rhythm, and a typical run repeats this loop thousands or even millions of times before a move is chosen. The first phase is selection, where the algorithm walks down from the root of the tree, choosing child nodes according to a policy that mixes exploitation of good moves with exploration of less-tried ones.

Once selection reaches a node that still has unexplored children, the second phase, expansion, adds one or more of those children to the tree. The third phase, simulation, takes the new node and rolls out a complete play to the end of the game using a fast default policy, usually random or lightly informed. The fourth phase, backpropagation, walks back up the path and updates win counts and visit counts for every node touched during selection and expansion.

The repeated iterations build an asymmetric tree that grows wider around promising moves and stays shallow elsewhere. Each iteration expands only a few nodes, keeping the algorithm tractable even when the underlying game has more legal positions than atoms in the observable universe. Developers often borrow ideas from related tree-based approaches such as the how to implement a trie for autocomplete systems tutorial when designing hash maps for transposition.

Walking the tree: selection strategies

The selection phase is where most of the cleverness lives. A simple win-rate heuristic, always picking the move with the highest observed average, will quickly lock onto the first plausible line and miss better options deeper in the tree. The fix is the UCB1 formula, which adds an exploration bonus that grows with the square root of the logarithm of the parent visits divided by the child visits.

In practice, the chosen formula is UCT, the same family of bounds used in the original Alberta research and replicated in Australian theses out of Monash and UNSW. The constant that multiplies the exploration term, often written as c, controls how adventurous the search is. Small constants produce tight, conservative play reminiscent of a careful Sydney barista measuring shots, while large constants encourage wild experimentation.

This selection rule treats the tree as a sequence of independent multi-armed bandits, one for each node along the path. It is an approximation, because the value of a move depends on the rest of the game, but the math behind the bounds still gives theoretical guarantees about convergence. As long as every node gets visited infinitely often, the algorithm will eventually identify and prefer the optimal move.

Branching out and rolling out

Expansion is the simplest of the four phases. When a leaf node still has legal moves that have not yet been added to the tree, the algorithm picks one and creates a new child. The choice can be sequential, in the order moves are generated, or guided by a heuristic that prioritises interesting continuations.

Simulation is where most of the compute time goes. A rollout policy plays the game to completion using whatever fast evaluation is available. Naive policies choose moves uniformly at random, which works well in games like Go where illegal moves are rare and outcomes are stable. Stronger policies use lightweight heuristics, such as capturing the most stones or threatening the largest group, to produce rollouts that resemble expert play. Researchers at the University of Melbourne have shown that even modest improvements in rollout quality can shave a sizable fraction off the iterations needed to find a strong move.

The depth of the rollout is also a tuning knob. Shorter rollouts run faster and encourage more breadth across the tree, while longer rollouts consume more time per iteration but produce more reliable value estimates. Most practical implementations cap the rollout at a fixed depth or terminate when a quiescent position is reached, trading accuracy for speed.

Feeding results back up the tree

Backpropagation closes the loop. The terminal result of the rollout, either a win, a loss, or a draw, is propagated up the path that selection and expansion followed. At each node, the visit count is incremented and the win count is updated by the appropriate amount. Some implementations track separate statistics for the player to move and the opponent, which gives the algorithm a clearer picture of who benefits from each move.

After enough iterations, every node carries a visit count and a win rate that estimates how good the corresponding position really is. The move chosen at the root is usually the most visited child rather than the highest-scoring one, because visits are a more robust signal than raw averages. This subtle choice protects the algorithm from the kind of variance that wrecks shallow statistical estimates.

Because each backpropagation touches only the nodes on the path, the cost is linear in the depth of the tree. That efficiency lets the algorithm scale to long games and combine with neural network evaluators inside systems such as AlphaZero. The shared lesson is that careful bookkeeping matters as much as clever search, a point that often gets lost in breathless coverage of modern game AI.

Pseudocode and practical implementation choices

A minimal implementation lives in a few hundred lines of code. The main data structure is the tree node, which stores a list of children, a visit count, and a win count. Selection runs a loop that descends through children picked by the UCT rule until it reaches a terminal node or one with unexpanded moves. Expansion adds a fresh child. Simulation plays out the game using a default policy. Backpropagation walks back up and updates statistics.

Developers building serious bots face a few standard decisions. The first is whether to use a single thread or many. Parallelising MCTS is non-trivial because of contention on the shared tree, but root parallelisation, where each thread runs its own tree and statistics are merged afterwards, is a popular compromise used at firms including Atlassian's Sydney office. The second is how to handle transposition, when the same position arises through different move orders. The third is how to integrate a learned value function in place of, or alongside, the rollout.

For pathfinding and decision problems with a clear heuristic, traditional informed search is often a better fit. Readers interested in a related approach will enjoy the understanding the a search algorithm for pathfinding breakdown, which covers a different tradeoff between exploration and goal-directed behaviour. The two methods are cousins, and many engineers find that mastering one makes the other much easier to grasp.

Where MCTS shines and where it stalls

MCTS excels when the branching factor is large, evaluation is expensive or unreliable, and a few high-quality moves are good enough. It is the workhorse of modern Go programs, a strong choice for Hex and Havannah, and a respected baseline for general game playing competitions. It also powers tactical planning in real-time strategy games, where small look-ahead windows can still produce sensible behaviour.

It struggles in games that demand long, exact sequences, such as chess endgames with forced mates many moves deep. It also struggles in highly reactive environments where a millisecond matters, because each iteration carries overhead. In those settings, deterministic search with strong heuristics or learned policies acting directly on raw state remain competitive.

The best way to learn the algorithm is to build a small version from scratch, run it on a toy game such as tic-tac-toe or Connect Four, then watch the win rate improve as iterations grow. Readers with questions about adapting the approach to their own projects can reach the maintainers through the contact page, where community contributions and clarifications are welcomed. From there, the road leads through deeper research papers, neural-guided variants, and eventually the self-play systems that have redefined what game AI can do.