KI spielt erfolgreich Brettspiel Stratego

 

• KI spielt Brettspiel Stratego auf hohem Niveau

 

• viele Zugoptionen und unvollständige Informationen machen das Spiel schwierig für KI

 

• Experten: beachtlicher Fortschritt, aber Übertragbarkeit auf andere Bereiche ist schwierig

 

Eine Künstliche Intelligenz (KI) von DeepMind erreicht in der digitalen Variante des Brettspiels Stratego erstmals das Niveau sehr guter menschlicher Spieler. Die vorher bereits als Preprint [I] verfügbare Studie wurde am 01.12.2022 im Fachjournal „Science“ veröffentlicht (siehe Primärquelle).

Laut den Autorinnen und Autoren ist Stratego eines der Spiele, bei dem KI bislang nicht auf gutem menschlichem Niveau spielen konnte. Der Grund dafür: Stratego erfordert einerseits strategische Weitsicht – ähnlich wie Schach – es muss aber auch auf Basis von nicht vollständigen Informationen entschieden werden, wie beispielsweise bei Poker. Denn bei Stratego haben die Figuren unterschiedliche Werte und schlagen verschiedene andere Figuren, werden allerdings anfangs verdeckt platziert. Darüber hinaus gibt es in dem Spiel sehr viele mögliche Optionen und Züge – mehr als bei GO oder Texas Hold’em Poker, also Spielen, bei denen KI in der Vergangenheit große Fortschritte erzielen konnte. Den Forschenden zufolge stellt das Spielen von Stratego auf hohem Niveau daher eine der nächsten zu brechenden Grenzen in der KI-Forschung dar.

Das in der Studie vorgestellt Programm „DeepNash“ konnte sich in Test sowohl gegen andere Stratego-Programme als auch gegen Menschen durchsetzen. Gegen andere Programme hatte DeepNash Gewinnraten zwischen 97 und 100 Prozent. Gegen menschliche Spieler konnte DeepNash auf der online-Plattform Gravon in 50 Spielen 84 Prozent der Partien gewinnen und stand damit temporär auf Rang drei unter den Stratego-Spielerinnen und Spielern der Seite. Dabei legte es der Studie zufolge auch Verhalten an den Tag, das als Täuschung oder Bluffen interpretiert werden kann.

Die KI basiert auf einem Reinforcement Learning Algorithmus und hat beim Spielen gegen sich selbst gelernt – ohne menschliche Demonstration. Das Ziel der Forschenden war es, die KI nach einem sogenannten Nash-Gleichgewicht suchen zu lassen. Das ist eine Strategie, die stabil ist, weil jeder Spieler bei einem einseitigen Abweichen von der Strategie schlechter dasteht, solange der andere seine Strategie beibehält. In einem Nullsummen-Spiel wie Stratego garantiert so eine Strategie laut den Autorinnen und Autoren auch bei starken Gegnern ein gutes Abschneiden.

Die Forschenden betonen, dass es momentan keine Hinweise gibt, ob der der KI zugrundeliegende Algorithmus in anderen Situationen Fortschritte bringen könnte. Sie stellen in Aussicht, dass diese Art von Algorithmen möglicherweise in Bereichen wie Verkehrsmodellierung, Auktionen oder bei Berechnungen zu Märkten Anwendung finden könnten.

Um den Stellenwert der Studie und die Implikationen für andere Bereiche nachvollziehen zu können, hat das SMC Experten um eine Einschätzung gebeten.

 

• Prof. Dr. Marc Toussaint, Leiter des Fachgebietes Intelligente Systeme, Technische Universität Berlin

 

• Dr. Georg Martius, Leiter der Gruppe Autonomous Learning, Max-Planck-Institut für Intelligente Systeme, Tübingen

 

• Prof. Dr. Kristian Kersting, Leiter des Fachgebiets Maschinelles Lernen, Technische Universität Darmstadt

 

Statements

Prof. Dr. Marc Toussaint

Leiter des Fachgebietes Intelligente Systeme, Technische Universität Berlin

