KI meistert nächstes komplexes Brettspiel: DeepNash siegt in Stratego

Inhaltsverzeichnis

DeepMind hat ein KI-System entwickelt, das sich im komplexen Strategiespiel Stratego gegen menschliche Gegner durchsetzen konnte. Auf der Online-Plattform Gravon hat es wohl einen Platz in den Top Drei erkämpft. Seinen Namen verdankt das System dem Nash-Gleichgewicht, das wesentlich zu seiner Stärke beiträgt.

Das 1946 zum ersten Mal veröffentlichte Stratego weist im Vergleich zu anderen Brettspielen einige Besonderheiten auf. Beide Spieler verteilen ihre 40 Steine verdeckt in beliebiger Formation auf ihrer jeweiligen Seite des Spielfelds. Die Figuren repräsentieren Soldaten mit unterschiedlichen Rängen und sind so gestaltet, dass ihr Wert nur von der Seite des zugehörigen Spielers erkennbar ist. Neben den aktiven Figuren gibt es sechs Bomben und eine Fahne. Primäres Spielziel ist es, die Fahne zu erobern.

Wie bei anderen Brettspielen ziehen die Kontrahenten abwechselnd. Treffen zwei Figuren aufeinander, schlägt die ranghöhere die niedrigere. Sind die Figuren gleich stark, verschwinden beide vom Spielfeld. Hinzu kommen Sonderregeln, die dem schwachen Aufklärer mehr Bewegungsraum geben und dem in der Rangfolge zuunterst stehenden Spion die Möglichkeit eröffnen, den ranghöchsten Feldmarschall zu besiegen.

Um zu gewinnen, muss man die Position der gegnerischen Figuren anhand ihrer Bewegungen und geschickten Ziehens der eigenen Figuren erschließen. Außerdem ist Bluffen wichtig, indem man die Steine so zieht, dass das Gegenüber daraus die falschen Schlüsse zieht.

Herausforderungen für die KI

Stratego bringt im Vergleich zu Spielen wie Schach oder Go zusätzliche Herausforderungen an ein KI-System. Im Schach waren Computer bereits vor 25 erfolgreich, als Big Blue II den Schachweltmeister Garri Kasparow geschlagen hat. Es dauerte fast zehn Jahre, bis ein KI-Agent das komplexe Spiel Go gegen einen der stärksten Spieler der Welt gewinnen konnte: AlphaGo setzte 2016 auf tiefe neuronale Netze und trainierte zuvor mit Reinforcement Learning, indem es unzählige Partien gegen sich selbst spielte. Auch das KI-Sytem Libratus, das 2017 vier professionelle Pokerspieler besiegte, setzte auf Reinforcement Learning und verzichtete dabei auf ein Deep Neural Network (DNN).

Die Strategien, die Machine-Learning-Modellen zum Sieg bei Brettspielen geholfen haben, greifen in Stratego nicht, da das System bei Schach und Go die Positionen aller Spielsteine kennt und damit auch die möglichen künftigen Positionen berechnen kann. Bei Stratego verfügt das System aufgrund der verdeckten gegnerischen Figuren nur über einen Teil der Informationen.

Außerdem ist es schon von den Möglichkeiten her deutlich komplexer. Der Blogbeitrag zu DeepNash beziffert die Zahl der möglichen Stellungen auf 10 hoch 535, und damit um ein Vielfaches höher als bei Go oder Schach. Die Techniken aus Poker scheitern alleine schon an der Vielzahl möglicher Züge, die bei Poker dagegen überschaubar ist. Das System muss auch Bluffs in eine Strategie einbinden, die zahlreiche Züge im Voraus kalkuliert ist.

Bestärkend, aber ohne Modellvorgabe

DeepNash setzt auf ein sogenanntes Model-free Deep Reinforcement Learning. Reinforcement Learning verwendet ein Belohnungssystem, anhand dessen das KI-System erkennt, welche Aktionen besonders hilfreich sind. Model-free bezieht sich nicht etwa auf ein fehlendes Machine-Learning-Modell, sondern bedeutet, dass DeepNash nicht versucht, den Status der gegnerischen Figuren zu modellieren. Das wäre gerade zu Beginn des Spiels ineffizient bis unmöglich.

