Monte Carlo Tree Search is Awesome

Monte Carlo Tree Search (MCTS) is my favorite algorithm. It has numerous applications, but was originally conceived for games, so that is how I'll introduce it. In this setting, it picks moves in a game by playing out many simulations, mostly at random, and uses the results of those simulations to guide its search. A nice feature is that all it needs to be useful is the rules of the game and a way to tell who won.

It has had a few notable successes. In the mid-2000s it beat Go programs that had decades of expert knowledge built into them, and about ten years later DeepMind used it in AlphaGo and AlphaZero.

In this post we will build up an understanding of how MCTS works, starting with a simple version, and working our way up to some more sophisticated versions. A useful property of the algorithm is that it is highly customizable, and you will see a few of those customizations, and even be able to play games against them, in this post.

I'm using two-player board games for the examples because that is easiest (and highly interactive), but don't be misled: MCTS has many other applications outside of games.

If you'd rather just play, the Game AIs page has the engines I talk about here.

It sucks when you can't just search everything

In the basic version of tic-tac-toe, the game is small enough that you can draw the whole tree of all possible games. This solves the game completely: you can see exactly which sequence of moves leads to a win, loss, or draw. The visual above shows it. 9! = 362,880 is not a big number for a computer, and there are fewer than 9! possible games of tic-tac-toe because many of those games end before the board is full.

Take a look at the visual of the tic-tac-toe game tree above. You can draw any two-player, turn-based game with no hidden information this way, be it chess, Go, Hex or Ultimate Tic-Tac-Toe (my personal favorite). We model each position as a node in the tree, and each legal move as an edge.

Like I said before, for small games like regular tic-tac-toe a computer can search the whole tree almost instantly. Chess, however, has around 35 legal moves in a typical position, which means the tree has a much larger effective branching factor. A famous rough estimate from Claude Shannon put the number of possible chess games at around 10¹²⁰. You can't brute force that tree.

Another fun game we will talk about, since chess is overdone, is Ultimate Tic-Tac-Toe. It is like tic-tac-toe, but starts with 81 legal moves, and the games go on for dozens of moves. You can't solve it exactly (yet, tho some smart people are working on it).

We will also talk about Hex, which is a kind of connection game played on a hexagonal grid. It presents some unique challenges that make it even trickier to search than Ultimate Tic-Tac-Toe.

A real game engine, for a game that you can't solve, has to search the tree selectively. MCTS is one way to do that.

What if we just search everything up to a fixed depth? Is that good enough?

I promise we will get to MCTS. Indulge me.

Let's first talk about depth-limited search. It leans into the fact that the tree is too big, and decides to limit the search, making a bet that there will be some good enough answer in the subtree.

The classic way is to do your depth-limited search, and then score the positions where you stopped with an evaluation function. An evaluation function takes a position, which may not be terminal, and assigns it some useful score.

Then, in a two-player board game, you use Minimax to carry those scores back up the tree. On our turn it takes the highest score, and on the opponent's turn it takes the lowest, since we assume the opponent will pick whatever hurts us most.

Strong chess engines like Stockfish are built on this. For all the fantastic complexity and engineering that went into Stockfish, at its core is a really basic idea: do a (clever) depth-limited search, score the positions at the bottom with an evaluation function, and back the scores up with minimax. Turns out the "clever" part there is a fantastically rich space to explore, and chess engine developers have spent decades exploring and optimizing their engines in that space.

No matter how clever you are, though, a lot of it depends on the evaluation function. Stockfish uses a (again clever) neural network approach called NNUE, which allows for significant speedups in evaluation of positions that are similar to each other, and training the NNUE to be a good evaluation function is a huge part of the work of making Stockfish good at chess. The current best MCTS-based approaches to chess also use neural networks, and also have an evaluation function, but they don't have to be as clever about the search. MCTS doesn't need an evaluation function to work, unlike depth-limited search, though.

Which is good, because in Hex a good evaluation function is hard to build. Much harder than in chess. Go was worse, because whether a group of stones lives or dies depends on the whole board, and nobody managed to write a handcrafted Go evaluation function that worked well, until DeepMind trained one with neural networks for AlphaGo.