„Der aktuellen Studie ging 2021 bereits eine Studie der DeepMind-Autoren voraus, die den neuen R-NaD-Algorithmus vorgestellt hat. Dieser Algorithmus ist beeindruckend, da er die Konvergenz von Reinforcement-Lernalgorithmen in sogenannten Nullsummenspielen sicherstellt, womit bisherige KI-Methoden eher Schwierigkeiten hatten. Methodisch liefern die DeepMind-Autoren damit einen beachtlichen Fortschritt hin zu optimalen Spielstrategien in Nullsummenspielen.“

„Stratego ist in der Tat ein herausforderndes Spiel, in dem die Größe des Entscheidungsraums und die Unsicherheit um die gegnerische Stellung deutlich größer sind als in bisherigen Spielen. Dennoch basiert die Methode natürlich auf einem Simulator – also vollständigem Wissen der Spielregeln. Wie bisherige Erfolge der KI in Spielen basiert auch die neue Methode darauf, solche Spiele sehr effizient zu simulieren und durch Selbst-Spiel enorme Datenmengen zu erzeugen.“

„Auf Probleme ohne exakten und effizienten Simulator sind diese Spiele-KI-Methoden kaum direkt anwendbar. Trotzdem hat sich in der Vergangenheit immer wieder gezeigt, dass Forschung an Spiel-Algorithmen auch Grundlagenforschung voranbringen kann. In diesem Fall ist dieser Fortschritt der neue R-NaD-Algorithmus, den die Autoren entwickelten, um mit Deep Learning auf diesen großen Datenmengen auch zu optimalem Spiel zu konvergieren.“

„Die Autoren geben gute Performance nach ungefähr zwei Millionen Lernschritten an. Für jeden Lernschritt werden circa 10.000 bis 100.000 Spiele simuliert, was insgesamt circa 10¹⁰ Spiele ausmacht. Wenn ein Mensch eine knappe Stunde pro Spiel bräuchte, entspräche das grob einer Millionen Jahren Spielzeit. Die simulierten Daten sind also enorm. In gewisser Weise komprimiert der Lernalgorithmus diese Daten in ein neuronales Nachschlagewerk, den Actor, das für jede Situation direkt die optimale Aktion liefert – wie von den Autoren betont ohne weiteres Suchen, Planen, oder Vorausschauen. Das unterstreicht, wie verschiedenartig diese Form der datenbasierten KI zur natürlichen ist.“

Dr. Georg Martius

Leiter der Gruppe Autonomous Learning, Max-Planck-Institut für Intelligente Systeme, Tübingen

„In dem Artikel stellt DeepMind ihren neuen DeepNash Bot vor, der lernt das Brettspiel Stratego auf Expertenniveau zu spielen. Bisher ist es keinem Computerprogramm gelungen, eine ähnlich starke Spielleistung zu erreichen.“

Auf die Frage zur Rolle von Stratego für die KI-Forschung:
„Im Gegensatz zu Schach oder dem Brettspiel Go ist bei Stratego ein Teil des Spielzustandes vom Gegner verborgen – so wie man es von Kartenspielen kennt, bei denen man die Karten auf der eigenen Hand nur selbst sieht. Der Gegner muss also aus den gespielten Zügen Rückschlüsse über die Karten ableiten. Ein bekanntes Spiel mit diesen Eigenschaften ist zum Beispiel Texas Hold'em Poker. Im Vergleich zu Poker gibt es bei Stratego eine viel größere Anzahl an möglichen Zügen.“

Auf die Frage, wie die KI und der dazugehörige R-NaD-Algorithmus funktionieren:
„Es handelt sich um ein tiefes neuronales Netz – welche auch für die Bildverarbeitung benutzt werden –, das den aktuellen Brettzustand und den der letzten 40 Züge als Eingabe bekommt. Es gibt für alle möglichen Optionen des nächsten Zuges eine Wahrscheinlichkeit aus, dass dieser Zug der beste Zug ist. Interessanterweise hat die KI DeepNash keinen expliziten Mechanismus, mit der verborgenen Information umzugehen oder diese direkt abzuschätzen. Stattdessen wird direkt aus dem Ablauf des Spiels und des aktuellen Bretts eine Entscheidung getroffen.“

