PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Julien Perolat, Bart de Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T. Connor, Neil Burch, Thomas Anthony, Stephen McAleer, Romuald Elie, Sarah H. Cen, Zhe Wang, Audrunas Gruslys, Aleksandra Malysheva, Mina Khan, Sherjil Ozair, Finbarr Timbers, Toby Pohlen, Tom Eccles, Mark Rowland, Marc Lanctot, Jean-Baptiste Lespiau, Bilal Piot, Shayegan Omidshafiei, Edward Lockhart, Laurent Sifre, Nathalie Beauguerlange, Remi Munos, David Silver, Satinder Singh, Demis Hassabis, Karl Tuyls

arXiv:2206.15378v1cs.AIcs.GTcs.MA

TL;DR

Stratego remained a grand challenge because existing state-of-the-art methods could not reach beyond amateur play in its complex imperfect-information setting. DeepNash addresses this with model-free, game-theoretic self-play using R-NaD and achieves expert-level performance, including an 84% overall win-rate against human experts and a top-three Gravon ranking.

  • Problem

    Stratego remained a grand challenge because state-of-the-art planning and imperfect-information techniques did not reach beyond human-amateur play.

  • Method

    DeepNash combines a model-free deep residual neural network with the game-theoretical R-NaD algorithm to learn Stratego through self-play.

  • Results

    DeepNash achieved an 84% overall win-rate against human-expert players on Gravon, placing it in the top-three rank, while empirically converging to an ϵ-Nash equilibrium.

  • Takeaways & Limitations

    DeepNash learns to play Stratego at a level reflected by top-three ranking on the Gravon platform.

  • Takeaways & Limitations

    Existing state-of-the-art perfect-information planning and imperfect-information methods could not be used for Stratego at the time described.

Abstract

from arXiv · show

We introduce DeepNash, an autonomous agent capable of learning to play the imperfect information game Stratego from scratch, up to a human expert level. Stratego is one of the few iconic board games that Artificial Intelligence (AI) has not yet mastered. This popular game has an enormous game tree on the order of $10^{535}$ nodes, i.e., $10^{175}$ times larger than that of Go. It has the additional complexity of requiring decision-making under imperfect information, similar to Texas hold'em poker, which has a significantly smaller game tree (on the order of $10^{164}$ nodes). Decisions in Stratego are made over a large number of discrete actions with no obvious link between action and outcome. Episodes are long, with often hundreds of moves before a player wins, and situations in Stratego can not easily be broken down into manageably-sized sub-problems as in poker. For these reasons, Stratego has been a grand challenge for the field of AI for decades, and existing AI methods barely reach an amateur level of play. DeepNash uses a game-theoretic, model-free deep reinforcement learning method, without search, that learns to master Stratego via self-play. The Regularised Nash Dynamics (R-NaD) algorithm, a key component of DeepNash, converges to an approximate Nash equilibrium, instead of 'cycling' around it, by directly modifying the underlying multi-agent learning dynamics. DeepNash beats existing state-of-the-art AI methods in Stratego and achieved a yearly (2022) and all-time top-3 rank on the Gravon games platform, competing with human expert players.

1 Introduction