A better way. A random way.

How about this: have both sides play random legal moves until the game ends, and see who won. Screw the evaluation function. Let's call this flat Monte Carlo search.

The idea in that is this: if the position is good, then random moves will lead to wins more often than losses. If the position is bad, then random moves will lead to losses more often than wins. Since a single random game doesn't tell you much, you run the simulation thousands of times, and it starts to signal the quality of the position. Seems plausible, right?

It isn't perfect, and there are many positions where this misses the mark, but it is a surprisingly good stand-in for an evaluation function.

The wonderful thing is that you don't need to know much about the game to do this. You just need to know the rules, and how to tell who won.

This approach is surprisingly effective, and it is the basis of MCTS.

The biggest problem is that flat Monte Carlo spreads the search budget evenly across all the moves below it in the tree. But if a move has lost 300 of its first 400 games, clearly that is a bad move, yet it keeps getting just as many new simulations as every other move.

The related problem: it doesn't remember anything between simulated games. Let's remember these limitations as we move on.

Oh, no! Bandits!

Are we back in skool? Indulge me and my bandit explanation.

You are in front of a row of slot machines. Each one pays out at some fixed rate that you don't know, and you only get so many pulls.

You pull around a few times to see what is going on, but eventually you'll want to figure out where to best spend your time.

Some of the machines seem to pay out more than others, and you have to decide if it is best to just go back to the ones that have paid out the most so far, or to keep exploring and pulling ones you haven't tried much, or at all.

Exploration vs exploitation. Classic bandit stuff.

Right, so, one way to handle it is to be very statistically minded about what you know and what you don't know. A machine you pull once is a lot more uncertain than a machine you pull 10,000 times, for example, so you keep track of two things: the average payout of each machine, and how uncertain you are about that average. Layer in a strategy for pulling things that you have no data on, and you can come up with a decent exploitation and exploration strategy.

Let's bring bandits to our Monte Carlo

Let's call this approach Upper Confidence Bounds (UCB), and let's write it as a formula. For each option j:

Q_j is its average payout so far, n_j is how many times you've tried it, N is how many pulls you've made in total, and C controls how much the bonus counts.

For the first extra pull in the animation, machine A has paid out 30 times in 50 pulls and machine B has paid out 4 times in 10. With 60 total pulls and $C=0.60$ it works out like this:

So, I hope you see that B gets the next pull, since 0.784 is a little bigger than 0.772, even though its average is worse.

UCT: Let's do UCB at every node

Pretty obvious next step: use UCB and treat every position in the game tree like a slot machine.

A whole simulation starts at the root and picks the first child using UCB, then keeps going down as long as the tree already has children for the position it's in. This creates an in-group and an out-group of nodes. When you hit a legal move the tree has never tried (the out-group), add it as a new node (to the in-group).

You back up the result of the simulation through the in-group, and repeat.

If you run the loop a few thousand times on a real game tree, you will see the tree get lopsided. The moves that keep winning for you get searched more and more, though you still get some visits to the other moves. Something something bandits and exploration vs exploitation, right? :)

Let's make sure we expect the best from our opponent

I'm sure you are screaming: random rollouts are dumb! The opponent won't play like that! You can do better, guy with an internet blog and a Claude subscription.

Yeah, so let's think of an example where this is a big problem. Let's say it's our turn and we have two options. One is a safe move whose simulations average +0.20. The other starts an attack, after which the opponent has eight legal replies. Seven of those replies lose for them, so we win (+1). The eighth is the only defense, and if they find it we lose (−1).

If we are using random rollouts, the attack looks great:

What matters here is not how we do against random replies, but how we do against the best reply. A Minimax approach would look at the opponent's replies and take the minimum:

So the attack is worth −1, and the safe move is better.

At first the opponent's replies aren't in the tree yet, so rollouts pick them at random, the attack wins a lot, and it gets more visits. As it gets visited, the opponent's replies get added to the tree one at a time, and eventually the search tries the defense and records its first −1.

Every simulation through that defense now adds another −1 to the attack. Importantly, we choose to keep the early wins still in the average, so the value comes down gradually. In this example, after twenty simulations through the attack it has nine wins and eleven losses:

