Mit vielen verborgenen Informationen hatte das Spiel Stratego die KI bisher überlistet.

Eine Truppe von 40 Figuren, die jeweils einen verborgenen Rang von Marschall bis Spion tragen, ist nun endlich von einer kostengünstigen Maschine entschlüsselt worden. Das Spiel ist Stratego, und das Programm, das es gelöst hat, heißt Ataraxos. Es besiegte Pim Niemeijer, der als der größte Stratego-Spieler aller Zeiten gilt, mit 15:1, bei vier Unentschieden.

Stratego hat den Aufstieg der Maschinen schon seit Jahrzehnten standgehalten. Deep Blues Triumph über Garry Kasparov bei Schach kam zuerst, bereits 1997. Dann besiegte AlphaGo Lee Sedol bei Go im Jahr 2016. Poker-Bots schlagen seit Jahren Profis. Doch Stratego leistete Widerstand, wobei sogar DeepMind, trotz seines riesigen Budgets, nicht in der Lage war, eine Maschine zu bauen, die die besten menschlichen Spieler zuverlässig besiegte.

Ein Team von vier Universitäten – Carnegie Mellon, MIT, New York University und Stanford – hat es nun produziert. Sie trainierten Ataraxos mit nur 16 GPUs und ein paar tausend Dollar.

Was Stratego verbirgt

Stratego ist ein Spiel, das auf Lügen basiert. Jede Seite beginnt mit 40 Figuren, die jeweils einen Rang von Marschall bis Spion sowie Bomben und eine Flagge repräsentieren. Das Ziel ist einfach: die Flagge des Feindes zu erobern. Was es funktioniert, ist, dass dein Gegner sehen kann, wo deine Figuren stehen, aber keine Ahnung hat, was eine von ihnen wirklich ist.

Zwei Spieler wissen nicht, was ihr Gegner hält, bis ihre Figuren im Kampf aufeinandertreffen. Die Figur mit dem niedrigeren Rang wird beiseite gestellt, und die Identität des Siegers wird allen bekannt. Deshalb wird Stratego als ein Spiel mit unvollständiger Information gezählt, ähnlich wie Poker, das Maschinen bereits vor langer Zeit lösen konnten. „Es gibt etwas sehr Besonderes an Stratego, nämlich eine riesige Menge an verborgenen Informationen, die sich über einen sehr langen Zeitraum entfalten“, merkte Eugene Vinitsky an, der als Forscher an der NYU tätig ist und Mitautor der Studie ist.

Der Vergleich zu Poker endet an der Oberfläche. Bei einigen Pokerarten ist die verborgene Information minimal. „Bei Texas Hold’em hat man nur zwei verdeckte Karten“, sagte Gabriele Farina, eine Informatikerin vom MIT und ebenfalls Mitautorin. Das lässt nur 1.326 mögliche Hände zu, was für eine Maschine ausreichend ist, um sie alle abzuwägen.

„In Stratego gibt es 40 Figuren auf dem Brett, die in beliebiger Reihenfolge angeordnet sein können“, sagte Farina. Das sind mehr als eine Dekillion mögliche Aufstellungen. Das Spiel dauert zudem deutlich länger als Schach. „Im Schach dauert ein Spiel normalerweise 40 Züge, aber in Stratego kann ein Spiel problemlos 2.000 Züge dauern“, sagte Farina.

Das Problem des Bluffens

Dann gibt es noch die Länge des Spiels. „Im Schach dauert ein Spiel normalerweise 40 Züge, aber in Stratego kann ein Spiel problemlos 2.000 Züge dauern“, sagte Farina. Darüber hinaus ist Stratego ein Bluffspiel. Manchmal bewegt man eine schwache Figur, als wäre es ein Marschall, nur um den Gegner abzuschrecken.

Wenn ein Spieler zu viel blufft, verlieren seine Drohungen jegliche Glaubwürdigkeit. Wenn er gar nicht blufft, wird er leicht durchschaut. Es ist dieses feine Gleichgewicht, so das Team, das früheren KI-Systemen wie DeepMind’s DeepNash, das 2022 vorgestellt wurde, schwerfiel.

