Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learning

In plain words

Stratego is a two-player board game where each side hides the identity of its 40 pieces, and the outcome depends on bluffing and guessing. Earlier game AIs that mastered chess or Go could plan ahead by searching the game tree, but Stratego hides too much for that to work. This paper's agent, DeepNash, learns the game the way it might learn to play cards: it plays against copies of itself and adjusts its habits over millions of games, with no human games to copy and no look-ahead search.

The learning rule is the hard part. Plain self-play tends to chase its own tail, with each side overreacting to the other's last move. DeepNash adds a pull toward a reference strategy and slowly moves that reference forward, so the learning settles toward a balanced strategy that is hard to exploit. The agent also learns where to place its pieces at the start, which is a secret setup phase, as part of the same training.

The authors report that the agent beat several existing Stratego programs almost every time and placed among the top three players on an online Stratego platform. These results come from the authors' own evaluation.

TL;DR

• DeepNash is a model-free deep RL agent for Stratego, trained only by self-play, with no search and no opponent modelling §2.
• Its core, R-NaD, repeats three steps: transform the reward around a regularisation policy, run replicator-style dynamics to a fixed point, and make that fixed point the new regulariser §2.2.
• Author-reported: 97% or higher win rate against eight known Stratego bots, and 84% (42 of 50 matches) against human experts on Gravon, ranked 3rd in its 2022 and all-time leaderboards §3.1 §3.2 tab. 1.
• No official code is public. Many hyperparameters are given only in the supplement, and the training scale (768 learner TPUs, 256 actor TPUs) is far beyond a typical re-implementation.

Problem

Stratego is a two-player zero-sum game with imperfect information. Its game tree is about 10^535 nodes, and each player has about 10^66 possible starting deployments §1 fig. 1. Hidden piece identities mean that a player's best move depends on beliefs about the opponent's private information.

Search methods that work in perfect-information games (Go, chess) and state-of-the-art imperfect-information search methods that break the game into sub-situations are, according to the authors, not applicable here §1. Full search would need to estimate the opponent's private state from public information for a huge number of configurations, which the authors say is intractable in Stratego §2. Model-free self-play RL is also unstable in general, and a loss whose minimisation converges to a Nash equilibrium is hard to define at this scale. Exploitability, a standard distance-to-equilibrium measure, needs best responses that are intractable here §2.1.

The paper therefore asks whether a model-free RL method with a convergence guarantee can scale to Stratego and reach expert human level, without human data and without search §1 §2.

Method

DeepNash has three parts §2.3 [supp. "DeepNash: R-NaD at Scale"]:

1. Core training: R-NaD, the model-free RL algorithm, implemented with a deep network.
2. Fine-tuning during training, which thresholds and discretises action probabilities to remove very rare mistakes §2.3.
3. Test-time post-processing, which removes remaining low-probability blunders and applies a few heuristics [supp. "Test Time Improvements"].

Game setting used by the agent

• The board is 10 x 10 with two 2 x 2 lakes. Each side has 40 pieces of 12 types (table below). Each side deploys in a 4 x 10 area [supp. "Basic Rules"].
• Each game is either won by capturing the flag or all movable pieces, or declared a draw after 2000 total moves or 200 consecutive moves with no attack. This draw rule is non-standard; the authors chose it for training and evaluation [supp. "Drawing rules"].
• The agent's action is a square (100 possible), chosen in two steps during play: first the piece, then its destination. During deployment, the agent places 40 pieces in a fixed order, Flag, Bombs, Marshal, and so on down to Spy [supp. "Agent action space"].

Source: [supp. "Basic Rules" table].

Step 1: R-NaD in normal-form games

The authors first explain R-NaD on a two-player zero-sum matrix game. Each iteration has three steps §2.2 fig. 2:

• Reward transformation. Given a regularisation policy pi_reg, the reward for player i is changed as in §2.2 (the main-text formula) and [supp. "Details on R-NaD in Two-Player Zero-Sum Normal Form Games"]. eta > 0 is the regularisation strength. The transformed reward depends on the policy being learnt, so it is not a fixed game.
• Dynamics. Run replicator dynamics on the transformed game until the policy reaches its fixed point §2.2. The replicator equation is the unnumbered display in §2.2 and [supp. "Details on R-NaD..."]. The fixed point is unique because of the transformation, and it decreases a Lyapunov function that the authors cite to [perolat2020poincar] §2.2.
• Update. The fixed point becomes the next regularisation policy §2.2.

