Concepts

DeepNash and regularised Nash dynamics

DeepNash (Perolat et al., Science 2022) was the first Stratego agent to play at expert human level. It learned from scratch by self-play with Regularised Nash Dynamics, R-NaD, on a U-Net-style convolutional network with residual blocks and four heads: a value and three policy heads for setup, piece selection and destination. Evaluated on the Gravon platform in April 2022 it won 42 of 50 ranked games (84%), placing third on both the annual and all-time leaderboards, and beat eight existing Stratego bots with a win rate of at least 97%. According to the Ataraxos authors, training took 1024 TPU nodes for two to three months, a run that would cost three to four and a half million dollars at current prices; DeepMind reported the code was no longer functional when a head-to-head was requested.

The learning rule

R-NaD has three steps, repeated. First, a reward transformation: with a regularisation policy and , player 's reward becomes

a penalty for straying from the regularisation policy and a bonus when the opponent strays. Second, the dynamics: run replicator dynamics on the transformed game. In the transformed game the dynamics have a Lyapunov function and converge to a unique fixed point instead of cycling. Third, make that fixed point the next regularisation policy and repeat; the sequence of fixed points converges to a Nash equilibrium of the original game.

Fictitious self-play, no regularisationWith the reward transformation (R-NaD)value of the mixed equilibrium: the dotreference policy refreshed every few thousand steps
Replicator dynamics on matching pennies cycle around the equilibrium, and the regularised reward makes them spiral into a fixed point that moves toward it.

At scale the dynamics step is a neural update: a v-trace estimate of the transformed values and a NeuRD policy-gradient step on the logits, with , a learning rate of , batches of 768 trajectories, and the regularisation policy refreshed every 10,000 to 100,000 steps over 7.21 million steps in total. Because a softmax never zeroes a bad move, DeepNash fine-tunes by thresholding probabilities below 0.03 and discretising to 32 levels, and adds test-time filters for obvious mistakes.

Same problem, two answers

Both systems face the cycling of self-play under hidden information. R-NaD changes the game so the dynamics converge, then walks the target. Ataraxos keeps the game and damps the optimiser, annealing regularisation toward the magnet policy and the step size together. Ataraxos also adds three things DeepNash did not have: a learned setup distribution trained separately, advantage filtering, and test-time search. Its authors do not attribute their result to any single one of these, and that is the open question for a replication on one machine.

The comparison this program registers

The DeepNash rung implements R-NaD's reward transformation and a NeuRD update inside the same training package, on the same environment, network and compute budget as the damped PPO loss. Two runs of equal wall-clock time, evaluated against the same frozen opponents and against each other, answer which learning rule reaches further on this hardware. The decision rule is on the DeepNash approach page.