The Science behind AlphaGo and AlphaGo Zero
A conceptual and friendly explanation
Background
Before I watched the documentary on AlphaGo, a Go-playing computer program developed by Google's research lab DeepMind, I was not aware of the fact that prior to AlphaGo, computer programs had not been able to compete against human players at a professional level. I had the naive assumption that computer programs were able to simply simulate every possible sequence of moves ("exhaustive search") from a particular state of the game and select the move with the best outcomes. It turns out that this was not feasible even for computers due to the astronomical number of possible scenarios.
Fascinated by the documentary which only briefly touched on the science behind AlphaGo, I turned to the research papers¹ ² published by DeepMind to understand the machine learning techniques used to develop AlphaGo (as well as AlphaGo Zero, a version of AlphaGo with better performance). The research papers were well-written, but may have been slightly too technical for someone without prior knowledge of Deep Reinforcement Learning and Monte Carlo Tree Search. Nontheless, this shouldn't stop anyone from grasping the interesting concepts and observations introduced by these papers, as it was widely accepted that AlphaGo and AlphaGo Zero represented ground-breaking machine learning applications.
This article is written with an aim to explain the science behind AlphaGo and AlphaGo Zero in a language understood by people who are interested to understand how they learned to play the game of Go at a superhuman level, but may be deterred by terminologies such as Reinforcement Learning or Monte Carlo Tree Search.
Simple Game Rule, Complex Game Play
The rule of Go is relatively simply. The game is played on a 19 by 19 grid on a board, where two Go players take turns to place stones on the intersections of the grid. A player's stones can be captured and removed from the board if surrounded by opponent's stones. The end goal for the players is to surround as much territory as possible on the game board with their stones.
Yet given the simple rules, humans have developed complex strategies over the years with respect to making effective Go moves to surround territories. Humans make judgements such as evalutating the trade-off between forming solid territories now and forming patterns of stones which help build influence to acquire territories later in the game, identifying ways to connect different groups of stones and prevent them from being captured, and etc.
Mathematically, this number of possible sequence of moves ("search space") is approximately 250¹⁵⁰. This is because to determine the winner in a game of Go, approximately 150 rounds¹ are played between players, with on average approximately 250 legal positions¹ for each move in a given round. This number has 360 digits based on the Python code below.
The problem statement effectively comes down to finding ways to reduce the search space, which DeepMind achieved with following:
Training a Policy to guide the sequence of moves worth exploring from the current state of the game. This reduces the search space for the (250) number of legal moves.
Training a Predictor of the winner of the game by a given board position. This reduces the search space for the (150) number of rounds.
The Policy
As mentioned previously, a Policy is needed to guide the computer program to search the sequence of moves worth exploring, so that it mostly simulates the game in those sequences. For AlphaGo, this Policy was trained by observing how professional players play based on 30 million games from the KGS Go Server. Essentially, this Policy ("Policy A") allowed AlphaGo to mimic human professional plays.
The output of Policy A is a probability distribution of plausible moves. To explain this using a simple example, assume we are making the next move with the white stone in the game board below, Policy A may suggest two possible moves, move 1 and 2, with a probability of 60% and 40% respectively. The 60% and 40% would have been based on the history of human professional gameplays, whereby given the current state of the game (i.e. the board with the one black stone), human professional players have made move 1 60 out of 100 times (and move 2 40 out of 100 times).
However, by intuition, mimicking moves, even from professional players, won't necessarily make a computer program excel at the game of Go. Policy A was then refined by self-play by two computer programs (initially) guided by Policy A against each other until a winner is determined. Policy A will then be updated to reflect the outcome of this game, to a better version of Policy A.
One may question how this improves the performance of the Policy. Using the same example as above, computer program A may choose to make move 1, whereas computer program B may choose the same move, or choose to explore move 2, as Policy A should initially guide the computer program to make move 1 60 out of 100 times and move 2 40 out of 100 times. With this happening at every turn of the game, it may prove that move 2 (or more generally, moves not necessarily attracing the highest probabilities under Policy A) would ultimately lead to a win for computer program B, in which case, the probabilities for the two moves may then be updated. In this instance, the 60% probability for making move 1 is reduced and concurrently the 40% for making move 2 is increased given the outcome of the game. The same process is repeated iteratively for millions of games of self-plays, until a close-to-optimal Policy B is formed. In theory, the higher the 'learned' probability is distributed to a move by Policy B, the better the game outcome the move leads to.
Taking a step back, I make the observation that self-play implicitly awards discovery beyond moves made by human professional players, which in part contributed to AlphaGo's success.
The Predictor
The Predictor outputs a single value indicating how likely the player is going to win given a state of the game (i.e. the current board position).
The data for training the Predictor is gathered again through self-plays, this time between two computer programs both guided by Policy B. In a particular game of self-play, numerous board positions and the outcome of the game (i.e. a win or a loss) are collected. With enough games of self-plays, the Predictor can be trained to inform the probability of the player in a certain board position winning the game with good accuracy. That is, it informs how favourable the current state (and subsequent states) of the game is for the player making the next move.
Making a move - AlphaGo
To recap, we have trained the following so far:
Policy A which informs the best moves based on human professional gameplays
Policy B which informs the best moves based on self-plays initiated by Policy A
Predictor which informs the likelihood of the player winning based on the current state of the game
To select the next move, AlphaGo performs N simulations from the current state of the game. To give a quick introduction to simulations, in my line of work, simulation is useful in understanding not only the average outcome of a particular event (e.g. average claims costs), but also the range of possible outcomes (e.g. the cost of a adverse claims event which happens once every 200 years, which can be sourced from the simulation returning the highest claims amount out of 200 simulations). In the context of Go, sequences of moves are simulated assuming you and your opponent would choose the best moves available until the end of the game. In addition, simulation adds randomness in choosing a sequence of moves, which is important as we do want to explore moves which may not have been seen or guided by the Policy.
For AlphaGo, in a particular simulation n, the sequence of move to be simulated is primarily regulated by:
Number of times a particular sequence has been visited
Prior experience of winning for the particular sequence of moves
I'll explain these two bullet points using a simple example. Let's assume that in a previous simulation n -1, guided by the Policy, the sequence of move 1 followed by move 4 (indicated by the solid blue arrows in the image below) was selected, and based on the state of the game at move 4, the Predictor informs a win. That is, this particular simulated sequence led to a win.
For the current simulation, AlphaGo recognises that the sequence of move 1 followed by move 4 has been visited, it will then drive the simulation to be more likely to take other sequences not previously visited, such as move 2, or move 1 followed by move 3. This was done to encourage exploration.
Separately, as the sequence of move 1 followed by move 4 led to a win in the previous simulation, it will also drive the simulation to take this particular sequence in the current simulation (and vice versa for a loss). This is sometimes termed exploitation.
There are a number of interesting consequences of the above which I would like to bring to the fore:
At the beginning of a game when the a player has much more options as to where to place the next stone, AlphaGo encourages the search to explore as prior experience in winning is uncertain due to the vast search space for the next best moves, even when guided by a Policy.
In contrast, when the board is reasonably filled with stones, prior experience in winning, from either the Policy or the Predictor, become more influential as AlphaGo pushes for sequence of moves which lead to a state, or a board position, with the highest certainty of winning. This exploits prior experience gained from human professionals as well as self-plays.
I find it interesting that exploration in a simulation is typically guided by Policy A as opposed to Policy B, as human intelligence is considered more diverse which cannot be entirely learned by machines. The primary use of Policy B for AlphaGo is to instead train the Predictor.
After N simulations, AlpohaGo selects the sequence of move (although only the first sequence is relevant) with the highest number of visits. By default this should be the move that strikes the right balance between exploration and exploitation.
Making a move - AlphaGo Zero
In short, AlphaGo Zero is a better version of AlphaGo, with the "Zero" emphasising the de-coupling from human professional gameplays.
Whilst the overall (training) structure of AlphaGo Zero is largely consistent with AlphaGo, they key differences are:
The Policy and Predictor from AlphaGo Zero were entirely trained by self-plays. That is, human input such as human professional gameplays were not used in training AlphaGo Zero.
A number of "hand-crafted" features were used by the AlphaGo architecture. Examples are number of empty adjacent points and number of stones captured. These are removed in AlphaGo Zero which uses only the raw board positions as input.
Alpha Go Zero combines a large part of the Policy and Predictor models. That is, they were trained together.
The number of rounds in a simulation is further reduced by the Predictor trained under AlphaGo Zero. This in part made training faster for AlphaGo Zero.
Overall, AlphaGo Zero is a more general application of machine learning with simpler structure and less human interactions compared to AlphaGo. DeepMind recognised that human knowledge in the game of Go can be learned (and exceeded) by self-plays alone, initiated by a random Policy. In fact, it took AlphaGo Zero merely 40 hours of training to exceed the performance of AlphaGo.
I found this fascinating, but intuitive at the same time. Let's assume there is always an optimal Policy which guides a player to win with certainty. Given the current Policy we have (which may well be a random under-performing Policy), through iterations of self-plays, the current Policy should gradually converge to the optimal Policy over time.
To demonstrate using another simple example, in a game state as shown in the image below, let's assume the optimal Policy has a probability distribution of (100%, 0%), that is, making move 1 definitely leads to a win. In addition, let's assume for simplicity that the game ends in one step from the current state. To learn the optimal Policy, if we start with a random Policy of (50%, 50%) for move 1 and move 2 respectively, through interactions of self-plays, the random Policy will always converge to the optimal Policy, as at each game of self-play, the Policy will be updated to increase the probability for move 1 as move 1 is played and vice versa for move 2.
Under AlphaGo, the random Policy we start the self-play with of (50%, 50%) above may have been closer to the optimal Policy (e.g. (90%, 10%)) under Policy A, as it was formed based on human professional gameplays. However, AlphaGo Zero demonstrated that regardless of how we initiate the Policy, the machine can always learn to improve the Policy iteratively by playing against the previous version of the Policy and ultimately find a close proxy to the optimal Policy.
The Learning of Human Intuitions
As shown in DeepMind's research paper², as AlphaGo Zero was being trained, it learned to play a number "common corner sequences" which are strategies developed and often played by humans, without the need to 'observe' how human professionals play as AlphaGo did. What's fascinating is that in the hours after these strategies were discovered, some were disregarded as it found new and supposedly better variations.
In addition, it was shown that in the early hours of training, AlphaGo Zero focussed on trying to immediately capture opponent's stones just like a human beginner. This is compared to exhibiting more balanced strategies and mastering the fundamentals of the game as the self-plays continued.
Summary
In this article I explain how AlphaGo and AlphaGo Zero were trained to select the best moves using a number of simple examples. At a high level, AlphaGo and AlphaGo Zero succeeded in achieving superhuman performance by effectively reducing both the breath and depth of the search space for the next best moves.
There are a number of thought-provoking observations in how AlphaGo and AlphaGo Zero operate which I would like to highlight again:
Although not relied upon by AlphaGo Zero, human knowledge (i.e. Policy A, in despite of Policy B) were given more influence in searching for the next best move by AlphaGo as humans tend to select "a diverse beam of promising moves", especially at the early stages of the game where players tend to explore more.
The move selections behind Alpha Go and AlphaGo Zero are guided by a Policy, but at the same time encourage exploration against the advice of the Policy. At a philosophical level, it teaches us that some times we shouldn't be afraid to take the path that gets us out of our comfort zone, which may turn out to be more rewarding.
Simulating or sampling sequence of moves helped shape the optimal Policy. This is not dissimilar to the the advantage the Random Forest algorithm has over a single Decision Tree. You never know what you may find travelling down the unknown path!
Here are some of my self-reflections inspired by the above observations.
Perfection vs. Practicality
Image that we do have a computer program which can perform a exhaustive search for the best moves and plays the perfect move at each turn. Is this necessary?
In many commercial applications, the marginal benefit of achieving 100% accuracy (compared to, say, 95% accuracy) for certain tasks may not outweigh the cost of diminishing returns. For example, it may take 10 times as long to train a model for a 0.05, or 5% improvement in accuracy. Another example is whether defeating Lee Sedol 4–1 or 5–0 makes a differece in determining the winner in a professional tournament.
Guidance vs. Instructions
A Policy, or instructions for performing a certain task, may be a double-edge sword, in a sense that it provides guidance as well as introduces limitations for the user. This was demonstrated by AlphaGo Zero achieving better performance by removing prior human knowledge which was thought to be valuable for training AlphaGo.
As a people manager, I sometimes would have an subjective view as to what's the best way to complete a task based on my own experience, and tended to provide and enforce such instructions to my direct reports based on this view. Instructions may be more process-driven, whilst the success of AlphaGo and AlphaGo Zero taught me that it's more effective to lead by focusing on the end goal (or reward in machine learning language), allowing people to 'search' for and learn the best ways to complete the task.
Exploration vs. Exploitation
The science behind AlphaGo and AlphaGo Zero reminds me of what happens in life. Don't we all tend to explore to gain experience which we exploit to make decisions later on.
At last, for readers interested to go a bit deeper into the technical aspects of AlphaGo and AlphaGo Zero, I recommend reading this article.
Reference
[1] Silver, D., Huang, A., Maddison, C. et al. Mastering the game of Go with deep neural networks and tree search. Nature 529, 484–489 (2016), https://storage.googleapis.com/deepmindmedia/alphago/AlphaGoNaturePaper.pdf, accessed January 25, 2022
[2] Silver, D., Schrittwieser, J., Simonyan, K. et al. Mastering the game of Go without human knowledge. Nature 550, 354–359 (2017). https://doi.org/10.1038/nature24270, accessed January 26, 2022
As I ride the AI/ML wave, I enjoy writing and sharing step-by-step guides and how-to tutorials in a comprehensive language with ready-to-run codes. If you would like to access all my articles (and articles from other practitioners/writers on Medium), you can sign up using the link here!