The matching-pennies example uses eta = 0.2 and a starting regulariser of [0.999, 0.001]; the replicator dynamics converge to [0.896, 0.104] for player 1 and [0.263, 0.737] for player 2 in the first iteration, and the Lyapunov function decreases over three iterations §2.2 fig. 2.

The authors state that the sequence of fixed points converges to a Nash equilibrium of the original game, and they assume the equilibrium is unique for simplicity [supp. "Details on R-NaD in Two-Player Zero-Sum Normal Form Games"].

Step 2: R-NaD at scale

The same three steps run on imperfect-information game trajectories. Learning is in self-play from full episodes §2.3.2 [supp. "Full games learning"].

Observation and network §2.3.2 [supp. "Neural Network Input Representation"]:

• The network input is a 10 x 10 x 82 tensor: lakes, the agent's private piece types, the opponent's and own public type-probability tensors, the last 40 moves encoded per square, and several scalars (game-length ratio, no-attack ratio, phase, selection flag, selected-piece mask).
• Player-centric: the blue player's tensor is rotated 180 degrees, so one network plays both colours [supp. "Player-centric observations and actions"].
• A U-Net-like pyramid torso (256 channels, residual blocks, inner blocks at 320 channels) produces a 10 x 10 x 256 embedding [supp. "Neural Implementation"].
• Four heads, all fed from that embedding: a value head, and three policy heads for deployment, piece selection and piece displacement §2.3.2 [supp. "Network Modules"]. Policy heads take the no-attack ratio and, for displacement, a one-hot of the selected piece. The value head uses the same inputs, zeroed as needed by phase.

Transformed reward (per step, for the player who acts) §2.3.2 [supp. "Transformation of the reward"]:

# Transformed reward for one step  [§2.3.2] [supp. "Transformation of the reward"]
# reward: r_t for the acting player; eta = 0.2
# policy, reg_policy: probabilities over the actions at the observation
def transformed_reward(reward, action, policy, reg_policy, is_acting):
    # Log-ratio of the current policy to the regulariser for the action
    log_ratio = log(policy[action] / reg_policy[action])
    # Acting player is penalised for drifting from the regulariser
    if is_acting:
        return reward - eta * log_ratio
    # Opponent's action gets the opposite sign  [§2.3.2]
    return reward + eta * log_ratio

Blending between regularisers. Each iteration m moves from the old regulariser to the new one over Delta_m steps [supp. "Transformation of the reward"]:

# Smooth switch from regulariser m-1 to m  [supp. "Transformation of the reward"]
# step: n in [0, Delta_m]
def blend_weight(step, delta_m):
    # alpha_n = min(1, 2 * n / Delta_m)
    return min(1.0, 2.0 * step / delta_m)

# reward_new uses reg m; reward_old uses reg m-1
alpha = blend_weight(step, delta_m)
reward = alpha * reward_new + (1.0 - alpha) * reward_old

Dynamics: the value function and Q-estimates use a two-player V-trace backward pass over the whole episode, with no bootstrapping [supp. "Dynamics: estimators for the value function"]. With ratio = pi(a_t|o_t) / mu_t(a_t), rho_bar = c_bar = 1, and the boundary values at t_eff + 1 set to zero:

# Backward two-player V-trace over a full episode  [supp. "Dynamics"]
# Output: value targets v_hat[t] for each step (per player)
def vtrace_backward(episode, policy, mu, values, t_eff):
    # Initial boundary: v_hat, next-value, reward accumulator = 0; xi = 1
    for t in reversed(range(t_eff)):
        # Ratio of current policy to the behaviour policy  [supp.]
        ratio = policy[a_t] / mu[a_t]
        if acting_player_at_t:
            # rho and c are truncated at 1  [supp.]
            rho = min(1.0, ratio * xi_next)
            c = min(1.0, ratio * xi_next)
            delta_v = rho * (r_t + ratio * r_hat_next
                             + v_next_next - values[t])
            v_hat[t] = values[t] + delta_v + c * (v_hat_next - v_next_next)
            v_next[t] = values[t]
            r_hat[t] = 0.0
            xi[t] = 1.0
        else:
            v_hat[t] = v_hat_next
            v_next[t] = v_next_next
            r_hat[t] = r_t + ratio * r_hat_next
            xi[t] = ratio * xi_next

