AIWiki
Malaysia
Back to all articles
AI FoundationsMonte Carlo tree searchsearch algorithmsAlphaGo

Monte Carlo Tree Search

4 min readUpdated November 2026
Monte Carlo Tree Search
Type
Search / planning algorithm
Introduced
2006 (Rémi Coulom)
Selection rule
UCT (Upper Confidence Bound applied to Trees)
Best known for
AlphaGo (2016), AlphaZero (2017)
Related
Reinforcement learning, game trees, reasoning models
Monte Carlo tree search (MCTS) is a heuristic search algorithm that finds good moves in a decision problem by repeatedly and randomly playing out random sequences of moves from the current position, then folding the results back up the tree of possible plays. It builds the search tree asymmetrically, concentrating computation on the most promising branches instead of exhaustively enumerating every position like classical minimax search.[1]

How It Works

Each iteration of MCTS performs four steps:

  • Selection — descend from the root through the tree, choosing at each node the child with the highest UCT value: UCT = (wins_i / visits_i) + c × sqrt(ln N / visits_i), where the first term is the observed win rate and the second is an exploration bonus that favours rarely visited nodes.
  • Expansion — add one or more untried child positions to the selected node.
  • Simulation (rollout) — play the position out to a terminal state, or a depth limit, using a fast default or random policy.
  • Backpropagation — propagate the rollout result (win/loss or value) back up the tree, updating visit counts and values for every node on the path.[1]

    • Because results come from random playouts, MCTS needs no hand-crafted evaluation function — the position's value estimate emerges from statistics. It is an anytime algorithm: stopping it at any moment yields the move backed by the most simulations so far, and increasing the simulation budget reliably improves play.[2]

    Impact on AI

    MCTS was introduced by Rémi Coulom in 2006 but became famous through AlphaGo, which combined deep neural networks with MCTS to defeat Go champion Lee Sedol 4–1 in March 2016 — a milestone widely regarded as a turning point in public perception of AI.[3] AlphaZero then removed human knowledge entirely, learning only from self-play with MCTS guiding exploration, and reached superhuman play in Go, chess and shogi from the same architecture; MuZero extended the idea by learning the model of the environment itself.[4]

    Beyond games, MCTS is used for combinatorial optimisation, scheduling and route planning where the search space is too large for exhaustive methods, and — as the reasoning era developed — as a planning scaffold for large language models, where tree search is applied over chains of reasoning steps to let a model explore and verify multiple solution paths before answering.[5]

    >See Also

    🇲🇾Malaysian Context

    🇲🇾 Relevance to Malaysia: AlphaGo's 2016 matches against Lee Sedol were a formative event for Malaysia's AI community, and MCTS remains a standard topic in local computer-science curricula (UM, USM, UTM, UTAR, APU) precisely because it is a compact, fully understandable example of how search plus learned evaluation produces superhuman play.

    Practically, the algorithm's descendants matter for Malaysian industry: MCTS-style planning underpins optimisation of container-terminal and port scheduling (Port Klang, Tanjung Pelepas, Penang Port), airline and logistics routing, and shift and capacity planning in manufacturing and palm-oil milling. As Malaysian organisations adopt reasoning models, understanding tree search over reasoning chains helps teams choose between a single-pass answer and a search-based approach that trades latency and inference cost for accuracy — a real cost decision in a market where token budgets are scrutinised. Talent-wise, MCTS sits squarely inside the AI skills agenda of MDEC and the National AI Office, and its open, dependency-free formulation makes it a favourite for student projects, hackathons and local AI competition entries.

    References

    1. ↑Wikipedia. (2026). Monte Carlo tree search. https://en.wikipedia.org/wiki/Monte_Carlo_tree_search
    2. ↑Coulom, R. (2006). Efficient Selectivity in Backups and UCT (origin of MCTS), as documented in the history of the algorithm. https://en.wikipedia.org/wiki/Monte_Carlo_tree_search#History
    3. ↑Silver, D. et al. (2016). Mastering the game of Go with deep neural networks and tree search. Nature 529, 484–489. https://www.nature.com/articles/nature16961
    4. ↑Silver, D. et al. (2018). A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science 362, 1140–1144. https://arxiv.org/abs/1712.01815
    5. ↑Wang, X. et al. (2023). Tree of Thoughts: Deliberate Problem Solving with Large Language Models. arXiv:2305.10601. https://arxiv.org/abs/2305.10601
    Back to all articles