Googles KI „DeepNash“ meistert Brettspiel Stratego – und kann sogar bluffen

Strategisch handeln, kurzfristig Nachteile für einen langfristigen Erfolg hinnehmen und, ja, auch mal bluffen: Qualitäten, die man eher Menschen zutraut als einer künstlichen Intelligenz (KI). Ein Algorithmus der Londoner Google-Tochter Deepmind zeigt nun aber genau diese Fähigkeiten, zumindest beim Spielen von „Stratego“, einem höchst komplexen Brettspiel. Die KI „DeepNash“ spielte bei der größten Online-Plattform für Stratego meisterlich gegen menschliche Spieler. Sie gewann 84 Prozent der Partien und stand damit zeitweise auf dem dritten Rang, wie Forscher um Julien Perolat im Fachmagazin Science mitteilen. Bisherige Algorithmen hätten Stratego nur auf Amateur-Niveau gespielt, schreiben die Forscher.

Stratego gilt seit Jahren als die nächste Herausforderung für die künstliche Intelligenz auf dem Gebiet menschlicher Spiele. Im Schach sind Computer schon seit 1997 besser als Menschen – damals verlor Weltmeister Garri Kasparov gegen IBM’s Schachcomputer Deep Blue. Allerdings ist Schach für einen Computer weit einfacher zu berechnen als etwa das asiatische Brettspiel Go, das sehr, sehr viel mehr mögliche Figurenstellungen erlaubt. Deepmind knackte diese Nuss im Jahr 2016 mit seiner KI „AlphaGo“, die mit Lee Sedol einen der weltbesten Go-Spieler bezwang.

Eine knifflige Mischung aus Brett- und Kartenspiel

Stratego ist nochmals eine andere Liga. Denn das Spiel ist in doppelter Hinsicht hoch komplex. Bei Stratego stehen sich, ähnlich wie beim Schach, zwei Parteien mit je 40 Spielfiguren gegenüber. Diese haben verschiedene Ränge und eine Figur ist die Fahne, die es zu erobern gilt. Ranghöhere Figuren schlagen niedrigere Ränge, wenn sie zusammentreffen. Das Problem ist nur: Der Spieler sieht die Ränge der gegnerischen Figuren nicht. Erst durch einen Angriff auf eine Figur findet er deren Rang heraus. Er muss sich die Information also unter dem Risiko, Figuren zu verlieren, nach und nach beschaffen. Hinweise gibt zudem das Zugverhalten des Gegners, der damit freilich auch bluffen kann. Somit besitzt Stratego nicht nur eine Unzahl an möglichen Zügen, die sogar größer ist als bei Go, sondern verdeckt auch noch Information, wie man das sonst von Kartenspielen kennt.

So einem Spiel ist nicht beizukommen, indem man alle möglichen Zugfolgen im Kopf durchgeht, sondern nur durch Erfahrung, unterschiedliche Strategien oder Finten, also typisch menschliche Fähigkeiten.

Künstliche Intelligenz hingegen ist vor allem gut darin, Muster in großen Datenmengen zu finden. Das lässt sich aber durchaus auf Brettspiele anwenden. Spielt ein Spieler sehr oft, dann erkennt er wiederkehrende Muster in der Stellung der Figuren und weiß, welche Strategie jeweils erfolgversprechend ist. Der Vorteil einer KI ist, dass sie gegen sich selbst spielen kann – mit der Geschwindigkeit eines Supercomputers. (Genauer gesagt spielen zwei Klone der KI gegeneinander, die Information voreinander verstecken können.) Der Algorithmus DeepNash hat etwa zehn Milliarden Mal gegen sich selbst gespielt. Ein Mensch könnte im ganzen Leben bei weitem nicht so oft spielen. Durch Ausprobieren von Zügen erlernt die KI Muster im Spielverlauf und jeweils dazugehörige erfolgversprechende Aktionen. Wichtig dabei: Auch die KI begegnet dabei längst nicht allen möglichen Spielvarianten, dafür sind diese viel zu zahlreich. Somit ist ihr Können durchaus mit Intelligenz zu vergleichen.

Figuren opfern und mit Finten täuschen

Besonders an DeepNash im Vergleich zu AlphaGo ist, dass es bei seinem Selbsttraining das Ziel verfolgte, ein so genanntes Nash-Gleichgewicht zu erreichen. Ein Spiel, das sich im Nash-Gleichgewicht befindet, verläuft stabil. Denn das einseitige Abweichen von der Strategie würde einen Nachteil bedeuten. Im realen Leben sieht man das etwa unter Discountern: Von der Billig-Strategie nach oben abzuweichen würde Kunden kosten. Nach unten abzuweichen und die Preise noch billiger zu machen, würde Verluste bedeuten. Ein stabiler Zustand resultiert. Bei Nullsummenspielen wie Stratego führe diese Strategie auch gegen starke Gegner zu einem guten Ergebnis, schreiben die Forscher von Deepmind. (Nullsummenspiele sind Spiele, bei denen die Gewinne und Verluste der einzelnen Spieler sich gegenseitig aufheben, also in der Summe Null ergeben.)

DeepNash habe im Spiel Verhaltensweisen gezeigt, wie man sie von Topspielern kenne, schreiben die Wissenschaftler. Zum Beispiel opferte es Figuren, um die Positionen der hochrangigen Figuren des Gegners zu erfahren. DeepNash hat also den Wert dieser Information höher eingeschätzt als den Nachteil, weniger Figuren auf dem Brett zu haben. Eine Abwägung, die nicht trivial sei, wie die Forscher schreiben.

„Dieser Algorithmus ist beeindruckend“

Der Algorithmus zeigte sich sogar versiert im Bluffen. Beispielsweise jagte er mit einer rangniederen Figur eine gegnerische, sodass der Gegner sie für einen „Feldmarschall“, die ranghöchste Figur hielt. Er griff sie mit einem „Spion“ an, die zwar den Feldmarschall schlagen kann, selbst aber von allen anderen Figuren geschlagen werden kann. Wegen des Irrtums verlor der Gegner diese nützliche Figur.

„Dieser Algorithmus ist beeindruckend“, kommentiert Marc Toussaint, Leiter des Fachgebietes Intelligente Systeme an der Technischen Universität Berlin. „Methodisch liefern die DeepMind-Autoren damit einen beachtlichen Fortschritt hin zu optimalen Spielstrategien in Nullsummenspielen“, so Toussaint.

Er betont, dass es sich eben um ein Spiel handelt, das feste Regeln hat und exakt simuliert werden kann. Herausforderungen des Alltags, etwa der Straßenverkehr oder die Haushaltsarbeit sind nicht von dieser Art. „Auf Probleme ohne exakten und effizienten Simulator sind diese Spiele-KI-Methoden kaum direkt anwendbar“, sagt der Forscher. „Trotzdem hat sich in der Vergangenheit immer wieder gezeigt, dass Forschung an Spiel-Algorithmen auch Grundlagenforschung voranbringen kann.“

Somit übertrumpft mit DeepNash erneut eine KI Menschen in einem bestimmten Gebiet – aber eben noch lange nicht in allen Belangen.