„Entscheidend ist, dass die KI ihr Spielverhalten gelernt hat, indem sie eine unglaublich große Anzahl an Spielen gegen sich selbst spielt. Bei diesem Spiel gegen sich selbst wird sich eine Strategie durchsetzen, die nicht durch kleine Änderungen des Gegners ausgenutzt oder umgangen werden kann. Das nennt man Nash-Gleichgewicht. Kein Spieler kann durch Änderung seines eigenen Verhaltens einen Vorteil erzielen. Jetzt passiert es aber, dass sich ein solches Gleichgewicht einstellt, das aber durch eine ganz andere Spielweise besiegt werden kann – das also nicht robust gegenüber ganz verschiedenen Strategien ist. In diesem Fall benutzt DeepNash eine Technik, diese Gleichgewichte robust zu machen, indem die Spieler Belohnungen bekommen, anders zu spielen als bisher. Das wird durch eine Regularisierung erreicht – auch Reward Transformation genannt –, was auch den Namen ‚Regularized Nash Dynamics‘ erklärt.“

„Praktisch spielt der Bot gegen sich selbst bis sich nichts mehr stark am Spiel ändert und dann wird in der nächsten Runde – von abermals Millionen Spielen, nehme ich an – mit einem veränderten Reward (Belohnungssignal) gespielt. Dieses belohnt zusätzlich zum Gewinnen auch noch, anders zu spielen als in der letzten Runde.“

„Auch wenn diese Idee schon eher publiziert wurde, ist sie erst in dieser Arbeit auf das komplizierte Spiel Stratego angewendet worden – und so angepasst, dass das Programm wirklich erfolgreich lernt. Methodisch ist damit ein neuer Baustein für KIs im Rennen, um sehr gute und robuste Strategien für Nullsummenspiele mit verborgenen Informationen zu erzielen. Nullsummenspiele sind solche, bei denen der Gewinn des einen den gleichwertigen Verlust des anderen bedeutet.“

Auf die Frage, welchen Stellenwert diese Erkenntnisse haben und welche Fortschritte in anderen Bereichen sich dadurch ergeben könnten:
„Das Prinzip ist allgemein und kann auf andere Nullsummenspiele mit zwei Parteien angewendet werden. Dazu wird ein schneller Simulator für das Spiel beziehungsweise das Problem benötigt. Eventuell kann man es auch auf weitere Situationen mit mehr als zwei Parteien ausweiten. Als mögliche Anwendungsgebiete werden in der Studie Energienetze oder Verkehrsoptimierung genannt.“

„Im Allgemeinen sind Ergebnisse auf Brettspielen nur bedingt auf andere Anwendungen übertragbar. Voraussetzung ist immer, dass der Ablauf genau simuliert werden kann. In den meisten Anwendungen des Alltags ist das nicht gegeben.“

„Nichtsdestotrotz wurden die Methoden des Reinforcement Learning – so heißt die Klasse der Verfahren, die aus Belohnungssignalen und der Interaktion lernen – und Erkenntnisse von Brettspiel-KIs dazu genutzt, AlphaFold zu entwickeln. Dieses System – auch von DeepMind – ermöglicht es, Proteinstrukturen vorherzusagen. Dabei handelt es sich um einen Durchbruch, da es ein sehr wichtiger Baustein für die Medikamentenentwicklung ist und in vielen anderen biologischen Anwendungen weiterhilft.“

Prof. Dr. Kristian Kersting

Leiter des Fachgebiets Maschinelles Lernen, Technische Universität Darmstadt

„Nach Schach und Go hat jetzt das KI-System DeepNash bei Stratego überzeugt. Es kam auf den dritten Platz in 50 Ranglisten-Spielen gegen menschliche Spitzenspieler im Laufe von zwei Wochen im April 2022. Das ist ein bedeutender Erfolg für die KI-Forschung, weil Stratego strategische Interaktionen im großen Maßstab benötigt. Um den Erfolg in den Alltag oder das Geschäftsleben zu übertragen, bleibt aber noch viel zu tun.“

