Ataraxos beats Stratego champion Niemeijer 15-1-4 in Nature

An AI system called Ataraxos beat Pim Niemeijer, described by its authors as 'the most decorated Stratego player of all time,' 15 wins to 1 across a 20-game series with 4 draws, in a result published in Nature on 30 September. The paper, from researchers at Carnegie Mellon, MIT, NYU and Stanford, reports it as the first superhuman performance in Stratego's history.

The training bill was roughly $8,000. The authors estimate DeepMind's prior DeepNash would cost $3 million to $4.5 million at current prices to reproduce.

'Our system reaches strictly higher playing strength than DeepNash while using less than one hundredth of the training examples and less than one thirtieth of the self-play games,' MIT's Gabriele Farina says. The authors credit a technique coordinating regularisation strength and policy update size during training. The three-piece architecture, a policy-value network, a belief network for the hidden pieces, and test-time search, generalised beyond Stratego: the same recipe produced a superhuman Barrage Stratego agent and state-of-the-art results on Hanabi and Dou Dizhu, beating prior systems PerfectDou and DouZero with statistical significance.

Stratego is hard precisely because so much is hidden. 'With Stratego, there is an explosion of possible universes you might have to deal with,' Farina told MIT News. Lead author Samuel Sokota at Carnegie Mellon put the bluffing problem flatly: 'The more you bluff, the more your opponent expects it, and the less each bluff is worth. It's not obvious how to reason about that.' Across top-player matches at the world championship, Ataraxos went 39-2. Two of the researchers we follow posted the Nature link the same day.

The paper's own closing claim: 'The success of this approach across adversarial, cooperative and team games establishes a design pattern for reinforcement learning and search that is effective under large amounts of hidden information.'