Stratego remains a difficult AI benchmark because its enormous game tree, imperfect information, and long, interdependent decision sequences challenge existing planning and search methods. DeepNash addresses this challenge with model-free self-play reinforcement learning and reaches human-expert performance.

  • Stratego’s challenges: Stratego has 10^535 possible states, creating a substantially larger game tree than imperfect-information poker and perfect-information board games.The game also begins with 10^66 possible deployments for each player, compared with 10^3 possible card pairs in poker.
  • Stratego’s challenges: Existing AI agents had reached only approximately human-amateur performance, while state-of-the-art perfect-information planning and imperfect-information search could not be applied directly.The game’s situations cannot readily be decomposed into independent subproblems.
  • DeepNash: DeepNash learns Stratego from scratch through self-play using model-free reinforcement learning, without human demonstrations or search.Its approach combines a deep neural network with the game-theoretic Regularized Nash Dynamics algorithm.
  • DeepNash: Regularized Nash Dynamics converges toward an ϵ-Nash equilibrium, supporting competitive play that is robust to opponents attempting to exploit the agent.This approach modifies multi-agent learning dynamics to avoid cycling around the equilibrium.
  • Stratego’s challenges: Stratego combines private piece deployment with sequential play under partial observation, requiring reasoning about hidden information and opponents’ decisions.Players secretly deploy 40 pieces, then take turns moving and revealing pieces through combat.
  • Results: DeepNash beats existing state-of-the-art Stratego bots with a win rate above 97% and achieves an 84% win rate against human experts.It ranks among the top three players on both the 2022 annual and all-time Gravon leaderboards.

2 Methods

DeepNash combines model-free reinforcement learning, self-play, and Regularized Nash Dynamics (R-NaD) to learn an approximate Nash equilibrium in Stratego without search. R-NaD modifies learning dynamics to support convergence while scaling through deep neural networks.

  • Motivation: Stratego’s imperfect information and enormous private-state search space make existing search techniques computationally intractable.The approach therefore avoids explicitly modeling opponent private states.
  • Approach: DeepNash learns Stratego through self-play using model-free reinforcement learning and a game-theoretic R-NaD algorithm, without search.The model-free formulation does not build an explicit opponent belief-space model.
  • Relation to prior work: Prior self-play methods required stabilization tricks such as training against past agents, reward shaping, or expert data, whereas DeepNash provides a game-theoretic alternative.The paper describes those earlier approaches as difficult to tune and not easily generalizable to new games.
  • R-NaD algorithm: R-NaD repeatedly transforms rewards, evolves the system through replicator dynamics, and updates the regularization policy.The transformed reward is policy-dependent and uses a regularization parameter η > 0.
  • R-NaD algorithm: The regularized dynamics have a unique fixed point, and repeated iterations can converge to a Nash equilibrium of the original game.The fixed point of an individual modified game is not itself necessarily a Nash equilibrium of the original game.
  • DeepNash at scale: DeepNash scales R-NaD with a deep neural network and combines core training with policy fine-tuning and test-time action filtering.The network receives a tensor encoding board position, known piece information, limited move history, and lake positions.

3 Results

DeepNash was evaluated against eight Stratego bots and human experts on Gravon, achieving dominant bot performance, human-expert-level play, and top-three rankings. Its play exhibits varied deployments, information–material trade-offs, and bluffing.

  • Evaluation on Gravon: 42 of 50 human-expert matches were wins, an 84% overall win-rate that placed DeepNash third on both 2022 and all-time Gravon leaderboards.The 2022 and all-time ratings were 1799 and 1778, respectively, each corresponding to third place.
  • Evaluation against Stratego bots: DeepNash wins the overwhelming majority of games against existing Stratego bots despite training exclusively through self-play.The evaluation covered eight known AI bots, with 800 games played against bots that could be run automatically.
  • Deployment: DeepNash generates billions of unique deployments, making it difficult for humans to exploit recurring setup patterns.Its deployment strategy co-evolves with gameplay and includes recurring patterns such as back-row Flag placement and dispersed high-ranking pieces.
  • Trade-off between information and material: DeepNash balances information and material, sometimes preserving piece identities over immediate captures and winning despite having less material.In one example, its value function v = 0.403 assigned around 70% expected win rate despite lesser material, and DeepNash won the game.
  • Deceptive behavior and bluffing: DeepNash executes positive and negative bluffs, including advancing unrevealed pieces to influence the opponent’s beliefs.The paper illustrates these behaviors through several Gravon match situations.

4 Conclusion

