AlfaZero

DruckversionDruckversion

Schach auf der Titelseite des Science Magazin

Das Computerprogramm „AlphaZero“ schaffte es am 7. Dezember 2018 auf die Titelseite von Science, einem der weltweit führenden Wissenschaftsmagazine. Das ist kein alltäglicher Vorgang, sondern etwas ganz besonderes.

Wer noch nichts von AlphaZero gehört hat: Es wurde von Google entwickelt, und zwar als Mittel zur Entwicklung artifizieller Intellegenz (AI). Bisher wurde es für Google Street View eingesetzt, aber auch mit Brettspielen auf seine Leistungsfähigkeit überprüft. Getestet wurde es mit den Spielen Go, Schach und Shogi, einer japanischen Form des Schach. Als Gegner wurden die besten „normalen“ Programme verwendet, für Schach war „Stockfish“, das beste herkömmliche Programm.

In dem Artikel in Science geht es um das Programm „AlphaZero“, das in einem sehenswerten Duell das mit Abstand beste Schachprogramm Stockfish vernichtend besiegte. Es gewann 155 von 1000 Partien und verlor 6 Partien, die anderen Partien endeten mit remis. Gespielt wurde mit einer Bedenkzeit von 3 Stunden und zusätzlich 15 Sekunden pro Zug. Stockfish spielte auf einem Rechner mit 44 CPUs (ein sehr guter Rechner aus dem Computerladen hat 8 CPUs), und AlphaZero auf einem Rechner mit 44 CPUs und zusätzlich 2 TPUs. Laut Angabe von MasterMind, das das Programm für Google entwickelt hat, waren die beiden Rechner vergleichbar.

AlphaZero ist ein Programm, das nur auf speziellen Rechnern läuft, die zusätzlich zu den in herkömmlichen Rechnern vorhandenen sogenannten CPUs noch die extra entwickelten TPUs besitzen.

Im Gegensatz zu Stockfish, das von Schachexperten in Zusammenarbeit mit Computerexperten programmiert wurde, lernt AlphaZero selbstständig mittels einer sehr einfachen Methode, die in der Wissenschaft als „Monte Carlo Tree Search“ bezeichnet wird. Das Wissen wird also nicht von Schachgroßmeistern an das Programm weitergegeben, sondern AlfaZero lernte selbstständig das Schachspiel. Bereits nach wenigen Tagen hatte es die Spielstärke von Weltmeister Carlsen, nach einigen Wochen Training war es wesentlich besser als Stockfish 8, das eine kalkulierte Elozahl von über 3300 hat. Im Vergleich dazu hat Weltmeister Carlsen etwas über 2800, ein guter Vereinsspieler hat etwa 2000 Elopunkte.

Der Monte Carlo Tree Search funktioniert im Prinzip so:

Der Rechner beginnt mit der Grundstellung und schaut sich in diesem Beispiel die Eröffnungszüge c4, d4 und e4 an. Er versucht es mit dem Zug c4 und testet die schwarzen Züge c5, e5 und e6. In der Expansion wird der Zug e6 gewählt, worauf die Erwiderungen Sc3 und Sf3 getestet werden. Hier wird der Zug Sc3 und die Antwort d5 getestet, die in der Simulation weiter evaluiert wird. Das Ergebnis der Simulation erhält einen Wert, der zurück an den Rechner gemeldet wird (Backpropagation). Durch wiederholte Selektion werden erneut Züge getestet, worauf eventuell nach vielfacher Selektion das folgende Bild entsteht:

Herkömmliche Rechner stoßen mit dieser Methode irgendwann an die Grenze der Rechenleistung – die Berechnung dauert bei komplexen Spielen wie Schach viel zu lange, um beispielsweise eine Turnierpartie mit drei Minuten Bedenkzeit spielen zu können. Ein "normaler" Computer würde mit dieser Methode ziemlich schwach spielen.

Für Programme wie AlphaZero braucht es Rechner, die sogenannte neuronale Netzwerke simulieren können. Speziell dafür werden sogenannte TPUs gebaut, die auch riesige Monte Carlo Tree Searches bewältigen. Im Prinzip sind es Parallelprozessoren, die von Google für Street View entwickelt wurden, aber auch für Go und Schach nützlich sind.

Schauen wir uns eine bestimmte Stellung an, die in einer Partie vorkam, und wie AlphaZero zog:

 