That's already below the safe move's +0.20, and it keeps dropping toward −1 as more of the opponent's visits go to the defense, so most of the root's visits shift over to the safe move.

The Minimax approach gets to the right answer by taking a minimum, but here MCTS with UCT never takes a minimum directly. It just keeps averages, and its selection rule sends its selections to the opponent's refutation more often than random.

Of course, in this situation the defense is only one move deep. When refuting the attack takes a sequence of precise moves, the tree has to grow far enough to find the whole sequence, so a short search might miss it. But I'm sure you get the idea.

Names are good, so let's give things names. The part of the game inside the stored tree is played by the tree policy, which uses what the search has learned so far. Everything past that is played by the rollout policy. As the tree grows along an important line, the tree policy covers more of it and the random part gets shorter.

MCTS can stop at any time, anytime.

Every finished simulation leaves the tree in a usable state, so you can stop whenever you want.

More search is better, sure, but MCTS is what we call an "anytime algorithm".

Just know this: canonically, the rule for picking the move to play is not the one with the best average score; it is the one that has been visited the most.

If you divide each move's visits by the total, you get a distribution over the legal moves:

If it's concentrated, the search kept coming back to one move. If it's spread out, several moves were still competing when time ran out, which is a useful signal!

In code

Here's a skeleton of the loop in Rust, leaving out the game interface and the bodies of select, expand_one, evaluate and back_up.

fn simulate_once<G: Game>(
    tree: &mut Tree<G>,
    root: G,
) {
    let (leaf, position) = select(tree, root);
    let (leaf, position) = expand_one(tree, leaf, position);
    let value = evaluate(position);
    back_up(tree, leaf, value);
}

Backup walks up the parent links and adds one visit and the result to each node. Every result is stored from the root player's point of view, so if our attack runs into the defense and we lose, every node on that path gets the same −1.

fn uct_score<M>(
    child: &Node<M>,
    parent_visits: u32,
    our_turn: bool,
    exploration: f64,
) -> f64 {
    if child.visits == 0 {
        return f64::INFINITY;
    }
 
    let mean = child.mean_value();
    let exploitation = if our_turn {
        mean
    } else {
        -mean
    };
    let n = f64::from(child.visits);
    let total = f64::from(parent_visits);
    let bonus = (total.ln() / n).sqrt();
    exploitation + exploration * bonus
}

If you forget to flip the sign for the opponent, the simulated opponent ends up helping you win, and the engine still reports numbers that look reasonable, so it's an easy bug to miss, which I did while implementing it :)

Most of the rest of this post is about changing what goes into select and evaluate.

It works well for Go

Chess engines were playing at world-champion level with alpha-beta (the clever Minimax we talked about) search, which turns out to still be the best way to play chess. Go, however, is different: its branching factor is much higher, so alpha-beta style engines aren't so effective.

In 2006, Rémi Coulom's Crazy Stone, the program behind the paper that gave MCTS its name, won the 9×9 Go tournament at the Computer Olympiad. In 2007, MoGo, which was built on UCT, won the 19×19 tournament at the Computer Olympiad in Amsterdam. The rollouts were random except for a few hand-written local patterns. In 2008 it beat a professional, Kim Myungwan, on the full board with a 9-stone handicap, and a few years after that Monte Carlo-style Go programs were playing at strong amateur dan level.

Search, not policy, is carrying things

None of the programs knew what a good Go position looked like. They didn't make use of an evaluation function better than random play with a few hand-written tweaks.

The search was carrying things. The AlphaGo Zero paper says something similar, describing MCTS as something that "may be viewed as a powerful policy improvement operator."

The search does that in two ways, and each one fixes a different kind of mistake.

The first is averaging, which fixes noise. One random game is a noisy verdict on a position, sometimes too hopeful and sometimes too gloomy, and those errors cancel out as you play more games.

The second is growing the tree, which fixes what I'll call short-sighted mistakes. That's the attack example: random rollouts kept assuming the opponent would miss the defense, and growing the tree past that move is what fixed it.

What neither of those fixes is bias, meaning a mistake about some kind of position that leans the same way every time. Think of a judge that's always a little too hopeful about positions with a certain shape. Averaging can't cancel it, and growing the tree doesn't escape it, because it shows up again at every new frontier.

