Kürzlich hat der KI-Agent DeepNash von DeepMind professionelle menschliche Spieler in Stratego erfolgreich besiegt und sich erfolgreich unter den Top 3 platziert.
Am 1. Dezember wurde der Artikel offiziell in Science veröffentlicht.
Papieradresse: http://www.science.org/doi/10.1126/science.add4679
In der heutigen Zeit hat sich die KI für Spiele zu einem entwickelt Eine ganz neue Bühne.
In der Vergangenheit verwendeten viele Wissenschaftler Schach und Go, um KI zu trainieren, aber DeepMind nutzte dieses Mal Stratego, ein klassisches Brettspiel, das komplexer als Schach und Go und cleverer als Poker ist.
Und dieser KI-Agent namens DeepNash lernte Stratego von der Pike auf, indem er gegen sich selbst spielte.
Mittlerweile gehört DeepNash zu den Top Drei in der Geschichte der menschlichen Experten auf Gravon, der weltweit größten Online-Plattform von Stratego.
DeepNash übernimmt eine brandneue Spielmethode, die theoretisch auf Spieltheorie und modellfreiem Deep Reinforcement Learning basiert.
Man erkennt, dass dieser Name auch eine Hommage an den berühmten amerikanischen Mathematiker John Nash sein soll.
Das von ihm vorgeschlagene Nash-Gleichgewicht, auch bekannt als nichtkooperatives Spielgleichgewicht, ist ein sehr wichtiger Teil der Spieltheorie.
Brettspiele waren in der Vergangenheit der Standard zur Messung des Fortschritts in der KI, da sie es uns ermöglichen, zu untersuchen, wie Menschen und Maschinen in kontrollierten Umgebungen Strategien formulieren und ausführen.
Und was ist das Geheimnis dieses Stratego?
Der Unterschied zu Schach und Go besteht darin, dass Stratego ein unvollständiges Informationsspiel ist: Spieler können die Identität der gegnerischen Figuren nicht direkt beobachten.
Aufgrund dieser Komplexität liegt das KI-basierte Stratego-System oft auf Amateurniveau, egal wie hart es arbeitet, es ist unmöglich, das „Experten“-Niveau zu erreichen.
Der Grund, warum verschiedene KIs in der Vergangenheit große Siege in Spielen errungen und Menschen völlig überwältigt haben, liegt in einer KI-Technologie namens „Game Tree Search“.
Obwohl „Game Tree Search“ alle Arten von Spielen mit vollständigen Informationen töten kann, ist es für Spiele wie Stratego etwas hilflos, da es nicht skalierbar genug ist.
Zu diesem Zeitpunkt hat DeepNash die Suche nach Wildbäumen vollständig zerstört.
Tatsächlich hat DeepNash den Wert von Stratego gemeistert, der das Spiel selbst bei weitem übertrifft.
Die reale Welt ist oft sehr komplex und die Informationen sind begrenzt. Wirklich fortschrittliche KI-Systeme sind mit Umgebungen wie Stratego konfrontiert.
DeepNash hat uns erfolgreich gezeigt, wie KI unter Unsicherheit Ergebnisse erfolgreich ausbalancieren und komplexe Probleme lösen kann.
So spielt man Stratego
Stratego ist ein rundenbasiertes Capture-the-Flag-Spiel. Im Spiel müssen die Spieler bluffen, Kreisverkehrtaktiken anwenden, Informationen sammeln und geschickt agieren.
Es handelt sich um ein Nullsummenspiel, d. h. jeder Gewinn für einen Spieler bedeutet den gleichen Verlust für den Gegner.
Es klingt unserem Militärschach sehr ähnlich.
Der Unterschied zwischen Stratego und Militärschach besteht darin, dass es eine größere Anzahl von Schachfiguren, mehr militärische Ränge, ein einfacheres Schachbrettdesign und keine Eisenbahnen, Lager und Schiedsrichter hat.
Wenn beide Seiten eine Formation aufbauen, sollten alle Schachfiguren aufrecht stehen und von der anderen Seite nicht gesehen werden können.
Nachdem die Formation abgeschlossen ist, bewegt sich die rote Seite zuerst und wechselt sich dann ab, um eine Figur zu bewegen.
Unter den Schachfiguren können die Militärflagge und die Minen nicht horizontal und vertikal bewegt werden, die anderen Schachfiguren können jedoch nur ein Feld horizontal oder vertikal bewegen.
Wenn sich die Schachfiguren beider Seiten im gleichen Raster befinden, werden sie gemeinsam aufgedeckt und nach ihrer Größe beurteilt. Die gewinnende Schachfigur wird zurück in ihre ursprüngliche Position gebracht, nach hinten gerichtet, und die verlierende Schachfigur wird entfernt.
Strategos Siegesmethode ähnelt dem chinesischen Militärschach. Der Sieg wird durch die Eroberung der Militärflagge des Gegners oder die Zerstörung aller sich bewegenden Schachfiguren erreicht.
Warum ist Stratego für KI so herausfordernd? Ein Grund dafür ist, dass es sich um ein Spiel unvollständiger Informationen handelt.
Zwei Spieler in Stratego verstecken sich voreinander, wenn sie 40 Spielsteine in die Startformation bringen.
Da Spieler nicht auf das gleiche Wissen zugreifen können, müssen sie bei jeder Entscheidung alle möglichen Ergebnisse abwägen.
Typen und Rangfolge der Stratego-Schachfiguren
Links: Rangfolge der Schachfiguren. Im Spiel gewinnt immer die Figur mit dem höheren militärischen Rang, mit der einzigen Ausnahme: 10 (Marschall), der von einem Spion angegriffen wird, gewinnt immer, mit der einzigen Ausnahme, die von einem Bergmann erbeutet wird.
Mitte: Mögliche Startformationen. Die Flagge soll sicher auf der Rückseite verstaut werden, wobei Bomben an den Seiten für Schutz sorgen. Die beiden hellblauen Bereiche sind „Seen“ und dürfen niemals betreten werden.
Rechts: Ein laufendes Spiel. Sie können sehen, dass der Spion des blauen Teams den Marschall des roten Teams gefangen genommen hat.
Dieses Spiel hat AlphaZero verblüfft
In Stratego sind Informationen verborgen.
Nur wenn Sie auf andere Spieler treffen, wird die Identität der gegnerischen Figuren enthüllt.
Der Unterschied zwischen Schach und Go besteht darin, dass es sich um „perfekte Informationsspiele“ handelt, da beide Spieler den Standort und die Identität jeder Schachfigur genau kennen.
AlphaZero von DeepMind hat in perfekten Informationsspielen immer gut abgeschnitten, aber in Stratego war es ratlos.
Im Schach überholte AlphaZero Stockfish nach 4 Stunden; im Shogi übertraf AlphaZero Elmo nach 2 Stunden; und im Go übertraf AlphaZero AlphaGo, das Lee Sedol nach 30 Stunden besiegte.
Stratego ähnelt eher Texas Hold. em und erfordert menschenähnliche Fähigkeiten – Menschen müssen Entscheidungen mit unvollständigen Informationen treffen und müssen bluffen.
Der amerikanische Schriftsteller Jack London hat einmal darauf hingewiesen: „Im Leben haben wir nicht immer gute Karten, aber manchmal können wir mit einer schlechten Hand gut spielen.“
Tatsächlich sind viele KIs auch sehr gut Als sie gegen Stratego spielten, waren sie verwirrt – der Prozess dieses Spiels ist zu lang!
Um zu gewinnen, müssen die Spieler Hunderte von Zügen ausführen. Daher muss die Argumentation im Spiel auf einer großen Anzahl kontinuierlicher Aktionen basieren. In diesem Prozess ist es schwierig, klar zu erkennen, wie sich jede Aktion auf das Endergebnis auswirkt.
Der Größenunterschied zwischen Schach, Poker, Go und Strategie
Auch die Anzahl der möglichen Spielzustände („Spielbaumkomplexität“) im Vergleich zu Schach, Go und Poker ist aus den Charts, es ist sogar noch schwieriger zu lösen.
Und deshalb ist Stratego so spannend – es stellt eine jahrzehntelange Herausforderung in der KI-Community dar.
Stratego: Das Hochland, das die KI erobern muss
Im Laufe der Jahre ist die Frage, wie man künstliche Intelligenz im Stratego-Spiel hervorheben kann, zum Fokus der KI-Forscher geworden.
Es gibt zwei Hauptschwierigkeiten beim Besiegen menschlicher Spieler in diesem Spiel.
Zuallererst hat der Spielbaum dieses Spiels 10 535. Potenzzustände, das heißt, es gibt 10 mögliche Layouts der 535. Potenz in einem Spiel. Im Gegensatz dazu gibt es in Go nur 10 mögliche Layouts.
Zweitens muss die künstliche Intelligenz in Stratego mehr als 10 hoch 66 über die Einsatzstrategie des Gegners nachdenken, während es beim Poker nur tausend mögliche Kartenpaare gibt.
Daher ist es nicht einfach, das komplizierte Layout von Stratego zu knacken. Wie man menschliche Stratego-Spieler besiegt, ist eine beispiellose Herausforderung für KI-Forscher.
DeepNash hat andere KIs völlig übertroffen, da es eine neuartige Methode anwendet, die auf einer Kombination aus Spieltheorie und modellfreiem Deep Reinforcement Learning basiert.
„Modelllos“ bedeutet, dass DeepNash nicht versucht, den Zustand des Gegners im Spiel explizit zu simulieren.
Besonders in der Anfangsphase des Spiels, wenn DeepNash wenig über die Figuren des Gegners weiß, ist diese Modellierung, selbst wenn sie abgeschlossen werden kann, mit hoher Wahrscheinlichkeit ungültig.
Da der Spielbaum von Stratego außerdem so komplex ist, kann DeepNash beim Spielen von Spielen nicht die Monte-Carlo-Baumsuche übernehmen, die von anderen KIs verwendet wird. Letzteres ist der Schlüssel zu den bahnbrechenden Errungenschaften der KI bei weniger komplexen Brettspielen und Poker.
Es zeigt sich, dass die Gleichgewichtsstrategie zwar in einem vollständigen Informationsspiel, in dem beide Parteien abwechselnd agieren, eine Rolle spielen kann, in einem unvollständigen Informationsspiel jedoch unzureichend ist.
DeepNash übernimmt eine neue spieltheoretische Algorithmusidee – Regularized Nash Dynamic Programming (Regularized Nash Dynamic, R-NaD).
Dieser modellfreie Reinforcement-Learning-Algorithmus ist der Kern von DeepNash.
Es leitet DeepNash und sorgt dafür, dass sich sein Lernverhalten in Richtung des Nash-Gleichgewichts entwickelt.
DeepNash kombiniert R-NaD mit einer tiefen neuronalen Netzwerkarchitektur und konvergiert zum Nash-Gleichgewicht.
Beinhaltet drei Schritte: Belohnungstransformation, dynamische Planung (Dynamik) und Aktualisierungsiteration (Udate).
Das Forschungsteam wandte diese drei Schritte wiederholt an, bis eine Reihe von Fixpunkten generiert wurde, um zu beweisen, dass der Algorithmus dem Nash-Gleichgewicht des Originalspiels konvergierte.
Im Spiel gegen die stärksten Stratego-Roboter (darunter mehrere Gewinner der Computer Strategy World Championship) hat DeepNash eine Siegesquote von 97 % und erreicht oft eine Siegesquote von 100 %.
Auf der Gravon-Gaming-Plattform erreichte DeepNash eine Gewinnquote von 84 % gegen die besten menschlichen Spieler und gehörte damit zu den Top Drei in der Geschichte.
Natürlich kann das Nash-Gleichgewicht durch die Spieltheorie nicht ohne Einschränkungen im Spiel erreicht werden, da die Gewinnquote des Spielers auf diese Weise nicht garantiert werden kann.
Die Gleichgewichtsstrategie ist nur in Spielen mit vollständigen Informationen vollständig anwendbar. In Spielen mit unvollständigen Informationen sind andere Strategien erforderlich, um unerwartet zu gewinnen.
Bei der anfänglichen Aufstellung der Truppen hat DeepNash ein außergewöhnliches Gameplay übernommen. Um die Ausbeutung zu erschweren, entwickelte DeepNash eine unvorhersehbare Strategie.
Das bedeutet, dass der anfängliche Einsatz flexibel genug sein muss, um zu verhindern, dass der Gegner in den folgenden Matchserien sein eigenes Muster entdeckt.
In der Spielphase wird DeepNash außerdem versuchen, möglichst viele scheinbar identische Aktionen zufällig zu verteilen, um zu verhindern, dass es selbst ausgenutzt wird.
In diesem Prozess ist das Verbergen von Informationen sehr wichtig.
Informationen verbergen und Ihren Gegner verwirren
In realen Szenarien nutzen die Leute auch andere Mittel, um zu gewinnen, wie zum Beispiel Bluffen.
Wie der „Vater der Spieltheorie“ von Neumann beschrieb: „Das wirkliche Leben ist voller ‚Bluffen‘, ‚kleiner Täuschungsmanöver‘ und ‚Raten, was andere denken, ich werde tun‘
Tao Zhexuans „Selbstmordproblem mit roten und blauen Augen“: Ich weiß, ich weiß, dass er es weiß, ich weiß, dass er weiß, dass er es weiß ...
In dieser Hinsicht liegt DeepNash nicht weit zurück.
Das Forschungsteam demonstrierte die beiden Blufftechniken von DeepNash: aktives Bluffen (positives Bluffen) und passives Bluffing (negatives Bluffing).
Das sogenannte aktive Bluffen besteht darin, vorzutäuschen, dass die eigenen Schachfiguren von hoher Qualität sind, um den Gegner einzuschüchtern. Einfach ausgedrückt handelt es sich um „Bluffen“.
In diesem Beispiel hat DeepNash uns eine gute Lektion erteilt:
Beim Spiel gegen menschliche Spieler (rote Seite) opferte DeepNash (blaue Seite) im frühen Spiel 7 (Major) und 8 (Oberst). Die Kosten für die Figuren betragen um die 10 (Marschall), 9 (General), eine 8 und zwei 7er des Gegners zu identifizieren.
Zu diesem Zeitpunkt hat DeepNash (blaue Seite) viele der stärksten Teile des Gegners gefunden und gleichzeitig seine eigenen Schlüsselteile versteckt.
Auf den ersten Blick scheint DeepNash klar im Nachteil zu sein: Seine 7 und 8 fallen aus, aber der menschliche Gegner behält alle Steine auf Rang 7 und höher.
Allerdings hatte DeepNash den letzten Lacher – basierend auf den zuverlässigen Informationen, die es über die Geschäftsleitung des Gegners erhalten hatte, schätzte es seine Gewinnwahrscheinlichkeit auf 70 %.
Am Ende hat es gewonnen.
Die „Kunst“ des Bluffens
Beim Poker spielen gute Spieler psychologische Kriegsführung, um die andere Partei einzuschüchtern, selbst wenn wir schwach sind.
DeepNash hat auch diese Bluff-Strategie gelernt – negatives Bluffen.
Das nennen wir oft „Stellen Sie sich vor, ein Schwein zu sein und fressen Sie den Tiger“: Verkleiden Sie Ihre High-Level-Schachfiguren als Low-Level-Schachfiguren, warten Sie, bis der Gegner getäuscht ist, und gewinnen Sie sie dann auf einen Schlag.
Im Beispiel unten verwendet DeepNash 2 (ganz schwach ein Scout), um die 8 des Gegners zu jagen, der seine Identität preisgibt.
Der menschliche Gegner ermittelt daraus, dass es sich bei dem Verfolger wahrscheinlich um 10 handelt, und versucht ihn daher in den Hinterhaltkreis des Spions zu locken.
Am Ende gelang es DeepNash, mit der kleinen Schachfigur 2 die Schlüsselschachfigur Spion des Gegners zu zerstören.
Der menschliche Spieler (rote Seite) ist überzeugt, dass die unbekannte Figur, die seiner 8 nachjagt, DeepNashs 10 sein muss (denn zu diesem Zeitpunkt hat DeepNash bereits seine einzige 9 verloren
Das Folgende ist ein Vergleich zwischen DeepNash und (anonym) menschliche Experten) Klicken Sie auf diese vier vollständigen Spielvideos, Spiel 1, Spiel 2, Spiel 3 und Spiel 4, und Sie erhalten weitere Überraschungen (die Videoadresse ist im Referenzmaterial aufgeführt)
DeepNashs Spielniveau bin ich Ich habe noch nie von einem künstlichen Stratego-Spieler gehört, der auch nur annähernd das erforderliche Niveau erreicht, um gegen einen menschlichen Spieler zu gewinnen. Aber nachdem ich selbst gegen ihn gespielt habe, war ich bei Gravon nicht überrascht Es ist erlaubt, an der menschlichen Weltmeisterschaft teilzunehmen, es wird gut abschneiden
——Vincent de Boer, Co-Autor des Papiers, ehemaliger Stratego-Weltmeister
Die Zukunft ist unermesslich
R-NaD hat das Potenzial, über die Spielumgebung für zwei Spieler hinauszugehen und groß angelegte Probleme der realen Welt zu lösen Darüber hinaus wird erwartet, dass R-NaD auch neue Anwendungen der KI in anderen Bereichen mit anderen Zielen erschließen wird.
Zum Beispiel bei der Maßstabsoptimierung des Verkehrsmanagements, bei dem Menschen die Absichten anderer oder Umweltinformationen nicht kennen, ist R-NaD dies Wir erwarten, dass wir die Reisezeit optimieren.
Die menschliche Welt ist von Natur aus unvorhersehbar.
Jetzt haben die Menschen ein allgemeines KI-System geschaffen, das angesichts der Unsicherheit robust ist und uns voller Hoffnung für die Zukunft der Menschheit macht .
Referenzen:
http://www.science.org/doi/10.1126/science.add4679
https :/ /www.deepmind.com/blog/mastering-stratego-the-classic-game-of-imperfect-information
https://youtu.be/HaUdWoSMjSY
https://youtu.be/L-9ZXmyNKgs
https://youtu.be/EOalLpAfDSs
https://youtu.be/MhNoYl_g8mo
Das obige ist der detaillierte Inhalt vonDeepMind ist zurück in der Wissenschaft! Die KI „Wall Breaker' spielt Streiche, um menschliche Meister zu besiegen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
