Superhuman AI for Stratego Using Self-Play Reinforcement Learning and Test-Time Search

Samuel Sokota, Eugene Vinitsky, Hengyuan Hu, J. Zico Kolter, Gabriele Farina · 2025

Read Superhuman AI for Stratego Using Self-Play Reinforcement Learning and Test-Time Search by Samuel Sokota, Eugene Vinitsky, Hengyuan Hu, J. Zico Kolter, Gabriele Farina (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-07312.txt.

Introduction

Samuel Sokota and five co-authors present Ataraxos, an AI that plays Stratego at superhuman level. Hidden information defeats standard reinforcement learning and search, and despite multimillion-dollar industrial efforts, top human Stratego play had resisted AI. Ataraxos combines general tools the team developed for self-play reinforcement learning and for test-time search under hidden information, rather than game-certain engineering.

It defeated the most decorated human Stratego player of all time by a large margin, the first superhuman result in the game's history. Using orders of magnitude less compute and data than earlier efforts. The same tools produced a superhuman Barrage Stratego player and state-of-the-art systems for Hanabi and dou dizhu. The authors argue this establishes a reusable design pattern for adversarial, cooperative, and team games saturated with hidden information.

Catalog record

CREATORSamuel Sokota, Eugene Vinitsky, Hengyuan Hu, J. Zico Kolter, Gabriele Farina
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE75 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-07312

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Superhuman AI for Stratego Using Self-Play Reinforcement Learning and Test-Time Search Samuel Sokota, Eugene Vinitsky, Hengyuan Hu, J. Zico Kolter, Gabriele Farina Abstract Few classical games have been regarded as such significant benchmarks of artificial intelligence as to have justified training costs in the millions of dollars. Among these, Stratego—a board wargame exemplifying the challenge of strategic decision making under massive amounts of hidden information—stands apart as a case where such efforts failed to produce performance at the level of top humans. This work establishes a step change in both performance and cost for Stratego, showing that it is now possible not only to reach the level of top humans, but to achieve vastly superhuman level—and that doing so requires not an industrial budget, but merely a few thousand dollars. We achieved this result by developing general approaches for self-play reinforcement learning and test-time search under imperfect information. Stratego is a board wargame resembling military chess (see Figure 1 ). It is distinctive among classical games regarded as major benchmarks of artificial intelligence (AI) in that it possesses a massive amount of hidden information. This contrasts not only with games that have no hidden information, like chess and Go, but also with games that have so little that AI systems can explicitly enumerate all possibilities, like Texas hold’em. The approaches that achieved superhuman performance in these other games [ 8 , 29 , 37 , 38 , 30 , 42 , 6 , 7 , 3 ] cannot even be meaningfully applied in settings with as much hidden information as Stratego. Stratego also stands apart for its sheer difficulty as a benchmark. It has been the subject of research efforts spanning multiple years, involving dozens of researchers, and culminating in the expenditure of computational resources with commercial costs in the millions of dollars [ 22 ] . Yet, top human players have remained superior, perhaps making it the only classical game in which such well-resourced efforts failed to produce superhuman performance. In this work, we introduce Ataraxos, an AI for Stratego. In a 20-game series, Ataraxos defeated the most decorated Stratego player of all time by a margin of victory unprecedented at the highest level of play: 15 wins, 4 draws, and 1 loss. Ataraxos achieved this result while only costing a few thousand dollars to train. This simultaneous step change in performance and cost was made possible by innovations in reinforcement learning and search. The simplicity and generality of these innovations suggest that superhuman decision-making systems may now be attainable at modest computational cost in many strategic settings. Figure 1 : An illustration of the game of Stratego. A The starting position of a game from the perspective of the red player. Each player arranges their pieces in secret, so the types of the blue pieces are concealed from the red player (and vice versa). From this starting position, the players alternate moves, each of which is defined by the displacement of a single piece, as in as chess. B A move in the game for the blue player. On this move, because a blue piece moves onto a square occupied by a red piece, there is a battle. During a battle, the types of both pieces are revealed and at least one of the two is captured (determined based on their types and attack-defense roles). If a Flag (see piece on a1) is captured in battle, the capturing player wins the game. 1 The Challenge of Imperfect Information Imperfect information is a term of art that describes interactions in which it is possible for some agents to possess information that others do not. It is a core feature of many real-world settings: in financial markets, traders may not observe the rationales of trades made by others; in military operations, forces may have incomplete intelligence about enemy positions and capabilities; and in negotiations, parties may lack knowledge about the priorities and constraints of their counterparts. Such settings contrast with perfect-information games, such as chess and Go, in which agents possess all strategically relevant information. This distinction has important consequences. In games like chess and Go, the conceptual right thing to do is obvious: select a move that maximizes the value of the resulting position. But under imperfect information, it is much less clear. The value of a decision depends not only on the policies agents employ thereafter, but also on the policies agents used—and counterfactually would have used—prior to and at the time of the decision (as these all affect the posterior distribution over hidden information). As illustrated by Figure 2 , even reasoning in isolation about the dependencies among contemporaneous counterfactuals is complex; incorporating dependencies across time is harder still. Figure 2 : Graphical representation of differential relationships between decision frequencies and values among contemporaneous counterfactuals under imperfect information. Nodes represent decisions. The color/dash pattern of an edge represents whether changing the frequency of a decision on one end of the edge increases (blue/solid) or decreases (brown/dashed) the marginal value of the decision on the other end of the edge. The interconnectedness of frequencies and values across decisions makes it difficult to intuit the frequencies with which decisions should be made. These dependencies have made developing AI for imperfect-information games challenging. The most successful approaches use sophisticated problem transformations based on public information [ 20 , 5 , 4 , 3 , 32 ] . But the cost of these transformations scales with the amount of hidden information, making them applicable only to games with small amounts of hidden information, like Texas hold’em (in which there are only 1,326 possible hands). Due to this fundamental limitation, and the absence of an alternative practical foundation, strategic decision making in settings with large amounts of hidden information has remained an open problem, as exemplified by sustained human supremacy at Stratego (in which there are over 10^{33} piece configurations). 2 Description of Ataraxos This work introduces Ataraxos, an AI for Stratego based on tabula rasa self-play reinforcement learning and test-time search. The core innovation that enables Ataraxos to leverage reinforcement learning and search where past approaches have floundered is a coordinated interplay of regularization strength, policy update size, and policy strength. Ataraxos employs strong regularization and aggressive updates when the policy is weak, and weak regularization and small policy updates when the policy is strong. Two complementary mechanisms motivate this interplay. First, keeping update sizes commensurate with regularization strength damps the otherwise cyclical, divergent, or chaotic learning dynamics engendered by imperfect information, leading to stable progress. Second, adapting both quantities to policy strength creates rapid improvements when the policy is weak and continued improvement when the policy is strong—avoiding both update sizes so small as to make improvements impractical and regularization so large as to compromise the policy. These mechanisms together beget a policy improvement operator that remains reliable and productive throughout training- and test-time, driving Ataraxos to superhuman strategic decision making under massive amounts of hidden information. 2.1 Interdependent Self-Play Reinforcement Learning Processes The foundation of Ataraxos is its self-play reinforcement learning module. This module comprises two separate but interdependent self-play processes associated with the two phases of Stratego. The first phase, wherein players privately determine starting positions for their

Read the complete text