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

arXiv: https://arxiv.org/abs/2206.15378 · HTML: https://mlsanity.com/paper/2206.15378/

## Key facts

- Cited by 131 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 33 references that are in the map.
- First posted on arXiv 30 Jun 2022.

## Builds on (most cited first, 6 of 6)

- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [Human-level performance in first-person multiplayer games with population-based deep reinforcement learning](https://mlsanity.com/paper/1807.01281/) (2018)
- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [Podracer architectures for scalable Reinforcement Learning](https://mlsanity.com/paper/2104.06272/) (2021)
- [Measuring the Size of Large No-Limit Poker Games](https://mlsanity.com/paper/1302.7008/) (2013)

## Built on by (most cited first, 30 of 131)

- [Nash Learning from Human Feedback](https://mlsanity.com/paper/2312.00886/) (2023)
- [Harms from Increasingly Agentic Algorithmic Systems](https://mlsanity.com/paper/2302.10329/) (2023)
- [Avalon's Game of Thoughts: Battle Against Deception through Recursive Contemplation](https://mlsanity.com/paper/2310.01320/) (2023)
- [Open-Endedness is Essential for Artificial Superhuman Intelligence](https://mlsanity.com/paper/2406.04268/) (2024)
- [Robust Autonomy Emerges from Self-Play](https://mlsanity.com/paper/2502.03349/) (2025)
- [GPUDrive: Data-driven, multi-agent driving simulation at 1 million FPS](https://mlsanity.com/paper/2408.01584/) (2024)
- [Honesty Is the Best Policy: Defining and Mitigating AI Deception](https://mlsanity.com/paper/2312.01350/) (2023)
- [RIME: Robust Preference-based Reinforcement Learning with Noisy Preferences](https://mlsanity.com/paper/2402.17257/) (2024)
- [The Consensus Game: Language Model Generation via Equilibrium Search](https://mlsanity.com/paper/2310.09139/) (2023)
- [Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback](https://mlsanity.com/paper/2303.02738/) (2023)
- [Brain-inspired Computational Intelligence via Predictive Coding](https://mlsanity.com/paper/2308.07870/) (2023)
- [Adversarial Policies Beat Superhuman Go AIs](https://mlsanity.com/paper/2211.00241/) (2022)
- [ASP: Learn a Universal Neural Solver!](https://mlsanity.com/paper/2303.00466/) (2023)
- [A Survey on Self-play Methods in Reinforcement Learning](https://mlsanity.com/paper/2408.01072/) (2024)
- [Beyond CAGE: Investigating Generalization of Learned Autonomous Network Defense Policies](https://mlsanity.com/paper/2211.15557/) (2022)
- [DSGBench: A Diverse Strategic Game Benchmark for Evaluating LLM-based Agents in Complex Decision-Making Environments](https://mlsanity.com/paper/2503.06047/) (2025)
- [Building reliable sim driving agents by scaling self-play](https://mlsanity.com/paper/2502.14706/) (2025)
- [General Intelligence Requires Rethinking Exploration](https://mlsanity.com/paper/2211.07819/) (2022)
- [Magnetic Preference Optimization: Achieving Last-iterate Convergence for Language Model Alignment](https://mlsanity.com/paper/2410.16714/) (2024)
- [SwarmBrain: Embodied agent for real-time strategy game StarCraft II via large language models](https://mlsanity.com/paper/2401.17749/) (2024)
- [Enhancing Rating-Based Reinforcement Learning to Effectively Leverage Feedback from Large Vision-Language Models](https://mlsanity.com/paper/2506.12822/) (2025)
- [Doubly Optimal No-Regret Learning in Monotone Games](https://mlsanity.com/paper/2301.13120/) (2023)
- [Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms](https://mlsanity.com/paper/2406.10631/) (2024)
- [Adaptive Advantage-Guided Policy Regularization for Offline Reinforcement Learning](https://mlsanity.com/paper/2405.19909/) (2024)
- [PUZZLES: A Benchmark for Neural Algorithmic Reasoning](https://mlsanity.com/paper/2407.00401/) (2024)
- [Reevaluating Policy Gradient Methods for Imperfect-Information Games](https://mlsanity.com/paper/2502.08938/) (2025)
- [Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Games](https://mlsanity.com/paper/2207.06541/) (2022)
- [Adapting to game trees in zero-sum imperfect information games](https://mlsanity.com/paper/2212.12567/) (2022)
- [Mastering Strategy Card Game (Legends of Code and Magic) via End-to-End Policy and Optimistic Smooth Fictitious Play](https://mlsanity.com/paper/2303.04096/) (2023)
- [Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games](https://mlsanity.com/paper/2303.12287/) (2023)

## Abstract (arXiv)

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 10535 nodes, i.e., 10175 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 10164 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.