Monte Carlo Tree Search: The Breakthrough Behind AlphaGo

In March 2016, the worlds of artificial intelligence and gaming were rocked by a momentous event. Google DeepMind‘s AlphaGo program defeated world champion Lee Sedol in a five-game match of Go, an ancient Chinese board game long thought to be a bastion of human intelligence. This watershed moment demonstrated the immense power of modern AI techniques to tackle enormously complex problems.

While AlphaGo utilized a number of cutting-edge machine learning technologies, arguably the most important was an algorithm called Monte Carlo Tree Search (MCTS). In this post, we‘ll dive deep into how MCTS works, why it‘s been so successful, and how it‘s driving exciting new frontiers in AI research.

A Primer on Monte Carlo Tree Search

At its core, Monte Carlo Tree Search is a heuristic search algorithm for optimal decision making in a given domain by taking random samples in the decision space and building a search tree according to the results. More plainly, it figures out the best actions to take by randomly simulating different sequences of decisions and learning from the outcomes.

The MCTS algorithm consists of four key steps that are repeated until some computational budget (time or memory) is exhausted:

1. Selection: Starting at the root node, use a tree policy (like UCB1) to recursively select optimal child nodes until a leaf node is reached.
2. Expansion: If the selected leaf node is not a terminal state, create one or more child nodes and select one.
3. Simulation: Run a simulated playout from the selected node to a terminal state using the default policy.
4. Backpropagation: Update the nodes on the path from the selected node to the root with the simulation result.

By repeating this process, the algorithm gradually builds up statistics at each node in the tree estimating the optimal decision at that state based on the simulated playouts. The tree policy balances exploring new or uncertain states with exploiting known good ones.

A Step-by-Step Example

To really solidify how MCTS works, let‘s walk through a simple example step by step. Consider a basic two-player game where each player takes turns placing a piece until the board is full. The goal is to get the most pieces in a line.

We start at the root node representing the empty board. On the first iteration, we use the tree policy to select the root node, since it‘s the only option. We expand it by adding a child node for each legal move and select one at random, since they‘re all unknown.

We then simulate a random playout from that new node, selecting moves according to the default random policy until the game ends. Let‘s say the end result is a loss for the current player. We backpropagate that result up the tree, updating the selected node and root node with the new information.

On the next iteration, we again start at the root and select a child node to expand using the tree policy. This time, we have some information to guide our choice using UCB1. We expand the selected node, simulate another playout, and backpropagate the result.

This process continues for as many iterations as we can afford. By the end, the root node will have robust statistics for each of its child nodes corresponding to different moves. We select the optimal move according to the tree policy.

Essentially, MCTS works by trying out different move sequences according to the tree and default policies, learning from the simulated outcomes, and gradually building up estimates for the optimal decisions. The UCB1 tree policy balances exploring uncertain or unexplored states and exploiting known good ones.

Why Monte Carlo Tree Search?

So what makes MCTS so powerful compared to other game AI techniques like minimax search with alpha-beta pruning? There are a few key advantages:

• Scalability: MCTS can handle massive state spaces and branching factors that are intractable for full-width search. It does this by sampling the most promising moves and incrementally building the search tree.
• Generality: The algorithm is domain-independent and doesn‘t require expert knowledge or heuristics. All it needs is a way to simulate the game or environment.
• Versatility: MCTS can be applied to all kinds of problems beyond classic games, from general game playing to optimization and planning. Any domain that can be modeled as a sequence of decisions is fair game.
• Performance: Empirically, MCTS has achieved state-of-the-art, often superhuman results on a wide range of challenging problems. It has a strong track record of success.
• Anytime: The algorithm can be stopped at any time and return the current best decision. More computing time or power leads to better results.

To quantify the difference, consider the game of Go. The number of possible board configurations is around 10^170, compared to "only" 10^47 for chess. The average branching factor at each turn is around 250, compared to about 35 for chess. Searching the full game tree with minimax is simply infeasible.

MCTS deals with this intractable complexity by focusing its search on the most promising paths informed by random simulations. It builds up a tree of the most likely or important states and makes decisions based on the approximate values of each state.

Applications and Variants

The success of AlphaGo was a watershed moment for MCTS, but the algorithm has been widely studied and applied long before and since. Originally developed for games like Go, MCTS has been successfully applied to a wide variety of domains beyond classic games.

Some key applications areas include:

• General game playing: Algorithms that can learn to play many different games with no game-specific knowledge. A key benchmark for AI.
• Optimization and planning: Problems like scheduling, resource allocation, and constraint satisfaction with massive combinatorial search spaces.
• Robotics and control: Autonomous helicopters, Mars rovers, warehouse robots, etc. that must make complex sequences of decisions in uncertain environments.
• Theoretical computer science: Analyzing the computational complexity of other algorithms, generating hard instances for combinatorial problems, etc.

There have also been many variations and enhancements to the core MCTS algorithm over the years. Some notable ones:

• UCT: A popular tree policy that applies UCB1 to trees. Balances exploration and exploitation.
• RAVE: Rapid Action Value Estimation. Generalize value estimates across subtrees to speed up learning.
• MCTS-Solver: Extend MCTS to prove the game-theoretic value of a state and solve games.
• PGMCTS: Policy gradient MCTS combines MCTS with neural network policies and value functions.
• AlphaZero/MuZero: Combine MCTS with deep reinforcement learning to master Go, chess, shogi, and Atari games with no human knowledge.

Research on MCTS is very active, with major conferences like AAAI, IJCAI, ICML, and NeurIPS publishing new work every year. A quick search on Google Scholar for "Monte Carlo tree search" turns up over 10,000 papers!

Under the Hood of AlphaGo

No discussion of MCTS would be complete without diving into the details of AlphaGo, the program that put the algorithm in the spotlight. While vanilla MCTS was a key part of AlphaGo‘s success, the program used a number of enhancements to achieve its incredible performance.

Specifically, AlphaGo used two deep neural networks to guide the MCTS search: a policy network and a value network. The policy network predicts the probability of making each move given the current board state. The value network estimates the probability of winning from a given state.

During the MCTS search, AlphaGo used the policy network to bias the selection step towards more promising moves, and the value network to better estimate the value of leaf nodes during the backpropagation step. Combining MCTS with deep learning allowed AlphaGo to achieve a level of play far beyond traditional MCTS programs.

To train these neural networks, AlphaGo used a pipeline consisting of three main stages:

1. Supervised learning: The policy network is initialized by training on a dataset of 30 million positions from human games. It learns a general strategy mimicking human play.
2. Reinforcement learning: The policy network is refined by playing against different versions of itself and tuning the weights to maximize winning probability.
3. MCTS: The final policy and value networks are used to guide the MCTS search in games against other opponents.

Through this training process, AlphaGo effectively learned its own unique playstyle that broke away from traditional human strategies. The version that beat Lee Sedol, AlphaGo Lee, used around 1200 CPUs and 200 GPUs to power its MCTS search and neural networks.

After the historic match, DeepMind continued to refine the AlphaGo algorithm, culminating in AlphaZero. This version mastered Go, chess, and shogi using pure reinforcement learning, with no human data. At each step, AlphaZero combined MCTS with neural networks to select its move, and updated the neural networks to make its search even stronger.

The results spoke for themselves. AlphaZero crushed world-champion programs like Stockfish in chess and Elmo in shogi after just a few hours of training. In Go, AlphaZero beat AlphaGo Lee 100-0 with just a fraction of the computing power.

Conclusion

From board games to robotics, Monte Carlo Tree Search has proven to be an incredibly powerful tool for optimal decision making under uncertainty. By combining precision tree search with the generality of random sampling, MCTS achieves state-of-the-art performance on problems that were previously intractable.

The success of AlphaGo was a landmark achievement for artificial intelligence, and kickstarted a new wave of research and excitement around MCTS and neural networks. Today, MCTS is being used to tackle all kinds of complex real-world problems, from self-driving cars to drug discovery.

As an expert in AI and machine learning, I believe we‘ve only scratched the surface of what‘s possible with MCTS. As we continue to refine the algorithm, combine it with other techniques like deep learning, and scale it up with more computing power, I expect to see even more impressive results in the future.

The core idea of learning to make good decisions by trial-and-error and building on past experience is a fundamentally powerful one. It will be exciting to see how MCTS and its descendants continue to push the boundaries of what‘s possible with AI. One thing is for sure – AlphaGo was just the beginning!

References

• Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., … & Colton, S. (2012). A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games, 4(1), 1-43.
• Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., … & Dieleman, S. (2016). Mastering the game of Go with deep neural networks and tree search. nature, 529(7587), 484-489.
• Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., … & Chen, Y. (2017). Mastering the game of go without human knowledge. nature, 550(7676), 354-359.