Alpha-Beta, Monte Carlo, Abwatschprämie, Inzucht - Chrilly Donningers Kommentar zu AlphaZero

von Chrilly Donninger
18.12.2017 – Chrilly Donninger hat sich vor zehn Jahren vom Computerschach zurück gezogen - leider. Verlernt hat er aber nichts. Wir baten ihn zu einem Kommentar zum Durchbruch von AlphaZero. (Foto: ChessBase-Archiv)

ChessBase 14 Download ChessBase 14 Download

ChessBase 14 ist die persönliche Schach-Datenbank, die weltweit zum Standard geworden ist. Und zwar für alle, die Spaß am Schach haben und auch in Zukunft erfolgreich mitspielen wollen. Das gilt für den Weltmeister ebenso wie für den Vereinsspieler oder den Schachfreund von nebenan.

Mehr...

Monte-Carlo funktioniert

Das aus meiner Sicht überraschende am Projekt war, dass Monte-Carlo Suche funktioniert hat. Der bislang übliche Suchalgorithmus war Alpha-Beta. Alpha-Beta sucht (konzeptionell) bis zu einer gewissen Tiefe und bewertet dann die Stellung. De facto werden manche Varianten weit länger, andere kürzer berechnet. Es steckt daher im Suchalgorithmus ebenfalls sehr viel Know-How.

Bei Monte-Carlo spielt man einfach ein Spiel zu Ende. In Backgammon haben das Menschen "immer schon" im Form des "Rollouts" gemacht. Wenn nach Zug A 60% der Partien gewonnen werden, nach Zug B 55%, dann ist A besser. Erfunden hat man diese Methode in Go aus Ratlosigkeit. Alpha-Beta hat da nicht funktioniert. Es war der Branching-Faktor zu groß, aber vor allem gibt es keine gutes Konzept von "Ruhiger Stellung". In Schach macht man nach der normalen Suche noch eine Ruhesuche. D.h. man schaut sich nur mehr die Schlagzüge an. Wenn dort nichts mehr geht, ist die Stellung "ruhig" und man bewertet. Es gibt nichts vergleichbares in Go. Die Frage ist, nach welchen Kriterien man die Partien zu Ende spielt.

Depperte Partien im Go

In Go waren das ursprünglich sehr einfache Regeln. Die Partien waren aus menschlicher Sicht ziemlich bizarr/deppert. Man hat das aber - ursprünglich durch Lernen von menschlichen Partien - verbessert. Durch das Deep-Learning wurde ein Konzept von "ähnliche Stellung" entwickelt und hat dann den Zug jener menschlichen Partie gemacht, die am ähnlichsten ist. Das hat die Qualität der Monte-Carlo Suche dramatisch verbessert. Wobei es schon genügt, wenn der Anteil der guten Züge über 50% liegt. Vor allem ist es wichtig, dass keine vollkommen "depperten" Züge gespielt werden. Es hat sich aber herausgestellt, dass man nicht von Menschen lernen sollte, sondern dass das Programm durch Autoplay selbst solche Konzepte entwickeln soll. Das überrascht mich nicht. Mein Programm Hydra war bewußt auf "nicht-menschliches Spiel" getunt.

"Sch... auf die Turmendspiele"

Ich habe selber seinerzeit auch der Monte-Carlo Suche experimentiert. Wir wollten das Verhalten in Turm-Endspielen verbessern. Diese sind oft recht tief und es ist schwierig, gute Regeln zu finden. Allerdings hat die Integration mit der normalen Alpha-Beta Suche nicht funktioniert. Ich habe das Projekt damals mit den Worten "Sch... auf die Turmendspiele, wir hauen sie schon vorher zusammen" beendet.

Erdogan Günes, Chrilly Donninger (Foto: ChessBase-Archiv)

Die Meldung "mit in einem Tag draufgekommen" ist relativ zu sehen. Deep Mind hatte 5.000 TPUs (eine von Google speziell entwickelte Hardware für Deep Learning) zur Verfügung. TPUs sind wesentlich mächtiger als eine CPU. Und eine Anmerkung zur Botschaft: "Besser als Menschen", sei auch gestattet: Die Programme spielen schon länger besser als die Menschen.

"Abwatschprämien"

Das Hydra Projekt wurde damals beendet, weil es schon fad war. Die Top-Spieler haben nur mehr wegen Antrittsprämien (wir sagten "Abwatschprämie" dazu) verhandelt. Aber nicht mehr über Siegprämien. Der Scheich, der das Hydra-Projekt finnazierte, wollte aber fürs reine Antreten (fast) nix bezahlen. Das Alpha-Go spielt nun etwas besser als das stärkste Programm Stockfish und Stockfish spielt (weit) stärker als die Menschen. Der Maßstab ist Stockfish.

Ein Punkt fehlt noch: Es bildet sich unter den Top-Programmen immer eine  gewisse "Inzucht" heraus. Die Entwicklung erfolgt auch da durch das Spiel gegen andere Programme. Mit Alpha-Zero dringt nun eine andere Spezies in dieses sehr enge Ökosystem  ein und nutzt die Schwächen der Inzucht aus. Wenn die bisherigen  Top-Programme die Möglichkeit hätten, ihrerseits gegen Alpha-Zero zu optimieren, würde sich das Verhältnis sicher wieder etwas ändern. Wobei es für einzelne Hobby-  oder semiprofessionale Programmierer natürlich schwierig ist, mit dem Formel-1 Team von Google  mitzuhalten. Da müsste es schon wieder so ein Team wie Hydra geben, das  auch ein bisserl Geldmittel hinter sich hat.

Es gibt aber dafür von meiner Seite keinerlei wie immer geartetes Interesse.  Ich finde das Börsenspiel interessanter. Sehr interessant wäre auch Poker.

Mehr zum Lesen von Chrilly Donninger, hier...



Chrilly Donninger aus Österreich arbeitete für die ESA, bevor er sich dem Computerschach widmete. Er entwickelte das Programm Nimzo und experimentierte dann mit dem FPGA-Projekt Hydra. Nebenbei schrieb und schreibt er geistreiche Essays, nicht nur über das Computerschach.
Discussion and Feedback Join the public discussion or submit your feedback to the editors


Diskutieren

Regeln für Leserkommentare

 
 

Noch kein Benutzer? Registrieren