A heuristic search algorithm used for decision-making processes, most famously in games like Go, Chess, and Shogi (e.g., AlphaGo). It combines the precision of a tree search with the generality of random sampling.
Estimates values by simulating many random games from a given state and averaging the outcomes.
The Four Phases of MCTS
- Selection: Starting at the root, the algorithm traverses down the tree using a selection policy (typically UCB1) until it reaches a “leaf” node that has unexplored children.
- Expansion: Unless the leaf node represents a terminal state (end of the game), one or more child nodes are created to represent possible next moves.
- Simulation (Playout): From the new node, the algorithm performs a “rollout”—simulating the rest of the game until a result is reached using a rapid, often random, policy.
- Backpropagation: The result of the simulation (win, loss, or draw) is propagated back up the path to the root, updating the statistics (visit count and win rate) of all nodes involved.
