Monte Carlo Tree Search

A Powerful Algorithm for Game-Playing AI

Understanding how machines master complex games through intelligent exploration

Introduction: MCTS Explained Simply

Imagine you're trying to find the best pizza place in a new city, but you only have time to try a few spots. MCTS works similarly: you start at your hotel (the root), and at each intersection you have to decide which direction to go. Instead of exploring every single street equally, you use a smart strategy - you go down streets that seem promising based on previous trips, but you also occasionally try new streets just in case they lead somewhere amazing.

When you reach a pizza place, you try it (that's the random "simulation"), then you walk back to your hotel remembering whether it was good or bad. You update your mental map of which directions led to good pizza. After doing this many times, you can confidently say "go left at the first intersection" because that direction led to the most good experiences.

That's MCTS in a nutshell - it builds a tree of possibilities, randomly tests outcomes, remembers what worked, and gradually figures out the best move without needing to exhaustively try every single possibility. For games, it plays out thousands of random games from each position and picks the move that won most often.

The Pizza Hunt Analogy
graph TD Hotel["🏨 Hotel
(Starting Position)"] --> Left["⬅️ Go Left
Found 7 good pizzas
out of 10 tries"] Hotel --> Right["➡️ Go Right
Found 3 good pizzas
out of 10 tries"] Hotel --> Straight["⬆️ Go Straight
Found 1 good pizza
out of 2 tries - unexplored!"] Left --> L1["Pizza Place A
⭐⭐⭐⭐⭐"] Left --> L2["Pizza Place B
⭐⭐⭐⭐"] Right --> R1["Pizza Place C
⭐⭐"] Right --> R2["Pizza Place D
⭐⭐⭐"] Straight --> S1["Pizza Place E
⭐⭐⭐⭐⭐"] style Hotel fill:#FFD700 style Left fill:#90EE90 style Right fill:#FFB6C6 style Straight fill:#87CEEB style L1 fill:#FFD700 style S1 fill:#FFD700

What MCTS learns: "Go Left" wins 70% of the time, so it's probably the best choice. But "Go Straight" is under-explored (only 2 tries) and might be even better - MCTS will occasionally explore it to be sure!

MCTS Algorithm in Action

Watch as the Monte Carlo Tree Search algorithm explores a simple game tree. The animation shows each of the four phases in real-time, with nodes growing brighter as they're visited more often.

Live MCTS Visualization
Iterations: 0
Current Phase: -
Total Nodes: 1
Best Move: -
█ Selection
█ Expansion
█ Simulation
█ Backpropagation
█ Unexplored
How to read the visualization:
  • Node size: Larger nodes have been visited more times
  • Node brightness: Brighter nodes have higher win rates
  • Numbers: Show wins/visits for each node
  • Color flashing: Shows which phase is currently active on each node
  • Thick edges: Indicate the most promising paths discovered so far
How MCTS Learns from One Iteration
graph LR A["1️⃣ START
Current game state"] --> B["2️⃣ WALK THE TREE
Follow promising paths
using past results"] B --> C["3️⃣ EXPLORE NEW AREA
Add a new move option
we haven't tried yet"] C --> D["4️⃣ TEST IT OUT
Play a random game
to see what happens"] D --> E["5️⃣ REMEMBER
Update all paths:
Good result? +1 point
Bad result? +0 points"] E --> F["6️⃣ REPEAT
Do this thousands
of times"] F -.-> A style A fill:#FFD700 style B fill:#90EE90 style C fill:#87CEEB style D fill:#FFB6C6 style E fill:#DDA0DD style F fill:#FFA07A

The magic: After thousands of iterations, the moves that consistently led to wins have higher scores. MCTS simply picks the highest-scoring move from the starting position - no complex strategy needed, just statistics!

What is MCTS?

Monte Carlo Tree Search is a heuristic search algorithm used in decision-making processes, particularly effective for game-playing AI. It combines the precision of tree search with the power of random sampling to evaluate positions and make intelligent decisions.

MCTS became famous when it powered AlphaGo, the first computer program to defeat a world champion Go player. Unlike traditional minimax algorithms that require extensive domain knowledge, MCTS can learn effective strategies through self-play and simulation.

Key Facts
  • Invented: 2006
  • Type: Best-first search
  • Best for: Large state spaces
  • Famous use: AlphaGo

The Four Phases of MCTS

MCTS operates in four distinct phases that repeat iteratively until a time or iteration limit is reached. Each iteration builds upon the knowledge gained from previous simulations.

1. Selection

Start from the root and traverse the tree using a selection policy (typically UCB1) to balance exploration and exploitation until reaching a leaf node.

2. Expansion

Add one or more child nodes to the selected leaf node, representing possible moves from that game state.

3. Simulation

Play out a random game (rollout) from the new node to a terminal state, following a default policy to reach the end quickly.

4. Backpropagation

Update the statistics of all nodes visited during selection by propagating the simulation result back up the tree.

MCTS Iteration Cycle
graph TD A[Start: Root Node] --> B[Selection Phase] B --> C{Leaf Node
Reached?} C -->|No| B C -->|Yes| D[Expansion Phase] D --> E[Create New Child Node] E --> F[Simulation Phase] F --> G[Random Playout
to Terminal State] G --> H[Backpropagation Phase] H --> I[Update Node Statistics
up the Tree] I --> J{More
Iterations?} J -->|Yes| A J -->|No| K[Select Best Move
from Root] K --> L[End] style A fill:#90EE90 style D fill:#87CEEB style F fill:#FFD700 style H fill:#FF6B6B style K fill:#DDA0DD

Deep Dive: Each Phase Explained

The selection phase uses the Upper Confidence Bound for Trees (UCT) formula to choose which child node to explore:

UCT Formula:
UCT = (w_i / n_i) + C × √(ln(N) / n_i)
  • w_i: wins for this node
  • n_i: visits to this node
  • N: total visits to parent
  • C: exploration parameter (typically √2)

The first term represents exploitation (choosing known good moves), while the second term represents exploration (trying less-visited moves). This balance is crucial for effective search.

When a leaf node is reached (a node that hasn't been fully expanded), we add one or more child nodes representing legal moves from that position.

Strategies for expansion:

  • Single child: Add one child per iteration (most common)
  • All children: Add all possible moves at once
  • Progressive widening: Gradually add more children as the node is visited more

Each new node is initialized with zero wins and zero visits, ready for its first simulation.

From the newly expanded node, we simulate a complete game using a rollout policy. This is typically random moves, but can be enhanced with domain knowledge.

Rollout strategies:

  • Pure random: Choose moves uniformly at random (fast, no bias)
  • Heuristic-guided: Use simple rules to prefer certain moves
  • Neural network: Use a trained policy network (like in AlphaGo)

The simulation continues until a terminal game state (win, loss, or draw) is reached, providing a concrete outcome to propagate back.

The simulation result is propagated back up the tree to the root. Each node on the path gets updated:

  • Visit count incremented by 1
  • Win count updated based on result (from the perspective of the player who made the move)
Important: Results are recorded from each node's perspective. A win for one player is a loss for the opponent, so the same outcome has different effects on alternating nodes in the tree.

MCTS Tree Structure

Here's how the MCTS tree grows over iterations. Each node stores the number of wins and visits (wins/visits):

graph TD Root["Root State
10/20"] --> A1["Move A
7/10"] Root --> A2["Move B
2/8"] Root --> A3["Move C
1/2"] A1 --> B1["Counter 1
4/5"] A1 --> B2["Counter 2
3/5"] A2 --> C1["Counter 1
1/4"] A2 --> C2["Counter 2
1/4"] B1 --> D1["Next Move
3/3"] B1 --> D2["Next Move
1/2"] style Root fill:#FFD700 style A1 fill:#90EE90 style A2 fill:#FFB6C6 style A3 fill:#FFB6C6 style B1 fill:#87CEEB
Interpreting the tree: Move A appears strongest with a 70% win rate (7/10), making it the likely choice. Less-explored Move C might still hold surprises, which is why MCTS continues to occasionally explore it.

Implementation Example

Here's a simplified Python implementation of MCTS:

import math
import random

class MCTSNode:
    def __init__(self, state, parent=None):
        self.state = state
        self.parent = parent
        self.children = []
        self.visits = 0
        self.wins = 0
        self.untried_moves = state.get_legal_moves()
    
    def uct_value(self, exploration=math.sqrt(2)):
        if self.visits == 0:
            return float('inf')
        
        exploitation = self.wins / self.visits
        exploration_term = exploration * math.sqrt(
            math.log(self.parent.visits) / self.visits
        )
        return exploitation + exploration_term
    
    def select_child(self):
        return max(self.children, key=lambda c: c.uct_value())
    
    def expand(self):
        move = self.untried_moves.pop()
        next_state = self.state.make_move(move)
        child = MCTSNode(next_state, parent=self)
        self.children.append(child)
        return child
    
    def simulate(self):
        current_state = self.state.clone()
        while not current_state.is_terminal():
            move = random.choice(current_state.get_legal_moves())
            current_state = current_state.make_move(move)
        return current_state.get_winner()
    
    def backpropagate(self, result):
        self.visits += 1
        self.wins += result
        if self.parent:
            self.parent.backpropagate(1 - result)

def mcts_search(root_state, iterations=1000):
    root = MCTSNode(root_state)
    
    for _ in range(iterations):
        node = root
        
        # Selection
        while node.untried_moves == [] and node.children:
            node = node.select_child()
        
        # Expansion
        if node.untried_moves:
            node = node.expand()
        
        # Simulation
        result = node.simulate()
        
        # Backpropagation
        node.backpropagate(result)
    
    # Return most visited child
    return max(root.children, key=lambda c: c.visits).state

Why MCTS is Perfect for Self-Play AI

1. No Domain Knowledge Required

MCTS only needs to know the game rules, not optimal strategies. This makes it perfect for learning from scratch through self-play.

2. Handles Large State Spaces

Unlike minimax which explores uniformly, MCTS focuses computational resources on promising branches, making it viable for complex games like Go.

3. Anytime Algorithm

MCTS can be stopped at any time and will provide the best answer found so far, making it suitable for time-constrained environments.

4. Asymmetric Tree Growth

The tree grows toward interesting positions rather than expanding uniformly, naturally focusing on critical game situations.

5. Natural Exploration-Exploitation Balance

The UCT formula ensures the algorithm doesn't get stuck in local optima while still preferring known good moves.

6. Parallelizable

Multiple simulations can run simultaneously, making MCTS highly scalable with modern multi-core processors.

MCTS in Self-Play Learning

When combined with machine learning, MCTS becomes even more powerful. Here's how modern AI systems use MCTS for self-play:

graph LR A[Game Position] --> B[MCTS Search] B --> C[Generate Training Data] C --> D[Train Neural Network] D --> E[Improved Policy] E --> F[Better Simulations] F --> B B --> G[Play Game] G --> H[Game Outcome] H --> C style A fill:#FFD700 style D fill:#90EE90 style G fill:#87CEEB
Training Cycle
  1. Use MCTS to play games against itself
  2. Record positions and the moves MCTS eventually chose
  3. Train a neural network to predict MCTS's move choices
  4. Use the neural network to guide future simulations
  5. Repeat, creating increasingly strong players
Key Benefits
  • Bootstrapping: Starts from random play and improves
  • No human data needed: Learns optimal play independently
  • Discovers novel strategies: Not constrained by human knowledge
  • Continuous improvement: Can train indefinitely
  • Transferable knowledge: Learns patterns applicable across positions

Real-World Applications

Board Games
  • Go (AlphaGo, AlphaZero)
  • Chess (AlphaZero, Leela Chess)
  • Shogi
  • Hex
  • Connect Four
Video Games
  • Real-time strategy games
  • Turn-based tactics
  • Card games (Hearthstone AI)
  • Fighting game AI
  • Puzzle games
Beyond Games
  • Robot motion planning
  • Scheduling problems
  • Chemical synthesis
  • Optimization problems
  • Decision support systems

MCTS vs. Other Approaches

Aspect MCTS Minimax/Alpha-Beta Deep RL (DQN, etc.)
Domain Knowledge Minimal required Heavy evaluation function needed Learns from scratch
Computation Time Adjustable (anytime) Fixed depth or time Fast after training
Sample Efficiency Very efficient Not applicable Requires many samples
State Space Size Excellent for large spaces Struggles with large spaces Handles large spaces
Interpretability Clear decision tree Clear evaluation Black box
Training Required None (can be enhanced) None Extensive training

Getting Started with MCTS

Implementation Checklist
What You Need:
  • Game state representation
  • Legal move generator
  • Move execution function
  • Terminal state detector
  • Winner determination function
Optional Enhancements:
  • Heuristic rollout policy
  • Neural network for move prediction
  • Parallel tree search
  • Opening book integration
  • Time management system
Recommended Starting Parameters:
  • Iterations: Start with 1,000-10,000 per move
  • Exploration constant (C): √2 ≈ 1.414
  • Rollout policy: Pure random initially
  • Expansion: One child per iteration

Conclusion

Monte Carlo Tree Search represents a paradigm shift in game-playing AI. By combining random sampling with intelligent tree search, MCTS can tackle games that were previously intractable for computer algorithms.

Its true power emerges in self-play scenarios where:

  • The algorithm can learn from millions of simulated games
  • No human expertise is required to bootstrap learning
  • The system can discover novel strategies beyond human knowledge
  • Continuous improvement is guaranteed with more computation time

When combined with deep learning (as in AlphaGo and AlphaZero), MCTS becomes even more powerful, using neural networks to guide its search and learn patterns from self-play data. This synergy has produced some of the strongest game-playing systems ever created.

Key Takeaway: MCTS is not just an algorithm; it's a framework for intelligent decision-making that learns and improves through experience, making it the foundation of modern game-playing AI systems.

Further Resources

Academic Papers
  • "Mastering the game of Go with deep neural networks and tree search" (AlphaGo paper)
  • "A Survey of Monte Carlo Tree Search Methods" by Browne et al.
  • "Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search"
Implementation Resources
  • Python MCTS libraries (pymcts, mcts)
  • Open-source game engines with MCTS
  • AlphaZero implementations on GitHub
  • Online MCTS visualizers and simulators