We need better judgment than random rollouts

I'll skip ahead and give you the answer. The main ways to make MCTS better are smarter rollouts, priors, and value functions.

Smarter rollouts

The obvious first upgrade is to replace random rollouts with something more clever.

But, paradoxically, a stronger rollout policy can make the search worse.

The explanation for that is bias: a better policy can be the stronger player, but it can have habits that tilt the simulated games the same way every time, which makes the search less effective at making practically strong moves.

You want a rollout policy with this property: its mistakes cancel out in a useful way for the tree search. The policy itself being strong isn't sufficient.

Priors and value functions

A prior $P(s,a)$ is a probability for each legal move, meaning how promising it looks before any search happens. It could come from hand-written rules or from a neural network.

We can give this a name: PUCT, which puts the prior into the exploration bonus:

A move the prior likes gets a big bonus, so it gets tried early. As it collects visits, the $1 + N(s,a)$ in the denominator shrinks that bonus and its actual results in $Q$ take over. Meanwhile $N(s)$ in the numerator keeps growing, so moves the prior passed over slowly build up bonus too. (At a brand-new node $N(s)=0$, so some implementations, including mine, use $\sqrt{N(s)+1}$ so the prior can still order the first visit.)

A wrong prior usually just costs time: the early simulations go to the wrong moves, and the search overrules the prior once the results come in. If it is wrong enough, though, it can steer the search away from the right move.

A value function can replace the rollout itself. So, when the search reaches a new position, it can ask the value function for a score instead of playing the game out.

Value functions can be biased as well, subtly wrong in the same way in multiple positions, and steer the search toward the wrong moves.

The most successful implementations of value functions have been neural networks trained on positions from games, but there are other ways to build them.

Here is how a value function can look accurate on a test set and still make search worse.

Getting more out of every game

Go and Hex both have a lot of legal moves: a 19×19 Go board has 361 opening moves and a 13×13 Hex board has 169.

This, of course, presents a problem for plain MCTS: computationally, we will struggle to visit the subtree of every legal move enough times to get a good estimate of its quality.

Here is an observation for stone-playing games like Hex and Go: each simulated game has dozens of moves in it that just get thrown away. Say Red plays at f7 late in a random game and goes on to win. In Hex stones never move, and a stone on f7 helps build a connection whether it was placed on move 1 or move 30. So that win is some evidence that f7 would have been a good first move too.

This observation is the basis of All-moves-as-first (AMAF), which is a way to get more out of each simulation.

When a simulation backs up through a node, every move the same player made later in that game gets credit as if it had been played right there.

Now we are getting clever.

Of course, it isn't perfect: AMAF is biased because it ignores move order. If the opponent is threatening to connect right now, only the blocking move works, and a move that would have been fine ten turns later loses on the spot.

But it is a tradeoff. We accept some of that bias in exchange for replacing a huge amount of noise with much more data.

Let's introduce a new term: RAVE (rapid action value estimation), which is an approach that blends the two estimates. In a formula:

The weight $\beta$ starts near 1 while a move has few direct visits and drops toward 0 as they add up. So the biased estimate steers the early search, and the search stops trusting it once the direct averages have enough games behind them.

RAVE came out of the MoGo work for exactly this problem in Go, and it works in Hex because it is a stone-playing game. The stones don't move! So the order is a bit less important than in other games.

Hex has proofs!

In Hex you can sometimes prove a position is won long before the board fills up. I won't over-explain this here, but play a few games and you will see it happen in a tit-for-tat exchange that turns into a forced win. The search can use this to its advantage.

Search itself can be a teacher

AlphaGo

AlphaGo, which DeepMind published in 2016, used deep neural networks for the prior and value.

It had a policy network trained on 30 million positions from human games, which supplied the priors, and a value network, which scored new positions.

A fast, simple rollout policy built from hand-made patterns also played each new position out to the end, and AlphaGo weighted the rollout result and the value network's score equally.

DeepMind first trained the value network on positions from complete human games, but it just memorized game outcomes, since positions from the same game look nearly identical and share one result. Training it on one position from each of 30 million self-play games fixed that.

