Self-Play and the Arms Race

Self-play is training against the only opponent who improves exactly as fast as you do.

That is its appeal and its trap. An agent that plays itself never runs out of opponents at its level, and never needs human games to learn from. It can also chase its own tail forever, beating last week's version while forgetting how to beat the version from the week before. This note starts from the smallest game where that happens, fixes it with averaging, scales the fix to populations, and ends with a runnable miniature of the AlphaZero loop, with measured numbers from each step.

The smallest arms race#

Rock-paper-scissors as a payoff matrix for the row player:

import numpy as np
 
# Row player's payoff. Order: rock, paper, scissors.
A = np.array([[ 0, -1,  1],
              [ 1,  0, -1],
              [-1,  1,  0]], dtype=float)
 
def best_response(opp_mix):
    """Pure strategy that maximises expected payoff against a mixed opponent."""
    br = np.zeros(3); br[np.argmax(A @ opp_mix)] = 1.0
    return br
 
def exploitability(mix):
    """How much a best responder wins against `mix`. Zero only at Nash."""
    return float(np.max(A @ mix))

Exploitability is the number that matters in a zero-sum game. It asks: if an adversary knew this strategy exactly, how much would it win per game? The Nash equilibrium, uniform play, has exploitability 0. Any pure strategy has exploitability 1.

Step 1: naive self-play cycles#

The naive loop trains each new generation to beat the previous one. In the limit of perfect training, that is a best response to the last generation:

pi = np.array([1.0, 0, 0])   # start: always rock
for gen in range(7):
    pi = best_response(pi)

Output, generation by generation:

naive self-play: R -> P -> S -> R -> P -> S -> R  exploitability stays 1.0

Every generation beats its predecessor by the maximum possible margin. Every generation is also maximally exploitable. Progress measured against the last opponent is real; progress measured against the space of opponents is zero. Real games have this structure buried inside them: a strategy that beats rushes loses to economy, which loses to rushes. Naive self-play walks around those cycles and calls it learning.

The bottleneck is memory. The best response to one opponent forgets everything that beat the others.

Step 2: fictitious play#

Brown's fictitious play (1951) changes one thing: respond to the average of every past strategy, not the last one.

counts = np.array([1.0, 0, 0])
for t in range(1, 100001):
    avg = counts / counts.sum()
    counts += best_response(avg)

Each step is still a pure best response, but the average it reacts to moves slowly, and in two-player zero-sum games the time-average provably converges to a Nash equilibrium (Robinson, 1951). Measured:

Two facts are worth noticing. The current best response is still a pure strategy at every step; it is the average that converges. And convergence is slow: in this run, exploitability falls about seventeen-fold for each hundred-fold increase in iterations. Fictitious play is a proof that averaging fixes cycling, not a recipe to run on a large game directly.

Step 3: populations and leagues#

In a large game, "the average of all past strategies" becomes "a population of past checkpoints", and "best response" becomes "train a new network against opponents sampled from that population".

def league_step(population, train_against, sample_weights):
    """One generation: train a new agent against a mixture of the population, then keep it."""
    opponents = np.random.choice(len(population), size=64, p=sample_weights(population))
    new_agent = train_against([population[i] for i in opponents])
    population.append(new_agent)
    return population

All the design lives in sample_weights.

AlphaStar (Vinyals et al., 2019) added a further role: exploiter agents whose only job is to find weaknesses in the main agents, without themselves needing to be robust. Their wins become training signal for the main agents. That is the arms race made explicit and kept under control: the population remembers, the exploiters probe, and the main agents are measured against all of them.

Step 4: the AlphaZero loop#

AlphaZero (Silver et al., 2017, arXiv:1712.01815) is self-play with one more ingredient: search as a policy-improvement operator. The loop is:

1. Act with MCTS guided by a network $f_\theta(s) = (p, v)$.
2. Record each position $s$, the search's visit distribution $\pi$, and the final result $z$.
3. Train the network so $p \to \pi$ and $v \to z$.
4. Repeat. The improved network makes the next search stronger.

The search uses the network in two places. Its prior $p$ steers selection through the PUCT rule:

and its value $v$ replaces the random rollout at the leaf. The loss is $(z - v)^2 - \pi^\top \log p$ plus weight decay.

Why does this not cycle like naive self-play? Because the training target is not "beat the last opponent". It is "match what search found", and search with a fixed network is already a stronger policy than the network alone. Each iteration distils a bit of lookahead into the network. The network does not need to be a neural network for the loop to work, which makes it possible to run a miniature in a few seconds.

import math, random
import numpy as np
from mcts import TicTacToe, random_player   # from the MCTS-from-scratch post
 
class TableNet:
    """Stand-in for the network: a lookup table of (policy, value) per board."""
    def __init__(self):
        self.P, self.V = {}, {}
    def predict(self, s):
        key = (s.board, s.to_move)
        if key not in self.P:
            p = np.zeros(9); p[s.moves()] = 1.0
            self.P[key], self.V[key] = p / p.sum(), 0.0
        return self.P[key], self.V[key]
    def train(self, data, lr=0.3):
        for s, pi, z in data:
            p, v = self.predict(s); key = (s.board, s.to_move)
            self.P[key] = (1 - lr) * p + lr * pi          # policy toward MCTS visits
            self.V[key] = (1 - lr) * v + lr * z           # value toward game outcome
    def copy(self):
        n = TableNet(); n.P = {k: v.copy() for k, v in self.P.items()}; n.V = dict(self.V); return n
 
