Wie spielt AlphaZero Schach?

Sicher habt ihr schon von AlphaZeros Sieg über das stärkste Schachprogramm, Stockfish, gehört und die Reaktionen der Großmeister dazu gelesen. 

Aber wie funktioniert AlphaZero eigentlich?

Wie unterscheidet es sich von anderen Engines und warum ist es so viel besser? In diesem zweiteiligen Artikel werde ich versuchen, ein wenig zu erklären, was unter AlphaZeros Motorhaube vor sich geht.

Lasst uns zuerst reflektieren, was passiert ist. AlphaZero wurde von DeepMind (einem Google Unternehmen) entwickelt und darauf spezialisiert, Zwei-Spieler-Spiele bei denen die Spieler die Züge abwechselnd ausführen, zu spielen. Es wurde mit den Regeln des Schachspiels gefüttert und sonst nichts.

Dann begann es Schach zu lernen, indem es Partien gegen sich selbst spielte. Spiel eins bestand aus völlig zufälligen Zügen. Am Ende der Partie hatte DeepZero gelernt, dass der Verlierer etwas getan hatten, das nicht so clever war und dass der Gewinner besser gespielt hatte. DeepZero hatte seine erste Schachlektion erlernt. Die Qualität der zweiten Partie war ein bisschen besser als die erste.

Neun Stunden und 44 Millionen Partien später hatte sich AlphaZero (höchstwahrscheinlich) selbst genug beigebracht, um der größte Schachspieler aller Zeiten zu werden, egal, ob auf Silizium- oder Kohlenstoffbasis.

Aber wie zum Teufel hat das funktioniert?

Das Google Hauptquartier in London von Innen, in dessen 8. Stock DeepMind sitzt. | Foto: Maria Emelianova/Chess.com.

Es hat nicht mehr Varianten als Stockfish berechnet.

Im Gegenteil: Stockfish berechnete 70 Millionen Stellungen pro Sekunde, während sich AlphaZero mit 99,89 Prozent weniger Stellungen begnügte: 80.000 pro Sekunde. Das erinnert mich an eine Bemerkung von Jonathan Rowson, nachdem ihn Michael Adams 1998 in einer Partie förmlich zerquetscht hatte: "Ich war erstaunt, wie wenig er gesehen hat."

Stärkere Spieler neigen dazu, weniger Varianten zu berechnen als schwächere. Stattdessen hilft ihnen ihre hochentwickelte Intuition, ihre Berechnungen auf die relevantesten Linien zu beschränken. Genau das hat AlphaZero getan. Es brachte sich Schach auf eine ziemlich menschenähnliche Art bei, entwickelte eine "Intuition", wie sie noch keine andere Schachengine je entwickelt hat und kombinierte diese Fähigkeit mit einer Menge kaltblütiger Berechnungen.

Sehen wir uns also an, wie AlphaZero das gemacht hat.

IM Danny Rensch erklärt das AlphaZero Match in einer Videoserie auf Twitch.

Der Analysebaum

Schachcomputer verwenden eine baumartige Struktur, um Varianten zu berechnen und verwenden eine Bewertungsfunktion, um der Position am Ende einer Variante einen Wert wie +1,5 (der Vorteil von Weiß ist einen Bauern wert) oder -9,0 (der Vorteil von Schwarz ist eine Dame wert). Der Ansatz von AlphaZero sowohl zum Berechnen von Varianten als auch zum Bewerten von Stellungen unterscheidet sich grundlegend von dem, was andere Engines tun.

Alle gebräuchlichen Schach-Engines basieren auf dem Minimax-Algorithmus, der einfach nur bedeutet, dass Sie den Zug wählen, der Ihnen den größten Vorteil bietet, unabhängig davon, was der Gegner spielt. Minimax wurde durch die Alpha-Beta-Beschneidung verbessert, was bedeutet, dass die Größe des zu berechnenden Baums reduziert wird. Hier ist ein extremes Beispiel dafür, wie dieses Beschneiden funktioniert: Angenommen, eine Engine denkt über einen Zug nach und sieht, dass der Gegner 20 mögliche Antworten hat. Eine dieser Antworten führt zu einem erzwungenen Schachmatt. Dann kann die Engine die Berechnung abschalten, ganz egal wie gut sie nach einem der anderen 19 Züge stehen würde.

