Künstliche Intelligenz:Jetzt auch noch Stratego

Künstliche Intelligenz: In Stratego werden jährlich Deutsche Meisterschaften ausgetragen, wie hier in Frankfurt.

In Stratego werden jährlich Deutsche Meisterschaften ausgetragen, wie hier in Frankfurt.

(Foto: Michael Schick/imago)

Eine KI überzeugt nun auch bei einem der letzten Brettspiele, in denen Menschen den Algorithmen bislang noch überlegen waren. Warum das als Durchbruch für die Forschung gilt.

Von Christian J. Meier

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). Doch ein Algorithmus der Londoner Google-Tochter Deepmind zeigt nun 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 nur auf Amateur-Niveau gespielt, schreiben die Forscher.

Stratego gilt seit Jahren als die nächste Hürde für KIs, die Spiele spielen. Im Schach sind Computer schon seit 1997 besser als Menschen - damals verlor Weltmeister Garri Kasparov gegen IBMs 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.

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. Auch das Zugverhalten des Gegners gibt Hinweise, 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.

Künstliche Intelligenz ist vor allem gut darin, große Datenmengen zu verarbeiten

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, 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. 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. Auf diese Weise erlernt die KI Muster im Spielverlauf und dazu passende 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.

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 und noch billiger kann man die Preise auch nicht machen: Ein stabiler Zustand. Bei Nullsummen-Spielen wie Stratego führe diese Strategie auch gegen starke Gegner zu einem guten Ergebnis, schreiben die Forscher von Deepmind.

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.

Das Programm kann sogar erfolgreich bluffen

Der Algorithmus zeigte sich sogar versiert im Bluffen. Beispielsweise jagte er mit einer rangniederen Figur eine gegnerische, sodass der Gegner sie für eine Ranghöhere hielt. Aufgrund dieses Irrtums verlor der Gegner letztlich eine wertvolle 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 aber, 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.

Zur SZ-Startseite

Künstliche Intelligenz und Recht
:Die Entmachtung des Menschen durch die Maschine?

Auf einer Tagung gingen Juristen der Frage nach, wie KI die Rechtsprechung beeinflussen könnte. Ein zentrales Problem: Der Mensch versteht nicht, wie der Computer zu Entscheidungen kommt.

Lesen Sie mehr zum Thema

Jetzt entdecken

Gutscheine: