KI spielt erfolgreich Brettspiel Stratego

„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.“

„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.“

„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.“