The Q-estimate for each action (acting player only) adds the regularisation term to the sampled reward, and is also written out in [supp. "Dynamics: estimators for the value function"].

Learning updates [supp. "Dynamics: learning update of the Q-function and of the policy"]:

# One learner step for the value and policy  [supp. "Dynamics: learning update"]
# Targets come from the target network (theta_target)
def learner_step(theta, theta_target, episodes, lr, beta, clip):
    # Value: regress v_theta(o_t) onto the V-trace target of the acting player
    value_loss = critic_loss(theta, episodes, v_hat_targets)
    # Policy: NeuRD update on clipped Q estimates  [§2.3.2] [supp.]
    neurd_grad = neurd_update(theta, episodes, q_hat_targets, lr, beta, clip)
    # Combined update direction Lambda; minus sign as in the paper
    direction = -(lr * grad(value_loss) + neurd_grad)
    # Gradient clipping at 10000, then Adam  [supp. parameter table]
    return adam_step(theta, clip_values(direction, 10000.0))

Adam settings and the averaging of the target network are listed in the parameter table below. After Delta_m steps the target policy is the fixed point for iteration m, and it becomes the next regulariser [supp. "Updating the transformed reward and the learning parameters"].

Fine-tuning during training (main text fine-tuning paragraph and [supp. "Fine-tuning"]): the policy used for value and Q estimates is projected with a threshold of 0.03 and a discretisation of 32 quanta, which removes very low-probability actions before estimation.

Test-time post-processing

These steps are applied only to the trained agent when playing [supp. "Test Time Improvements"]:

• Thresholding and discretisation of the policy, with the settings in the table below. If no action would remain, the policy is left unchanged.
• Avoid pointless threats. After three back-and-forth threats between the same pieces in the same 2 x 2 region, only a single threat is allowed unless no other moves exist. The restriction applies to the agent only.
• Eagerness. The no-attack ratio r is replaced by 1 - (1 - r)^alpha with alpha = 2.0, to make the agent less passive.
• Memory heuristic. Assumes a Spy attacks a known Marshal, a Marshal attacks a known General or Colonel when no recapture is possible, and a General attacks a known Colonel similarly. Non-attacks then rule out types, which are set to zero in the public-information tensors.
• Value bounds heuristic. Two-step lookahead bounds the value of each action. Actions whose bound is below the current value minus a margin of 0.05 are removed, if other actions remain. The authors say it changed fewer than 1.5% of the agent's turns on Gravon [supp. "Value bounds heuristic"].

Infrastructure

The pipeline follows the Sebulba Podracer design with IMPALA-style actors. Actors generate full games in a replay buffer, a learner samples batches and computes exact returns by a forward pass and then a backward pass over chunks, and evaluators run separately against fixed bots [supp. "Infrastructure for learning", "Full games learning"]. Training used 768 TPU nodes for learners and 256 TPU nodes for actors [supp. "Infrastructure and Setup"].

Hyperparameters

Training values from the supplement's parameter table app. parameter table unless noted; the R-NaD schedule is described in §2.3.2. Test-time values from the supplement's test-time table app. test-time table.

Not stated: the network's exact layer counts for N and M, optimizer step counts for each iteration beyond Delta_m, the random seed count, and the number of evaluation games per checkpoint.

Results

Author-reported. Setup: DeepNash trained by self-play only §2.3. Evaluated on the Gravon platform against human players §3.1 and against eight existing Stratego bots, with 800 games each for the automated bots §3.2 tab. 1.

The authors state a minimum win rate of 97% against the bots §4. The bots are not all of the same strength; Probe and Master of the Flag were evaluated in fewer games and the authors note Master of the Flag plays only as Blue tab. 1 [supp. "Details on external Stratego program evaluation"]. The Celsius1.1 losses came mostly from a high-risk early capture strategy §3.2.

The paper gives no ablation numbers for the R-NaD core, the fine-tuning or the test-time heuristics. It says the memory and value-bounds heuristics do not significantly raise the win rate of the agent against a version of itself without them [supp. "Value bounds heuristic"].

Behaviour observations §3.3 fig. 4 fig. 5 are described qualitatively: varied deployments that avoid simple patterns, a Flag usually on the back row and often protected by Bombs, bluffing with a Scout, and trade-offs between material and information.

