Monte Carlo tree search

Monte Carlo tree search, abbreviated MCTS, does not try to examine every variation to the same depth. It grows a tree gradually and uses accumulated results to choose where the next portion of computation should go. A heavily visited move is not automatically good, but its estimate is usually supported by more search.

One MCTS cycle

1. Selection: begin at the starting position and follow existing branches while balancing moves that already look strong against moves that remain uncertain.
2. Expansion: add a position or move that the tree has not developed yet.
3. Evaluation: estimate the outcome from the new position. Classical methods may complete simulated games, while modern systems may use a neural network, a trained model that recognizes patterns, to assess it.
4. Backpropagation: carry the result back along the visited path and update its visit counts and estimates.

Repeating this cycle balances exploitation and exploration. Exploitation means spending more effort where the evidence is already favorable. Exploration means testing uncertain alternatives so a surprise is not rejected too early. The exact balancing rule depends on the implementation.

Unlike minimax, MCTS commonly decides how much to investigate a branch from evidence collected during the search rather than from a uniform depth alone. In some chess programs based on neural networks, a network supplies a policy, which suggests likely moves, and a value, which estimates the outcome. The value has a role related to an evaluation function, although the overall search process is different.