Das Problem, das sich daraus ergibt, ist, dass eine Engine einen Zug, der schlecht erscheint, wie z.B. ein Zug der Material verliert, abschaltet. Das erklärt, warum ältere Engines so materialistisch waren und fast nie Opfer in Betracht zogen. In aktuellen Engines wie Stockfish wird die Alpha-Beta-Beschneidung mit einer Reihe anderer schachspezifischer Verbesserungen, wie der Killer-Zug-Heuristik (ein Zug, der in einer ähnlichen Stellung stark war, ist hier wahrscheinlich ebenfalls stark), der Konter-Heuristik (auf einige Züge gibt es unabhängig von der Stellung natürliche Antworten wie z.B axb5 axb5) und vielen anderen Heuristiken kombiniert.

Im Gegensatz dazu verwendet AlphaZero  die Monte Carlo Tree Search, kurz MCTS. Monte Carlo ist berühmt für seine Casinos. Wenn man diesen Begriff im Zusammenhang mit Computern hört, bedeutet das, dass etwas Zufälliges passiert. Ein Computer, der ein reines MCTS verwendet, würde eine Stellung bewerten, indem er eine Anzahl von Zügen ("Playouts") aus dieser Stellung zufällig erzeugt und den wahrscheinlichen Partieausgang (Gewinn / Remis / Verlust), der sich aus diesem Zug ergibt, ermittelt. Dieser Ansatz mag zu einfach erscheinen, aber wenn man darüber nachdenkt, wird man feststellen, dass dies eine ziemlich plausible Möglichkeit ist, eine Stellung zu bewerten.

Das Monte Carlo Casino. 

AlphaZero erstellt bei jedem Zug 800 Playouts. Zusätzlich ergänzt es die reine MCTS, indem es Züge vorzieht, die es noch nicht (oft) versucht hat, die wahrscheinlich erscheinen und zu "guten" Stellungen führen, wobei "gut" für AlphaZero bedeutet, dass ihnen die Bewertungsfunktion einen hohen Wert gibt (mehr dazu im nächsten Artikel). Es erzeugt wirklich halb-zufällige Playouts. Varianten, die zu ihrer immer besser werdenden Stellungen passen. Ist das nicht so, wie Menschen auch rechnen? Durch Konzentration auf plausible Varianten?

Bis jetzt hat AlphaZero absolut nichts Schachspezifisches gemacht. In meinem nächsten Artikel, wenn wir uns ansehen, wie AlphaZero lernt, Stellungen auszuwerten und wir werden sehen, dass es auch dort absolut nichts Schachspezifisches gibt!

Wie ein neugeborenes Baby kam AlphaZero mit wenig Wissen auf die Welt und ist nur auf das Lernen ausgerichtet. Eine Schwäche von MCTS ist, da es auf der Erzeugung halb-zufälliger Playouts basiert, dass es in Stellungen, in denen es nur genau eine spielbare Fortsetzung gibt, einen absoluten Fehler machen kann. Wenn diese Fortsetzung nicht zufällig ausgewählt wird, ist der nächste Zug ziemlich wahrscheinlich ein Fehler. Diese "Blindheit" war wohl der Grund, warum der AlphaZero-Vorgänger AlphaGo ein Spiel gegen den 18-fachen World-Go-Champion Lee Sedol verlor. Im Match mit Stockfish scheint das jedoch kein Problem gewesen zu sein.

MCTS wurde für das Gameplay zwischen zwei Spielern entwickelt, aber es wurde festgestellt, dass es viel schlechter abschneidet als des etablierte Minimax plus Alpha-Beta-Programm. In AlphaZero wurde MCTS sehr gut mit der verwendeten neuronalen Netzwerk-basierten Bewertungsfunktion kombiniert.

In meinem nächsten Artikel werde ich mehr über dieses neuronale Netzwerk und besonders die faszinierende Art und Weise erklären, wie es alleine lernt, verschiedene Stellungen zu bewerten. Ich werde auch die Hardware, auf der AlphaZero läuft, beschreiben und einige Vorhersagen darüber treffen, wie sich all das auf das Schach wie wir es kennen, auswirken wird.

Was denkt ihr über AlphaZero? Schreibt Eure Meinung in den Kommentaren.