Die Monte-Carlo-Baumsuche – ein heuristischer Suchansatz, der unter anderem AlphaZero zum Erfolg im Go verholfen hat – taugt aufgrund der unzähligen möglichen Stellungen laut dem Blogbeitrag nicht für Stratego. Daher hat DeepMind einen eigenen Ansatz für einen Algorithmus der Spieltheorie entwickelt und ihn Regularised Nash Dynamics (R-NaD) getauft. Die Details finden sich in einer Abhandlung auf arXiv.org.

Der Algorithmus setzt auf Regularisierung, um ein Nash-Gleichgewicht zu erreichen, das auch zentral für das Pokergeschick von Libratus war. Der Begriff aus der Spieltheorie trägt den Namen seines Entwicklers John F. Nash und beschreibt einen Spielzustand, bei dem der Mitspieler nicht von seiner Strategie abweicht. Wie andere KI-Agenten hat DeepNash Stratego von Grund auf durch unzählige Partien gegen sich selbst erlernt.

DeepNash besteht aus drei Komponenten. Es beginnt mit dem zentralen Training mit dem Model-free RL-Algorithmus. Die zweite Komponente kümmert sich um das Feintuning der erlernten Strategie, um die Möglichkeit unwahrscheinlicher Aktionen zu reduzieren, die sich dadurch ergeben, dass die Policy des Algorithmus jeder Aktion eine Wahrscheinlichkeit größer als Null zuordnet. Die letzte Komponente ist für die Nachbearbeitung zuständig, um Fehler zu beseitigen und weitere Aktionen mit geringer Wahrscheinlichkeit herauszufiltern.

Eine langfristige Stärke von DeepNash soll darin bestehen, dass er möglichst unvorhersehbar agiert, also keine Muster erkennen lässt, die Gegner ausnutzen können. Als Mittel dagegen variiert das System unter anderem gleichwertige Züge im Spielverlauf zufällig. Anfang November hatte ein Team ein Paper über ein KI-System auf arXiv.org veröffentlicht, das mit Adversarial Policies Googles KataGo besiegt, obwohl es gegen schwache menschliche Spieler verliert.

Erfolge gegen Mensch und Maschine

Das Team hinter DeepNash hat das System sowohl gegen menschliche Kontrahenten als auch gegen andere Stratego-Bots ins Rennen geschickt. Laut dem DeepMind-Blog hat es mehr als 97 Prozent der Bots geschlagen und auf der Online-Platttorm Gravon gegen menschliche Spieler eine Siegesquote von 84 Prozent erzielt.

Mit dem Erfolg in Stratego hat DeepNash eine weitere, wenn auch nicht die letzte Spielebastion eingenommen, die für KI als äußerst komplex gilt. Vor Kurzem hatte Meta einen Erfolg in dem aufgrund der Verhandlungen mit anderen Spielerinnen und Spielern komplexen Diplomacy durch das KI-Modell Cicero veröffentlicht. In anderen Bereichen hat die KI nach wie vor das Nachsehen. Immer noch schwer tun sich die Systeme mit dem Computerspiel NetHack.

Wie Metas Cicero soll auch DeepNash jenseits der Brettspiele in praktischen Anwendungen seinen eigentlichen Zweck finden – überall dort, wo unvollständige Informationen und enorm viele mögliche Zustände zusammenkommen.Als Beispiel nennt der Blogbeitrag die groß angelegte Optimierung des Verkehrsmanagements.

Empfohlener redaktioneller Inhalt

Mit Ihrer Zustimmmung wird hier ein externes YouTube-Video (Google Ireland Limited) geladen.

YouTube-Video immer laden YouTube-Video jetzt laden

Ich bin damit einverstanden, dass mir externe Inhalte angezeigt werden. Damit können personenbezogene Daten an Drittplattformen (Google Ireland Limited) übermittelt werden. Mehr dazu in unserer Datenschutzerklärung.

Weitere Details lassen sich dem DeepMind-Blogeintrag entnehmen. Dort finden sich auch Links zu vier Videos mit Partien, die DeepNash gegen Menschen gespielt hat. Der Sourcecode von R-NaD ist auf GitHub zu finden.

(rme)