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

Abstract

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.

References in corpus (4)

• DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker
• Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learning
• A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning
• From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization

Cited by in corpus (9)

• Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learning
• Harms from Increasingly Agentic Algorithmic Systems
• Student of Games: A unified learning algorithm for both perfect and imperfect information games
• Scalable Imaginary Time Evolution with Neural Network Quantum States
• Symbolic Equation Solving via Reinforcement Learning
• Canaries and Whistles: Resilient Drone Communication Networks with (or without) Deep Reinforcement Learning
• Neural Network-based Information Set Weighting for Playing Reconnaissance Blind Chess
• AI-Powered Augmented Reality as a Threat Vector for Human Manipulation
• Efficient representations for team and imperfect-recall equilibrium computation