Ataraxos: Neue KI knackt Stratego als eines der letzten Brettspiele, in denen Menschen überlegen waren

Niemeijer gilt als der am höchsten dekorierte Spieler in der Geschichte des Spiels: Er gewann vier Weltmeisterschaften, 15 niederländische Meistertitel sowie zwei Online-Weltmeisterschaften und führte mehr als 600 Wochen die Weltrangliste an. Laut George Franka, dem einzigen Spieler, der seit 1997 an jeder Weltmeisterschaft teilgenommen hat, sei Niemeijer "der beste Stratego-Spieler aller Zeiten".

Stratego gilt als besonders harte Prüfung für KI, weil beide Seiten ihre 40 Figuren verdeckt aufstellen. Laut dem Paper gibt es mehr als 10³³ mögliche Aufstellungen. In solchen Spielen mit unvollständiger Information hänge der Wert eines Zuges nicht nur davon ab, wie danach weitergespielt werde, sondern auch vom Verhalten vor und während der Entscheidung, schreibt Erstautor Samuel Sokota auf X.

Verfahren aus der Poker-KI umgingen dieses Problem zwar, so Sokota, allerdings nur bei wenig verborgener Information. Im Texas Hold'em gibt es lediglich 1.326 mögliche Starthände, und der Aufwand dieser Methoden wächst laut dem Paper mit der Menge versteckter Information. Stratego sei deshalb eines der letzten großen Wettkampfbrettspiele gewesen, in denen Menschen der KI überlegen blieben.

Millionenbudget gegen Uni-Rechner

Genau an diesem Spiel war zuvor DeepMind nicht über das Niveau der Spitzenspieler hinausgekommen. Das System DeepNash wurde laut dem Paper auf 1.024 TPU-Knoten trainiert, nach Erinnerung des korrespondierenden DeepNash-Autors zwei bis drei Monate lang. Zu Preisen von 2025 entspräche das nach Rechnung der Ataraxos-Autoren drei bis 4,5 Millionen US-Dollar.

Ataraxos kam dagegen mit einer Woche auf 16 Nvidia-H100-GPUs und weiteren vier Tagen auf vier GPUs für das sogenannte Belief-Netz aus, was zu Preisen von 2025 weniger als 8.000 Dollar koste. Das entspreche etwa einem Fünfhundertstel der Rechenkosten, einem Dreißigstel der Self-Play-Partien und einem Hundertstel der Trainingsbeispiele. Die Forscher führen das nicht nur auf ihren eigens geschriebenen GPU-Simulator zurück, sondern auf eine deutlich höhere Sample-Effizienz. Man sei auf akademische Rechenressourcen beschränkt gewesen und habe über die Jahre zahlreiche Tricks gefunden, schreibt Sokota.

Einen direkten Vergleich der beiden Systeme gibt es nicht. Die Forscher boten DeepMind nach eigenen Angaben an, die nötige Infrastruktur zu bauen. DeepMind habe jedoch geantwortet, das sei nicht möglich, weil der Code von DeepNash nicht mehr funktionsfähig sei. Bei der Weltmeisterschaft 2023 hatte DeepNash 19 von 28 Partien gewonnen, aber gegen die meisten Topspieler verloren, darunter Niemeijer.

Ein Lernverfahren, das sich selbst bremst

Ataraxos lernt ohne menschliche Daten, ausschließlich durch Partien gegen sich selbst. Entscheidend ist dabei laut dem Paper, wie stark das System zur Abwechslung gezwungen wird. Eine zusätzliche Bedingung im Training sorgt dafür, dass die KI ihre Aufstellungen und Züge breit streut, statt sich früh auf eine feste Strategie festzulegen. Fachleute sprechen von Regularisierung. Für Stratego ist das wichtig, weil starkes Spiel laut den Autoren viel Zufall erfordert: Wer berechenbar spielt, lässt sich ausnutzen.