„Stratego ist ein Brettspiel für zwei Spieler, bei dem jeder Spieler versucht, die Flagge des Gegners zu erobern – und es ist eines der wenigen Brettspiele, das Systeme der künstlichen Intelligenz (KI) noch nicht bewältigen konnten. Das liegt daran, dass das beliebte Spiel einen riesigen Spielbaum mit 10 hoch 535 Knoten hat. Das sind 10 hoch 175 mal mehr Knoten als der Spielbaum von Go. Nur zum Vergleich, die Zahl der Atome im Universum beläuft sich im Bereich zwischen 10 hoch 84 und 10 hoch 89.“

„Die Komplexität hat einen Grund. Jeder Spieler hat 40 Figuren mit unterschiedlichen Werten. Allerdings wissen die Spieler nicht, wo sich die gegnerische Flagge befindet oder welche Figuren vor ihnen liegen. Das Brett besteht aus 100 Feldern, von denen acht zwei unpassierbare Seen sind. Die Spieler beginnen das Spiel, indem sie ihre Spielsteine auf die ersten vier Linien des Spielbretts vor sich setzen (Phase eins). Dann beginnt Phase zwei. Die Spieler ziehen abwechselnd Figuren, mit Ausnahme der Flagge und der sechs Bomben, die unbeweglich sind. Wenn zwei Figuren aufeinandertreffen, wird ihr Wert aufgedeckt und die schwächere Figur wird entfernt – oder beide, wenn sie die gleiche Stärke haben. Ausnahme: Greift der schwächere Spion den Marschall mit dem Wert 10 an, gewinnt der Spion.“

„Wie AlphaGo und Co ist auch DeepNash ein lernendes System und bedient sich des verstärkenden Lernens mittels neuronaler Netzwerke – gewünschte Verhaltensweisen werden durch Belohnungen und Bestrafung verstärkt. Diese Art des Lernens ist auch beim Menschen bekannt und geht auf die Arbeiten der Psychologen Thorndike und Skinner aus der ersten Hälfte des vergangenen Jahrhunderts zurück. Für mich ist es immer wieder faszinierend zu sehen, wie dieses doch einfache Prinzip zu neuen Algorithmen und Durchbrüchen in der KI führt.“

„Allerdings geht DeepNash einen Schritt weiter. Neben dem Verstärkungslernen bedient es sich der Spieltheorie, um Entscheidungsverhalten abzuleiten, das nicht nur vom eigenen Handeln, sondern auch von den Aktionen des Gegners abhängt. Was heißt das? Sowohl DeepNash als auch seine Gegner verfolgen ihre eigenen Handlungsstrategien: In dieser Spielsituation greife ich diese Figur an, beide Spieler verkünden den Rang ihrer Figur und die rangniedrigere wird vom Feld genommen. DeepNash will nun ein Nash-Gleichgewicht erreichen. Das liegt vor, wenn sich keiner der beiden Spieler durch einseitiges Abweichen seiner Strategie individuell besser stellen kann, auch nicht ein ‚Angstgegner‘, der uns in besonders bedrohliche Spielsituationen führt.“

„Dazu braucht DeepNash keine menschlichen Partien oder Demonstrationen. Wie schon AlphaZero und Co lernt DeepNash seine Spielstrategie, indem es gegen sich selbst spielt. Zwar hatten auch schon andere Forscher das verstärkende Lernen mittels neuronaler Netzwerke für Stratego ausprobiert, aber erst die R-NaD Formulierung erlaubt es, die erlernte Spielstrategie in Richtung des Nash-Gleichgewichts und damit zum Erfolg bei Stratego zu lenken.“

Angaben zu möglichen Interessenkonflikten

Prof. Dr. Marc Toussaint: „Obwohl ich in einem thematisch eng verwandten Bereich arbeite, gibt es meinerseits keine Interessenkonflikte.“

Alle anderen: Keine Angaben erhalten.

Primärquelle

Perolat J et al. (2022): Mastering the game of Stratego with model-free multiagent reinforcement learning. Science. DOI: 10.1126/science.add4679.

Literaturstellen, die vom SMC zitiert wurden

[I] Perolat J et al. (2022): Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learning. Arxiv.
Hinweis der Redaktion: Es handelt sich hierbei um eine Vorabpublikation, die noch keinem Peer-Review-Verfahren unterzogen und damit noch nicht von unabhängigen Experten und Expertinnen begutachtet wurde.