Monte Carlo Tree Search
- Definition
- Monte Carlo Tree Search (MCTS) is a heuristic tree search algorithm for decision processes, most notably used in game-playing programs. It combines random sampling of game outcomes with tree search to find optimal decisions without requiring explicit evaluation functions.
How does it work?
MCTS builds a search tree incrementally by simulating random games from the current position. Unlike minimax, it doesn't need to explore the entire game tree—instead, it focuses on the most promising moves based on accumulated statistics.
The algorithm balances two competing goals:
- Exploration - Try less-visited nodes to discover potentially better moves
- Exploitation - Focus on known good moves that have yielded positive results
The Four Phases
Each iteration of MCTS consists of four phases:
-
Selection
Starting from the root, select child nodes using a tree policy (typically UCB1: Upper Confidence Bound) until reaching a node that hasn't been fully expanded or is terminal. -
Expansion
Add one or more child nodes to the selected node to represent possible future moves. -
Simulation (Rollout)
Play out the game randomly from the new node until reaching a terminal state or predefined depth. -
Backpropagation
Update the statistics (win/loss counts) for all nodes along the path from the new node back to the root.
Applications
- Game AI - Chess, Shogi, Go, Checkers, Backgammon
- Video Games - Turn-based strategy games (e.g., Total War AI)
- Automated Theorem Proving
- General Game Playing
- Planning under uncertainty
Advantages
- No need for domain-specific evaluation functions
- Works well with large branching factors (like Go)
- Anytime algorithm—can be stopped at any time
- Handles both perfect and imperfect information games
Limitations
- Requires many simulations for accuracy
- Memory-intensive for deep games
- May struggle in games with strong tactical elements
- Performance depends on simulation quality