KI hasst Unsicherheit. Um sich jedoch in unserer unvorhersehbaren Welt zurechtzufinden, muss es lernen, Entscheidungen mit unvollkommenen Informationen zu treffen – so wie wir es jeden Tag tun.
DeepMind eben nahm einen Stich bei der Lösung dieses Rätsels. Der Trick bestand darin, die Spieltheorie in eine algorithmische Strategie zu verweben, die lose auf dem menschlichen Gehirn basiert und als Deep Reinforcement Learning bezeichnet wird. Das Ergebnis, DeepNash, stürzte menschliche Experten in einem hochstrategischen Brettspiel namens Stratego. Stratego ist ein notorisch schwieriges Spiel für KI und erfordert mehrere Stärken des menschlichen Verstands: langfristiges Denken, Bluffen und Strategieentwicklung, ohne die Figuren Ihres Gegners auf dem Brett zu kennen.
„Im Gegensatz zu Schach und Go ist Stratego ein Spiel mit unvollständigen Informationen: Spieler können die Identität der Figuren ihres Gegners nicht direkt beobachten“, DeepMind schrieb in einem Blogbeitrag. Mit DeepNash haben „spielespielende künstliche Intelligenz (KI)-Systeme eine neue Grenze erreicht“.
Es ist nicht alles Spaß und Spiel. KI-Systeme, die die Zufälligkeit unserer Welt leicht manövrieren und ihr „Verhalten“ entsprechend anpassen können, könnten eines Tages reale Probleme mit begrenzten Informationen bewältigen, wie z Autos werden immer präsenter.
„Wenn Sie ein selbstfahrendes Auto bauen, wollen Sie nicht davon ausgehen, dass alle anderen Fahrer auf der Straße vollkommen rational sind und sich optimal verhalten werden.“ sagte Dr. Noam Brown von Meta AI, der nicht an der Forschung beteiligt war.
Der Triumph von DeepNash folgt diesen Monat einem weiteren KI-Fortschritt, wo ein Algorithmus, der gelernt hat, Diplomatie zu spielen– ein Spiel, das Verhandlungen und Zusammenarbeit erfordert, um zu gewinnen. Wenn die KI flexibler wird, verallgemeinert und lernt, sich in sozialen Situationen zurechtzufinden, kann sie auch Einblicke in die neuronalen Prozesse und die Kognition unseres eigenen Gehirns geben.
Lernen Sie Stratego kennen
In Bezug auf die Komplexität ist Stratego ein völlig anderes Tier als Schach, Go oder Poker – alles Spiele, die die KI zuvor gemeistert hat.
Das Spiel besteht im Wesentlichen darin, die Flagge zu erobern. Jede Seite hat 40 Teile, die sie an einer beliebigen Position auf dem Brett platzieren können. Jedes Stück hat einen anderen Namen und einen anderen numerischen Rang, wie „Marschall“, „General“, „Späher“ oder „Spion“. Höherrangige Stücke können niedrigere erobern. Das Ziel ist es, die Opposition auszuschalten und ihre Flagge zu erobern.
Stratego ist eine besondere Herausforderung für die KI, da die Spieler die Position der gegnerischen Spielfiguren nicht sehen können, sowohl während des anfänglichen Aufbaus als auch während des gesamten Spiels. Im Gegensatz zu Schach oder Go, bei dem jede Figur und Bewegung im Blickfeld stehen, ist Stratego ein Spiel mit begrenzten Informationen. Die Spieler müssen bei jeder Entscheidung „alle möglichen Ergebnisse abwägen“, erklärten die Autoren.
Dieses Maß an Unsicherheit ist teilweise der Grund, warum Stratego KI seit Ewigkeiten ratlos ist. Selbst die erfolgreichsten Spielalgorithmen wie AlphaGo und AlphaZero, verlassen Sie sich auf vollständige Informationen. Stratego dagegen hat einen Hauch von Texas Holdem, ein Pokerspiel, das DeepMind zuvor mit einem Algorithmus erobert hat. Aber diese Strategie scheiterte für Stratego, vor allem wegen der Länge des Spiels, das im Gegensatz zum Poker normalerweise Hunderte von Zügen umfasst.
Die Anzahl der möglichen Spielzüge ist überwältigend. Schach hat eine Ausgangsstellung. Stratego hat über 1066 möglichen Startpositionen – weit mehr als alle Sterne im Universum. Der Spielbaum von Stratego, die Summe aller möglichen Züge im Spiel, beläuft sich auf erstaunliche 10535.
„Die schiere Komplexität der Anzahl möglicher Ergebnisse in Stratego bedeutet, dass Algorithmen, die bei Spielen mit perfekter Information gut abschneiden, und sogar solche, die für Poker funktionieren, nicht funktionieren.“ sagte Studienautor Dr. Julien Perolat bei DeepMind. Die Herausforderung ist, „was uns begeistert“, sagte er.
A Beautiful Mind
Die Komplexität von Stratego bedeutet, dass die übliche Strategie zum Suchen von Gameplay-Moves nicht in Frage kommt. Die Technik, die als Monte-Carlo-Baumsuche bezeichnet wird, ein „unerschütterlicher Ansatz für KI-basierte Spiele“, zeichnet potenzielle Routen auf – wie Äste an einem Baum – die zum Sieg führen könnten.
Stattdessen kam der magische Touch für DeepNash von dem im Film porträtierten Mathematiker John Nash A Beautiful Mind. Als Pionier der Spieltheorie erhielt Nash den Nobelpreis für seine Arbeit für die Nash-Gleichgewicht. Einfach ausgedrückt, können die Spieler in jedem Spiel auf eine Reihe von Strategien zurückgreifen, die von allen befolgt werden, sodass kein einzelner Spieler etwas gewinnt, wenn er seine eigene Strategie ändert. In Statego führt dies zu einem Nullsummenspiel: Jeder Gewinn, den ein Spieler erzielt, führt zu einem Verlust für seinen Gegner.
Aufgrund der Komplexität von Stratego hat DeepNash einen modellfreien Ansatz für seinen Algorithmus gewählt. Hier versucht die KI nicht, das Verhalten ihres Gegners genau nachzubilden. Wie ein Baby hat es eine Art unbeschriebenes Blatt zu lernen. Dieses Setup ist besonders in frühen Stadien des Spiels nützlich, „wenn DeepNash wenig über die Figuren seines Gegners weiß“, was Vorhersagen „schwierig, wenn nicht sogar unmöglich“ macht, sagten die Autoren.
Das Team nutzte dann Deep Reinforcement Learning, um DeepNash anzutreiben, mit dem Ziel, das Nash-Gleichgewicht des Spiels zu finden. Es ist ein himmlisches Match: Reinforcement Learning hilft bei der Entscheidung über den besten nächsten Zug in jedem Schritt des Spiels, während DeepNash eine umfassende Lernstrategie bietet. Um das System zu evaluieren, entwickelte das Team außerdem einen „Tutor“, der das Wissen aus dem Spiel nutzte, um offensichtliche Fehler herauszufiltern, die in der realen Welt wahrscheinlich keinen Sinn ergeben würden.
Übung macht den Meister
Als ersten Lernschritt spielte DeepNash in 5.5 Milliarden Spielen gegen sich selbst, ein beliebter Ansatz im KI-Training, der als Selbstspiel bezeichnet wird.
Wenn eine Seite gewinnt, wird die KI ausgezeichnet und ihre aktuellen künstlichen neuronalen Netzwerkparameter werden gestärkt. Die andere Seite – dieselbe KI – erhält eine Strafe, um die Stärke ihres neuronalen Netzwerks zu dämpfen. Es ist, als würde man vor einem Spiegel eine Rede für sich selbst proben. Mit der Zeit finden Sie Fehler heraus und werden besser. Im Fall von DeepNash driftet es für das beste Gameplay in Richtung eines Nash-Gleichgewichts.
Was ist mit der tatsächlichen Leistung?
Das Team testete den Algorithmus gegen andere Elite-Stratego-Bots, von denen einige die Computer-Stratego-Weltmeisterschaft gewannen. DeepNash hat seine Gegner mit einer Gewinnrate von ungefähr 97 Prozent zerquetscht. Als es gegen Gravon – eine Online-Plattform für menschliche Spieler – losgelassen wurde, schlug DeepNash seine menschlichen Gegner. Nach über zwei Wochen voller Spiele gegen Gravons Spieler im April dieses Jahres stieg DeepNash in allen Ranglistenspielen seit 2002 auf den dritten Platz auf.
Es zeigt, dass das Bootstrapping menschlicher Spieldaten für KI nicht erforderlich ist, damit DeepNash eine Leistung auf menschlichem Niveau erreicht – und sie übertrifft.
Die KI zeigte auch ein faszinierendes Verhalten bei der Ersteinrichtung und während des Spiels. Anstatt sich beispielsweise auf eine bestimmte „optimierte“ Startposition festzulegen, verschob DeepNash ständig die Figuren, um zu verhindern, dass sein Gegner im Laufe der Zeit Muster entdeckte. Während des Spiels hüpfte die KI zwischen scheinbar sinnlosen Zügen – wie dem Opfern hochrangiger Figuren – hin und her, um bei einem Gegenangriff die noch höherrangigen Figuren des Gegners zu lokalisieren.
DeepNash kann auch bluffen. In einem Spielzug bewegte die KI eine Figur mit niedrigem Rang, als wäre sie eine hochrangige, und lockte den menschlichen Gegner dazu, der Figur mit ihrem hochrangigen Oberst nachzujagen. Die KI opferte den Bauern, lockte aber im Gegenzug die wertvolle Spionagefigur des Gegners in einen Hinterhalt.
Obwohl DeepNash für Stratego entwickelt wurde, ist es auf die reale Welt verallgemeinerbar. Die Kernmethode kann die KI möglicherweise anweisen, unsere unvorhersehbare Zukunft mit begrenzten Informationen besser anzugehen – von der Kontrolle von Menschenmassen und Verkehr bis hin zur Analyse von Marktturbulenzen.
„Durch die Schaffung eines verallgemeinerbaren KI-Systems, das angesichts von Unsicherheit robust ist, hoffen wir, die Problemlösungsfähigkeiten der KI weiter in unsere von Natur aus unvorhersehbare Welt zu bringen“, sagte das Team.
Bild-Kredit: Derek Bruff/Flickr
