KI Ataraxos der CMU schlägt die besten menschlichen Stratego-Spieler

Ein System für verdeckte Informationen

Ataraxos wurde an der Kenneth C. Griffin School of Computer Science der Carnegie Mellon University entwickelt. Laut der Universität verbessert das Ergebnis die Fähigkeit von KI, Entscheidungen zu treffen, wenn wichtige Informationen verborgen sind.

Das Projekt leiteten Samuel Sokota, Doktorand für maschinelles Lernen an der CMU, und Gabriele Farina, der an der CMU in Informatik promoviert hat und heute Professor am Massachusetts Institute of Technology (MIT) ist. Zu den Mitwirkenden zählen Zico Kolter, Professor und Leiter des Machine Learning Department der CMU, Eugene Vinitsky, Professor an der New York University, Hengyuan Hu, Doktorand an der Stanford University, sowie Zhiyuan Fan, Doktorand am MIT.

Die CMU weist darauf hin, dass Stratego für KI-Forscher bereits eine anerkannte Herausforderung ist. Google DeepMind hatte zuvor ein starkes Stratego-System entwickelt, das jedoch nicht das Niveau der besten menschlichen Spieler erreichte.

Warum Stratego für KI so schwierig ist

Bei Stratego befehligt jeder Spieler eine Armee aus 40 Figuren mit unterschiedlichen Stärken. Die Spieler verbergen die Identität ihrer Figuren vor dem Gegner und versuchen zugleich, dessen Flagge zu erobern. Jeder Zug ist deshalb mit Unsicherheit verbunden.

Anders als beim Schach müssen die Spieler aus begrenzten Hinweisen ableiten, was der Gegner plant. Das Verhalten eines Gegners kann etwas über dessen Strategie verraten, ohne Gewissheit über den Plan zu geben. Bei 40 Figuren pro Seite ist die Zahl möglicher verdeckter Konfigurationen enorm, sodass eine KI nicht einfach jede denkbare Stellung betrachten und das Ergebnis berechnen kann. Stattdessen muss sie auf Grundlage des bisherigen Spielverlaufs abwägen, was verborgen sein könnte und wie wahrscheinlich jede Möglichkeit ist.

So funktioniert Ataraxos

Die Forscher kombinierten zwei Ansätze. Zunächst spielt das System per Reinforcement Learning gegen sich selbst und erlernt dabei schrittweise eine allgemeine Strategie für Stratego. Das liefert ihm eine starke Ausgangsbasis für jede Partie.

Ataraxos folgt dieser Strategie jedoch nicht einfach. Vor jedem Zug nutzt es eine Technik namens Decision-Time Planning, um seine Optionen für die konkrete Partie neu zu bewerten. Ein generatives Modell schätzt dabei die wahrscheinlichen Identitäten der verdeckten gegnerischen Figuren. So kann das System mögliche künftige Züge betrachten, ohne jede denkbare Konfiguration des Spielbretts berücksichtigen zu müssen.

Die Arbeit baut auf einer langen Forschungstradition zu Entscheidungen bei verdeckten Informationen auf. Die CMU verweist auf Tuomas Sandholm, Angel Jordan University Professor of Computer Science an der Universität, der seit Jahrzehnten KI-Systeme für Szenarien mit unvollständigen oder komplexen Informationen entwickelt. Seine KI-Pokersysteme haben Spitzenprofis geschlagen.

Was das über Spiele hinaus bedeuten könnte

Die CMU sagt, die Techniken könnten KI-Systemen langfristig helfen, mit realen Situationen umzugehen, in denen mehrere Entscheider unterschiedliche Informationen und konkurrierende Ziele haben, etwa an Finanzmärkten oder bei Verhandlungen.

"Viele Entscheidungen in der realen Welt betreffen andere Entscheider, deren Informationen und Interessen sich von unseren unterscheiden", sagte Sokota. "Wir wollen allgemeine Methoden entwickeln, die solche Situationen effektiv und mit praktikablem Rechenaufwand bewältigen können. Die Stratego-Ergebnisse zeigen, wie weit wir dabei gekommen sind."

Farina ordnete das Ergebnis in die Tradition von Spielen als Forschungsmeilensteine ein. "Schach lieferte frühe Maßstäbe für maschinelle Intelligenz. Poker brachte eine weitere Schwierigkeitsstufe, weil die Spieler verdeckte Informationen über ihre Karten haben. Stratego treibt diese Herausforderung weiter, denn die KI muss Entscheidungen treffen und dabei mit einer deutlich größeren Menge verborgener Informationen umgehen", sagte er.

Spiele bieten kontrollierte Umgebungen mit klar definierten Regeln, Aktionen und Zielen, und die Leistung lässt sich mit der von versierten menschlichen Spielern vergleichen. Die Forschung wurde teilweise vom Office of Naval Research und der National Science Foundation finanziert.