CMU's Ataraxos AI Beats Top Human Players at Stratego

A system built for hidden information

Ataraxos was developed at Carnegie Mellon's Kenneth C. Griffin School of Computer Science. According to the university, the result advances the ability of AI to make decisions when important information is hidden.

The project was led by Samuel Sokota, a CMU machine learning Ph.D. student, and Gabriele Farina, who earned his Ph.D. in computer science at CMU and is now a professor at the Massachusetts Institute of Technology (MIT). Collaborators include Zico Kolter, professor and head of CMU's Machine Learning Department; Eugene Vinitsky, professor at New York University; Hengyuan Hu, a Ph.D. student at Stanford University; and Zhiyuan Fan, a Ph.D. student at MIT.

CMU notes that Stratego is already a recognized challenge for AI researchers. Google's DeepMind previously developed a strong Stratego-playing system, but it did not reach the level of the best human players.

Why Stratego is so hard for AI

In Stratego, each player commands a 40-piece army made up of pieces with different strengths. Players hide the identities of their pieces from the opponent while trying to capture the opponent's flag. Every move therefore involves some uncertainty.

Unlike chess, players must infer what the opponent is planning from limited clues. An opponent's behavior might reveal something about their strategy without giving certainty about their plan. With 40 pieces per side, the number of possible hidden configurations is enormous, so an AI cannot simply consider every possible position and calculate the outcome. Instead, it has to reason about what might be hidden and how likely each possibility is, based on what has happened so far.

How Ataraxos works

The researchers combined two approaches. First, the system uses reinforcement learning to play games against itself, gradually learning a general strategy for Stratego. This gives it a strong starting point for approaching a game.

Ataraxos does not simply follow that strategy, however. Before each move, it uses a technique called decision-time planning to reconsider its options for the specific game it is playing. A generative model estimates the likely identities of the opponent's hidden pieces. This lets the system consider possible future moves without accounting for every possible configuration of the board.

The work builds on a long line of research into decision-making with hidden information. CMU points to Tuomas Sandholm, the university's Angel Jordan University Professor of Computer Science, who has spent decades developing AI systems for scenarios with imperfect or complex information. His AI poker systems have beaten top professional players.

What it could mean beyond games

CMU says the techniques could eventually help AI systems handle real-world situations in which multiple decision-makers have different information and competing goals, such as financial markets and negotiations.

"Many real-world decisions involve other decision-makers whose information and interests differ from our own," Sokota said. "We want to develop general methods that can handle these situations effectively and at a practical computational cost. The Stratego results show how much progress we've made."

Farina placed the result in the tradition of games as research milestones. "Chess provided early benchmarks for machine intelligence. Poker gave another layer of difficulty because players have hidden information about their cards. Stratego pushes that challenge further, requiring AI to make decisions while facing a much larger amount of hidden information," he said.

Games offer controlled environments with clearly defined rules, actions and goals, and performance can be measured against skilled human players. The research was partially funded by the Office of Naval Research and the National Science Foundation.