Chapter 13 AlphaGo—Bringing It All Together
This chapter covers Diving into the guiding principles that led
GoBots to play at superhuman strength.
Using tree search, supervised deep learning, and reinforcement learning to build such a
bot.
Implementing your own version of DeepMind's AlphaGo engine
When DeepMind's GoBot AlphaGo played Move 37 of Game 2 against Lee Sedol in 2016, it
took the Go world by storm.
Commentator Michael Redmond, a professional player with nearly a thousand top-level games
under his belt, did a double-take on air.
He even briefly removed the stone from the demo board while looking around as if to confirm
that AlphaGo made the right move.
I still don't really understand the mechanics of it, Redmond told the American Go e-journal
the next day.
Lee, the worldwide dominant player of the past decade, spent twelve minutes studying
the board before responding.
Figure 13.1 displays the legendary move.
Figure 13.1—the legendary shoulder hit that AlphaGo played against Lee Sedol in the second
game of their series.
This move stunned many professional players.
The move defied conventional Go theory.
The diagonal approach, or shoulder hit, is an invitation for the white stone to extend
along the side and make a solid wall.
If the white stone is on the third line and the black stone is on the fourth line, this
is considered a roughly even exchange.
White gets points on the side, while black gets influence toward the center.
But when the white stone is on the fourth line, the wall locks up too much territory.
To any strong Go players who are reading, we apologize for drastically oversimplifying
this.
A fifth-line shoulder hit looks a little amateurish, or at least it did until Professor Alpha took
four out of five games against a legend.
The shoulder hit was the first of many surprises from AlphaGo.
Fast forward a year, and everyone from top pros to casual club players is experimenting
with AlphaGo moves.
In this chapter, you're going to learn how AlphaGo works by implementing all of its building
blocks.
AlphaGo is a clever combination of supervised deep learning from professional Go records,
which you learned about in chapters 5 through 8, deep reinforcement learning with self-play,
covered in chapters 9 through 12, and using these deep networks to improve tree search
in a novel way.
You might be surprised by how much you already know about the ingredients of AlphaGo.
To be more precise, the AlphaGo system we'll be describing in detail works as follows.
You start off by training two deep convolutional neural networks, policy networks, for move
prediction.
One of these network architectures is a bit deeper and produces more accurate results,
whereas the other one is smaller and faster to evaluate.
We'll call them the strong and fast policy networks, respectively.
The strong and fast policy networks use a slightly more sophisticated board encoder
with 48 feature planes.
They also use a deeper architecture than what you've seen in chapters 6 and 7, but other
than that, they should look familiar.
Section 13.1 covers AlphaGo's policy network architectures.
After the first training step of policy networks is complete, you take the strong policy network
as a starting point for self-play in section 13.2.
If you do this with a lot of compute power, this will result in a massive improvement
of your bots.
As a next step, you take the strong self-play network to derive a value network from it
in section 13.3.
This completes the network training stage, and you don't do any deep learning after this
point.
To play a game of Go, you use tree search as a basis for play, but instead of plain
Monte Carlo rollouts as in chapter 4, you use the fast policy network to guide the next
steps.
Also, you balance the output of this tree search algorithm with what your value function
tells you.
We'll tell you all about this innovation in section 13.4.
Performing this whole process from training policies to self-play to running games with
search on a superhuman level requires massive compute resources and time.
Section 13.5 gives you some ideas on what it took to make AlphaGo as strong as it is,
and what to expect from your own experiments.
Figure 13.2 gives an overview of the whole process we just sketched.
Throughout the chapter, we'll zoom into parts of this diagram and provide you with more
details in the respective sections.
Figure 13.2, how to train the three neural networks that power the AlphaGo AI.
Starting with a collection of human game records, you can train two neural networks to predict
the next move, a small, fast network and a large, strong network.
You can then further improve the playing strength of the large network through reinforcement
learning.
The self-play games also provide data to train a value network.
AlphaGo then uses all three networks in a tree search algorithm that can produce incredibly
strong gameplay.
Section 13.1, training deep neural networks for AlphaGo.
In the introduction, you learned that AlphaGo uses three neural networks, two policy networks
and one value network.
Although this may seem like a lot at first, in this section, you'll see that these networks
and the input features that feed into them are conceptually close to each other.
Perhaps the most surprising part about deep learning as used in AlphaGo is how much you
already know about it after completing chapters 5 to 12.
Before we go into details of how these neural networks are built and trained, let's quickly
discuss their role in the AlphaGo system.
Fast policy network.
This go-move prediction network is comparable in size to the networks you trained in chapters
7 and 8.
Its purpose isn't to be the most accurate move predictor, but rather a good predictor
that's really fast at predicting moves.
This network is used in section 13.4 in tree search rollouts, and you've seen in chapter
4 that you need to create a lot of them quickly for tree search to become an option.
We'll put a little less emphasis on this network and focus on the following two.
Strong policy network.
This move prediction network is optimized for accuracy, not speed.
It's a convolutional network that's deeper than its fast version and can be more than
twice as good at predicting go-moves.
As the fast version, this network is trained on human gameplay data, as you did in chapter
7.
After this training step is completed, the strong policy network is used as a starting
point for self-play by using reinforcement learning techniques from chapters 9 and 10.
This step will make this policy network even stronger.
Value network.
The self-play games played by the strong policy network generate a new data set that you can
use to train a value network.
Specifically, you use the outcome of these games and the techniques from chapters 11
and 12 to learn a value function.
This value network will then play an integral role in section 13.4.
Section 13.1.1, network architectures in AlphaGo.
Now that you roughly know what each of the three deep neural networks is used for in
AlphaGo, we can show you how to build these networks in Python using Keras.
Here's a quick description of the network architectures before we show you the code.
If you need a refresher on terminology for convolutional networks, have a look at chapter
7 again.
The strong policy network is a 13-layer convolutional network.
All of these layers produce 19 by 19 filters.
You consistently keep the original board size across the whole network.
For this to work, you need to pad the inputs accordingly, as you did in chapter 7.
The first convolutional layer has a kernel size of 5, and all following layers work with
a kernel size of 3.
The last layer uses softmax activations and has one output filter, and the first 12 layers
use ReLU activations and have 192 output filters each.
The value network is a 16-layer convolutional network, the first 12 of which are exactly
the same as the strong policy network.
Layer 13 is an additional convolutional layer, structurally identical to layers 2 through
12.
Layer 14 is a convolutional layer with kernel size 1 and one output filter.
The network is topped off with two dense layers, one with 256 outputs and ReLU activations,
and a final one with one output and TAN activation.
As you can see, both policy and value networks in AlphaGo are the same kind of deep convolutional
neural network that you already encountered in chapter 6.
The fact that these two networks are so similar allows you to define them in a single Python
function.
Before doing so, we introduce a little shortcut in Keras that shortens the network definition
quite a bit.
Recall from chapter 7 that you can pad input images in Keras with the zero-padding 2D utility
layer.
It's perfectly fine to do so, but you can save some ink in your model definition by
moving the padding into the conv2d layer.
What you want to do in both value and policy networks is to pad the input to each convolutional
layer so that the output filters have the same size as the input, 19 by 19.
For instance, instead of explicitly padding the 19 by 19 input of the first layer to 23
by 23 images so that the following convolutional layer with kernel size 5 produces 19 by 19
output filters, you tell the convolutional layer to retain the input size.
You do this by providing the argument padding equals same to your convolutional layer, which
will take care of the padding for you.
With this neat shortcut in mind, let's define the first 11 layers that AlphaGo's policy
and value networks have in common.
You find this definition in our GitHub repository in alphago.py in the dlgo.networks module.
Listing 13.1, initializing a neural network for both policy and value networks in AlphaGo.
Note that you didn't yet specify the input shape of the first layer.
That's because that shape differs slightly for policy and value networks.
You'll see the difference when we introduce the AlphaGo board encoder in the next section.
To continue the definition of model, you're just one final convolutional layer away from
defining the strong policy network.
Listing 13.2, creating AlphaGo's strong policy network in Keras.
As you can see, you add a final flatten layer to flatten the predictions and ensure consistency
with your previous model definitions from chapters 5 to 8.
If you want to return AlphaGo's value network instead, adding two more conv2d layers, two
dense layers, and one flatten layer to connect them will do the job.
Listing 13.3, building AlphaGo's value network in Keras.
We don't explicitly discuss the architecture of the fast policy network here.
The definition of input features and network architecture of the fast policy is technically
involved and doesn't contribute to a deeper understanding of the AlphaGo system.
For your own experiments, it's perfectly fine to use one of the networks from our dlgo.networks
module, such as small, medium, or large.
The main idea for the fast policy is to have a smaller network than the strong policy that's
quick to evaluate.
We'll guide you through the training process in more detail throughout the next sections.
Section 13.1.2, the AlphaGo board encoder.
Now that you know all about the network architectures used in AlphaGo, let's discuss how to encode
Go board data the AlphaGo way.
You've implemented quite a few board encoders in chapters 6 and 7 already, including OnePlane,
7Plane, or Simple, all of which you stored in the dlgo.encoders module.
The feature planes used in AlphaGo are just a little more sophisticated than what you've
encountered before, but represent a natural continuation of the encoders shown so far.
The AlphaGo board encoder for policy networks has 48 feature planes.
For value networks, you augment these features with one additional plane.
These 48 planes are made up of 11 concepts, some of which you've used before and others
that are new.
We'll discuss each of them in more detail.
In general, AlphaGo makes a bit more use of Go-specific tactical situations than the board
encoder examples we've discussed so far.
A prime example of this is making the concept of ladder captures and escapes, see figure
13.3, part of the feature set.
Figure 13.3.
AlphaGo encoded many Go tactical concepts directly into its feature planes, including
ladders.
In the first example, a white stone has just one liberty, meaning black could capture on
the next turn.
The white player extends the white stone to gain an extra liberty, but black can again
reduce the white stones to one liberty.
This sequence continues until it hits the edge of the board, where white is captured.
On the other hand, if there's a white stone in the path of the ladder, white may be able
to escape capture.
AlphaGo included feature planes that indicated whether a ladder would be successful.
A technique you consistently used in all of your Go board encoders that's also present
in AlphaGo is the use of binary features.
For instance, when capturing liberties, empty adjacent points on the board, you didn't just
use one feature plane with liberty counts for each stone on the board, but chose a binary
representation with planes indicating whether a stone had one, two, three, or more liberties.
In AlphaGo, you see the exact same idea, but with eight feature planes to binarize counts.
In the example of liberties, that means eight planes to indicate one, two, three, four,
five, six, seven, or at least eight liberties for a stone.
The only fundamental difference from what you've seen in chapters six to eight is that
AlphaGo encodes stone color explicitly in separate feature planes.
Recall that in the seven-plane encoder from chapter seven, you had liberty planes for
both black and white stones.
In AlphaGo, you have only one set of features counting liberties.
Additionally, all features are expressed in terms of the player to play next.
For instance, the feature set capture size, counting the number of stones that would be
captured by a move, counts the stones the current player would capture, whatever stone
color this might be.
Table 13.1 summarizes all the features used in AlphaGo.
The first 48 planes are used for policy networks, and the last one only for value networks.
Table 13.1, Feature Planes Used in AlphaGo, View Table Figure.
The implementation of these features can be found in our GitHub repository under alphago.py
in the dlgo.encoders module.
Although implementing each of the feature sets from Table 13.1 isn't difficult, it's
also not particularly interesting when compared to all the exciting parts making up AlphaGo
that still lie ahead of us.
Implementing ladder captures is somewhat tricky, and encoding the number of turns since a move
was played requires modifications to your Go board definition.
So if you're interested in how this can be done, check out our implementation on GitHub.
Let's quickly look at how an AlphaGo encoder can be initialized so you can use it to train
deep neural networks.
You provide a Go board size and a Boolean called UsePlayerPlane that indicates whether
to use the 49th feature plane.
This is shown in the following listing.
Listing 13.4, Signature and Initialization of Your AlphaGo Board Encoder.
Section 13.1.3, Training AlphaGo Style Policy Networks.
Having network architectures and input features ready, the first step of training policy networks
for AlphaGo follows the exact procedure we introduced in Chapter 7, specifying a board
encoder and an agent, loading Go data, and training the agents with this data.
Figure 13.4 illustrates the process.
The fact that you use slightly more elaborate features and networks doesn't change this
one bit.
The supervised training process for AlphaGo's policy networks is exactly the same as the
flow covered in Chapters 6 and 7.
You replay human game records and reproduce the game states.
Each game state is encoded as a tensor.
This diagram shows a tensor with only two planes.
AlphaGo used 48 planes.
The training target is a vector the same size as the board, with a one where the human actually
played.
To initialize and train AlphaGo's strong policy network, you first need to instantiate an
AlphaGo encoder and create two Go data generators for training and testing, just as you did
in Chapter 7.
You find this step on GitHub under Examples, AlphaGo, AlphaGoPolicySL.py.
Listing 13.5, Loading Data for the First Step of Training AlphaGo's Policy Network.
Next, you can load AlphaGo's policy network by using the AlphaGoModel function defined
earlier in this section and compile this Keras model with categorical cross-entropy and stochastic
gradient descent.
We call this model AlphaGoSL policy to signify that it's a policy network trained by supervised
learning, SL.
Listing 13.6, Creating an AlphaGo Policy Network with Keras.
Now all that's left for this first stage of training is to call Fit Generator on this
policy network, using both training and test generators as you did in Chapter 7.
Apart from using a larger network and a more sophisticated encoder, this is precisely what
you did in Chapters 6 to 8.
After training has finished, you can create a deep learning agent for model and encoder
and store it for the next two training phases that we discuss next.
Listing 13.7, Training and Persisting a Policy Network.
For the sake of simplicity, in this chapter you don't need to train fast and strong policy
networks separately, as in the original AlphaGo paper.
Instead of training a smaller and faster second policy network, you can use AlphaGoSL agent
as the fast policy.
In the next section, you'll see how to use this agent as a starting point for reinforcement
learning, which will lead to a stronger policy network.