Nach 100 Simulationen standen die Züge Th1, De2, Tf1, f3, d5, Tcd1, Dd1, Tg1 und Te3 in der näheren Auswahl. Nach 1000 Simulationen standen nur mehr c6, das ursprünglich nicht in den Top 10 war, sowie d5 in der engeren Wahl. Nach 10.000 Simulationen hatte d5 eine leichte Präferenz (66) über c6 (65). Nach 100.000 Simulationen stand nur noch d5 als bester Zug zur Wahl, was nach einer Million Simulationen bestätigt war, worauf AlphaZero d5 zog.

 

Walter Haselsteiner hat zu diesem Bericht einige sehr interessante Anmerkungen:

Einen Aspekt, möchte ich zum Thema „KI“ (Künstliche Intelligenz) als Ergänzung zum Beitrag anmerken:

So wie ich den Algorithmus verstanden habe, hat das Programm mit dem, was wir (aus Sicht der Psychologie) unter „Intelligenz“ verstehen, rein gar nichts zu tun. Der Algorithmus beruht auf einem letztlich einfachen Verfahren und ist damit vergleichsweise primitiv. Es wurden, wie ja auch schon beschrieben ist, von einem gigantischen Google-Rechner im Vorfeld Billionen Stellungen von Ausgangsstellungen sehr mechanisch gespielt und (nur grob) bewertet, um dann wieder weiter zu rechnen. Versuch und Irrtum einfach. Ohne intelligentes Schlussfolgern. Das Vorgehen erinnert mich stark daran, wie es schon IBM mit Big Blue gegen Kasparov machte. In den genannten „wenigen“ Tagen wurde also eine Rechenleistung abgerufen, die auch eine große Gruppe normal sterblicher Schachenthusiasten/Programmierer sich in 100ten Jahren nicht leisten können.  Ich hatte den Eindruck, dass das auf einen  Vergleich rausläuft, wenn man David Hamilton im aufgepeppten, für normal sterbliche Freaks aber leistbaren Golf GTI gegen einen Google-Chauffeur antreten lässt, der im Formel 1 Wagen sitzt.

Dieser einfache Mechanismus wird auch während einer aktiven Schachpartie so eingesetzt. Damit ist die Vorgehensweise des Programms prinzipiell einer ernsthafter Diskussion hinsichtlich der Optimierung von Schachprogrammen wert. Ob das Alpha-Zero am Ende tatsächlich besser war oder nur besser sein „musste“, damit es ins Google-Unternehmens/Marketing-Politik rein passt, kann durch geringe Transparenz seitens Google nicht entschieden werden. Dies wurde auch von Fachexperten festgehalten. Der nach wissenschaftlichen Kriterien ermittelte Beweis steht damit aus.

Was mich aber v. a. stört,  ist hier die Verwendung des Begriffs  künstliche „Intelligenz“ für dieses einfache Rechenschema. Das schafft Unbehagen, da die Thematik (auch bei Google) weit über Schachprogramme hinaus relevant ist. Es geht ja hier v. a. auch um die ethische/rechtliche Diskussion wie weit Maschinen/Computer Entscheidungen treffen dürfen (z. B in der Medizintechnik, beim Autofahren etc.). Mit der Aktion  wird im Sinne von Google beeinflusst, dass es gut ist, wenn Maschinen Entscheidungen treffen. Diese Diskussion muss aber erst ernsthaft und breit geführt werden.

Dazu noch eine Bemerkung des Autors dieses Berichts:

Tatsächlich "lernte" AlphaZero das Schachspiel nicht mit dem oben beschriebenen Setup von 44 CPUs und 2 TPUs, mit dem es gegen Stockfish antrat, sondern mit einem Supercomputer, der mit 5000 parallel rechnenden TPUs ausgestattet war. Eine hochwertige CPU ist um ca. 1000 Euro zu haben, für TPUs gibt es keine Preisangaben, da sie nicht verkauft werden. Da sie als Einzelanfertigungen nicht serienmässig produziert werden, ist von einem Wert von 10.000 Euro oder mehr pro Stück auszugehen. Das macht für 5000 TPUs mindestens 50 Millionen Euro.

 

Wen das Thema mehr interessiert:

 Der Originalartikel aus Science (englisch)

Das ergänzende Material zum Science Artikel (enthält viele Details, wie z.b. 20 ausgewählte Partien) (englisch)

Das von Exweltmeister Garry Kasparov dazu geschriebene Editorial (englisch)

Ein Kommentar über den Algorithmus von AlphaZero (englisch)

Artikel in Chess Base (deutsch)

rv 11.12.2018, update 12.12.2018