Mit einer Gewinnrate von 99,41 % schlägt die KI menschliche Schachspieler. Wird die KI den Menschen dieses Mal wirklich schlagen?

Auch dieses Mal hat die KI die Menschen geschlagen.

Ein Forschungsteam unter der Leitung von Dai Zonghong, CTO von Huawei Cloud AI, und Yang Yaodong, Assistenzprofessor am KI-Institut der Peking-Universität, hat einen Algorithmus entwickelt, der menschliche Gegner mit einer Gewinnrate von 99,41 % in Schachspielen vernichtend schlagen kann – JiangJun (ausgesprochen „General“).

Das zugehörige Forschungspapier mit dem Titel „JiangJun: Mastering Xiangqi by Tackling Non-Transitivity in Two-Player Zero-Sum Games“ wurde auf der Preprint-Website arXiv veröffentlicht.

Die Verwendung menschlicher Spieler als Gegner und die Durchführung kontinuierlicher Versuche und Iterationen ist die übliche Art der Entwicklung aktueller auf bestärkendem Lernen basierender KI-Agenten. Angesichts der Tatsache, dass in realen Szenarien üblicherweise mehrere Agenten gleichzeitig agieren, haben Forscher in den letzten Jahren ihren Fokus vom Einzelagentenbereich auf den Multiagentenbereich ausgeweitet.

Tatsächlich hat das bestärkende Lernen mit mehreren Agenten in verschiedenen Spielbereichen bemerkenswerte Erfolge erzielt und sich in Spielen wie Hide and Seek (einem Spiel auf Steam), Go, StarCraft II, Dota 2 und Militärschach bewährt.

Allerdings sind Algorithmen wie AlphaZero und AlphaGo, die sich beim Training auf die jüngste Leistung ihres Gegners konzentrieren, möglicherweise nicht in der Lage, Spiele mit nicht-transitiven Strukturen konstant zu gewinnen oder den gewünschten Zustand zu erreichen. Obwohl dieses Problem bei Spielen mit unvollständigen Informationen intensiv untersucht wurde, wurde es bei Spielen mit vollständigen Informationen relativ weniger untersucht.

Spiel mit perfekter Information: Ein Spiel, bei dem jeder Teilnehmer genaue Informationen über die Eigenschaften, Strategien und Auszahlungsfunktionen aller anderen Teilnehmer hat, wie beispielsweise Schach.

Spiel mit unvollständigen Informationen: Mindestens ein Teilnehmer verfügt über unvollständige Kenntnisse der oben genannten Informationen, z. B. Western Army Chess.

Derzeit ist die Überwindung des Problems der Nichttransitivität in Spielen mit perfekter Information ein ungelöstes Forschungsproblem. In der jüngsten Forschung lag der Schwerpunkt auf der Verwendung von PSRO-Algorithmen (Strategy Space Response Oracle) zur Ermittlung von Nash-Gleichgewichten. Allerdings wurden diese Methoden noch nicht in Spielen mit perfekter Information untersucht.

Aufgrund seiner Zugänglichkeit ist Schach ein hervorragendes Thema für die Erforschung von Brettspielen und nicht-transitiver Geometrie. Die Studie untersuchte die komplexen geometrischen Eigenschaften des Schachspiels und deckte anhand eines umfangreichen Datensatzes von mehr als 10.000 menschlichen Partien die signifikante Nichttransitivität des Schachspiels im transitiven Mittelbereich auf.

Zur Lösung des Nichttransitivitätsproblems schlugen die Forscher den JiangJun-Algorithmus vor, der im Gegensatz zur Selbstspielstrategie von AlphaZero Nash-Reaktionen zur Auswahl der Gegner verwendet.

Der JiangJun-Algorithmus besteht aus zwei Basismodulen: MCTS Actor und Populationer. Gemeinsam nutzen diese Komponenten Monte-Carlo-Tree-Search-Techniken (MCTS), um ein Nash-Gleichgewicht innerhalb einer Spielerpopulation zu approximieren.

Die Wirksamkeit des Algorithmus von JiangJun wurde anhand einer Reihe von Kennzahlen umfassend bewertet. Die Forscher schlugen ein Trainingsframework vor, das die Rechenleistung von bis zu 90 V100-GPUs auf der Huawei Cloud ModelArt-Plattform effektiv nutzte, um den JiangJun-Algorithmus auf Master-Niveau zu trainieren.

Mehrere Metriken, darunter die relative Populationsleistung, die Visualisierung der Nash-Verteilung und die Visualisierung der niedrigdimensionalen Spiellandschaft in zwei Haupteinbettungsdimensionen, bestätigen gemeinsam die Leistungsfähigkeit des JiangJun-Algorithmus bei der Lösung des Nichttransitivitätsproblems im Schach.

Darüber hinaus übertrifft der JiangJun-Algorithmus seine zeitgenössischen Algorithmen in der Gewinnrate deutlich, mit Gewinnraten von über 85 % bzw. 96,40 % im Vergleich zum Standard-AlphaZero-Schach und zum Behavior Clone-Schach. Bei der Bewertung der Ausnutzbarkeit lag der Algorithmus von JiangJun deutlich näher an der optimalen Strategie (8,41 % Gewinnrate für nahezu optimale Antworten) als der Standard-Schachalgorithmus von AlphaZero (25,53 %).

Darüber hinaus entwickelten die Forscher ein Schach-Applet auf der WeChat-Plattform, das über einen Zeitraum von sechs Monaten mehr als 7.000 Spielaufzeichnungen zwischen dem JiangJun-Algorithmus und menschlichen Gegnern zusammenstellte. Den Spieldaten zufolge besiegte JiangJuns Algorithmus menschliche Gegner mit einer erstaunlichen Gewinnrate von 99,41 %.

Zusätzlich zu seiner erstaunlichen Gewinnrate von fast 100 % zeigen Fallstudien verschiedener Endspiele, dass der Algorithmus von JiangJun auch über eine starke Fähigkeit verfügt, flexibel auf die Komplexität von Schachendspielen zu reagieren.

Die Einführung des JiangJun-Algorithmus stellt eine erstaunliche Leistung der KI im Schachbereich dar. Durch die Lösung des Nichttransitivitätsproblems in Spielen mit vollständiger Information führte das Forschungsteam erfolgreich die Nash-Reaktions- und Monte-Carlo-Baumsuchtechnologie ein und brachte so eine neue Denkweise in das Schachspiel. Dieser Algorithmus erzielte nicht nur eine erstaunliche Gewinnrate, sondern demonstrierte auch die leistungsstarke Fähigkeit der KI, mit komplexen und unsicheren Problemen umzugehen.

Referenzlinks:

https://arxiv.org/abs/2308.04719

https://openreview.net/forum?id=MMsyqXIJuk

https://sites.google.com/view/jiangjun-site/

Autorin: Hazel Yan