DeepNash combines model-free reinforcement learning with game-theoretic regularization to learn Stratego end-to-end without search or explicit opponent modelling. It reaches approximate Nash-equilibrium behavior and human-expert performance through self-play.

  • Contribution: DeepNash learns Stratego from scratch in self-play to human expert-level performance, including both deployment and gameplay.The approach handles the deployment phase and actual gameplay end-to-end in one method.
  • Method: DeepNash combines a deep residual neural network with Regularized Nash Dynamics in a model-free method that uses no search or explicit opponent modelling.The method is presented as orthogonal to model-based approaches used in other complex games.
  • Method: R-NaD repeatedly transforms rewards, applies replicator dynamics to obtain a fixed point, and updates the regularization policy to that point.The repeated process empirically demonstrates convergence to an ϵ-Nash equilibrium.
  • Implications: The results support applying reinforcement learning to multi-agent problems with astronomical state spaces and imperfect information.The conclusion frames this as a possible direction for applications currently out of reach for state-of-the-art methods.

Related Work

Prior Stratego and game-playing methods include regret minimization, best-response, and policy-gradient approaches, but each faces scaling, memory, convergence, or evaluation limitations. DeepNash extends policy-gradient ideas with regularization and demonstrates large-scale human-level performance.

  • Regret minimization: Regret-minimization methods approach Nash equilibria in self-play, but tabular CFR and related methods cannot scale to Stratego’s enormous information-set space.CFR stores regrets and action probabilities for all information sets, while compressed variants remain far below Stratego’s scale.
  • Scaling limitations: Deep regret-based methods face practical obstacles in Stratego, including large branching factors, long-horizon importance weights, and difficult average-strategy approximation.These issues affect external sampling, outcome-sampling methods, and neural-network implementations.
  • Best-response methods: Best-response methods can achieve strong results but remain memory-intensive and slow because they may require exponentially many policies and costly best-response computation.Population-based methods such as PSRO and systems inspired by it have achieved human-level results in other games.
  • Policy gradients: Policy-gradient methods include RPG and NeuRD, but before this work they had not demonstrated large-scale human-level performance.NeuRD was proven to converge in the time average, whereas DeepNash combines it with regularization to converge in the last iterate.
  • Stratego-specific prior work: Barrage Stratego methods had beaten handcrafted bots but had not shown results against top human players.The reported PSRO result reached at most an 81% win-rate against those handcrafted bots.

Methods: additional information

R-NaD modifies a two-player zero-sum game with regularization, finds a fixed point through replicator dynamics, and iteratively updates the regularizer with that point. Under the stated assumptions, the sequence converges toward a Nash equilibrium.

  • Game formulation: In a two-player zero-sum normal-form game, each player selects an action from its action set and receives opposite rewards.Player 2’s reward is r2(a1, a2) = −r1(a1, a2).
  • Reward transformation: R-NaD transforms each player’s reward using a regularization policy before applying replicator dynamics to the modified game.The regularization policy may be chosen arbitrarily provided every action has non-zero probability.
  • Replicator dynamics: Replicator dynamics increase probabilities for above-average-fitness actions and decrease probabilities for below-average-fitness actions.The dynamics have a fixed point whose distance decreases exponentially under the stated Lyapunov condition.
  • Iterative update: R-NaD starts from an arbitrary regularization policy, computes a fixed point, then uses that fixed point as the next iteration’s regularizer.The resulting sequence of fixed points converges to the original game’s Nash equilibrium as the distances decrease to zero.
  • Regularization parameter: The regularization parameter η trades off stability and speed against bias toward the current regularization policy.Higher η can require more overall iterations to approach the Nash equilibrium sufficiently closely.

DeepNash: R-NaD at Scale