Paper vs code

No official code.

Searched: the paper and abstract contain no code link, the arXiv entry has no comment with a link, and no project page was linked. A GitHub repository search for deepnash returned 12 repositories, all owned by individual users rather than DeepMind or the authors, and all independent reimplementations (for example the Kuhn-poker and Connect-4 variants); none were used. A search for r-nad stratego returned nothing. A search for rnad within the google-deepmind organisation returned nothing.

Pitfalls

• Sign convention. The transformed reward subtracts eta times the log-ratio for the acting player and adds it for the opponent §2.3.2. The paper's supplement writes the same rule as a single sign term; a flipped sign would change the learning dynamics, and the paper gives no sanity check for it.
• Two-player V-trace is custom. The supplement's backward recursion is adapted from IMPALA to two players. Its boundary values (v_hat, V_next, r_hat, xi at the end of the episode) must be set as stated [supp. "Dynamics"]. The text writes the acting branch with v^i_{t+1} in the c_t term; the intended quantity is the estimate v_hat_{t+1}, which is our reading and not stated explicitly.
• Critic loss form. The supplement writes the critic term with a norm (not squared) and an unspecified reduction across the episode [supp. "Dynamics: learning update"]. Implement as a squared error only if you verify it; the paper does not say.
• Action count. The supplement says the value estimator faces "3600 possible actions at every step", while the action space is stated as 100 squares per step with a two-step move decomposition [supp. "Dynamics: estimators..."] [supp. "Agent action space"]. The 3600 figure appears to refer to pairs or a different counting; the authors do not explain it.
• Thresholding and discretisation are not a plain softmax. Both the training fine-tuning and the test-time post-processing change the policy that gets sampled or used in estimates. Values with probability below 0.03 are dropped and the rest are rounded up to multiples of 1/32 (deploy) or 1/16 (play) at test time [supp. "Test Time Improvements"]. The supplement says probabilities are sorted high to low and remaining weight is discarded once the sum reaches 1; implement that rule as written. Whether the same rounding is used during training is not stated; the training fine-tuning text gives only the threshold and quanta [supp. "Fine-tuning"].
• Draw rule. The draw conditions (2000 total moves, or 200 consecutive moves without attack) differ from standard rules, which allow a draw only by agreement [supp. "Drawing rules"]. Results and behaviour depend on this.
• Schedule is not a single number. Delta_m changes at iterations 100 and 165, so a fixed-length run does not reproduce the schedule [supp. parameter table].
• Unstated pieces. The paper does not state the exact policy and value head layer counts (N, M), how many evaluation matches per checkpoint were used for each bot, or the random seed count. The supplement's pyramid description leaves N and M as symbols.
• Costs. The reported run used 768 learner and 256 actor TPU nodes and a replay buffer of full episodes with two passes per batch [supp. "Infrastructure and Setup"]. A smaller reproduction will have different convergence behaviour, and the authors do not give a smaller configuration.
• Equation citations. The main text's replicator and transformed-reward equations are unnumbered displays, and the supplement's numbered equations are not labelled in the LaTeX source. Cite by section, as this card does.
• Evaluation caveats. The Gravon figure rests on 50 ranked matches, a small sample for an 84% estimate; the paper gives no interval. The bot results depend on the bot version or setting used (for example Demon of Ignorance at AI level 8; some bots run with a modified repetition rule) [supp. "Details on external Stratego program evaluation"].
• Heuristics reviewed by the authors. The memory and value-bounds heuristics are described as not significantly improving win rate against a version of the agent without them; they are described as avoiding visible mistakes [supp. "Value bounds heuristic"].

Lineage

• Builds on: the R-NaD theory of regularised dynamics [perolat2020poincar] (arXiv id only; not on this site); NeuRD, the neural replicator dynamics update [hennes2020neural]; V-trace from IMPALA [espeholt2018impala]. The paper changes V-trace to a two-player, full-episode form [supp. "Dynamics"].
• Compared against: Probe, Master of the Flag, Demon of Ignorance, Asmodeus, Celsius, Celsius1.1, PeternLewis and Vixen §3.2; regret- and best-response methods such as Deep CFR, DREAM, ARMAC, NFSP and PSRO are discussed as related work [supp. "Related Work"].
• Superseded by: not known from content already in this wiki.