Monte Carlo Tree Search
A search algorithm that uses random sampling to explore decision trees for optimal action selection.
Overview
Monte Carlo Tree Search (MCTS) is a planning algorithm that builds a search tree incrementally through four phases: selection (traversing the tree using a policy like UCB1), expansion (adding a new node), simulation (playing out a random game from the new node), and backpropagation (updating statistics along the path).
Key Details
MCTS gained fame as the key component of DeepMind's AlphaGo, combined with deep neural networks for position evaluation and move selection. It's used in game-playing AI (Go, chess, Hex), automated planning, program synthesis, and has been applied to LLM reasoning (Tree of Thoughts). MCTS excels in domains with large action spaces where exhaustive search is infeasible.