AlphaGo beat the European champion Fan Hui 5–0 in October 2015, and then Lee Sedol, one of the best players in the world, 4–1 in March 2016.

AlphaGo Zero and AlphaZero

In 2017 AlphaGo Zero dropped the human games and the custom rollouts entirely.

It uses one network that looks at a position and outputs both a prior $p$ over moves and a value $v$ for the position. MCTS uses $p$ as its PUCT prior and $v$ to score new positions.

The training of the network is a loop like so:

1. From each position in a self-play game, run MCTS guided by the current network. The result is the visit distribution $\pi$ from earlier in this post.
2. Play a move sampled from $\pi$, and keep going until the game ends with a result $z$.
3. Train the network so its prior $p$ matches $\pi$ and its value $v$ predicts $z$.

The search is able to take the network's judgment and use it to make it better, with $\pi$ as a better policy than $p$. Train $p$ toward $\pi$ and the network gets better, the next search starts from a better prior, and it produces a better $\pi$ again.

The loop is also why AlphaGo Zero's learned value doesn't stay exploited the way I warned you about earlier, because every self-play game ends with a real result, and $v$ is trained on that result, including in the positions the search went to because $v$ overrated them. It is a bit of a bias correction loop because it is grounded in real game outcomes.

Most of the strength comes from the search still, though. AlphaGo Zero's final network, picking moves directly with no search, was rated around 3,055 Elo, and the same network with MCTS on top was rated around 5,185. After three days of training from nothing but the rules, a smaller version had already beaten the program that beat Lee Sedol, 100 games to 0.

AlphaZero, later in 2017, ran the same loop for chess and shogi. In chess it looked at about 80,000 positions per second, while Stockfish, the strongest chess engine at the time, looked at about 70 million. AlphaZero won the match reported in the paper. That's roughly one position for every thousand Stockfish looked at, although each of AlphaZero's evaluations was much more expensive. These days, though, Stockfish's alpha-beta-style search, guided by an NNUE eval, is the best engine. But the ideas of AlphaZero live on in the Leela Chess Zero project.

While Stockfish has managed to retain the top spot for a while, Leela Chess Zero has proven a formidable opponent, often coming second to Stockfish in computer tournaments, and occasionally beating it. I find it likely that with more resources, or a clever trick or two, the MCTS/PUCT-style chess engines could reclaim chess, and that is something I'm working on :)

Additional reading

• Bernd Brügmann, Monte Carlo Go (1993). The first attempt to score Go positions with random games.
• Rémi Coulom, Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search (2006). Crazy Stone and the paper that started MCTS.
• Levente Kocsis and Csaba Szepesvári, Bandit Based Monte-Carlo Planning (ECML 2006). UCT and its convergence proof.
• Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer, Finite-time Analysis of the Multiarmed Bandit Problem (2002). The UCB1 formula.
• Sylvain Gelly and David Silver, Combining Online and Offline Knowledge in UCT (ICML 2007). The stronger rollout policy that made MoGo weaker, and the first version of RAVE.
• David Silver and Gerald Tesauro, Monte-Carlo Simulation Balancing (ICML 2009). Training rollout policies for accurate averages instead of strong play.
• Sylvain Gelly and David Silver, Monte-Carlo Tree Search and Rapid Action Value Estimation in Computer Go (Artificial Intelligence, 2011). The full treatment of RAVE, and MoGo's history.
• Mark Winands, Yngvi Björnsson, and Jahn-Takeshi Saito, Monte-Carlo Tree Search Solver (CG 2008). Storing proofs alongside averages.
• David Silver et al., Mastering the Game of Go with Deep Neural Networks and Tree Search (Nature, 2016). AlphaGo.
• David Silver et al., Mastering the Game of Go without Human Knowledge (Nature, 2017). AlphaGo Zero, the self-play loop, and the search-versus-network Elo comparison.
• David Silver et al., Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm (2017). AlphaZero, including the positions-per-second comparison with Stockfish.
• Cameron Browne et al., A Survey of Monte Carlo Tree Search Methods (2012). The standard map of MCTS variants, including the ones this post skips.