AlphaZero
# AlphaZero

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.

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.

| Spiel | Brettgröße Felderanzahl | Zustandsraum-Komplexität (als dekadischer Logarithmus $log_{10})$ | Spielbaum- Komplexität $(log_{10})$ | Mittlere Spieldauer in Halbzügen | Komplexität einer passenden Verallgemeinerung |
| - | - | - | - | - | - |
| Schach | 8×8=64 | 50 | 123 | 80 | EXPTIME-vollständig |
| Shōgi | 9×9=81 | 71 | 226 | 110 | EXPSPACE-vollständig |
| Go | 19×19=361 | 171 | 360 | 250 | EXPSPACE-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:

   “The match results by themselves are not particularly meaningful because of the rather strange choice of time controls and Stockfish parameter settings: The games were played at a fixed time of 1 minute/move, which means that Stockfish has no use of its time management heuristics (lot of effort has been put into making Stockfish identify critical points in the game and decide when to spend some extra time on a move; at a fixed time per move, the strength will suffer significantly). The version of Stockfish used is one year old, was playing with far more search threads than has ever received any significant amount of testing, and had way too small hash tables for the number of threads. I believe the percentage of draws would have been much higher in a match with more normal conditions.”
   „Die Spielergebnisse an sich sind nicht besonders aussagekräftig, da die Wahl der Zeitsteuerung und der Parametereinstellungen von Stockfish ziemlich merkwürdig ist: Die Spiele wurden mit einer festen Zugdauer von einer Minute pro Zug gespielt, was bedeutet, dass Stockfish seine Heuristiken zum Zeitmanagement nicht nutzen konnte (es wurde viel Mühe darauf verwendet, Stockfish beizubringen, kritische Situationen im Spiel zu identifizieren und zu entscheiden, wie viel Zeit es für einen Zug benötigt; bei festgesetzter Dauer pro Zug leidet die Spielstärke erheblich). Die verwendete Version von Stockfish ist bereits ein Jahr alt und spielte mit weit mehr Such-Threads, als jemals signifikant getestet wurde. Die Hashtabellen waren viel zu klein für die Anzahl der Threads. Ich glaube, dass der Prozentsatz an Unentschieden in einem Spiel mit gewöhnlichen Bedingungen viel höher gewesen wäre.“

### 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.

### 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: “It was managed in little more than the time between breakfast and lunch.” 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 “knack for good publicity” (deutsch: „Talent für gute Öffentlichkeitsarbeit“) sie in eine starke Position gegenüber Mitkonkurrenten bringe:

   “It's not only about hiring the best programmers. It's also very political, as it helps makes Google as strong as possible when negotiating with governments and regulators looking at the AI sector.”
   „Es geht nicht nur darum, die besten Programmierer einzustellen. Es ist auch sehr politisch, da es hilft, Google so stark wie möglich zu machen, wenn es mit Regierungen und Aufsichtsbehörden verhandelt, die sich mit dem KI-Sektor befassen.“

Der dänische Großmeister Peter Heine Nielsen sagte in einem Interview mit der BBC:

   “I always wondered how it would be if a superior species landed on earth and showed us how they played chess. Now I know.”
   „Ich habe mich immer gefragt, wie es sei, wenn eine überlegene Spezies auf der Erde landete und uns ihre Art Schach zu spielen zeigte. Nun weiß ich es.“

Der norwegische Großmeister Jon Ludvig Hammer charakterisierte AlphaZero als “insane attacking chess” (deutsch: „wahnsinniges Angriffsschach“) mit tiefgreifendem Positionsspiel. Der frühere Schachweltmeister Garri Kasparow sagte:

   “It’s a remarkable achievement, even if we should have expected it after AlphaGo. We have always assumed that chess required too much empirical knowledge for a machine to play so well from scratch, with no human knowledge added at all.”
   „Es ist eine bemerkenswerte Leistung, auch wenn wir das nach AlphaGo erwarten konnten. Wir haben immer angenommen, dass Schach zu viel empirisches Wissen erfordert, als dass eine Maschine es von Grund auf, ohne jedes zusätzliche menschliche Wissen, so gut spielen könnte.“

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. Es basiert auf der ähnlich motivierten Go-Engine Leela und erzielte bereits im Jahr 2018 Achtungserfolge bei Computer-Schachmeisterschaften. Im Mai 2019 siegte Lc0 erstmals bei der Top Chess Engine Championship (TCEC Season 16).

