Neues KI-System Ataraxos schlägt Stratego-Spitzenspieler

Ein Spiel mit verdeckten Informationen

Stratego ist ein Zweipersonenspiel mit unvollständiger Information. Die Spieler ordnen 40 Figuren auf ihrer Brettseite an und bewegen sie über das Feld, um die Flagge des Gegners zu erobern. Die Identität jeder Figur bleibt geheim, bis zwei Figuren aufeinandertreffen. Dann scheidet die rangniedrigere aus.

Laut MIT gibt es mehr als 10 hoch 66 mögliche Anordnungen der Figuren, exponentiell mehr als beim Schach. Das macht das Spiel für KI-Systeme sehr schwierig, weshalb es oft als Benchmark für das strategische Denken leistungsfähiger Modelle dient.

Verdeckte Informationen verändern die Entscheidungsfindung. Sam Sokota, Hauptautor der Studie und Doktorand an der Carnegie Mellon, formulierte es so: „Je mehr man blufft, desto mehr rechnet der Gegner damit, und desto weniger ist jeder Bluff wert.“ Er stellte dies dem Schach gegenüber, „wo der beste Zug der beste Zug bleibt, egal wie oft man ihn schon gespielt hat“.

Dem Artikel zufolge setzten frühere Ansätze wie der von Googles DeepMind auf aufwendige Verfahren, die rechenintensiv und teuer waren. Selbst bei Trainingskosten in Millionenhöhe waren diese Modelle nicht stark genug, um Stratego-Spitzenspieler zu schlagen.

So funktioniert Ataraxos

Der Name stammt von einem griechischen Wort für jemanden, der unbeirrt und frei von Angst ist. Das System kombiniert zwei Hauptbestandteile.

• Reinforcement Learning durch Selbstspiel: Das Modell spielt viele Male gegen sich selbst, um eine starke „Blueprint-Strategie“ zu erlernen. Das Team entwarf besonders effiziente Algorithmen, damit Ataraxos schneller lernt als frühere Methoden und sich nicht darin verliert, jeden möglichen Zug vorhersagen zu wollen.
• Planung zur Entscheidungszeit: Während einer Partie geht Ataraxos von der Blueprint-Strategie aus und verfeinert seine Entscheidungen dann laufend. Ein generatives Modell schätzt mithilfe von Wahrscheinlichkeiten die wahrscheinliche Identität der verdeckten gegnerischen Figuren, und das System bewertet künftige Optionen, bevor es einen Zug auswählt.

Gabriele Farina, Assistant Professor für EECS am MIT und Seniorautor der Studie, sagte, der Ansatz erlaube es dem System, „genau auf das konkrete Brett und den jeweiligen Gegner zu fokussieren“. Den Einsatz dieses generativen Modells für die Planung zur Entscheidungszeit bezeichnet das MIT als das fehlende Puzzleteil für die übermenschliche Leistung.

Ergebnisse und Effizienz

Ataraxos schlug laut MIT den stärksten Stratego-Spieler der Welt mit einem Rekordergebnis von 15-1-4. Gegen Spitzenspieler bei der Stratego-Weltmeisterschaft erzielte es außerdem eine Bilanz von 39-2.

Zur Effizienz sagte Farina: „Unser System erreicht eine strikt höhere Spielstärke als DeepNash (das System von DeepMind) und braucht dafür weniger als ein Hundertstel der Trainingsbeispiele und weniger als ein Dreißigstel der Selbstspielpartien. Das zeigt eine enorme Effizienzsteigerung.“

Die Forschenden passten das System außerdem an andere Spiele mit unvollständiger Information an: Barrage Stratego, eine schnellere Variante mit weniger Figuren, Hanabi, ein kooperatives Kartenspiel für mehrere Spieler, und Dou dizhu, bei dem zwei Spieler gegen einen dritten zusammenarbeiten. In allen erreichte Ataraxos übermenschliche Leistung, was das Team als Beleg dafür anführt, dass sich die Methode verallgemeinern lässt.

Farina beschrieb auch die Spielweise des Bots: „Ein Mensch gerät womöglich in Panik, wenn seine wertvollste Figur aufgedeckt wird, doch der Bot kann erstaunlich gelassen bleiben. Er überkorrigiert nicht und gibt seine Geheimnisse nicht preis.“

Was das über Spiele hinaus bedeuten könnte

Die Forschenden sagen, das System ließe sich auf reale Probleme mit verdeckten Informationen übertragen, etwa Geschäftsverhandlungen, Cybersicherheit und militärische Manöver. Farina merkte an, dass man bei solchen Aufgaben „oft nicht den Luxus hat, alle Möglichkeiten durchzuspielen“.

Ein Einsatz steht allerdings nicht unmittelbar bevor. Das Team will in Ataraxos Maßnahmen zur Interpretierbarkeit einbauen, damit das System seine Entscheidungen so erklären kann, dass Menschen sie nachvollziehen können. „Menschen müssen das letzte Wort darüber haben, ob einer Empfehlung gefolgt wird. Bevor ein Einsatz möglich ist, brauchen wir also eine Möglichkeit, die Entscheidungen des Modells zu überprüfen“, sagte Farina.

Die Studie, zu deren Autoren auch Eugene Vinitsky von der NYU, Zico Kolter von der Carnegie Mellon, Hengyuan Hu von Stanford und Zhiyuan Fan vom MIT gehören, erscheint in Nature. Die Forschung wird unter anderem vom Office of Naval Research, dem Department of Civil and Urban Engineering der New York University, dem C2SMART Center, der National Science Foundation und einem Schmidt Sciences AI2050 Early Career Fellowship finanziert.