Chrysolites Tech Academy

Applied Deep Learning · Course book

Chapter 4: Learning Games by Self-Play

Pairs with Lesson 4: AlphaZero from Scratch

AlphaZero astonished the world by learning to play board games at a superhuman level with no human examples at all: it was given only the rules, and it taught itself by playing millions of games against itself. Remarkably, the core algorithm is compact enough to build from scratch. This chapter explains each of its parts in the order you would build them: a game to play, Monte Carlo tree search for planning ahead, a neural network that judges positions and suggests moves, the combination of the two, the self-play loop that generates training data and the training step that improves the network. It then covers the refinements that make learning reliable, the move from Tic Tac Toe to Connect Four, running many games in parallel and evaluating the result. Every formula is worked through with numbers.

The games and the big picture

The algorithm needs a game with a small, clear interface: the starting state, the legal moves in any state, the state after a move, whether the game has ended, and who won. Tic Tac Toe is the ideal first target. Its 3 × 3 board has at most 39 = 19,683 arrangements of crosses, noughts and blanks, of which only 5,478 can arise in real play, so mistakes are easy to spot. Connect Four, played on a board 7 columns wide and 6 rows high, is a real test: it has about 4.5 trillion reachable positions, far too many to search exhaustively.

A neat trick simplifies the code. Instead of tracking whose turn it is everywhere, the board is always viewed from the perspective of the player about to move: their pieces are +1, the opponent's are −1 and empty squares are 0. After each move the board is multiplied by −1, so the same code works for both players, and a value that is good for one player is simply negated for the other.

AlphaZero then rests on two components that improve each other. A search looks ahead through possible moves and finds better moves than the network would choose alone. A network learns from the results of those searches, which in turn makes future searches stronger. That cycle of planning and learning is the whole idea.

Monte Carlo tree search

Monte Carlo tree search (MCTS) builds a tree of possible futures, one node per position, keeping for each node a visit count n and a total value W, so that its average value is Q = W / n. Each search iteration has four steps. Selection walks down the tree from the root, at each node choosing the child with the best score. Expansion adds a new child when it reaches a node not yet fully explored. Simulation plays random moves from the new position to the end of the game. Backpropagation carries the result back up the path, adding to each node's visits and value, flipping the sign at each level because the players alternate.

The selection score must balance exploitation, choosing moves that have done well, against exploration, trying moves that have been visited little. Classic MCTS uses the upper confidence bound Q + c × √(ln N / n), where N is the parent's visit count. After many iterations, the move from the root with the most visits is played; visit counts are more reliable than average values because they reflect where the search chose to spend its effort.

Why not simply search every possible continuation, as a classic game program might? For Tic Tac Toe that is feasible, but the number of positions grows explosively with each move in larger games, and a full search of Connect Four or chess is far beyond any computer. MCTS avoids this by growing the tree unevenly, spending most of its iterations on the lines of play that look most promising and only occasionally checking the others. Its strength grows smoothly with the number of iterations, so the same code can play quickly and weakly or slowly and strongly.

The network and AlphaMCTS

Random simulations are slow and noisy, so AlphaZero replaces them with a neural network. The input is the board encoded as three planes, one marking the current player's pieces, one the opponent's and one the empty squares. A stack of residual blocks, convolutional layers with batch normalisation and shortcut connections, extracts features. Two heads sit on top. The policy head outputs a probability for each possible move, 9 for Tic Tac Toe and 7 for Connect Four, one per column. The value head outputs a single number between −1 and 1 through tanh, estimating who will win from this position.

AlphaMCTS combines them. There is no random simulation: when the search reaches a new node, it asks the network, uses the value as the result to backpropagate, and stores the policy probabilities P as prior beliefs about each child. Illegal moves are masked out and the remaining probabilities rescaled to sum to 1. Selection uses a modified score that gives weight to the network's prior: Q + c × P × √N / (1 + n).

