Monte Carlo tree search
In plain wordsA way for a game-playing program to choose a move by simulating many possible continuations, focusing on the most promising lines, and picking the move that worked out best on average.
A heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer. search method for sequential decisions that grows a tree of possible continuations from the current statestate, n.: A snapshot of the situation an AI agent is in — for a chess program, the arrangement of pieces and whose turn it is — containing what it needs to decide what to do next., steered by the outcomes of simulated play; each iteration runs through four phases: selection (descend the tree with a rule balancing promising and under-explored moves, typically UCBupper confidence bound, n.: A rule for choosing among uncertain options that gives each one a bonus for how little is known about it, so promising but rarely tried options get a fair chance. applied to trees, UCT); expansion (add a new node); simulation or evaluation (estimate the new position's value by a random rolloutrollout, n.: Letting an AI play out a task with its current strategy, from some starting point to the end, to see how things turn out and gather data for learning or planning. to the end of the game or, in modern systems, by a learned value networkvalue function, n.: An estimate of how promising a situation is for an AI agent, judged by the rewards it is likely to collect from that point on, the way a chess player sizes up a board.); and backpropagation (update visit counts and value estimates along the path). The most-visited move is played. MCTS needs no hand-crafted evaluation function, can stop at any time and concentrates effort on relevant lines, which made it the breakthrough method in computer Go. AlphaGoAlphaGo, prop. n.: A DeepMind program that in 2016 beat Lee Sedol, one of the world's best players of the board game Go, a decade or more before many experts expected a computer to manage it., AlphaZeroAlphaZero, prop. n.: A 2017 DeepMind program that taught itself chess, shogi and Go from nothing but the rules by playing against itself, and within hours of training beat the strongest existing programs. and MuZeroMuZero, prop. n.: A DeepMind game-playing program from 2019 that mastered Go, chess, shogi and Atari games without being told the rules, by learning its own simplified model of each game to plan with. guide it with policy and value networks (the PUCT rule); it is also used in planning, scheduling, theorem proving and language-model reasoning.
Each self-play move ran 800 MCTS simulations guided by the policy network's priors.
Origin
Evaluating game positions by random playouts was explored by Bruce Abramson (1987) and applied to Go by Bernd Brügmann (1993). Rémi Coulom coined 'Monte-Carlo tree search' in a 2006 paper describing his Go program Crazy Stone, and Levente Kocsis and Csaba Szepesvári's UCT algorithm (2006) supplied a bandit-based selection rule; MoGo and later AlphaGo (2016) built on both.
Usage note
Despite the name, AlphaZero-style MCTS often performs no random simulations; the Monte Carlo element survives only in sampling paths through the tree. Unlike minimaxminimax, n.: A way for a game-playing program to choose moves by assuming the opponent will always make their best reply, and picking the move whose worst-case outcome is best. search with alpha–beta pruningalpha–beta pruning, n.: A shortcut for game programs: tracking the best result each side is already sure of, it ignores lines of play that could only do worse, and when promising moves come first it searches about twice as deep., it does not search to a fixed depth or require a hand-written evaluation function.
Related
- upper confidence boundupper confidence bound, n.: A rule for choosing among uncertain options that gives each one a bonus for how little is known about it, so promising but rarely tried options get a fair chance.
- rolloutrollout, n.: Letting an AI play out a task with its current strategy, from some starting point to the end, to see how things turn out and gather data for learning or planning.
- AlphaGoAlphaGo, prop. n.: A DeepMind program that in 2016 beat Lee Sedol, one of the world's best players of the board game Go, a decade or more before many experts expected a computer to manage it.
- AlphaZeroAlphaZero, prop. n.: A 2017 DeepMind program that taught itself chess, shogi and Go from nothing but the rules by playing against itself, and within hours of training beat the strongest existing programs.
- MuZeroMuZero, prop. n.: A DeepMind game-playing program from 2019 that mastered Go, chess, shogi and Atari games without being told the rules, by learning its own simplified model of each game to plan with.
- game treegame tree, n.: A branching diagram of every way a game could unfold: each point is a position, each branch a possible move, and the tips of the branches are wins, losses or draws.
- self-playself-play, n.: Training an AI by having it play against copies of itself, so it always has an opponent at its own level and can keep improving without human examples.
- minimaxminimax, n.: A way for a game-playing program to choose moves by assuming the opponent will always make their best reply, and picking the move whose worst-case outcome is best.
- alpha–beta pruningalpha–beta pruning, n.: A shortcut for game programs: tracking the best result each side is already sure of, it ignores lines of play that could only do worse, and when promising moves come first it searches about twice as deep.
Sources
- Coulom, R. (2007). Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. Computers and Games (CG 2006), Lecture Notes in Computer Science 4630.
- Kocsis, L. & Szepesvári, C. (2006). Bandit Based Monte-Carlo Planning. ECML 2006.
- Browne, C. B. et al. (2012). A Survey of Monte Carlo Tree Search Methods. IEEE Transactions on Computational Intelligence and AI in Games 4(1), 1–43.
Mentioned in
AlphaGoAlphaGo, prop. n.: A DeepMind program that in 2016 beat Lee Sedol, one of the world's best players of the board game Go, a decade or more before many experts expected a computer to manage it., AlphaGo ZeroAlphaGo Zero, prop. n.: A program from DeepMind that taught itself to play the board game Go better than any human in 2017, starting from nothing but the rules and learning only by playing millions of games against itself., AlphaZeroAlphaZero, prop. n.: A 2017 DeepMind program that taught itself chess, shogi and Go from nothing but the rules by playing against itself, and within hours of training beat the strongest existing programs., beam searchbeam search, n.: A search method that keeps several of the best partial answers at each step, rather than only the single best, to find a better overall result without trying every possibility., David SilverDavid Silver, prop. n.: A British computer scientist who led the reinforcement-learning research behind AlphaGo and AlphaZero, programs that taught themselves to play board games better than any human., game treegame tree, n.: A branching diagram of every way a game could unfold: each point is a position, each branch a possible move, and the tips of the branches are wins, losses or draws., minimaxminimax, n.: A way for a game-playing program to choose moves by assuming the opponent will always make their best reply, and picking the move whose worst-case outcome is best., model-based reinforcement learningmodel-based reinforcement learning, n.: Learning in which an AI agent builds, or is given, an inner simulation of how its world responds, and uses it to plan or practice in imagination before acting., Monte Carlo methodMonte Carlo method, n.: Estimating an answer by running many random trials and averaging the results — like estimating the odds in a card game by dealing thousands of hands instead of calculating., multi-armed banditmulti-armed bandit, n.: A puzzle named after a gambler choosing between slot machines: you must keep picking among options whose payoffs are unknown, learning which is best while wasting as few tries as possible on the others., neuro-symbolic AIneuro-symbolic AI, n.: AI that combines neural networks, which learn patterns from data, with symbolic methods, which follow explicit rules and logic, aiming for systems that both learn flexibly and reason reliably., rolloutrollout, n.: Letting an AI play out a task with its current strategy, from some starting point to the end, to see how things turn out and gather data for learning or planning., self-playself-play, n.: Training an AI by having it play against copies of itself, so it always has an opponent at its own level and can keep improving without human examples., state space searchstate space search, n.: Solving a problem by treating every situation it could be in as a point on a map, with each possible move as a road between points, and searching for a route from the start to a goal., test-time computetest-time compute, n.: The computing effort an AI model spends while answering a question, as opposed to while being trained. Letting a model think longer or try many answers can make it markedly smarter., alpha–beta pruningalpha–beta pruning, n.: A shortcut for game programs: tracking the best result each side is already sure of, it ignores lines of play that could only do worse, and when promising moves come first it searches about twice as deep., counterfactual regret minimizationcounterfactual regret minimization, n.: A method for working out near-unbeatable strategies in games with hidden information, like poker, by repeatedly playing against itself and shifting each decision toward the moves it most regrets not making., expert iterationexpert iteration, n.: A learning loop in which a slow, careful search finds better moves or solutions than the AI's quick instincts, and the AI is then trained to imitate them, so each round's search starts smarter., general game playinggeneral game playing, n.: Building AI players that are handed the rules of a game they have never seen and must work out how to play it well on their own, with no game-specific help from their programmers., MuZeroMuZero, prop. n.: A DeepMind game-playing program from 2019 that mastered Go, chess, shogi and Atari games without being told the rules, by learning its own simplified model of each game to plan with., tree of thoughtstree of thoughts, n.: A method in which an AI explores several possible next steps of a problem, judges which look promising and backs out of dead ends, like a chess player weighing moves, instead of reasoning in one straight line., upper confidence boundupper confidence bound, n.: A rule for choosing among uncertain options that gives each one a bonus for how little is known about it, so promising but rarely tried options get a fair chance.