What is Monte Carlo Tree Search?
Monte Carlo Tree Search (MCTS) is a heuristic search algorithm for decision processes, most notably used in game-playing AI. Unlike exhaustive search algorithms like Minimax, MCTS builds a search tree by performing randomized simulations (playouts) of a game. This allows it to operate effectively in games with massive branching factors (like Go) where traditional heuristics are difficult to define.
The 4 Phases of MCTS
MCTS iterates through four distinct phases to gradually explore the most promising branches of a decision tree:
- 1Selection
Starting at the root, move down the tree by picking nodes with the best UCT (Upper Confidence Bound for Trees) score until a leaf node is reached.
- 2Expansion
If the leaf node isn't a terminal state, create one or more child nodes to represent possible future moves.
- 3Simulation
Perform a "playout" from the new node by choosing moves (often randomly) until the end of the game is reached.
- 4Backpropagation
Propagate the result of the simulation (win or loss) back up the path to update the visit count and win rate of all ancestor nodes.
Balancing via UCT
To decide which node to visit, MCTS uses the Upper Confidence Bound for Trees formula. This helps balance the need to exploit high-winning branches and explore less-visited ones:
Why MCTS?
MCTS offers several advantages over traditional game-tree search algorithms:
Massive Complexity
It handles games with huge branching factors where Minimax fails due to depth limits.
No Expert Knowledge
It doesn't require a hand-crafted evaluation function; the "knowledge" is built statistically.