Worked example. A root node has been visited 10 times, and c = 2, so c × √10 = 6.325. Child A has n = 4, Q = 0.5 and prior P = 0.3: its score is 0.5 + 6.325 × 0.3 / 5 = 0.879. Child B has n = 5, Q = 0.2 and P = 0.2: 0.2 + 6.325 × 0.2 / 6 = 0.411. Child C has never been visited, n = 0, with Q = 0 and P = 0.5: 0 + 6.325 × 0.5 / 1 = 3.162. The search selects C, because the network rates it highly and it is unexplored. As C collects visits, its bonus shrinks, and it will keep being chosen only if its value holds up.

Self-play and training

Self-play generates the training data. The current network plays games against itself, running a full AlphaMCTS search before every move. At each position it records three things: the board, the search's move probabilities π, obtained by dividing each child's visit count by the total, and, once the game ends, the outcome z from that position's player's point of view, +1 for a win, −1 for a loss and 0 for a draw.

Training then fits the network to this data with a two-part loss. The value head should predict the outcome, measured by (z − v)2. The policy head should match the search's probabilities, measured by the cross-entropy −Σ π ln p. A small weight decay is added to discourage large weights.

PartTargetPredictionLoss
Valuez = 1 (the player won)v = 0.6(1 − 0.6)2 = 0.160
Policyπ = (0.7, 0.2, 0.1)p = (0.5, 0.3, 0.2)0.7 × 0.693 + 0.2 × 1.204 + 0.1 × 1.609 = 0.887
Total––0.160 + 0.887 = 1.047, plus weight decay

The full loop alternates: play a batch of self-play games with the current network, train on the collected positions for a few epochs, save the model, and repeat. Because search is stronger than the raw network, training the policy towards search results is a form of self-improvement; and because the value head learns from real outcomes, its judgements become more accurate, which makes the next round of searches better still.

Tweaks, scaling up and evaluation

A few refinements make learning much more reliable. Temperature controls how moves are picked during self-play: probabilities are taken proportional to visit counts raised to the power 1/τ. A high temperature spreads choices, adding variety to the games; a low one plays almost always the most-visited move.

0.470.330.190.600.300.100.780.200.02 τ = 2τ = 1τ = 0.5 00.51 bars in each group: moves visited 60, 30 and 10 times
Figure 4.1 — The same visit counts turned into move probabilities at three temperatures. Lower temperatures concentrate play on the most-visited move.

A second tweak adds Dirichlet noise to the network's priors at the root of each search, mixing, for example, 75 percent of the network's policy with 25 percent random noise, so that self-play keeps trying moves the network currently undervalues. Moving from Tic Tac Toe to Connect Four then needs no change to the algorithm, only a new game class, a larger network and more searches per move, which shows how general the method is.

Self-play is slow because each move requires many network calls on one board at a time, which leaves a GPU mostly idle. AlphaParallel plays many games at once and, at each search step, gathers the positions from all games into a single batch for one network call, which keeps the GPU busy and speeds up data generation many times over. Finally, evaluation tests the trained model by playing against it, against earlier versions of itself and against an established reference opponent. A strong Tic Tac Toe model never loses, and against perfect play the result is always a draw.

Check your understanding

  1. Compute the score of a child with n = 9, Q = 0.4 and P = 0.25 under a parent visited 16 times, with c = 2.
  2. Why is the board always shown from the current player's perspective, and what must happen to values during backpropagation?
  3. Visit counts at the root are 50, 30, 15 and 5. Give the training policy π, and the move probabilities at a temperature of 0.5.
  4. Compute the AlphaZero loss, ignoring weight decay, for z = −1, v = −0.5, π = (0.5, 0.5) and p = (0.6, 0.4).
  5. Explain the purpose of Dirichlet noise at the root and what might go wrong without it.
  6. Describe how playing many games in parallel makes better use of a GPU.

Install Chrysolites Tech Academy

Android / Chrome / Edge: open the browser menu and choose Install app or Add to Home screen.

iPhone / iPad (Safari): tap the Share button, then Add to Home Screen.