Monte Carlo Tree Search

A decision algorithm that estimates how good each choice is through large numbers of random simulations, growing a search tree as it goes.

Monte Carlo tree search is used to find good decisions in sequential-choice problems. Rémi Coulom coined the name in 2006, and that same year Kocsis and Szepesvári proposed the most commonly used variant, UCT. Each iteration does four steps: selection (descend from the root, picking the currently most-promising branch at each level), expansion (add a new node), simulation (play out randomly, or according to a policy, from the new node to some end state, getting a result), and backpropagation (update the statistics of every node along the path with that result). Selection commonly uses the UCB formula w/n + c·√(ln N / n): w/n is the branch's average score, n how many times it's been tried, N the parent's visit count, and c a knob balancing exploring new branches against exploiting known-good ones. It needs no hand-written position-evaluation function, and can report its current best answer even mid-search. AlphaGo, which beat Lee Sedol in 2016, combined it with neural networks; in robotics it is used for task planning, decision-making under partial observability, and contact-sequence planning.

ExampleFor a legged robot crossing stepping stones, Dhédin et al. (2025) used MCTS to search, at a discrete level, over which leg, in what order, and onto which foothold region to step, handing each candidate sequence to whole-body trajectory optimization to check feasibility and using the result to update the search tree.

Also called

MCTS

Related

Task Planning · Exploration vs. Exploitation · Partially Observable Markov Decision Process · MuZero · Multi-contact Planning · Value Function

Sources

Wikipedia: Monte Carlo tree search
Simultaneous Contact Sequence and Patch Planning for Dynamic Locomotion (arXiv 2508.12928)