DeepNash scales Regularised Nash Dynamics into a model-free deep reinforcement-learning system for imperfect-information games. Its training combines reward transformation, value and policy updates, fine-tuning, and full-trajectory learning.

  • Core algorithm: DeepNash combines R-NaD, a model-free deep reinforcement-learning algorithm, with policy fine-tuning and test-time improvements.The three components are R-NaD, fine-tuning to reduce highly improbable actions, and test-time improvements targeting obvious mistakes.
  • Core algorithm: R-NaD transforms policy-dependent rewards, iteratively updates value and Q-functions, and learns policies through dynamics steps.The dynamics step estimates values and updates the Q-function and policy; later iterations update the regularization policy.
  • Challenge: Stratego’s 3600 possible actions per step make accurate Q-function estimation especially challenging, even though many actions are illegal.The action space is large and has no straightforward action-outcome relationship in the supplied description.
  • Learning updates: R-NaD estimates values and Q-functions with a two-player adaptation of v-trace using future trajectory information.The estimator is computed over the full trajectory backward without bootstrapping, which the paper states minimizes bias.
  • Fine-tuning: Fine-tuning thresholds and discretizes action probabilities to reduce rare errors caused by softmax assigning non-zero probability to every action.The paper notes that an opponent can exploit such errors by prolonging the game with neutral waiting moves.
  • Trajectory learning: Full episodes are stored in replay, split into fixed-length chunks, processed forward for states and statistics, then backward for gradients.This preserves exact returns and recurrent states across chunks while accumulating gradients for the network update.

Game Rules and Neural Network Input Representation

Stratego combines private deployment with alternating movement and combat, creating imperfect information about opponent piece types. DeepNash represents this setting through board, move-history, and probabilistic public-information tensors.

  • Game phases: Stratego begins with a private deployment phase followed by alternating play, and victory comes from capturing the opponent’s Flag or all remaining pieces.Each player privately places 40 pieces in a 4 × 10 area before the red player opens the play phase.
  • Combat rules: Attacks reveal both piece types; the higher-valued piece survives, equal-valued pieces are removed, and Miners and Spies provide exceptions.Miners can capture Bombs, while Spies can capture Marshals when attacking.
  • Action representation: The agent uses 100 discrete board-location actions, with play moves decomposed into selecting a piece and selecting its legal destination.The two-step action structure changes according to game phase and affects both observations and agent design.
  • Player-centric encoding: The observation and action encodings are player-centric, rotating Blue’s board view and interpreting action squares relative to each player’s side.This lets one agent play both sides of the board.
  • Observation representation: Public information tracks uncertainty using piece locations, revealed types, movement history, and counts of unrevealed piece types.The construction distinguishes pieces that have moved from those that have never moved and excludes policy-dependent deductions.

Network Architecture

DeepNash uses a pyramid-like convolutional network with phase-specific policy heads and a shared value head. Its inputs and outputs are structured around Stratego’s two-stage moves and deployment phase.

  • Pyramid architecture: The pyramid architecture uses convolutional and deconvolutional residual blocks with skip connections to produce spatial action logits.Strided residual paths use a 1 × 1 convolution to match changed dimensions.
  • Network modules: The network processes observations through a torso and supplies three phase-specialized policy heads plus one value head.The policy heads cover deployment, piece selection, and piece displacement, while the value head computes the training value function.
  • Policy heads: The deployment head outputs a board-location distribution for placing the next piece during the first 40 game steps.Deployment order is fixed, so the head uses the board-game embedding without an additional deployment-order observation.
  • Policy heads: The piece-selection head chooses a playable unit, while the piece-displacement head selects its destination and may initiate an attack.The displacement head also receives a one-hot representation of the selected piece.
  • Value head: The shared value head receives the board embedding, no-attack ratio, and selected-piece representation, with inactive inputs zeroed by phase.A single value head serves all three policies to reduce memory usage while preserving a fixed input shape.
  • Outputs: Forbidden actions are masked with −∞ logits, and the remaining logits are converted into probabilities with softmax.The value head instead flattens its final spatial representation and produces a scalar through a linear layer.

Infrastructure and Setup

