Self-Play and Fictitious Play

Why Does This Exist?

Two-player zero-sum games have no fixed curriculum. A hand-built opponent that challenges you at week one is trivial by week ten, and hiring humans for every training step does not scale. Markov games write the rules for these worlds, and multi-agent RL trains the teams, but neither says who you should practice against.

Self-play answers with yourself:

$\pi_{t+1} \approx \arg\max_{\pi} \; \mathbb{E}\left[ R(\pi, \pi_t) \right]$

As you improve, your opponent improves at the same pace, so the difficulty calibrates itself. Chess, Go, and StarCraft systems all lean on this loop.

Naive self-play answers only the latest checkpoint $\pi_t$, and that breaks in games with circular strengths. Rock beats Scissors, Scissors beats Paper, Paper beats Rock, so no single style stays best. The agent learns Paper to beat Rock, meets Paper, switches to Scissors, meets Scissors, switches back to Rock, and chases its own tail while forgetting basics. Fictitious play (Brown, 1951) fixes the loop: answer the empirical average of all past opponents $\bar{\pi}_t$, not the latest one. The average moves slowly, gimmicks that beat only yesterday fail against history, and time-averaged play converges to a minimax Nash equilibrium in finite zero-sum games (Robinson, 1951). Neural fictitious self-play and league training scale the same idea to poker and StarCraft. For the cooperative side of the same multi-agent world see cooperative versus competitive environments.

Think of It Like This

How It Actually Works

Two players share a payoff matrix $M$ where rows are your actions, columns are the opponent actions, and entries are your reward. The opponent gets $-M$ in a zero-sum game. Let $\bar{\pi}_t$ be the empirical frequency of opponent actions through round $t$. The fictitious play reply is a best response to that average:

$a_{t+1} \in \arg\max_a \; (M \bar{\pi}_t)_a$

In words: weight each column by how often the opponent played it, score every row, and play the highest-scoring row. Each round adds one observation, so step sizes shrink like $1/t$ and the average spirals inward instead of jumping.

Why the latest checkpoint spins

Naive self-play sets $\bar{\pi}_t$ to one point: yesterday action only. In rock-paper-scissors the best response to Rock is Paper, to Paper is Scissors, to Scissors is Rock, so play cycles Rock to Paper to Scissors forever. Nothing accumulates, so nothing converges. History averaging fixes exactly this: the average after Rock, Paper, Scissors in equal counts is uniform, whose best responses tie, which stops the chase.

Neural and league versions in one paragraph each

Neural fictitious self-play (Heinrich and Silver, 2016) keeps two networks for large games where counting is impossible: a Q-network that learns the best response to current average behavior, and a supervised average-policy network trained on a reservoir of its own past best responses. The agent mixes between them, exploring with the first and banking stability with the second.

League training and policy-space response oracles keep a population instead of one average: main agents that play the meta-Nash mixture over the pool, plus exploiters whose job is to find holes in the main agent and force the pool to cover them. AlphaStar used this shape for StarCraft. One average blurs incompatible styles; a population keeps them.

Worked example

Rock-paper-scissors with rows and columns ordered Rock, Paper, Scissors:

$M = \begin{pmatrix} 0 & -1 & 1 \\ 1 & 0 & -1 \\ -1 & 1 & 0 \end{pmatrix}$

After 10 rounds the opponent played Rock 5 times, Paper 3 times, Scissors 2 times, so:

$\bar{\pi} = [0.50, 0.30, 0.20]$

Score each reply by $M \bar{\pi}$:

• Rock: $0 \times 0.50 + (-1) \times 0.30 + 1 \times 0.20 = -0.10$.
• Paper: $1 \times 0.50 + 0 \times 0.30 + (-1) \times 0.20 = +0.30$.
• Scissors: $(-1) \times 0.50 + 1 \times 0.30 + 0 \times 0.20 = -0.20$.

Best response is Paper at $+0.30$. Playing Paper adds one more Paper to your own history, which nudges the opponent average toward Scissors next, then yours toward Rock, but each nudge now weighs $1/11$, $1/12$, and so on. By a few thousand rounds both averages sit near $[1/3, 1/3, 1/3]$, the minimax Nash point. Those three payoffs are what the diagram draws.

Code

Scores the worked example and reads off the best response. No sampling, just the matrix product.

1import numpy as np2
3m = np.array([[0.0, -1.0, 1.0], [1.0, 0.0, -1.0], [-1.0, 1.0, 0.0]])4opp = np.array([0.50, 0.30, 0.20])5payoffs = m @ opp6print([f"{v:.2f}" for v in payoffs])7# -> ['-0.10', '0.30', '-0.20']8print(int(np.argmax(payoffs)))9# -> 110print(round(float(np.max(payoffs)), 2))11# -> 0.3

Index 1 is Paper at $+0.30$, matching the hand math. Repeating this reply-against-average loop drives both frequencies toward one third each.

Watch Out For

The Quick Version

• Self-play answers yourself so difficulty tracks skill, with the update $\pi_{t+1} \approx \arg\max_{\pi} \mathbb{E}[R(\pi, \pi_t)]$.
• Answering only the latest checkpoint cycles in non-transitive games: Rock to Paper to Scissors forever.
• Fictitious play answers the empirical average $\bar{\pi}_t$ instead, and the average converges to minimax Nash in finite zero-sum games.
• Against $[0.50, 0.30, 0.20]$, replies score $-0.10$, $+0.30$ and $-0.20$, so Paper is best at $+0.30$.
• Neural versions split best response and average policy into two networks; leagues keep a population plus exploiters.
• Keep history wide or the agent forgets old threats while chasing new ones.

What to Read Next

• Markov Games
• Multi-Agent RL
• Cooperative vs. Competitive Environments