Eine riesige Menge an verborgenen Informationen, eine extreme Länge und ständige Täuschung machten Stratego zu einem schwierigeren Ziel als Schach oder Go. Das Spiel fordert eine Balance aus Berechnung und Psychologie, die frühere Systeme nicht bewältigen konnten.

Ataraxos Gewinnt

Das Ataraxos-Team entwickelte eine Lösung, die deutlich weniger Ressourcen benötigte als DeepMind’s frühere Arbeit. Sie trainierten ihre KI auf 16 GPUs und gaben ein paar tausend Dollar aus, erreichten aber dennoch eine Leistung, die DeepMind’s vorherige Versuche entsprach.

Niemeijer wird weithin als der beste Stratego-Spieler aller Zeiten angesehen. Sein Rekord spricht für sich. Das Ergebnis des Teams war 15 Siege zu einem, mit vier Unentschieden. Das ist eine dominante Leistung gegen einen Spieler, der sein Leben damit verbracht hat, die verborgenen Tiefen des Spiels zu studieren.

Warum es wichtig ist

Stratego ist endlich gefallen, und der Sieg ist von Bedeutung, da er eine Lücke in der Aufzeichnung der KI schließt. Frühere Spiele wichen Maschinen: Deep Blue besiegte Schach, AlphaGo überwand Go, und Poker-Bots begannen schon vor langer Zeit, menschliche Profis zu besiegen. Stratego erwies sich jedoch als widerstandsfähiger, seine immense Menge an verborgenen Informationen und außergewöhnliche Länge machten es zu einem schwierigeren Ziel als jedes Spiel zuvor.

Dieser Sieg demonstriert, was ein kleines Team erreichen kann. Obwohl die Forscher von vier renommierten Universitäten stammten, blieben ihre Ressourcen bescheiden: Sie trainierten Ataraxos auf 16 GPUs und gaben ein paar tausend Dollar aus.

Dieses Ergebnis markiert einen Wendepunkt. Ein Spiel, das sich über viele Jahre gegen KI behauptet hat, hat nun endgültig nachgegeben, und das mit kaum Geld im Hintergrund.

Die Zahlen hinter dem Sieg

• Spiel: Stratego
• Gewinner: Ataraxos (KI)
• Verlierer: Pim Niemeijer (wohl der beste Stratego-Spieler aller Zeiten)
• Ergebnis: 15 Siege zu einem, mit vier Unentschieden
• Trainingshardware: 16 GPUs
• Trainingskosten: Ein paar tausend Dollar
• Früherer KI-Versuch: DeepMind’s DeepNash, vorgestellt 2022

Was wir daraus ableiten können

Der Fortschritt der KI verläuft nicht in einer geraden Linie. Manche Probleme werden schnell gelöst, während andere Schwierigkeiten über Jahre hinweg bestehen bleiben. Stratego war eines dieser schwierigen Fälle. Es wurde nun gelöst, und die Antwort kam von Universitätsforschern und nicht von einer gut finanzierten Firma.

Eine kleine Aufstellung lieferte ein starkes Ergebnis, was eine Lektion für alle ist, die KI-Systeme aufbauen: Manchmal ist weniger mehr. Der Ansatz des Teams war effizient und lieferte ein starkes Ergebnis mit minimalen Ressourcen.

Der Sieg zeigt, dass die KI-Forschung zunehmend für alle offen ist, da ein bescheidener Geldbetrag und 16 GPUs nun in die Reichweite vieler Labore fallen.

Dieser Sieg markiert eine bedeutende Leistung, doch es bleibt noch viel zu tun. Viele Spiele verbergen ihre Geheimnisse noch vor uns, und die für Ataraxos entwickelten Methoden könnten als Grundlage für die weitere Forschung dienen und Forschern helfen, diese verbleibenden Rätsel anzugehen.

Die Gruppe hat Lob dafür erhalten, ein Problem gelöst zu haben, vor dem auch DeepMind gesucht hat. Ihr Erfolg zeigt, dass künstliche Intelligenz nach wie vor ein relativ neues Gebiet ist, in dem unerwartete Ergebnisse immer wieder auftauchen.

Quelle: „Mit den meisten Informationen verborgen hatte das Spiel Stratego die KI zuvor überlistet“, Ars Technica.