Monte Carlo tree search, visually

Go was supposed to be the game that held out. Chess fell to Deep Blue in 1997, and for most of the time since, the standard line has been that Go is different, that the board is too big and that good play is too much about “shape” and intuition to brute-force. The best programs were decent amateurs. Two years ago Crazy Stone beat Yoda Norimoto, a 9-dan pro, but with a four-stone head start, which is a lot.

Yesterday DeepMind published a paper in Nature, Mastering the game of Go with deep neural networks and tree search, and announced that back in October their program, AlphaGo, played Fan Hui, the reigning European champion and a 2-dan professional, on an even board. It won all five formal games. (They also played five faster informal games, and those went 3-2.) Against the other Go programs it won 494 games out of 495. In March it plays Lee Sedol in Seoul, for a million dollars.

Most of the coverage is about the neural networks, which is fair, they’re the new part. But the thing holding it all together is Monte Carlo tree search, which has been the main idea in computer Go since about 2006, and which I think is one of the nicer algorithms around. So this post is mostly about that, and then how AlphaGo bolts the networks onto it.

Why the old approach doesn’t work for Go

The classic game-playing program is minimax with alpha-beta pruning: look at every move, every reply to every move, and so on down to some depth, score the positions at the bottom with an evaluation function, and back the scores up the tree, assuming each side picks its best option. I wrote a tic-tac-toe player like this in Turbo C as a teenager and was unreasonably proud that it never lost. (Tic-tac-toe is small enough that you don’t even need the evaluation function, you just search to the end.)

The paper puts numbers on why that breaks for Go. A game tree has roughly b^d positions, where b is the number of legal moves per position and d is the game length. For chess, b is about 35 and d about 80. For Go, b is about 250 and d about 150. Pruning helps, but it doesn’t help with that.

The bigger problem is the evaluation function. In chess you can get surprisingly far by counting material: a queen is worth about nine pawns, and so on. In Go every stone is the same, and whether a group is alive or dead can depend on a fight on the other side of the board fifty moves from now. Nobody’s managed to write down a good static evaluation function for Go positions, and decades of people have tried.

The Monte Carlo idea

The trick that got Go programs out of the beginner leagues is simple to say. If you can’t evaluate a position, play it out. From the position you care about, play random moves for both sides until the game ends, and see who won. Do that a few thousand times. The fraction of wins is a rough estimate of how good the position is.

This sounds like it shouldn’t work. Random Go is terrible Go. But it turns out the average of a lot of terrible games carries real information: a position where you’re solidly ahead tends to win more random playouts than one where you’re behind. It’s the same reason Monte Carlo integration works. You don’t need any single sample to be good, you need the samples to be unbiased-ish and plentiful.

Plain Monte Carlo spreads its playouts evenly over all the candidate moves, which wastes most of them on moves that are obviously bad. Monte Carlo tree search builds a tree as it goes and spends its playouts where they’re most informative. Rémi Coulom, who wrote Crazy Stone, coined the name in 2006, and the same year Kocsis and Szepesvári published UCT, the selection rule most programs have used since.

The four steps

Each iteration of MCTS does four things. Repeat it tens of thousands of times and then play the move at the root that got visited most.

Select. Start at the root (the current position) and walk down the tree, at each node picking a child by some rule, until you reach a node that still has unexplored moves.

Expand. Add one new child for one of those moves.

Simulate. From the new node, play a fast random game to the end.

Back up. Walk back up the path and update every node on it: one more visit, and one more win if the side to move at that node won.

The tree grows unevenly, which is the whole idea. Branches that keep winning get visited more, so they get expanded deeper, so their estimates get sharper. Bad moves get a few visits, lose, and get left alone. It’s alpha-beta’s “don’t waste time on bad lines” idea, except it’s learned from the statistics instead of proven from the bounds.

The selection rule

All the cleverness is in step 1. If you always pick the child with the best win rate, you get stuck: a move that got unlucky in its first two playouts never gets another look. If you pick at random you’re back to plain Monte Carlo. It’s the multi-armed bandit problem, the slot machine one, and UCT borrows the standard answer to it, UCB1. Pick the child that maximizes

