Die KI DeepNash meistert Stratego

Autor*innen: Jessica Arnold und Jan Heinemeyer

DeepNash ist die neue KI der Firma Deepmind, die erstmals in der Lage ist das Brettspiel Stratego trotz unvollständiger Informationen zu meistern.


Darstellung des Brettspiels Stratego [3 ]

Inhalt

Die neue KI DeepNash

Während die künstliche Intelligenz „AlphaZero“ Schach und „MuZero“ als Nachfolger verschiedene Spiele der Spielkonsole Atari meisterte, veröffentlichte die Firma Deepmind die nächste Entwicklungsstufe. Diese KI trägt den Namen DeepNash. AlphaZero meisterte Brettspiele mit klaren Regeln über ein modell-basiertes Training und MuZero, die schwer in Regeln auszudrückenden Atari-Spiele durch ein modell-freies Training. DeepNash hingegen legt sowohl die Spielregeln wie auch das Modell eines Spiels für die Planung fest. Die Besonderheit ist hierbei, dass von der gängigen Methode der Monte-Carlo-Baumsuche abgewichen wird. In der nachfolgenden Tabelle wird die unterschiedliche Komplexität von Brettspielen nochmals deutlich. [1][6]

SchachPokerGo 19*19Stratego
durchschnittliche Züge je Spiel60153001000
mögliche Startaufstellungen110611066
Komplexität des Spielbaums1012310171036010535
Übersicht der Komplexität unterschiedlicher Brettspiele [3]

Die Nash-Spieltheorie

Das Besondere an DeepNash ist, dass es in den Spielen versucht ein Nash-Gleichgewicht zu erreichen. Hierdurch verläuft das Spiel stabil. Das Nash-Gleichgewicht ist nach dem Spieltheorie-Mathematiker Jon Forbes Nash benannt. Die Theorie folgt der Annahme, dass ein Abweichen der Strategie zu einem schlechteren Ergebnis führt. DeepNash und das Nash-Gleichgewicht folgen also konstant einer Strategie. Infolgedessen hat DeepNash mindestens eine 50%ige Chance zu gewinnen. [1][3]

Die KI DeepNash spielt Stratego

Youtube-Kanal Deepmind: Die erste Stratego Partie von DeepNash gegen einen menschlichen Gegner[2]

Die KI DeepNash nahm als Trainingsgrundlage das Brettspiel Stratego. Das Brettspiel hat im Schnitt 381 Spielzüge und die besondere Schwierigkeit, dass nicht alle Informationen von Beginn an gegeben sind, da mit verdeckten Figuren gespielt wird und der Gegner mit Hilfe von Bluffs i.d.R. seine Taktik verschleiert. Optimale Spielabläufe gibt es nicht, da die Züge inkonsequent sind, das heißt jederzeit ist das Spielergebnis offen. Es wird daher anders als beim Schach nicht in Zügen, sondern in Spielen gedacht. [1][3]

Die optimale Strategie in Stratego erreicht die KI nach 5,5 Milliarden simulierten Partien. [1] DeepNash besiegte damit 97% der derzeitigen Computersysteme und erreichte eine Siegesquote von 84% gegen menschliche Spieler auf der Online-Stratego-Plattform Gravon. DeepNash gelangte damit in die Top 3 der dortigen Bestenliste. Eine weitere Besonderheit der KI stellte die Anwendung menschlicher Spielstrategien dar. So zeigte DeepNash das Bluffen oder auch das Opfern von Figuren als Taktik. Der Algorithmus „Regularised Nash Dynamics“ (R-NaD) wird außerdem für Forschende als OpenSource Download auf Github zur Verfügung gestellt. [1][4][5]

Ausschnitt aus der OpenSource Publikation zu DeepNash[7]

Zukünftige KI Anwendungsfelder

DeepNash ist die nächste Weiterentwicklung, um Menschen in Brettspielen zu übertrumpfen und wird künftig als Grundlage für alltägliche Herausforderungen genutzt werden können. Insbesondere mit unvollständigen Informationen zu arbeiten stellt einen weiteren Meilenstein dar, der in der Lage ist bei komplexen Problemen wie der Optimierung des Verkehrssystems oder auch im Bereich des autonomen Fahrens – wie auch MuZero zuvor – einen Beitrag leisten zu können. [3][4][6]

Quiz

Teste nun dein Wissen über DeepNash in einem kleinen Quiz.

Über die Autoren

Die Autorin Jessica Arnold arbeitet derzeit in der Hochschulbibliothek Emden und studiert berufsbegleitend Informationsmanagement an der Hochschule Hannover.

Der Autor Jan Heinemeyer arbeitet derzeit in der Stadtbücherei Penzberg und studiert berufsbegleitend Informationsmanagement an der Hochschule Hannover.

Beide Autoren eint das private Interesse an Informatik, Gaming, KI und Brettspielen.

Quellen:

Fußnoten:

1: Bastian, Matthias (2022)

2: DeepMind (2023)

3: Perolat, Julien u.a. (2023)

4: Meier, Christian J. (2022)

5: Menge-Sonnentag, Rainald (2022)

6: Schreiner, Maximilian (2020)

7: Perolat, Julien u.a. (2022)

Literaturverzeichnis:

Bastian, Matthias (2022): Deepminds neue Spiele-KI soll ein Game-Changer in der echten Welt werden. . In: THE-DECODER.de, Ausgabe vom 04.12.2020. Online verfügbar unter https://the-decoder.de/deepminds-neue-spiele-ki-soll-ein-game-changer-in-der-echten-welt-werden/, zuletzt geprüft am 05.01.2023.

DeepMind (2023): DeepNash Stratego game 1. Online verfügbar unter https://www.youtube.com/watch?v=HaUdWoSMjSY, zuletzt aktualisiert am 05.01.2023, zuletzt geprüft am 05.01.2023.

Meier, Christian J. (2022): Künstliche Intelligenz spielt Stratego und besiegt Menschen: ein Durchbruch. In: Süddeutsche Zeitung, 02.12.2022. Online verfügbar unter https://www.sueddeutsche.de/wissen/kuenstliche-intelligenz-stratego-brettspiel-durchbruch-menschen-1.5707877, zuletzt geprüft am 05.01.2023.

Menge-Sonnentag, Rainald (2022): KI meistert nächstes komplexes Brettspiel: DeepNash siegt in Stratego. In: heise online, 05.12.2022. Online verfügbar unter https://www.heise.de/news/KI-meistert-naechstes-komplexes-Brettspiel-DeepNash-siegt-in-Stratego-7365933.html, zuletzt geprüft am 05.01.2023.

Perolat, Julien u.a. (2022): Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learning. Online unter https://arxiv.org/pdf/2206.15378.pdf [Abruf am 07.01.2023]

Perolat, Julien u.a. (2023): Mastering Stratego, the classic game of imperfect information. Online verfügbar unter https://www.deepmind.com/blog/mastering-stratego-the-classic-game-of-imperfect-information, zuletzt aktualisiert am 05.01.2023, zuletzt geprüft am 05.01.2023.

Schreiner, Maximilian (2020): Deepmind MuZero: Auf dem Weg zum Universalalgorithmus. In: THE-DECODER.de, Ausgabe vom 24.12.2020. Online unter https://the-decoder.de/deepmind-muzero-auf-dem-weg-zum-universalalgorithmus/#top, zuletzt geprüft am 05.01.2023.