CMU Researchers Develop AI That Tackles Hidden Information in Stratego

Researchers from Carnegie Mellon University's Kenneth C. Griffin School of Computer Science have developed an AI system called Ataraxos that can outperform even the best human players in Stratego, a classic board game in which participants must make decisions without knowing the identity of their opponent's pieces.

The work, published in Nature, advances AI's ability to make decisions when important information is hidden. The techniques could eventually help AI systems navigate real-world situations where multiple decision-makers have different information and competing goals, from financial markets and negotiations to other complex situations where the best decision depends on what others might do.

"Many real-world decisions involve other decision-makers whose information and interests differ from our own," said Samuel Sokota, a CMU machine learning Ph.D. student. "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."

The achievement is particularly notable because Stratego has already emerged as a major challenge for AI researchers. Google's DeepMind previously developed a strong Stratego-playing system but did not reach the level of the best human players.

In addition to Sokota, the project was led by Gabriele Farina, who earned his Ph.D. in computer science at CMU and is currently a professor at the Massachusetts Institute of Technology (MIT). They collaborated with Zico Kolter, professor and head of CMU's Machine Learning Department; Eugene Vinitsky, professor at New York University; Hengyuan Hu, Ph.D. student at Stanford University; and Zhiyuan Fan, Ph.D. student at MIT.

In Stratego, each player commands a 40-piece army made up of pieces with different strengths. Players hide the identities of their pieces from their opponent while trying to capture the opponent's flag. Because players do not know what pieces their opponent has, every move involves some uncertainty.

Stratego may seem like an unusual proving ground for AI, but its complexity makes it an especially useful test. Unlike games like chess, players must infer what their opponent is planning based on limited clues when plotting their next move. An opponent's behavior might reveal something about their strategy without providing certainty about their plan.

That uncertainty makes Stratego an especially difficult test for AI. With 40 pieces for each player, there are an enormous number of possible hidden configurations, so an AI system cannot merely consider every possible position and calculate what would happen. Instead, it must reason about what might be hidden and the likelihood of different possibilities based on what has happened so far.

The researchers developed Ataraxos using two complementary approaches. First, the system uses reinforcement learning to play games against itself, gradually learning a general strategy for playing Stratego. This experience gives the system a strong starting point for deciding how to approach a game.

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

The work builds on a long history of AI research into decision-making with hidden information. Tuomas Sandholm, CMU's Angel Jordan University Professor of Computer Science, has spent decades developing AI systems for scenarios with imperfect or complex information. His AI poker systems have beaten top professional players, and his work helped establish games with hidden information as important tests for AI systems that must reason under uncertainty.

Sokota and Farina see Stratego as more than a difficult board game. Games provide AI researchers with controlled environments where they can test whether a system can solve a particular type of decision-making problem. The rules, possible actions and goals are clearly defined, and the system's performance can be measured against skilled human players.

"Stratego is a game, of course, but I think we're actually lucky that we have these board games," Farina said. "Games have often served as milestones for AI research. 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."

This research was partially funded by the Office of Naval Research and the National Science Foundation. To learn more, read the article in Nature.