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.[1] 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[2] 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.[3] 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.[4]

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.[5] Der Algorithmus mit dem trainierten neuronalen Netzwerk spielte dann auf einem einzigen Computer mit lediglich vier TPUs.[6]

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öße
Felderanzahl		Zustandsraum-Komplexität
(als dekadischer Logarithmus log10)		Spielbaum-
Komplexität (log10)		Mittlere Spieldauer
in Halbzügen		Komplexität
einer passenden Verallgemeinerung
Schach8×8=6450[7]123[7]80EXPTIME-vollständig[8]
Shōgi9×9=8171[9]226[9]110EXPSPACE-vollständig[10]
Go19×19=361171[11]360[12]250EXPSPACE-vollständig[13]

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.[1] 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,[5] wohingegen Stockfish 70 Millionen und Elmo 35 Millionen berechnet.[14] 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.[15][16] 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.[17] Tatsächlich unterliefen Stockfish in einigen Partien bereits in der Eröffnung grobe Fehler, die mit einem Eröffnungsbuch vermieden worden wären.[18]

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

– Tord Romstad[19]

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.[20]

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[21] 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.”[22] Wired bejubelte AlphaZero als "the first multi-skilled AI board-game champ".[23] 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.“[16]

Der norwegische Großmeister Jon Ludvig Hammer charakterisierte AlphaZero als “insane attacking chess” (deutsch: „wahnsinniges Angriffsschach“) mit tiefgreifendem Positionsspiel.[24] 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.“[25]

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

Weblinks

Einzelnachweise

  1. ↑ a b Lars Fischer: Künstliche Intelligenz schlägt besten Schachcomputer der Welt. In: Spektrum. 6. Dezember 2017, abgerufen am 13. Dezember 2017.
  2. ↑ Stefan Löffler: AlphaZero statt Alpha Beta. In: Frankfurter Allgemeine Zeitung. 10. Dezember 2017, abgerufen am 13. Dezember 2017.
  3. ↑ David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, Demis Hassabis: Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm. 5. Dezember 2017 (englisch, arxiv.org [PDF; 623 kB]).
  4. ↑ 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
  5. ↑ a b Varun Kumar: Google’s AlphaZero AI Masters Chess and Go Within 24 Hours. In: RankRed. 8. Dezember 2017, abgerufen am 13. Dezember 2017 (britisches Englisch).
  6. ↑ James Vincent: DeepMind’s AI became a superhuman chess player in a few hours, just for fun. In: The Verge. 6. Dezember 2017, abgerufen am 9. Dezember 2017 (amerikanisches Englisch).
  7. ↑ a b Die Größe des Zustandsraumes und des Spielbaumes für Schach wurden erstmals abgeschätzt in Claude Shannon: Programming a Computer for Playing Chess. In: Philosophical Magazine. 41. Jahrgang, Nr. 314, 1950 (computerhistory.org [PDF]). Shannon gab die Abschätzungen 1043 bzw. 10120 an, kleinere Werte als die in der Tabelle, die aus der Arbeit von Victor Allis stammen.
  8. ↑ Aviezri Fraenkel, David Lichtenstein: Computing a perfect strategy for n×n chess requires time exponential in n. In: Journal of Combinatorial Theory, Series A. Nr. 31, 1981, S. 199–214, doi:10.1016/0097-3165(81)90016-9.
  9. ↑ a b Shi-Jim Yen, Jr-Chang Chen, Tai-Ning Yang, Shun-Chin Hsu: Computer Chinese Chess. In: International Computer Games Association Journal. Band 27, Nr. 1, März 2004, S. 3–18 (englisch, psu.edu [PDF; 221 kB]).
  10. ↑ Adachi Hiroyuki, Kamekawa Hiroyuki, Iwata Shigeki: Shogi on n×n board is complete in exponential time. In: Trans. IEICE. J70-D. Jahrgang, 1987, S. 1843–1852.
  11. ↑ John 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.
  12. ↑ Victor Allis: Searching for Solutions in Games and Artificial Intelligence. 1994, ISBN 90-90-07488-0 (englisch, online [PDF; 10,3 MB; abgerufen am 14. Dezember 2017] Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands).
  13. ↑ J. M. Robson: Information Processing; Proceedings of IFIP Congress. 1983, The complexity of Go, S. 413–417 (englisch).
  14. ↑ Shivali Best, Joe Pinkstone: Google's 'superhuman' AlphaZero AI becomes one of the best chess players in the world after learning the game from scratch in just FOUR HOURS. In: Daily Mail. 7. Dezember 2017, abgerufen am 13. Dezember 2017 (britisches Englisch).
  15. ↑ Googles „Alphazero“ kann auch Schach. (Nicht mehr online verfügbar.) In: DLF24. Deutschlandfunk, 9. Dezember 2017, archiviert vom Original am 10. Dezember 2017; abgerufen am 10. Dezember 2017.
  16. ↑ a b 'Superhuman' Google AI claims chess crown. In: BBC News. 7. Dezember 2017, abgerufen am 11. Dezember 2017 (britisches Englisch).
  17. ↑ Mike Klein: Google's AlphaZero Destroys Stockfish In 100-Game Match. In: Chess.com. 6. Dezember 2017, abgerufen am 10. Dezember 2017 (englisch).
  18. ↑ Stockfish (Computer) vs AlphaZero (Computer). In: chessgames.com. 11. Dezember 2017, abgerufen am 11. Dezember 2017 (englisch).
  19. ↑ Peter Doggers: AlphaZero: Reactions From Top GMs, Stockfish Author. In: chess.com. 8. Dezember 2017, abgerufen am 9. Dezember 2017 (englisch).
  20. ↑ Some concerns on the matching conditions between AlphaZero and Shogi engine. In: uuunuuun.com. 7. Dezember 2017. (englisch)
  21. ↑ Alexander Armbruster: Schlauer Computer spielt Weltklasse-Schach – nach nur vier Stunden. In: Frankfurter Allgemeine Zeitung. 8. Dezember 2017, abgerufen am 9. Dezember 2017.
  22. ↑ Nadeem Badshah: Google’s DeepMind robot becomes world-beating chess grandmaster in four hours. In: The Times of London. 7. Dezember 2017, abgerufen am 10. Dezember 2017 (britisches Englisch).
  23. ↑ Tom Simonite: Alphabet's Latest AI Show Pony Has More Than One Trick. In: Wired. 6. Dezember 2017, abgerufen am 11. Dezember 2017 (amerikanisches Englisch).
  24. ↑ Sarah Knapton, Leon Watson: Entire human chess knowledge learned and surpassed by DeepMind's AlphaZero in four hours. In: The Telegraph. 6. Dezember 2017, abgerufen am 10. Dezember 2017 (britisches Englisch).
  25. ↑ Samuel Gibbs: AlphaZero AI beats champion chess program after teaching itself in four hours. In: The Guardian. 7. Dezember 2017, abgerufen am 9. Dezember 2017 (britisches Englisch).
  26. ↑ Machine Learning: Alpha Zero selbermachen (Memento des Originals vom 26. Mai 2018 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/www.crn.de. In: crn.de
  27. ↑ Lc0 for the Web. In: frpays.github.io.
  28. ↑ Pete: CCC 3: Rapid Redux. In: Chess.com. 4. Oktober 2018.
  29. ↑ 24th WCCC Stockholm 2018. In: chessprogramming.org.
  30. ↑ A new age in computer chess? Lc0 beats Stockfish! Abgerufen am 5. Februar 2020 (englisch).