Monte Carlo Tree Search (MCTS) is a search algorithm that finds good choices in problems with large branching factors — not by exhaustively evaluating every possibility, but by running many lightweight simulations. It comes up frequently in domains like Go, chess, and game AI where the number of possible moves explodes combinatorially, and more recently it offers a useful conceptual lens for problems like Graph RAG, where you need to select paths and evidence over a graph.
The core idea is straightforward. If you can't explore every path right now, sample a subset of them quickly, then dig deeper into the ones that looked promising. MCTS is less a complete depth-first search and more an approximation of deep search via probabilistic simulation.
MCTS builds a tree of choices and accumulates simulation results to explore promising paths more deeply. Source: GeeksforGeeks
Why This Kind of Search Is Needed
Tree search typically deals with structures where choices keep branching. In a game where each player has 30 legal moves, just two plies deep already yields 900 states. Go a few moves deeper and the search space grows to a scale that's completely intractable to enumerate by hand.
The simplest approach — exploring every branch to the end — is impractical for real-world problems with limited time and compute. This forces a fundamental question: if you can't look at every path, which paths should you look at first?
MCTS answers that question empirically. Early on, it samples many paths broadly. Over time, it allocates more search effort to paths that have shown better results. Rather than computing the answer analytically, it converges on better choices through repeated experimentation.
What "Monte Carlo" Means in the Name
Monte Carlo refers to methods that use random sampling to approximate solutions to problems. The Monte Carlo method approximates complex computations by iterating probabilistic sampling.
MCTS applies the same intuition. Since you can't know exactly how good a choice is, you assume it's been made and then play out the rest randomly — or according to some policy — until the game ends. Repeat that process many times, and you get an increasingly reliable estimate of whether a given choice tends to produce good outcomes on average.
Importantly, "random" here doesn't mean arbitrary. MCTS uses random simulations, but it accumulates the results in the tree and feeds them back into future decisions. As iterations pile up, the search gradually becomes more directed.
The Four Phases of MCTS
MCTS iterates over four phases. The MCTS survey by Browne et al. defines this structure as Selection, Expansion, Simulation, and Backpropagation.
- Selection: Traverse the existing tree to decide which node to visit next.
- Expansion: Add new nodes for choices that haven't been explored enough yet.
- Simulation: From the new node, play out the game to the end using a rollout policy.
- Backpropagation: Propagate the simulation result back up through all the nodes that were traversed.
Selection, expansion, simulation, and backpropagation are the fundamental repeating loop you need to grasp first when learning MCTS. Source: Spot Intelligence
These four phases don't run just once — they repeat until the time budget is exhausted. As iterations accumulate, each node builds up statistics like visit count and average reward. The final decision is typically made by picking the node with the most visits or the highest average outcome.
A Simple Example
Consider a maze with three forks: A, B, and C. The goal is to find treasure, and you have no idea which path is best.
In the first few iterations, you try each path briefly. A frequently dead-ends, B yields middling rewards, and C occasionally leads close to the treasure. MCTS starts allocating more trials to C.
But it doesn't abandon A and B entirely — they may not have been explored enough to rule out. The balance between exploiting the currently best-looking path and continuing to probe less-visited alternatives is central to how MCTS works.
The Exploration–Exploitation Trade-off
A concept that comes up constantly in MCTS is exploration vs. exploitation.
- Exploration means trying choices you don't know much about yet.
- Exploitation means going deeper into choices that already look good.
Pure exploitation risks getting stuck on a path that only seemed good early on due to luck. Pure exploration means you keep discovering promising paths without ever developing any of them. MCTS expands the tree by balancing both.
The standard mechanism for this is UCT (Upper Confidence bounds applied to Trees). Kocsis and Szepesvári's UCT paper introduced a selection criterion that is widely used in MCTS variants. UCT considers both the average reward of a choice and how infrequently it has been visited.
The formula can look intimidating, but the idea is simple: favor paths with good results, but still give underexplored paths a chance.
MCTS as an Approximation of Deep Search
Viewing MCTS as an approximation of depth-first search makes it easier to understand. Ordinary DFS follows one path all the way down before backtracking and trying another. MCTS doesn't blindly go deep on a random path — it allocates depth based on simulation results, concentrating on paths that appear more valuable.
In other words, MCTS doesn't explore the tree uniformly. It spends more compute on subtrees that seem likely to yield good outcomes. This is exactly what makes it practical for problems with enormous branching factors, even under tight time constraints.
This perspective also applies to Graph RAG. Graph RAG connects documents and entities in a graph, then retrieves evidence from that graph structure to improve answer quality. Microsoft GraphRAG is described as an approach that combines knowledge-graph-based retrieval with generation.
As the number of possible traversal paths over a graph grows, evaluating all of them becomes infeasible. An MCTS-style approach — sample a subset of candidate paths, then allocate more search budget to the more promising ones — maps naturally onto this setting. To be precise, not every Graph RAG system uses MCTS. But when thinking about path selection and search budget allocation in graph-based retrieval, MCTS is both a useful analogy and a directly applicable search framework.
From a Graph RAG perspective, deciding which paths to pursue through a graph of connected documents and entities is a central challenge. Source: AltexSoft
AlphaGo and MCTS
One of the events that brought MCTS to wide public attention was AlphaGo. The AlphaGo paper describes combining a policy network and a value network with MCTS to achieve strong performance at Go.
Traditional MCTS improves decision quality by running many simulations. AlphaGo augmented this with neural networks: the policy network identifies promising moves, and the value network evaluates how favorable the current board position is. This makes search far more efficient than pure random rollouts.
The lesson here is that MCTS doesn't have to stand alone. It can be combined with evaluation models, policy models, and heuristics. That's what makes it a viable search framework not just for classical game AI but for complex decision-making problems more broadly.
Problems Where MCTS Fits Well
MCTS is particularly well-suited to problems with the following characteristics:
- Choices unfold across multiple sequential steps.
- Exhaustive enumeration of all possibilities is infeasible.
- The quality of a choice can be approximately assessed through simulation or evaluation.
- A reasonable decision is required within a limited time budget.
Game AI fits these criteria naturally. Each move creates a turn-taking structure that forms a tree, and the reward signal — win or loss — is usually clear.
Problems like recommendation, planning, robot action selection, and pathfinding can also be viewed through an MCTS lens depending on how they're structured. That said, forcing MCTS onto every problem isn't appropriate. It may underperform when simulation is expensive, when state evaluation is unstable, or when reward design is difficult.
Key Takeaways
MCTS is not exhaustive search. It repeatedly samples a subset of choices, progressively focusing exploration on directions that appear more promising.
The algorithm in four sentences:
- Pick a choice in the tree.
- Expand choices that haven't been explored yet.
- Simulate play to the end and observe the outcome.
- Propagate that outcome back up to inform future decisions.
Repeat this loop, and the search tree grows in increasingly promising directions. That's what makes MCTS a practical approach to finding good decisions within a limited time budget — without having to evaluate the entire search space.