Diesen Zwang zur Vielfalt lockern die Forscher im Lauf des Trainings und stimmen die Größe der Lernschritte darauf ab. Anfangs streut Ataraxos stark und lernt in großen Sprüngen, später spielt es gezielter und korrigiert sich nur noch in kleinen Schritten. Das verhindere, dass das Lernen im Kreis läuft oder chaotisch wird, wie es bei unvollständiger Information sonst geschehe. Die Forscher vergleichen die Regularisierung mit einer Energiereserve: Werde sie zu schnell abgebaut, mache die KI zunächst rasche Fortschritte, verliere dann aber die Fähigkeit, weiter zu lernen, und lasse sich oft leicht ausnutzen.

Hinzu kommt ein Belief-Netz, das die Typen der verdeckten gegnerischen Figuren vorhersagt. Vor jedem Zug erzeugt Ataraxos damit mögliche Spielzustände, spielt Kandidatenzüge durch und führt einen zusätzlichen Lernschritt nur für die aktuelle Entscheidung aus. Bisherige Arbeiten hatten laut den Autoren auf eine solche Suche verzichtet, weil sie bei so viel verborgener Information als zu schwierig galt.

Klarer Sieg trotz Handicap

Die Serie gegen Niemeijer verteilten die Forscher auf drei Wochen, um Ermüdung zu vermeiden und ihm Zeit zur Vorbereitung zu geben. Niemeijer wusste, dass sich Ataraxos nicht an sein Spiel anpassen würde. Er erhielt 1.000 Dollar für die Teilnahme sowie 100 Dollar pro Sieg und 50 Dollar pro Remis, damit sich Leistung für ihn auch finanziell lohnte.

Die effektive Siegquote von 85 Prozent, bei der Remis halb zählen, sei auf höchstem Niveau ohne Beispiel, schreiben die Autoren. Laut dem dreimaligen Vize-Weltmeister Max Roelofs seien die Abstände an der Spitze hauchdünn, weil im Spiel zwangsläufig Risiken eingegangen werden müssten. Dabei hatte die KI einen strukturellen Nachteil: Niemeijer konnte sich über viele Partien auf sie einstellen, sie sich aber nicht auf ihn. Der dreimalige Weltmeister Vincent de Boer wertet das laut Paper als großes Handicap.

Bei einer Vorführung auf der Stratego-Weltmeisterschaft 2025 gewann Ataraxos zudem 38 von 40 Partien gegen Turnierteilnehmer. Spieler beschreiben seinen Stil als schwer durchschaubar: Die KI nutze Bluffs, die Menschen für zu riskant hielten, und verzögere im Rückstand so hartnäckig, dass manche das als unhöflich empfänden. Sie wirke zudem fast unheimlich glücklich, weil ihre Figuren stets am richtigen Ort zu stehen scheinen. Die Partien gegen Niemeijer sind online einsehbar.

Mehr als ein Stratego-Trick

Mit derselben Methode bauten die Forscher weitere Systeme. In der Variante Barrage Stratego gewann ihre KI vier Serien über je 50 Partien gegen drei der vier bestplatzierten Spieler, allesamt zweifache Barrage-Weltmeister. Im kooperativen Kartenspiel Hanabi erreichte sie in allen Varianten neue Bestwerte, in der Zwei-Spieler-Version mit zwei Größenordnungen weniger Rechenaufwand als der bisherige Spitzenreiter. Im chinesischen Kartenspiel Dou dizhu schlug sie die bisherigen Referenzsysteme PerfectDou und DouZero.

Die Autoren leiten daraus einen weitreichenden Anspruch ab: Große Mengen verborgener Information seien für Reinforcement Learning und Suche kein Hindernis mehr. Praktisch einsetzbare KI rücke damit für viele strategische Entscheidungsprobleme in Reichweite, sofern sich schnelle und genaue Simulatoren dafür bauen ließen. Als Beispiele für Situationen mit unvollständiger Information nennt das Paper Finanzmärkte, militärische Konflikte und Verhandlungen.

Eine Grenze benennen die Forscher selbst: Weil die Suche nur einen einzelnen Lernschritt nachahme, lasse sich ihre Leistung nicht beliebig durch mehr Rechenzeit steigern. Ein ausgefeilteres Suchverfahren könnte das ändern. Den Code für Ataraxos haben sie öffentlich zugänglich gemacht.