Mastering the game of Stratego with model-free multiagent reinforcement learning

2022/06/30 by Julien Pérolat, Julien Perolat, Bart de Vylder +38 · 6 voices · 21 citations
Computer Science · Decision Sciences · #Reinforcement Learning in Robotics #Artificial Intelligence in Games #Advanced Bandit Algorithms Research

paper · pdf · doi:10.1126/science.add4679

Abstract

We introduce DeepNash, an autonomous agent that plays the imperfect information game Stratego at a human expert level. Stratego is one of the few iconic board games that artificial intelligence (AI) has not yet mastered. It is a game characterized by a twin challenge: It requires long-term strategic thinking as in chess, but it also requires dealing with imperfect information as in poker. The technique underpinning DeepNash uses a game-theoretic, model-free deep reinforcement learning method, without search, that learns to master Stratego through self-play from scratch. DeepNash beat existing state-of-the-art AI methods in Stratego and achieved a year-to-date (2022) and all-time top-three ranking on the Gravon games platform, competing with human expert players.

Citations

• DeepStack: Expert-level artificial intelligence in heads-up no-limit poker
• Non-Cooperative Games

Cited by

• The Curvature Shadow: An Apparent Failure of Maximum-Entropy Equilibrium Selection is a Removable Artifact
• SportD: Can VLMs Physically Strategize?
• Reevaluating Policy Gradient Methods for Imperfect-Information Games
• Robust Autonomy Emerges from Self-Play
• GAE Falls Short in Imperfect-Information Self-Play Reinforcement Learning
• A Direct Second-Order Method for Solving Two-Player Zero-Sum Games
• Diffusion Policies with Value-Conditional Optimization for Offline Reinforcement Learning
• Superhuman AI for Stratego Using Self-Play Reinforcement Learning and Test-Time Search
• Outbidding and Outbluffing Elite Humans: Mastering Liar's Poker via Self-Play and Reinforcement Learning
• Solving Continuous Mean Field Games: Deep Reinforcement Learning for Non-Stationary Dynamics
• Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoretic Approach
• Nash Policy Gradient: A Policy Gradient Method with Iteratively Refined Regularization for Finding Nash Equilibria
• Tight Regret Upper and Lower Bounds for Optimistic Hedge in Two-Player Zero-Sum Games
• Look-ahead Reasoning with a Learned Model in Imperfect Information Games
• On the O(1/T) Convergence of Alternating Gradient Descent-Ascent in Bilinear Games
• STAIR: Addressing Stage Misalignment through Temporal-Aligned Preference Reinforcement Learning
• Which Nash Equilibrium? Solver-Dependent Selection on Zero-Sum Nash Polytopes
• Efficient representations for team and imperfect-recall equilibrium computation
• Efficient Last-Iterate Convergence in Regret Minimization via Adaptive Reward Transformation
• Last-Iterate Convergence in Adaptive Regret Minimization for Approximate Extensive-Form Perfect Equilibrium
• Policy Learning from Large Vision-Language Model Feedback without Reward Modeling

Discussions

• Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learning [hn, 131 points, 77 comments]
• The GDM paper on Stratego doesn't cite any papers by their titles?!? If you go look at the bibliography there just aren't titles for the papers listed. I sure how there aren't multiple papers that ma [bsky, 17 points, 5 comments]
• DeepMind: Mastering the Game of Stratego with Model-Free Multiagent RL [hn, 3 points, 0 comments]
• DeepNash: Mastering the Game of Stratego with Model-Free Multiagent RL [hn, 2 points, 0 comments]
• Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learning [hn, 2 points, 0 comments]
• Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learning [hn, 1 points, 0 comments]

Related

• Superhuman AI for Stratego Using Self-Play Reinforcement Learning and Test-Time Search
• Reinforcement Learning in Strategy-Based and Atari Games: A Review of Google DeepMinds Innovations
• Deep Reinforcement Learning to Master the Asymmetric Strategy of Baghchal
• Reinforcing Competitive Multi-Agents for Playing 'So Long Sucker'
• Deep RTS: A Game Environment for Deep Reinforcement Learning in\n Real-Time Strategy Games