Monte Carlo Tree Search
Monte Carlo tree search plans by selectively growing a search tree, balancing promising moves against unexplored ones through sampled rollouts.
Planning by sampling
Monte Carlo tree search (MCTS) is a planning method that builds a search tree incrementally, focusing computation on the most promising lines of play. It powered strong game-playing systems and pairs naturally with learned value functions and policies in model-based RL.
The four phases
- Selection: descend the tree from the root, choosing child nodes by a rule that balances value and uncertainty.
- Expansion: add a new child node at the frontier of the tree.
- Simulation: play out from the new node to an outcome, historically by random rollout.
- Backpropagation: propagate the outcome back up the visited path, updating value estimates and visit counts.
Balancing the search
Selection commonly uses the UCT rule, an upper confidence bound applied to trees: prefer children with high average value plus a bonus for being visited less often. This treats each node as a bandit, steering search toward strong moves while still probing uncertain ones. Over many iterations the tree grows deepest along the best lines.
Combining with learning
Modern systems replace random rollouts with a learned value network and guide selection with a learned policy network. The search then acts as a powerful policy-improvement operator on top of the networks, and the search results become training targets for them — a loop of self-improvement used in AlphaZero-style agents.
Requirements and use
MCTS needs a model it can query to simulate moves, so it is model-based. It shines in tasks with large branching factors and a reliable simulator — board games, combinatorial planning, and any control problem where a fast, accurate simulator lets the agent look ahead before committing to an action.