Um den Verschwörungstheoretikern mal etwas den Wind aus den Segeln zu nehmen, nachfolgend ein Auszug aus einem langen Artikel
„Planet >Alpha Zero< oder Schach aus einer anderen Galaxie“, der in
SCHACH 2/2018 vollständig nachgelesen werden kann.
Johannes Zwanzger nimmt darin eine Einordnung des Matches zwischen AlphaZero und Stockfish 8 vor.
Zwanzger ist Computerweltmeister 2015, mit dem von ihm programmierten „Jonny“. Ist also geradezu prädestiniert, sich des Themas anzunehmen. Ausführlicher wird Zwanzger auch noch mal in den „Schach-Fragen“ im selben Heft vorgestellt.
Ich möchte hier nur das letzte Drittel des erwähnten Artikels zitieren. Es fehlen also der Anfang, sowie der Mittelteil mit ausführlich kommentierten Partien des Matches. Wer Interesse hat, kann sich das Heft noch im Handel erwerben, also die aktuelle Ausgabe von
SCHACH.
"
Die MatchbedingungenTrotz aller Begeisterung wurden auch kritische Töne betreffs der Durchführung des Matches laut. Tord Romstad, einer der Gründungsväter des Stockfish-Projektes, verwies darauf, dass nicht die aktuellste Version (*12) zum Einsatz kam und eine absolut unübliche Zeitkontrolle (exakt 60 Sekunden pro Zug, ohne Möglichkeit zur freien Einteilung) Stockfish Spielstärke gekostet habe. Ferner sei das Programm nie ausführlich mit 64 parallel rechnenden Prozessorkernen getestet worden und die Größe der Hashtabellen von 1 GB hierfür viel zu klein.
Romstad ist nicht als schlechter Verlierer bekannt und seine Einwände sind durchaus fundiert. Allerdings kann man die genannten Faktoren auch leicht überbewerten, daher versuche ich mich mit einer Schätzung. Die größte Spielstärkesteigerung hätte vermutlich die Verwendung der neuesten Stockfish-Version bewirkt (ca. +50 Elo gegenüber Version 8). Der Einfluss der fixierten Zugzeit ist schwer zu quantifizieren, daher habe ich ein Experiment durchgeführt. Auf jeweils einem Prozessorkern gewann Stockfish 8 dabei mit zwei Minuten Startbedenkzeit und einem Inkrement von 60 sek/Zug mit 246 : 222 gegen ein auf fixe 60 sek/Zug eingestelltes Pedant (ca. +18 Elo). Der potentielle Elogewinn durch größere Hashtabellen ist selbst experimentell nur schwer auszumachen, er steigt (vermutlich) mit der Zahl der eingesetzten Prozessoren. Ein statistisch aussagefähiger Test dauert dann sehr lange, da immer weniger Partien gleichzeitig auf demselben Rechner gespielt werden können. Nach meinen bisherigen Erfahrungen und ein paar Tests halte ich es für relativ „großzügig“, eine Steigerung von +5 Elo pro Verdoppelung der Hashgröße anzusetzen. Bei sinnvoll erscheinenden 32 GB (fünf Verdoppelungen) käme man also auf +25 Elo.
Das Argument von zu wenig Testerfahrung auf derartiger Hardware kann ich nicht gänzlich nachvollziehen: In den späteren Runden bei TCEC spielen die Engines auch auf 44 Kernen, da ist es nicht mehr weit zu den 64 bei Google.
Ein weiterer – unter anderem von Hikaru Nakamura sowie Komodo-Mitentwickler Larry Kaufmann – geäußerter Kritikpunkt ist, dass beide Programme ohne Eröffnungsbuch angetreten sind. Stockfish sei auf die Verfügbarkeit eines solchen angelegt, während AlphaZero durch das eigenständige Lernen im Laufe der Zeit quasi selbst eine Art „Buch“ entwickelt habe. Vielleicht hätte Stockfish mit einer guten Eröffnungsbibliothek etwas besser abgeschnitten.(*13) Mir ist aber nicht klar, warum das Lernen von AlphaZero in der Trainingsphase (das höchstwahrscheinlich keine explizit nachschlagbare Bibliothek erzeugt, sondern nur ein allgemein besseres Spielverhalten in der Eröffnungsphase) etwas anderes sein soll als das in Form hunderter Patches in den Stockfishcode eingeflossene Tuning von Bewertungstermen, die sich auch (teilweise sogar explizit) auf die Eröffnungsbehandlung auswirken. Nebenbei: Bei TCEC kommen phasenweise ebenfalls nur ganz kleine Bücher zum Einsatz, was dort nach meinem Eindruck mehrheitlich akzeptiert ist. Ich sehe allenfalls ein Problem in der möglicherweise verminderten statistischen Aussagekraft des Matches aufgrund einer gewissen „Eröffnungsmonotonie“ (trotz des prinzipiellen Nichtdeterminismus wiederholt ein buchloser Stockfish noch mit hoher Wahrscheinlichkeit dieselben Varianten, und AlphaZero vermutlich auch).
Unter dem Strich würde ich sagen, dass ein aktueller Stockfish unter günstigeren Bedingungen knapp 100 Elo stärker und damit auf Augenhöhe mit AlphaZero hätte agieren können (das Matchergebnis legt eine Spielstärkedifferenz in genau dieser Größenordnung nahe).Noch schwieriger wird es, wenn man die von beiden Programmen verwendete Hardware vergleichen will: Das 64-Prozessorsystem von Stockfish ist eindrucksvoll, die vier sog. Tensor Processing Units (TPUs), die AlphaZero während des Matches nutzte, sind jedoch in dieser Form wohl nicht einmal frei erhältlich. Da ich mich auf dem Gebiet selbst (noch) nicht wirklich auskenne, zitiere ich mit Remi Coulom einen Experten (und ehemaligen Computerschächer): Er schätzt, dass die Leistung einer solchen TPU ungefähr der einer „V100“ von Nvidia entspricht (Stückpreis ca. 10.000 EUR).(*14) Die Hardware von AlphaZero wäre also kein Schnäppchen, andererseits aber auch nichts, was sich Carlsen & Co. nicht leisten könnten.
Darüber hinaus hält Coulom es für möglich, dass das fertig trainierte AlphaZero Stockfish auch auf gewöhnlicher Hardware hätte schlagen können. Vielleicht ist ein Äquivalent für den Privatanwender also näher, als wir denken?
Aus technischer SichtWas macht AlphaZero anders als die etablierten Programme? Für eine Klärung dieser Frage muss man zunächst die unterschiedlichen Arbeitsweisen betrachten.
Stockfish & Co. suchen, ausgehend von der aktuellen Position, jeweils bis zu einer gewissen Tiefe in die einzelnen Variantenäste hinein (*15) und schätzen die am Ende entstehenden Stellungen mithilfe statischer Bewertungskriterien ab (Materialverhältnis, Königssicherheit, Freibauern, Figurenmobilität etc.). Genau eine solche Bewertung (die zur Hauptvariante) schafft es nach abwechselndem Maxi- und Minimieren über die Züge (je nachdem, wer am Zug ist) bis zur Wurzel zurück. Im Unterschied dazu verwendet der Algorithmus von AlphaZero – eine „Monte-Carlo Tree Search“ (MCTS) – gar keine Bewertung im obigen Sinne mehr. Eine Stellung wird vielmehr anhand der Resultate bei mehrfachem Ausspielen („Rollouts“) bewertet. Hierfür kommen in der Regel (im Vergleich mit einer tiefen Suche) einfach zu berechnende Heuristiken zum Einsatz. Im Extremfall wird jeweils mit reinen Zufallszügen zu Ende gespielt, was dem Algorithmus auch den Namen gab.(*16) Bei den Positionen nahe an der Ausgangsstellung wird die Suche zusätzlich durch die bis zu diesem Zeitpunkt vorliegenden Ausspielergebnisse geführt: Züge mit einem hohen Score werden im Mittel häufiger betrachtet. Diese Strategie wird als „Exploitation“ bezeichnet. Trotzdem wird auch immer wieder mal ein Zug angeschaut, der nicht so gut abgeschnitten hat, wenn er bislang nur sehr selten getestet wurde („Exploration“).
Ein sinnvolles Verhältnis zwischen Exploitation und Exploration ist der eigentliche Clou der MCTS.(*17) Deren Durchbruch kam, als damit vor rund einem Jahrzehnt im Computer-Go erstmals bessere Ergebnisse erzielt wurden als mit der zuvor üblichen Suchtechnik. Dennoch war bis vor wenigen Jahren noch nicht daran zu denken, dass die Menschheit bald auch im Go entthront werden würde. Und selbst dann glaubten die meisten Schachprogrammierer - inklusive Ihres Autors – nicht an einen größeren Erfolg dieser Ansätze im Schach, weil es als äußerst taktisches Spiel mit klaren „Etappenzielen“ (Materialgewinn, Schaffung von Bauernschwächen usw.) dem traditionellen Suchverfahren stark entgegen kommt. So kann man sich täuschen!
Das Ausspielen der Stellungen bis zum Ende dürfte AlphaZero vor allem in Positionen bevorteilen, die einer konkreten Analyse nur schwer zugänglich sind; solche, wo Menschen schreiben würden: „Die Praxis wird zeigen ...“ Als greifbaren Beleg für diese These sehe ich unter anderem die korrekte Einschätzung der Überlegenheit des Läuferpaares in Partie Nr. 1, den Übergang ins Endspiel mit ungleichfarbenen Läufern in Partie Nr. 2 sowie die extrem langfristigen Bauer- bzw. sogar Figurenopfer in einigen anderen Partien. Auch tiefe Zugzwänge, die Stockfish erst sehr spät erkennt, während AlphaZero damit (der Natur von MCTS gemäß) keine besonderen Probleme hat, gehen auf die unterschiedlichen Suchsysteme zurück – was vor allem am Versagen der von fast allen Engines eingesetzten „Nullzug-Heuristik“ liegt. Sie glauben, sie in Zugzwang bringende Züge durch ein nicht legales Aussetzen widerlegen zu können.
Eine weitere Neuerung des AlphaZeroschen Ansatzes ist (zumindest für ein Programm auf diesem Niveau), dass sog. „künstliche neurale Netze“ zum Einsatz kommen. Grob umschrieben dienen diese dem Zweck, vorteilhafte Methoden der Informationsverarbeitung, die sich bei der Entwicklung der Vernetzung von Nervenzellen im Gehirn beobachten lassen, abstrakt nachzubilden (eine echte 1:1-Simulation wird nicht zwingend angestrebt). Ein Computer kann damit anhand von Trainingstests, die Paare aus Inputmustern („Aufgaben“) und gewünschten Outputs („Musterlösungen“) enthalten, lernen, auch neuartige Inputs im Sinne der absolvierten Übungsbeispiele zu beantworten. Konkret wurde bei AlphaZero ein solches Netz offenbar vor allem darauf trainiert, zu einer beliebigen Brettstellung sinnvolle Ausspielwahrscheinlichkeiten für die einzelnen Züge zu generieren. Das Beste aber ist und bleibt: Für das Training wurden nicht etwa menschliche Partien zugrunde gelegt, sondern AlphaZero lernte, als blutiger Anfänger startend, allein durch das Spiel gegen sich selbst!(*18) Das ist für mich, Diskussionen um 100 Elopunkte mehr oder weniger der eigentliche „Schocker“. Heutige Technik kann innerhalb von Stunden selbstständig das Wissen aus Jahrhunderten von Schach- und einigen Jahrzehnten Computerschachforschung aufholen! Hält man sich diesen Fakt in Ruhe vor Augen, fragt man sich, was noch alles unserer harrt …
Ob AlphaZero aufgrund der MCTS oder der neuronalen Netze so stark spielt, vermag ich aktuell nicht zu sagen. Vermutlich ist es gerade die Kombination aus beidem. Jedenfalls sind meines Wissens alle bisherigen Versuche, die jeweils nur eines von beidem involvierten, nicht annähernd an das Level der Topengines herangekommen. Das mag aber auch an dem Trainingsaufwand liegen: Zwar spricht (die Marketingabteilung von) Google von vier Stunden,(*19) setzte in dieser Zeit aber stolze 5.000 TPU ein! Mit nur einer TPU bräuchte man also über zwei Jahre. Andererseits: Die Rechenzeit, die für die Tests im Stockfish-Framework aufgewendet wurde (aktuell über 900 CPU-Jahre), liegt auch nach der Umrechnung CPU-TPU (Faktor 50 zugunsten der TPU?) weit darüber.
Mit Zahlen muss man also vorsichtig sein. Das gilt auch für die 80.000 Stellungen pro Sekunde, die AlphaZero laut Paper untersuchte (gegenüber den 70 Millionen von Stockfish). Solange man nicht weiß, was sich hinter „eine Stellung untersuchen“ verbirgt – eine rein statistische Bewertung oder das komplette Ausspielen einer Partie? -, sollte man keine voreiligen Schlüsse ziehen.
Im Paper wird auch die Vermutung angestellt, dass die Spielstärke durch den Einbau einiger Techniken aus der klassischen Schachprogrammierung noch weiter gesteigert werden könnte. Das deckt sich mit meinem Eindruck, dass für DeepMind bei AlphaZero vor allem die generelle Anwendbarkeit auf verschiedene Spiele im Fokus stand (*20) und auf schachspezifische Optimierungen verzichtet wurde. Auch ein längeres Training hätte die Elokurve sicher weiter nach oben getrieben.
Fazit und PrognoseWas bedeutet dieser Durchbruch für die Zukunft unseres Spiels? An die Tatsache, dass die Engines in einer anderen Liga agieren, haben wir uns längst gewöhnt, und trotzdem wird weiter munter „Menschenschach“ gespielt. Daran würde auch ein für jeden erhältliches AlphaZero nichts ändern. Welche Engine mir den verpassten Figurengewinn zeigt, ist letztlich egal. Für Amateurspieler sehe ich daher abseits der Faszination keine größeren Auswirkungen.(*21)
Profis dagegen könnte durch den Zugriff auf ein AlphaZero-Äquivalent ein temporärer Vorteil bei der Eröffnungsvorbereitung winken. Einige von der Elite spontan geäußerte Meinungen sollte man nicht überbewerten, lesenswert ist auf jeden Fall, was Peter Swidler zu sagen hatte.(*22) Dass AlphaZero auch ohne Buch das Potential zu spannenden Eröffnungsneuerungen hat, ist jedenfalls mindestens anhand des Damenindisch-Komplexes deutlich geworden.
Wie hoch ist die Wahrscheinlichkeit, dass in absehbarer Zeit eine vergleichbare Engine auf unseren Rechnern läuft? Sehr hoch! Die Programmierer sind alarmiert, im Stockfish-Lager werden bereits die ersten MCTS-Experimente aufgesetzt. Auch die Rechenpower dieser Community für das eventuelle Trainieren eines neuralen Netzes sollte man nicht unterschätzen. Schach war für AlphaZero zudem nur eines von mehreren Spielen – nicht unwahrscheinlich also, dass sich mit spezifischen Optimierungen Ansätze finden lassen, die auch mit Standarthardware schon gut funktionieren. Da neuronale Netze jüngst auch auf anderen Gebieten (Bilderkennung, autonomes Fahren) spektakuläre Durchbrüche ermöglicht haben, rechne ich ohnehin damit, dass bald jeder eine TPU im Rechner stecken hat.
Eine letzte Beobachtung. Zwischen den Weiß- und Schwarzergebnissen von AlphaZero gibt es eine auffallend hohe Diskrepanz: +190 Elo gegenüber Stockfish mit Weiß, nur +20 mit Schwarz, also 170 Punkte Unterschied. Normalerweise sollte die Differenz um die 60 Zähler betragen. Sehen wir hier schon eine Art Sättigungseffekt, der AlphaZeros Überlegenheit infolge der hohen Remisbreite in den Schwarzpartien abschwächt? Das könnte umgekehrt bedeuten, dass Stockfish bereits heute gut genug ist, um mit Weiß (fast) nie zu verlieren, egal gegen wen …
*12
Stockfish 8 wird zwar auf stockfish.org immer noch prominent zum Download angeboten, unter „Development build“ finden sich jedoch bereits verbesserte Programmversionen. (Inzwischen gibt es brandaktuell auch Stockfish 9)
*13
Was direkte Eröffnungsfehler angeht, ist mir allerdings nur Partie 4 ins Auge gestochen, wo Stockfish als Schwarzer in einem Franzosen mit 9...c4? Zu früh das Zentrum abriegelte.
*14
http://talkchess.com/forum/viewtopic...741302&t=65909*15
Die Tiefe ist aber heute längst nicht mehr für alle Varianten gleich (was man als sog. „Shannon-A-Strategie“ bezeichnen würde). Vielmehr kommen ausgefeilte Heuristiken zum Einsatz, um wichtige von unwichtigen Varianten zu unterscheiden und entsprechend tiefer oder flacher zu suchen. Jedes Programm, das so agiert, folgt der „Shannon-B-Strategie“. Daher ist die Aussage, AlphaZero habe sich Letzterer „angenähert“ (mit der Kasparow zitiert wird), so nicht richtig. AlphaZero setzte sie allenfalls noch stärker um als bisher üblich.
*16
Laut Wikipedia wurde der Begriff „Monte-Carlo-Simulation“ (für eine auf Zufallsergebnissen basierende Simulation) durch John von Neumann in Anlehnung an den Namen einer Spielbank in Monaco geprägt.
*17
Ein anschauliches Problem (vgl.
https://en.wikipedia.org/wiki/Multi-armed_bandit), dessen Lösung sogar Einfluss auf MCTS hatte, ist folgendes: Stellen Sie sich vor, Sie bekommen einen festen Betrag und dürfen damit an einigen Spielautomaten mit unterschiedlichen, Ihnen unbekannten Gewinnwahrscheinlichkeiten zocken, Wie gehen Sie vor? Wählen Sie einfach einen Automaten und werfen all Ihr Geld hinein (0% Exploration, 100% Exploitation)? Oder füttern Sie die Automaten gleichmäßig, womit Sie im Laufe der Zeit immer bessere Statistiken zu Ihren Gewinnwahrscheinlichkeiten bekommen, aber natürlich auch immer wieder Geld in diejenigen stecken, die in dieser Hinsicht nicht sehr attraktiv erscheinen (100% Exploitation, 0% Exploitation)? Beides ist suboptimal.
*18
Obwohl DeepMind-Gründer Demis Hassabis – mit 13 Jahren weltweite Nr. 2 in der U14 hinter Judith Polgar – sicher bis zu einem gewissen Punkt hätte helfen können.
*19
Dass diese Zeit auch benötigt wurde, kann man einer Grafik des Papers entnehmen: Nach 100.000 Partien gegen sich selbst (statt der finalen 700.000) spielte AlphaZero erst auf Großmeister- statt auf 3500er-Niveau.
*20
„Nebenbei“ wurde mit den gleichen Methoden auch noch das beste Shogi-Programm und mit AlphaZero sogar ein hauseigener Vorläufer im Go geschlagen, der seinerseits AlphaGo mit 100 : 0 (!) besiegt hatte.
*21
Nicht ausschließen würde ich jedoch, dass sich bei Verbreitung von MCTS und neuronalen Netzen in Standardprogrammen neue Analyse- und Trainingsmöglichkeiten auftun könnten. Ein einfaches Beispiel wäre, die Ergebnisse der Rollouts zu nutzen, um die Remistendenz einer Eröffnungsvariante abzuschätzen oder – durch gezieltes Verschieben der Gewichtung von Remis und Sieg – die Engine bei den Kalkulationen von vornherein nur die Gewinnchance maximieren zu lassen.
*22
https://www.chess.com/blog/Spektrows...uss-alpha-zero "
Ende des Auszuges aus
SCHACH 2/2018