computer science//algorithms//Monte Carlo tree search

2026-02-15

Monte Carlo tree search (MCTS) is a planning algorithm that chooses the next action by growing a search tree of possible futures from the current state and judging each branch by simulated play-outs to the end, and it is used where a simulator of the problem exists but no good formula for how promising a position is: board games, planning for robots and vehicles, decisions under partial observation. It needs no evaluation function written by hand, only the ability to simulate.

Each iteration does four things, and the tree grows by one node per iteration.

1Select a path from the root, favouring branches that have paid off or been tried little2Expand one new child at the end of it3Simulate from there to the end with fast, often random moves4Back up the result along the path

The selection rule balances the two pulls of the exploration-exploitation trade-off. The common one (UCT) picks the child that maximizes

Xˉj+cln⁡Nnj,\bar X_j + c\sqrt{\frac{\ln N}{n_j}},Xˉj+cnjlnN,

the average result Xˉj\bar X_jXˉj of child jjj plus a bonus that is large while the child's visits njn_jnj are few compared with the parent's NNN; the constant ccc sets how curious the search is. Visits concentrate on the moves that keep winning, while every move keeps being tried now and then.

It is an anytime algorithm. Stop it at any moment and the most-visited child of the root is a sensible move, and more time only sharpens the statistics, which suits a robot that must answer within a planning period of fixed length.

Learned guidance makes it strong. AlphaGo guided the selection and the evaluation with networks that propose moves and value positions, so the search spends its budget where experience says it matters; the same pairing of search with a learned prior appears in the tree search of reasoning language models. Saying that a reasoning model such as o3 is MCTS goes beyond the evidence: its internals are unpublished, and MCTS is an analogy for spending test-time compute on exploring and scoring alternatives.

Its backing up is bookkeeping. The fourth phase adds the play-out's result to the visit counts and averages of every node on the path; it shares a name with the backpropagation that computes gradients in a neural network and nothing else, since no parameter is learned and the tree is discarded after the move.

Under partial observation it runs on sampled states. POMCP, an online POMDP solver, grows the tree over histories of actions and observations and draws hidden states from the belief at each simulation; it solves medium problems and remains near research. Where a map and a heuristic exist, A* search finds deterministic paths faster and with a guarantee.