Many self-play agents only learn stable strategies if they train against a mixture of their own past selves rather than only their latest version. This idea, fictitious play, means best-responding to the historical average of the opponent's strategies instead of its current one. In large games it works best when the past selves are kept literally, as a pool of saved network snapshots (checkpoints) from which opponents are sampled. The cost is that every checkpoint is a full network that must be stored and run during data generation. We propose storing each checkpoint as a shared dense "anchor" network plus a small sparse correction, meaning a weight difference in which most entries are zero. During rollouts, all sampled opponents run through one batched dense pass of the anchor, and each opponent then adds its own sparse correction. The bet is that a pool of $K$ past policies can then cost roughly one dense model plus a few percent per checkpoint, in both memory and wall-clock time, while staying as strategically diverse as the full pool.
The second research direction, the overhead of unstructured sparsity, is what makes this tractable. GPUs usually fail to speed up networks with arbitrarily scattered zeros: the reads are irregular, decoding the index metadata costs time, and general-purpose sparse libraries are built for matrices that are over 99% zero. The best software fixes reorder rows so scattered nonzeros pack onto dense matrix hardware. That reordering is expensive when the sparsity pattern changes every few steps, which is exactly why it is dismissed for dynamic sparse training. A historical checkpoint never changes. Its layout can be computed once, when it enters the pool, and reused for millions of rollouts. Fictitious-play pools may therefore be one of the few settings where unstructured sparsity gets close to its theoretical speedup.
Core Claim
Fictitious-play checkpoint pools are a nearly ideal workload for unstructured sparse execution, for three reasons. The sparse parts are frozen, so preprocessing cost is paid once. They are small relative to a shared dense backbone, so the irregular part of the computation is a minor share of runtime. And they are batched across many opponents, so the dense part runs at full hardware efficiency.
The scientific question is whether compressing checkpoint differences to sparse deltas preserves the property that made explicit pools beat single-network averaging. That property is a faithful mixture of genuinely different past strategies, measured by exploitability, meaning how much a best-responding adversary could win against the mixture. If it does, memory-bound fictitious play becomes affordable at much larger pool sizes. If it does not, we learn where strategic diversity lives in weight space. That is useful even as a negative result.
Prior Work and Positioning
The case for explicit pools comes from Learning to Play No-Press Diplomacy with Best Response Policy Iteration. That paper compared a variant that trains one network to imitate the historical average (FPPI-1, close in spirit to Neural Fictitious Self-Play) against a variant that samples opponents from stored checkpoints (FPPI-2), and found the stored pool more stable. FPPI agents reached 25–29% winrate in 1v6 games against DipNet-SL, where 14.3% is the fair share. This paper motivates the work and sets the target, but it made no attempt to compress the pool.
Model-Free Neural Counterfactual Regret Minimization With Bootstrap Learning addresses the same memory problem from the algorithmic side. It replaces stored cumulative regrets with recursively bootstrapped values and keeps the convergence rate. Its dense networks and the regret-based setting are not our target. We keep the explicit-pool algorithm and change only how snapshots are represented and executed.
Three papers supply the execution machinery, and their limits shape the design. SMaT reorders rows of unstructured sparse matrices onto Tensor Cores and reports up to 125x over generic sparse libraries, but the reordering cost is only worthwhile when the pattern is reused. Sparse GPU kernels for deep learning reports 3.5x speedups with custom kernels at the moderate sparsity levels neural networks use. Accelerating Sparse DNN Models without Hardware-Support via Tile-Wise Sparsity shows a structured alternative, pruning whole rows or columns inside tiles, with 1.95x on V100 Tensor Cores at 75% sparsity. We use tile-wise structure as a competing delta format.
Two papers on 2:4 sparsity constrain the design. NVIDIA's 2:4 pattern keeps exactly 2 nonzeros in every 4 consecutive weights. Learning N: M Fine-grained Structured Sparse Neural Networks From Scratch and ARMOR both show that forcing a 2:4 pattern onto weights loses accuracy unless training or post-hoc factorization repairs it. That warns against the obvious move of simply 2:4-pruning each checkpoint.
The research file found no published work that compresses fictitious-play pools. The obvious version of the idea, "prune each checkpoint," compresses each snapshot independently. Our version differs in two ways. It encodes snapshots relative to a shared anchor, so what is stored is the strategic change rather than the whole policy. And it exploits the fact that the snapshots are frozen to make unstructured execution efficient.
Research Program
Let $\theta_k$ be the weights of checkpoint $k$ and let $\theta_a$ be an anchor, either the earliest checkpoint in a window or the window's mean. We store a sparse delta $\Delta_k = S_\rho(\theta_k - \theta_a)$, where $S_\rho$ keeps the fraction $\rho$ of entries with the largest magnitude, chosen per layer.
At rollout time the opponents in a batch share the anchor. A layer computes
$$ y_k = x_k \theta_a + x_k \Delta_k , $$
where $x_k$ is the input of the opponent drawn as checkpoint $k$. The first term is one dense matrix multiply over the whole batch. The second term is a set of small sparse multiplies, each laid out once with SMaT-style reordering when checkpoint $k$ is added. Nonlinearities make the network output differ from a plain weight average, so the delta is applied to every layer's weights. The construction is still exact when $\rho = 1$.
Because drift accumulates over training, the pool is split into windows. Each window has its own anchor, and a new anchor is promoted once the deltas in the current window would need more than a budgeted $\rho$ to reach a fidelity target. That target is the average KL divergence between the action distributions of the original and compressed checkpoint on states sampled from self-play.
The program has three parts. First, an empirical study of how concentrated checkpoint differences are. This asks how small $\rho$ can be before the per-checkpoint KL and the exploitability of the pool mixture degrade, and whether the answer differs between early, rapidly changing checkpoints and late ones. Second, a kernel study of the anchor-plus-delta layer on an Ampere GPU and a V100. The V100 has no 2:4 hardware, which tests the claim that this works without special sparse support. We compare unstructured deltas run with reordered Tensor Core kernels, tile-wise structured deltas, and 2:4 deltas. Third, end-to-end fictitious play in which the learner trains against the compressed pool. This tests whether small per-checkpoint errors compound into a worse equilibrium.
Baselines
The naive reference is a full dense FPPI-2 pool with every checkpoint stored and run as a separate dense network. It defines the quality ceiling and the cost we want to cut. It is run on the same game, learner, number of iterations, and checkpointing frequency. The only reported figure for this method in the file is the Diplomacy result of 25–29% winrate against DipNet-SL from Learning to Play No-Press Diplomacy with Best Response Policy Iteration. For our main exploitability benchmarks there is no reported result found on Lacuna for Leduc or Flop Hold'em exploitability under FPPI-2, so we will measure the dense pool ourselves. Beating it means matching its exploitability within seed variance at a fraction of its memory and rollout time.
The strongest competitor at equal memory is a subsampled dense pool. It keeps only as many full checkpoints as fit in the memory our method uses, spaced uniformly or chosen to maximize disagreement between policies, with the opponent-sampling weights renormalized. This is the real threat, because many pool entries may be strategically redundant. It gets the same memory budget, the same total rollout compute, and the same tuning budget for selecting checkpoints. We beat it only if, at equal bytes, our pool reaches lower final exploitability or reaches a target exploitability in fewer iterations.
A second equal-memory competitor quantizes each full checkpoint to int8 or int4. It is run with the same memory budget, and it is also tested in combination with our method, because the two are compatible.
A third competitor prunes each checkpoint independently to 2:4 or to tile-wise sparsity, following Learning N: M Fine-grained Structured Sparse Neural Networks From Scratch and Accelerating Sparse DNN Models without Hardware-Support via Tile-Wise Sparsity. It is given a short post-pruning distillation step on self-play states, with the same compute as our delta construction.
The single-network average, FPPI-1/NFSP style, is included at matched parameters, mainly to reproduce the gap that motivates explicit pools.
Two ablations isolate the key ingredients. Replacing sparse deltas with low-rank deltas of equal byte count tests whether sparsity is the right shape for strategic change. Running the unstructured deltas with generic sparse kernels instead of once-per-checkpoint reordering tests whether freezing is what removes the sparsity overhead.
Why not just…?
Why not just keep fewer checkpoints? This may work as well, and we treat it as the main competitor rather than a strawman. If late checkpoints are near-duplicates, dropping most of them loses little. The equal-memory comparison above settles it. The breakdown of exploitability by pool age also tells us where the redundancy is. If subsampling ties our method, the honest conclusion is that pool diversity is concentrated in a few snapshots, and the contribution shrinks to the kernel result.
Why not just quantize the checkpoints? Quantization shrinks each checkpoint by a fixed factor of 2–4x and keeps execution dense and fast, but it still runs $K$ separate networks. Anchor sharing targets the factor of $K$ itself. Because the two are compatible, the experiment that matters is whether quantized anchor-plus-delta beats quantized full checkpoints at equal bytes. If it does not, delta encoding adds nothing.
Why not just train one network to imitate the average, as in NFSP? Learning to Play No-Press Diplomacy with Best Response Policy Iteration found that this single-network variant was less stable than an explicit pool in Diplomacy. Model-Free Neural Counterfactual Regret Minimization With Bootstrap Learning offers a different single-network route, but for regret-based learning rather than pool sampling. We reproduce the single-network baseline to confirm the gap holds in our games.
Why not just use low-rank deltas, which run densely? Low-rank corrections avoid sparse kernels altogether and are a serious alternative. Whether strategic change is low-rank or sparse in weight space is unknown, and the equal-byte ablation answers it directly. If low-rank wins, we report it, and the anchor-sharing part of the proposal still stands.
Proposed Experiments
We start with Leduc poker, where exploitability can be computed exactly. This gives a clean curve of exploitability against delta density $\rho$ and against pool memory for every baseline, over at least five seeds. We then move to Heads-up Flop Hold'em, used by Model-Free Neural Counterfactual Regret Minimization With Bootstrap Learning, as the mid-scale game. There we report approximate exploitability from a trained best-response network and head-to-head mbb/g, again with no externally reported FPPI-2 number to borrow. If compute allows, No-Press Diplomacy serves as the high-stakes case, using 1v6 winrate against a DipNet-style supervised agent and comparing to the 25–29% reported range.
Hardware metrics are opponent rollouts per second and peak GPU memory as the pool grows from 8 to 256 checkpoints, measured on an Ampere GPU and a V100.
Three checks decide the outcome. The first is whether exploitability of the compressed pool stays within seed noise of the dense pool at $\rho \le 0.1$. The second is whether, at equal memory, the compressed pool beats the subsampled dense pool. The third is whether rollout throughput with 64 or more opponents stays within roughly 1.5x of a single dense model, while generic sparse kernels on the same deltas do not. If the first check fails, sparse deltas cannot preserve the pool's strategic diversity. If the second fails, the pool was redundant to begin with. If only the third fails, the freezing argument about sparsity overhead is wrong.
References
- Learning to Play No-Press Diplomacy with Best Response Policy Iteration
- Model-free Neural Counterfactual Regret Minimization with Bootstrap Learning
- High Performance Unstructured SpMM Computation Using Tensor Cores
- Sparse GPU Kernels for Deep Learning
- Accelerating sparse DNN models without hardware-support via tile-wise sparsity
- Learning N: M Fine-grained Structured Sparse Neural Networks From Scratch
- ARMOR: High-Performance Semi-Structured Pruning via Adaptive Matrix Factorization