DeepNash trains through a distributed Actors–Replay Buffer–Learner–Evaluators pipeline. Full variable-length games are retained so learners can compute exact returns while synchronizing gradients across machines.

  • Training pipeline: Actors self-play and write full games to replay, learners improve network weights, and evaluators assess the agent against fixed opponent bots.Updated weights are periodically distributed to actors and evaluators.
  • Resource allocation: Actors, replay buffers, learners, and evaluators use different resources, with learners relying heavily on accelerator FLOPS and replay on RAM.Evaluators run separately as low-priority machines, decoupling their hardware requirements from the main training system.
  • Distributed training: SIMD scaling synchronizes learner machines, averages their independently computed gradients, and applies the averages to network weights.Each machine reads different games while performing the same learning step in sync.
  • Distributed training: Training used 768 TPU nodes for learners and 256 TPU nodes for actors.The supplied passage reports these as the node allocations used to train the final agent.
  • Full-game learning: Learners consume batches of full, variable-length games, padding shorter games and splitting batches into fixed-length time chunks.The chunked batch is processed forward to recover states and statistics, then backward to compute gradients.
  • Full-game learning: Forward processing avoids bootstrapping and approximations for returns and recurrent states, while backward processing computes and accumulates weight gradients.The accumulated gradients are applied with an optimizer after all chunks have been reprocessed.

Test Time Improvements

DeepNash applies test-time policy adjustments to remove low-probability blunders, reduce repetitive play, and improve human-facing behavior while preserving stochasticity. Additional heuristics use game-specific memory and value bounds, but their winrate effect is limited in self-play evaluation.

  • Policy post-processing: Long games make rare stochastic blunders consequential, because low-probability losing actions can occur repeatedly across up to 2,000 moves.An opponent can prolong the game with neutral waiting moves, increasing exposure to such actions.
  • Policy post-processing: Thresholding drops actions below a fixed probability threshold and renormalizes the remaining policy; discretization rounds probabilities to multiples of 1/n_disc.If thresholding removes all positive-probability actions, the policy remains unchanged; discretization discards remaining weights once the total reaches 1.
  • Limitations: The neural network lacks sufficient history for detailed Stratego-state assessment, leaving long-memory architectures as a potential improvement area.The reported heuristics empirically avoid some mistakes against humans, but they do not significantly improve self-play winrate.
  • Memory heuristic: A memory heuristic tracks move-pattern-based deductions about piece identities and updates the network input, but its assumptions are often, not always, satisfied.The heuristic primarily improves tracking of information humans possess about the agent’s pieces and helps avoid inconsistent bluffing.
  • Value bounds heuristic: A value-bounds heuristic uses two-step lookahead and the learned value function to remove actions whose estimated upper bound is below the current state value.It affected less than 1.5% of DeepNash’s turns on Gravon and did not significantly improve winrate against an unprocessed version of itself.

Additional results

DeepNash was evaluated against human players and several established Stratego programs under specified platform, version, and rule settings. The evaluation included roughly 50 ranked Gravon matches and adjustments for invalid actions or repetitive-draw conditions.

  • Gravon evaluation: Roughly 50 ranked matches were used to evaluate DeepNash on Gravon in April 2022, with three matches excluded from rating computation.The exclusions comprised two earlier training snapshots and one timeout caused by human error.
  • AI baselines: Probe was evaluated at AI-level 8, where its performance against DeepNash saturated; games producing three consecutive invalid actions were discarded.Probe had previously won the Computer Stratego World Championship three times.

Quotes from Stratego Experts

Stratego experts described DeepNash as an unprecedentedly strong artificial player. Their comments connect its human-level competitiveness with its later top-3 Gravon ranking.

  • Expert assessment: Many players had believed no Stratego AI would seriously compete with humans or reach the platform’s top ten, but DeepNash challenged that expectation.The statement is attributed to Gravon platform owner Thorsten Jungblut.
  • Expert assessment: Former world champion Vincent de Boer reported that DeepNash approached the level needed to beat experienced humans and was unsurprised by its later top-3 Gravon ranking.He also expected the agent to perform well in the World Championship.
Loading 2206.15378v1…