A Tree Too Large to Read
Every board game can be drawn as a tree. The current position is the root, each legal move is a branch, and each branch leads to a new position with branches of its own. A program that could read the whole tree would play perfectly. No program can, so the classical approach in chess was to read a few moves ahead with minimax and alpha-beta pruning, then stop and score the positions at the edge of the search with a hand-written evaluation function (material, king safety, pawn structure).
Go broke that recipe. The 2016 AlphaGo paper puts the typical breadth of the game at about 250 legal moves per position and its length at about 150 moves, against roughly 35 and 80 for chess. The bigger problem was the evaluation function. In chess, counting pieces gives a decent first guess of who is winning. In Go, nobody managed to write a formula that told a strong position from a weak one in the middle of a game, so even a deep search ended on scores that meant very little.
Monte Carlo Tree Search (MCTS) gets around this by not writing an evaluation function at all. To judge a position, it plays the game out to the end many times, usually with fast and mostly random moves, and counts how often each side wins.
Random Games as an Evaluation Function
The idea that random playouts could say something about Go is older than the name. In 1993, Bernd Brügmann wrote a short report called «Monte Carlo Go» in which he treated move choice as an optimization problem and borrowed from simulated annealing. His program was weak, but the average result of many careless games turned out to carry real information about a position.
For more than a decade the idea stayed on the margins. Then, in 2006, two groups turned it into a search method. Rémi Coulom presented a randomized tree search for his Go program Crazy Stone and gave the approach its name. In the same year, Levente Kocsis and Csaba Szepesvári published «Bandit Based Monte-Carlo Planning» at ECML, which introduced the UCT algorithm. The two lines of work were independent.
The Four Steps
MCTS builds its tree gradually, one simulated game at a time. Each iteration has four parts.
1. Selection. Starting at the root, the algorithm walks down the part of the tree it has already built, choosing a child at each node according to a rule that balances good results against little-tried moves.
2. Expansion. When it reaches a node with moves that have never been tried, it adds one (or a few) new child nodes to the tree.
3. Simulation. From the new node, it plays a complete game with a cheap default policy, often uniformly random moves, until someone wins.
4. Backpropagation. The result travels back up the path to the root. Every node on the way updates two numbers: how many times it was visited and how many of those visits ended in a win.
After thousands of iterations, the program plays the move at the root with the most visits. The visit count is used instead of the raw win rate because a move with a high win rate over only a handful of visits may simply have been lucky.
What makes this different from minimax is the shape of the tree. Minimax looks at every move to a fixed depth. MCTS grows the tree unevenly: promising lines get searched deeply, and poor ones stop receiving visits once the statistics make it clear they are poor.
The Bandit Behind the Selection Rule
The selection step hides a hard question. Should the algorithm keep visiting the move that looks best so far, or spend some visits on moves that might be better but have barely been tried? This is the multi-armed bandit problem, named after a gambler deciding which slot machine to play.
Kocsis and Szepesvári took their answer from UCB1, a bandit strategy analyzed by Peter Auer, Nicolò Cesa-Bianchi and Paul Fischer in 2002. At each node, UCT picks the child that maximizes the average reward plus an exploration bonus. The bonus is a constant times the square root of the logarithm of the parent’s visit count divided by the child’s visit count. A rarely visited move gets a large bonus, which shrinks as its visit count rises.
The constant controls the balance, and in practice it is tuned for each game. The theoretical result in the 2006 paper is what made UCT attractive: given enough simulations, the probability of choosing a suboptimal move at the root goes to zero. MCTS is also an anytime algorithm. It can be stopped after any number of iterations and still return its current best move, which suits games with a clock.
Case: MoGo and Go Before Deep Learning
The first strong MCTS programs were Go programs, and MoGo was one of the most successful. Sylvain Gelly and David Silver added an idea called RAVE (rapid action value estimation). Plain UCT learns about a move only from simulations where it was played at that exact node. RAVE also credits a move whenever it appeared later in the same simulated game, a heuristic known as «all moves as first.» The estimate is biased, but it arrives much faster, and the algorithm gradually shifts weight to the unbiased value as visits accumulate. Their AAAI 2008 paper reported that MoGo, with RAVE and heuristic knowledge, became the first program to reach master level in 9×9 Go.
On August 7, 2008, MoGo, running on a supercomputer, beat the professional Kim Myungwan (8 dan) in a 19×19 game with a nine-stone handicap. Nine stones is a large handicap, and even games on the full board stayed out of reach for years.
Neural Networks Inside the Tree
AlphaGo, published by David Silver and colleagues in Nature in 2016, kept MCTS as its search procedure and replaced the weak parts with neural networks. A policy network trained on expert games gave each move a prior probability, so selection favored moves a strong player would consider. A value network estimated the winner from a position directly, and AlphaGo mixed that estimate with the result of fast rollouts. AlphaGo beat the European champion Fan Hui 5 to 0 in October 2015 and Lee Sedol 4 to 1 in March 2016.
AlphaGo Zero (Nature, 2017) went further. It learned only from self-play, starting from the rules, and dropped random rollouts entirely: leaf positions were scored by the value network alone. Its selection rule, a variant called PUCT, multiplies the exploration bonus by the network’s prior for each move. The search and the network also trained each other. With 1,600 simulations per move during self-play, MCTS produced move distributions that were stronger than the raw network, and the network was then trained to imitate those distributions. The finished program beat the version of AlphaGo that played Lee Sedol 100 games to 0. A generalized version, AlphaZero (Science, 2018), applied the same recipe to chess and shogi.
MuZero (Julian Schrittwieser and colleagues, Nature, 2020) removed the last piece of given knowledge, the rules themselves. It learns a model that predicts rewards, values and policies inside a learned representation and runs the tree search on that model. It matched AlphaZero in Go, chess and shogi and set a new state of the art on the Atari benchmark, where nobody hands the program a simulator.
Search Outside of Games
MCTS needs little from a problem: a way to list actions, apply them and score a finished sequence. In General Game Playing, programs receive the rules of a game they have never seen and must play it with no human tuning. CadiaPlayer, written by Yngvi Björnsson and Hilmar Finnsson at Reykjavik University, used Monte Carlo simulations instead of classical game tree search and won the AAAI competition in 2007 and 2008.
Chemistry is a less obvious fit. In retrosynthesis, a chemist works backward from a target molecule, choosing reactions that break it into simpler precursors until everything can be bought. Marwin Segler, Mike Preuss and Mark Waller (Nature, 2018) treated each step as a move in a tree search. A policy network trained on millions of published reactions proposed likely transformations, another network filtered out implausible ones, and MCTS searched for complete routes. Their system solved almost twice as many molecules as a traditional rule-based computer search, about thirty times faster. In a blinded test, chemists judged its routes as roughly equivalent to routes reported in the literature.
Shallow Traps
MCTS has a known weakness, and chess exposes it. Raghuram Ramanujan, Ashish Sabharwal and Bart Selman (ICAPS 2010) studied what they called shallow traps: moves after which the opponent has a forced win within a few plies. Minimax finds these easily, because it checks every reply. MCTS averages over random continuations, and in a position where only one precise reply wins, most random games will miss it. The trap looks safe on average.
The authors found that such traps are rare in Go but common in chess, including in grandmaster games. This helps explain why plain MCTS never threatened alpha-beta engines in chess, and why later work tried hybrids that run small minimax searches inside the MCTS tree. AlphaZero, which did beat strong chess engines, never relied on random playouts there. Its leaves were scored by a trained value network, which can learn to recognize a forcing line that random games would average away.
A Final Observation
The exploration bonus in UCT is a formula for admitting ignorance. It does not say a move is good. It says the program has not looked at it enough to know, and it attaches a number to that. Classical game engines had nothing like it: an evaluation function returned a confident score whether the position was well understood or not. MCTS lets a program be uncertain on purpose and spend its computation where that uncertainty is largest. AlphaGo and its successors changed almost every other part of the algorithm, but they kept that.
By: Max Johnson B.
Deja una respuesta