Artificial intelligence has conquered another classic board game, but this time the challenge was not simply finding the best move.

Researchers have developed an AI system called Ataraxos that defeated one of the world’s most accomplished Stratego players in a 20 game match. The system won 15 games, lost one and drew four, marking what the researchers describe as the first superhuman result in Stratego. The findings were published in Nature on September 30.

Why Stratego Has Been So Difficult for AI

Stratego looks somewhat like chess, but the information available to each player is dramatically different.

Each player secretly arranges 40 pieces on a 10 by 10 board. Players can see where their opponent’s pieces are located, but they cannot see the identity or rank of those pieces until a battle reveals it.

That creates a huge number of possible board configurations. Researchers say Stratego has more than 10 to the 33rd possible piece configurations, making it an unusually difficult test for artificial intelligence.

Unlike chess, where both players can see the entire board, Stratego requires players to make decisions while constantly working with information they do not have.

Ataraxos Takes a Different Approach

The research team combined self play reinforcement learning with decision time planning to create Ataraxos.

During training, the AI played against itself repeatedly to develop a strong overall strategy. When playing an actual opponent, it then uses additional planning to evaluate possible moves based on what it believes may be hidden on the board.

A separate generative model helps Ataraxos estimate the likely identities of hidden pieces. Instead of attempting to examine every possible board arrangement, the system focuses on plausible scenarios and evaluates how different decisions could play out.

That approach helped the researchers overcome one of the biggest problems that had limited previous Stratego systems.

The AI Beat a Top Stratego Player

Ataraxos faced Pim Niemeijer, described by the researchers as the most decorated Stratego player of all time.

Across a 20 game series, Ataraxos recorded 15 wins, one loss and four draws. The researchers said the margin was unprecedented at the highest level of Stratego competition.

The system also reportedly achieved a 39 and 2 record against top human players at the Stratego world championship, according to MIT’s account of the research.

The result is notable because earlier AI efforts had spent substantial computing resources trying to solve Stratego without reaching superhuman performance.

Ataraxos Uses Far Less Computing Power

The researchers say Ataraxos reached a higher playing strength than DeepMind’s earlier Stratego system, DeepNash, while using less than one hundredth of the training examples and less than one thirtieth of the self play games.

Nature reports that the Stratego system was trained for only a few thousand dollars, a striking difference from previous industrial research efforts that involved millions of dollars in computing costs.

That efficiency could be one of the most important parts of the research. The breakthrough is not simply that an AI can play Stratego at an elite level, but that researchers found a more economical way to handle enormous amounts of hidden information.

The Research Goes Beyond Stratego

The researchers also tested the underlying techniques on other games.

They developed an AI for Barrage Stratego that defeated top human players, including multiple world champions. They also reported state of the art results in Hanabi and dou dizhu, two games that involve different forms of hidden information and strategic decision making.

That broader testing suggests the approach is not limited to one board game.

What Stratego Could Teach AI

The researchers say problems involving hidden information are common outside games.

Business negotiations, financial markets and other strategic situations can involve people making decisions without knowing everything their competitors know. The researchers believe techniques developed for Stratego could eventually help AI systems reason through some of these situations.

That does not mean Ataraxos is ready to handle real world decisions on its own. Stratego has fixed rules and a clearly defined objective, while real situations are considerably more complicated.

Still, the research offers a new example of how AI can make decisions when it cannot see the entire picture.

A New Chapter for Game Playing AI

Chess, Go and poker have already served as major proving grounds for artificial intelligence. Stratego presented a different challenge because much of the information needed to make a decision remains hidden.

Ataraxos has now demonstrated that an AI can achieve superhuman performance in that environment while using substantially fewer resources than earlier approaches.

For researchers, the bigger question may no longer be whether AI can handle hidden information, but how broadly these techniques can be applied to other problems where the next move depends on what an opponent might be keeping secret.