wins/visits + c * sqrt( ln(parent_visits) / visits )

The first term is how good the move looks so far. The second term is a bonus for uncertainty: it’s big for children that haven’t been visited much relative to their parent, and it shrinks as a child gets visited. c trades the two off; √2 is the textbook value.

A worked example. Say the root has been visited 100 times, split between three moves:

move	wins / visits	win rate	bonus (c = √2)	total
A	60 / 80	0.75	0.34	1.09
B	6 / 12	0.50	0.88	1.38
C	2 / 8	0.25	1.07	1.32

(ln 100 is about 4.6. For A, √2 · √(4.6/80) ≈ 0.34, and so on.)

A is clearly the best move so far, but the next playout goes to B, because twelve games isn’t enough to be sure B is worse. Notice how close C is, too: a couple more visits to B and C gets its turn. Over time A gets most of the visits anyway, because its win rate keeps it on top once the others’ bonuses shrink. The nice property, and the reason this was a big deal in 2006, is that this provably converges to the right answer in the limit, while spending most of its effort on the moves that matter.

I find this genuinely beautiful as a piece of math. My undergrad degree is in mathematics and I spent a lot of it on things with no obvious use; a formula that takes the explore/exploit tradeoff, which every one of us faces every day, and gives it a precise answer with a log and a square root is the kind of thing that made me like the subject in the first place.

What AlphaGo adds

MCTS with random playouts took Go programs from weak to strong amateur. AlphaGo’s contribution is replacing the two weakest parts of it with neural networks.

The first is a policy network. It looks at a board and outputs a probability for every possible move, “how likely is a strong human to play here”. They trained it on 30 million positions from games on the KGS Go server, and it predicts the expert’s move 57% of the time, where the previous best was 44%. Then they improved it further by having it play against older versions of itself.

The policy network’s output becomes a prior in the selection step. AlphaGo’s rule is still “value so far plus exploration bonus”, but the bonus is proportional to the network’s probability for that move and shrinks as the move gets visited. So instead of being curious about every legal move equally, the search is curious about the moves a strong player would consider. That’s what deals with b being 250: most of those 250 get a tiny prior and almost no visits.

The second is a value network: give it a board, and it estimates who’s going to win, directly, with no playout. This is the evaluation function that everybody said couldn’t be written for Go. They didn’t write it, they trained it, on 30 million positions each taken from a different game of self-play (one per game, because positions from the same game are so correlated that the network just memorized outcomes).

At a leaf, AlphaGo evaluates the position both ways: with the value network, and with a fast playout using a much smaller, cheaper policy rather than purely random moves. Then it averages the two, equally weighted. The paper reports that the mix plays better than either one alone, which I find really interesting. The playouts and the network make different kinds of mistakes.

The distributed version that played Fan Hui ran on 1,202 CPUs and 176 GPUs. Even a single-machine version beat every other program out there. And DeepMind says it evaluates thousands of times fewer positions than Deep Blue did against Kasparov, because it’s choosing far better which positions to look at.

What I think

I have a small personal stake in the neural network half. Andrew Ng’s online machine learning class in 2011 was where I first trained a neural network, a tiny one, in Octave, on handwritten digits. The idea that you’d train a network on 30 million board positions and get something that looks at a Go board the way a strong player does is a long way from that, but the building blocks are the ones from the class. That’s part of what’s exciting here. It’s mostly well-known pieces, combined well and trained at enormous scale.

The other thing I keep thinking about is how general the MCTS half is. Nothing in it is specific to Go. You need a way to list legal moves, a way to play a game to the end, and a way to tell who won. People have been using it for other games, and for planning problems that look like games if you squint. The neural networks are what made it Go-strong, but the search is what made the networks useful.

Will it beat Lee Sedol in March? Fan Hui is a strong professional, but Lee Sedol is a different level, arguably the best player of the last decade, and DeepMind has had five months since October to make AlphaGo stronger. Most of the Go people I’ve read expect Lee to win. My gut says the same, and I wouldn’t bet much on my gut here.