AI Conquers Imperfect Information Games: How DeepNash Mastered Stratego

A Board Game That Long Stumped AI

After AI conquered complete information games like Go and chess, one seemingly simple board game continued to baffle artificial intelligence — Stratego. Unlike Go, where all pieces are fully visible to both players, Stratego is a classic imperfect information game: each player's piece identities are hidden from the opponent, and players must gradually uncover the enemy's layout through combat, deduction, and probing.

This very quality — the fact that most information is hidden — forms the core challenge in AI research. According to discussions in the HackerNews community, this breakthrough has sparked a new wave of attention around the limits of AI's game-playing capabilities.

Why Is Stratego Harder Than Go?

Combinatorial Explosion from Information Asymmetry

Although Go has a massive search space, it is fundamentally a complete information game — everything on the board is visible to both players. Stratego is different. Its game tree is enormous; research estimates the number of possible game states far exceeds that of Go, reaching roughly 10^535. More critically, players cannot know the true identity of each of their opponent's pieces when making decisions.

The AlphaGo Playbook Doesn't Apply

Traditional Monte Carlo Tree Search (MCTS) performs well in complete information games, but hits a wall when faced with hidden information. Players must reason under massive uncertainty while avoiding revealing their own intentions. This means AI must learn not only to "attack," but also to "conceal" and "deceive" — precisely the aspects that previous methods struggled to handle.

MCTS works by starting from the current game state and running large numbers of random simulations of future move sequences, tallying win rates along each path to estimate the value of each move. This approach succeeded in Go and chess because all information is known during simulation. In Stratego, however, the identities of the opponent's pieces are unknown, so assumptions must be made about hidden information during simulation. If these assumptions are handled poorly, the AI may generate a strategy that is optimal in an "imagined fully-observable world" but riddled with vulnerabilities in the actual hidden-information environment — a problem known in game theory as the imperfect recall trap. Simply assigning random identities to hidden pieces and running MCTS causes the AI to systematically overestimate the safety of certain attack lines, leaving it vulnerable to repeated exploitation by the opponent.

DeepNash's Solution: Converging on Nash Equilibrium

The key insight behind solving Stratego was to abandon traditional search-based methods and instead have the AI directly learn to approximate the Nash equilibrium strategy from game theory. A Nash equilibrium is a state in which both players are using optimal strategies, and neither can improve their outcome by unilaterally changing their own.

For an imperfect information game like Stratego, pursuing Nash equilibrium means the AI develops a robust strategy with appropriate randomness that is difficult for opponents to exploit. Rather than rigidly following a predictable playbook, it strikes a balance between unpredictability and effective offense. This approach is achieved through large-scale self-play reinforcement learning, learning end-to-end to make sound decisions under hidden information — without needing to manually search an enormous game tree.

DeepNash was developed by the DeepMind research team, and its core algorithm is based on a method called R-NaD (Regularized Nash Dynamics). Traditional reinforcement learning in self-play tends to fall into "cycles" — AI A defeats AI B, AI B improves and defeats A in return, and strategies oscillate between several local optima without ever converging to a truly robust equilibrium. R-NaD addresses this by introducing a regularization term into the training objective, providing a mathematically guaranteed convergence direction for strategy evolution, allowing the self-play process to stably approach Nash equilibrium rather than cycling aimlessly through strategy space. Notably, DeepNash does not rely on expert game records or human prior knowledge — it learns entirely from scratch through self-play, similar in spirit to AlphaZero, but facing far more complex challenges due to information hiding.

The Significance: From the Board to the Real World

The significance of conquering Stratego goes far beyond adding another game to AI's list of victories. A vast number of real-world problems are fundamentally imperfect information games — trade negotiations, traffic scheduling, cybersecurity offense and defense, and financial market strategy all involve participants who cannot access complete information.

An AI system capable of learning robust gameplay — and even appropriate bluffing — in highly information-obscured environments offers a new methodological reference for tackling these real-world challenges. It demonstrates that reinforcement learning combined with game-theoretic ideas can handle uncertain decision-making scenarios previously considered intractable.

Imperfect information games have a rigorous academic taxonomy. Stratego is classified as a two-player zero-sum imperfect information game, meaning one player's gain equals the other's loss, and both hold private information unknown to the other. Many complex real-world scenarios are even more challenging — they often involve multiple parties, are non-zero-sum, and feature more complex private information structures. Nevertheless, the theoretical tools developed for two-player zero-sum settings (such as methods for computing Nash equilibria) form the foundation for studying more complex scenarios. Previously, poker served as the iconic battleground for imperfect information AI research, with systems like Libratus and Pluribus achieving successive breakthroughs. What makes Stratego distinctive is its extremely long game sequences (a single game may last hundreds of moves) and continuously accumulating chains of inference, making strategic deception and information management far more complex than in poker.

A Measured Reception from the Community

Despite the exciting results, discussions on HackerNews maintained a degree of rationality. Some pointed out that there remains a significant gap between AI reaching expert-level performance in games with clear, well-defined rules and achieving equivalent performance on open-ended, ambiguously-defined real-world problems. Games provide clear reward signals and well-defined boundaries — conditions the real world often lacks.

Nonetheless, this breakthrough represents an important step forward in AI's long-term goal of "making decisions under uncertainty." It fills a crucial gap in AI's game-playing repertoire — the leap from complete information to imperfect information.

Conclusion

Stratego was one of the few remaining "hard nuts to crack" in AI game-playing, and its defeat marks genuine progress in artificial intelligence's ability to handle hidden information and strategic deception. For researchers, this is not merely another victory — it is a methodological expansion. When information is incomplete, training AI to approximate Nash equilibrium may be exactly the right direction toward real-world intelligent decision-making.