AlphaZero ist ein autodidaktisches Computerprogramm von DeepMind, dessen Algorithmus mehrere komplexe Brettspiele einzig anhand der Spielregeln und Siegbedingungen sowie durch intensives Spielen gegen sich selbst erlernt. Das Programm verwendet einen verallgemeinerten Ansatz von AlphaGo Zero und beherrscht nach entsprechendem Training nicht nur Go, sondern auch die Strategiespiele Schach und Shōgi.
Am 5. Dezember 2017 veröffentlichte DeepMind, eine Forschungseinrichtung für Künstliche Intelligenz und Tochterunternehmen von Alphabet Inc., ein Preprint auf ArXiv über das Programm AlphaZero, in dem beschrieben wird, dass AlphaZero innerhalb von 24 Stunden durch bestärkendes Lernen eine überragende Spielstärke erreichte und die leistungsstärksten Programme Stockfish, Elmo und eine Drei-Tages-Version von AlphaGo Zero in ihren jeweiligen Disziplinen besiegte, dabei jedoch leistungsfähigere Hardware als die Gegnerprogramme verwendete. Mit dem Dokument wurden lediglich zehn Gewinnpartien von AlphaZero gegen Stockfish veröffentlicht. Alle weiteren Partien sowie auch AlphaZero selbst waren zunächst nicht zugänglich und die Ergebnisse des Dokuments nicht durch ein Peer-Review verifiziert. Eine erweiterte und begutachtete Version des Artikels erschien am 7. Dezember 2018 in der Zeitschrift Science.David Silver, Thomas Hubert1, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, Demis Hassabis: A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. In: Science. Vol. 362, Issue 6419, S. 1140–1144 doi:10.1126/science.aar6404
AlphaZero schlug das freie Schachprogramm Stockfish 8 nach neun Stunden Selbstlernen. Für das Anlernen des künstlichen neuronalen Netzwerks wurden 64 Tensor Processing Units (TPU) der zweiten Generation verwendet. Weitere 5.000 TPUs der ersten Generation wurden für das Erzeugen der dazu notwendigen Trainingspartien eingesetzt. Der Algorithmus mit dem trainierten neuronalen Netzwerk spielte dann auf einem einzigen Computer mit lediglich vier TPUs.
Zusammenhang mit AlphaGo Zero AlphaZero (AZ) nutzt eine generalisierte, generische Variante des Algorithmus von AlphaGo Zero (AGZ) und ist fähig, nach entsprechendem Anlernen die drei Brettspiele Shōgi, Schach und Go auf übermenschlichem Niveau zu spielen. Unterschiede zwischen AZ und AGZ sind: AlphaZero hat fest programmierte Algorithmen zur Berechnung von Hyperparametern. Das „künstliche neuronale Netzwerk“ wird kontinuierlich aktualisiert. Die Regeln des fernöstlichen Brettspiels Go sind (im Gegensatz zu Schach) invariant zur Lage des Spielfelds, also auch nach Spiegelung und Drehung gültig. Die Programmierung von AlphaZero zieht im Gegensatz zu AlphaGo Zero keinen Vorteil aus diesen Symmetrien. Schach und Shōgi können (genauso wie auch Go) mit einem Unentschieden enden, weshalb AlphaZero dieses zusätzliche Spielende als Möglichkeit in Betracht ziehen muss. Statt der Gewinnrate versucht AlphaZero daher den zu erwartenden Partieausgang zu optimieren.
AlphaZero im Vergleich zu Stockfish und Elmo In der Spieltheorie sind die Brettspiele Schach, Shōgi und Go endliche Zwei-Personen-Nullsummenspiele mit perfekter Information ohne Zufallseinfluss. Zwei Kontrahenten führen abwechselnd einen Zug auf einem quadratischen Spielfeld aus. Die Strategiespiele unterscheiden sich hinsichtlich ihrer jeweiligen Spielfeldgröße, der Anzahl der Figuren, der Spiel-Komplexität, ihrer Varianz bei Drehung oder Spiegelung der Spielfläche und ihrer möglichen Spielenden.
SpielBrettgrößeFelderanzahlZustandsraum-Komplexität(als dekadischer Logarithmus log10)Spielbaum-Komplexität (log10)Mittlere Spieldauerin HalbzügenKomplexitäteiner passenden VerallgemeinerungSchach 8×8=64 50Die Größe des Zustandsraumes und des Spielbaumes für Schach wurden erstmals abgeschätzt in Shannon gab die Abschätzungen 1043 bzw. 10120 an, kleinere Werte als die in der Tabelle, die aus der Arbeit von Victor Allis stammen. 123 80EXPTIME-vollständigShōgi 9×9=81 71 226 110EXPSPACE-vollständigGo 19×19=361 171John Tromp, Gunnar Farnebäck: Combinatorics of Go. In: tromp.github.io. 31. Januar 2016. (PDF; 483 kB; 38 Seiten; englisch) Diese Arbeit leitet die Abschätzungen 48<log(log(N))<171 für die Anzahl der möglichen Spielverläufe N her. 360 250EXPSPACE-vollständig
Klassische Schachprogramme wie Stockfish evaluieren Positionen und Figuren anhand von Merkmalen, die zumeist von menschlichen Großmeistern definiert und gewichtet werden, kombiniert mit einer leistungsstarken Alpha-Beta-Suche, die einen riesigen Suchbaum mit einer großen Anzahl von Heuristiken und domänenspezifischen Anpassungen erzeugt und bewertet. Der Algorithmus von AlphaZero spielt nur auf Grundlage der Spielregeln und ausgehend von Zufallszügen gegen sich selbst, bewertet die Ergebnisse und optimiert seine Züge und Strategien durch Anpassung der Gewichte seines Netzwerks. Im Hinblick auf das von AlphaZero verwendete Monte-Carlo-Suchverfahren bewertet das Programm lediglich 80.000 Positionen pro Sekunde bei Schach und 40.000 bei Shōgi, wohingegen Stockfish 70 Millionen und Elmo 35 Millionen berechnet. AlphaZero kompensiert die weitaus geringere Anzahl an Auswertungen durch ein neuronales Netzwerk, das sich auf die aussichtsvolleren Varianten innerhalb des Suchbaums konzentriert.
Ergebnisse Schach Das Schachprogramm Stockfish 8 gewann im Dezember 2016 die Top Chess Engine Championship (TCEC Season 9), eine internationale, jährlich ausgetragene Computerschach-Meisterschaft. In den Schachpartien von AlphaZero gegen Stockfish 8 hatten beide Programme jeweils eine Minute Bedenkzeit pro Spielzug. Von 100 Spielen mit klassischer Startaufstellung gewann AlphaZero 25 Spiele mit weißen Figuren, dreimal mit Schwarz und erzielte 72 Unentschieden. Aus einer Reihe von zwölf 100-Spiele-Serien gegen Stockfish, die mit den zwölf populärsten Eröffnungen begannen, gewann AlphaZero 290 Mal, verlor 24 Mal und spielte 886 Mal Unentschieden. Da der Algorithmus von AlphaZero in beiden Fällen über mehr Rechenleistung als Stockfish verfügte, lassen sich keine eindeutigen Schlüsse bezüglich der Leistungsfähigkeit der verwendeten Algorithmen ziehen.
Einige Schachgroßmeister, wie Hikaru Nakamura und der Komodo-Entwickler Larry Kaufman, kritisieren den Sieg von AlphaZero dahingehend, dass das Ergebnis deutlich knapper ausgegangen wäre, wenn die beiden Programme Eröffnungsdatenbanken hätten verwenden dürfen, da Stockfish hierfür optimiert sei. Tatsächlich unterliefen Stockfish in einigen Partien bereits in der Eröffnung grobe Fehler, die mit einem Eröffnungsbuch vermieden worden wären.
Tord Romstad, einer der leitenden Entwickler von Stockfish, publizierte auf Chess.com folgenden Kommentar:
Shōgi Im Vergleich zu Schach ist das japanische Shōgi ein komplexeres Strategiespiel in Hinblick auf die Anzahl möglicher Züge, da es auf einem größeren Brett und mit mehr Figuren gespielt wird und da die meisten geschlagenen Figuren nahezu überall eingesetzt werden können. Nach 12 Stunden Selbstlernen gewann AlphaZero 90 von 100 Spielen gegen Elmo, verlor acht und zwei gingen Unentschieden aus. Um die Spielstärke von Elmo zu erreichen, wurden weniger als zwei Stunden Training benötigt. Innerhalb der Community von Shōgi-Programmierern gab es Kritik an den Spielbedingungen zwischen den Engines von AlphaZero und Elmo.. In: uuunuuun.com. 7. Dezember 2017. (englisch)
Go Nach 34 Stunden Selbstlernen von Go gewann AlphaZero gegen eine drei Tage trainierte Version von AlphaGo Zero in 60 Fällen und verlor 40-mal. AlphaZero erreichte aber schon nach acht Stunden die Spielstärke von AlphaGo Lee. Das ist jene Programmversion, die im März 2016 den Vergleichskampf AlphaGo gegen Lee Sedol 4:1 gewann.
Reaktionen Mehrere Zeitungen wie die Frankfurter Allgemeine Zeitung oder die The Times of London titelten den Umstand, dass das Schachtraining lediglich vier Stunden benötigte: Wired bejubelte AlphaZero als "the first multi-skilled AI board-game champ". Joanna Bryson, eine Expertin für Künstliche Intelligenz, merkte an, dass Googles sie in eine starke Position gegenüber Mitkonkurrenten bringe:
Der dänische Großmeister Peter Heine Nielsen sagte in einem Interview mit der BBC:
Der norwegische Großmeister Jon Ludvig Hammer charakterisierte AlphaZero als mit tiefgreifendem Positionsspiel. Der frühere Schachweltmeister Garri Kasparow sagte:
Der englische Großmeister Matthew Sadler analysierte alle verfügbaren Partien von AlphaZero und veröffentlichte zusammen mit Natasha Regan im Frühjahr 2019 das Buch Game Changer ISBN 978-90-5691-818-7, in dem er die Spielweise des Programms als „bahnbrechend“ und dessen Spielstärke als „phänomenal“ bezeichnet.
Das Open-Source-Projekt Leela Chess Zero, kurz Lc0, versucht die bisher von DeepMind veröffentlichten Designansätze und Algorithmen für heimische PCs und mobile Geräte zu implementieren und wird mit Hilfe der Community trainiert.Lc0 for the Web. In: frpays.github.io. Es basiert auf der ähnlich motivierten Go-Engine Leela und erzielte bereits im Jahr 2018 Achtungserfolge bei Computer-Schachmeisterschaften.Pete: CCC 3: Rapid Redux. In: Chess.com. 4. Oktober 2018.24th WCCC Stockholm 2018. In: chessprogramming.org. Im Mai 2019 siegte Lc0 erstmals bei der Top Chess Engine Championship (TCEC Season 16).
Weblinks
Einzelnachweise
Kategorie:Schach 2017 Kategorie:Maschinelles Lernen Kategorie:Go-Programm Kategorie:KI-Software Kategorie:Schachprogramm