def terminal_value(s):
    w = s.winner()
    return 0.0 if w == -1 else (1.0 if w == s.to_move else -1.0)
 
def puct_search(root, net, sims=50, c=1.5):
    """MCTS with a learned prior and value; no random rollouts."""
    N, W, P = {}, {}, {}
    def visit(s):                                         # returns value for the parent's mover
        if s.winner() != 0:
            return -terminal_value(s)
        key = (s.board, s.to_move)
        if key not in P:                                  # leaf: ask the network
            p, v = net.predict(s)
            P[key], N[key], W[key] = p, np.zeros(9), np.zeros(9)
            return -v
        n, w, p = N[key], W[key], P[key]
        q = np.where(n > 0, w / np.maximum(n, 1), 0.0)
        u = q + c * p * math.sqrt(n.sum() + 1) / (1 + n)
        legal = s.moves()
        a = legal[int(np.argmax(u[legal]))]
        v = visit(s.play(a))
        n[a] += 1; w[a] += v
        return -v
    for _ in range(sims):
        visit(root)
    counts = N[(root.board, root.to_move)]
    return counts / counts.sum()
 
def self_play_game(net, sims=50, temp_moves=3):
    s, history = TicTacToe(), []
    while s.winner() == 0:
        pi = puct_search(s, net, sims)
        a = np.random.choice(9, p=pi) if len(history) < temp_moves else int(np.argmax(pi))
        history.append((s, pi)); s = s.play(a)
    w = s.winner()
    return [(st, pi, 0.0 if w == -1 else (1.0 if w == st.to_move else -1.0)) for st, pi in history]

The first temp_moves moves are sampled from $\pi$ rather than taken greedily. Without that, every self-play game from the same network is identical, and the training data is one game repeated.

Step 5: tracking progress with Elo#

Self-play needs a scoreboard that does not move with the player. Elo turns a head-to-head score $s$ into a rating gap via the logistic model $s = 1 / (1 + 10^{-\Delta/400})$:

AlphaGo Zero used a gate: a candidate replaced the champion only if it scored above 55%. AlphaZero dropped the gate and updated one network continuously. The miniature keeps the gate, because it makes the dynamics visible:

def az_player(net, sims=50):
    return lambda s: int(np.argmax(puct_search(s, net, sims)))
 
def score(p1, p2, games=40, opening=2):
    """p1's mean score, alternating colours, after `opening` random moves."""
    total = 0.0
    for g in range(games):
        a, b = (p1, p2) if g % 2 == 0 else (p2, p1)
        s = TicTacToe()
        for _ in range(opening):
            s = s.play(random.choice(s.moves()))
        while s.winner() == 0:
            s = s.play((a if s.to_move == 1 else b)(s))
        w, me = s.winner(), 1 if g % 2 == 0 else 2
        total += 0.5 if w == -1 else (1.0 if w == me else 0.0)
    return total / games
 
def elo_gap(p):
    p = min(max(p, 0.01), 0.99)
    return 400 * math.log10(p / (1 - p))
 
best, elo = TableNet(), 0.0
for gen in range(1, 11):
    cand = best.copy()
    for _ in range(50):
        cand.train(self_play_game(cand))                  # self-play, then fit
    s = score(az_player(cand), az_player(best), 100)      # 100 games, 2 random opening moves
    if s > 0.55:
        elo += elo_gap(s); best = cand

The first run of this loop printed a candidate score of exactly 0.500 in every generation after the first. The players are deterministic, so 40 evaluation games were two games, each replayed twenty times. Evaluation needs diversity just as training does; the fix was two random opening moves per evaluation game. With that fix, ten generations (selected rows; the omitted ones are also rejections):

An untrained table with 50 PUCT simulations already scores 0.918 against random; after one generation, the champion as X beat random in 99 of 100 games, and as O lost 7 of 100. After generation 1 the gate rejects everything. That is the honest shape of the result: tic-tac-toe is too small for the loop to have anywhere to climb, so the candidate-versus-champion score hovers around 0.5 and the gate does its job by refusing noise. The "champion vs random" column wobbles between 0.925 and 0.963 with no change in the champion at all, a reminder that 200 games against a random opponent carry about $\pm 0.02$ of noise.

What to measure in a self-play run#

1. Exploitability or a fixed-opponent ladder, not only the score against the previous generation. Score against the last generation is the quantity naive self-play maximises while cycling.
2. Win rate against a frozen set of old checkpoints. If it ever drops for an old opponent, the agent is forgetting, and the population needs that opponent back.
3. Policy entropy at the root of self-play games. Collapse to one opening means the data has stopped exploring.
4. Value calibration: bucket positions by predicted $v$ and compare to the actual outcome.
5. Search gain: network alone versus network plus MCTS. When the gap closes, the network has absorbed what this search budget can teach, and the budget or the game must grow.
6. Evaluation diversity: random openings or sampled moves in evaluation games, and enough games that the standard error is below the gate margin. A gate at 55% with 40 games is mostly testing luck.