Monte Carlo Tree Search


This page is dedicated to Windows UCI engines using MCTS. I write in german because almost everything written about MCTS engines on the internet is in english.

MCTS Windows UCI Engines


LCZero is a super strong UCI engine based on AlphaZero.


Komodo MCTS is a super strong UCI engine based on Komodo (Alpha-Beta).


New Neural Network UCI Engine: Allie.


LCZero: Drück mich.


Vorwort 15.01.2019:
Diese Seite ist solchen Schachmotoren (Engines) gewidmet, die MCTS verwenden. Das Meiste darüber im Internet ist leider in englisch. Auch die Präsenz der aktuell verfügbaren Engines ist englisch. Deshalb möchte ich das Thema mit einem deutschsprachigen Beitrag ergänzen.

    

Anmerken möchte ich, dass ich von programmiertechnischen Dingen nicht viel verstehe. Ich bin Praktiker, und mich interessieren solche Tests. Dabei lege ich auf Statistisches (Resultate sowie Ranglisten) weniger Wert. Es ist gut dass wir Computerschach Ranglisten haben, aber mich interessiert der Inhalt von Partien.


Von Alpha-Beta zu AlphaZero:

Die herkömmlichen Schachmotoren nutzen für die Auslese des Zuges die sogenannte Alpha-Beta-Suche. Hierbei wird ein Minimax-Algorithmus optimiert. Die Programmierer finden zwar ständig ausgefeiltere Techniken, die Grundlage bleibt jedoch dieselbe. Das stärkste AB Programn ist derzeit Stockfish. Dieser Schachmotor ist übrigens Open Source und kostenlos. Stockfish läuft unter fast allen grafischen Schach Oberflächen (GUI). Dadurch dass die Quelle offen vorliegt, wird Stockfish nicht nur von einem Autor verbessert. Deshalb er so stark. Mehr Gehirne entdecken eben mehr Neues.


Leela Chess Zero (LCZero) baut auf einer anderen Grundlage auf. Leela ist der Name (wie Stockfish). Das Zero steht aber für Null Schachwissen! Die Idee wurde im Dezember 2017 gefunden. Da hat nämlich die britische Tochterfirma von Google, DeepMind, die sich ausschließlich mit künstlicher Intelligenz (AI) zu wissenschaftlichen Zwecken befasst, anlässlich eines Schachturniers in London, zehn faszinierende Schachpartien veröffentlicht. Das Staunen war groß. Der Inhalt begeisterte. Man sah Taktisches und Strategisches wie man es bislang so noch nicht gesehen hat. Der Spieler war ein neues Schachprogramm mit dem Namen AlphaZero. Gerade erscheint in englischer Sprache ein Buch darüber, der Name des Buchs lautet Game Changer. Die ersten 28 Seiten kann man im pdf Format kostenlos hier herunterladen.


DeepMind veröffentlichte auch ein Papier über die Funktionsweise. Die Seele ist ein neuronales Netzwerk (abgekürzt NN), welches mit Unterstützung spezieller TPUs, sich das Schachspielen vollkommen selbstständig beigebracht hat. Die Macher haben in AlphaZero nur die Schachregeln implementiert. Die Züge werden über einem Zuggenerator ausgespielt. Für die Auslese dient die Monte Carlo Tree Search (abgekürzt MCTS). Hier werden Züge, bevor sie gespielt werden, nach einem gewissen Zufallsprinzip erstmal simulativ ausgeführt. In vielen sogenannten Playouts wird das Spiel bis zum Ende ausgespielt, indem die Züge zufällig ausgewählt werden. Das NN steuert die Selektion von zu untersuchenden Zügen. Dabei ist das NN in der Lage zu lernen. Aus jedem Spiel lernt es dazu und speichert das neue Wissen als Wichtung ab. Diesen Vorgang nennt man Trainieren. Nachdem AlphaZero fertiggestellt wurde, hat es dann sogenannte Selfplays durchgeführt. Innerhalb von 9 Stunden spielte AlphaZero ewa 30 Mio Partien gegen sich selbst. Durch die schnellen TPUs war das möglich. AlphaZero spielte danach so stark, dass es das bis dahin stärkste AB Schachprogramm, Stockfish 8, in einem 100 Spiele Match besiegt hatte. Man könnte auch sagen: Am Anfang war es Zufall, am Ende die Vollendung. Man rätselt übrigens heute noch darüber, wie AlphaZero denkt. Komplett verstanden ist es noch nicht.


Leela Chess Zero:

LCZero ist Open Source, und jeder darf mitmachen! Anstelle von teuren TPUs, wie sie bei AlphaZero Verwendung findet, übernimmt bei LCZero die Community den Teil des Trainers! Viele Anwender stellen ihre PCs zur Verfügung, und LCZero fügt die Grafikeinheiten ihrem neuronalen Netzwerk zu. Die Netzwerke werden ständig verbessert. Inzwischen gibt es viele NN, auch von verschiedener Größe. Das ausführende Programm, die Lc0.exe, wird auf dem PC als UCI Engine installiert, ähnlich wie Stockfish. Die User können LCZero insofern beeinflussen, dass sie auch vorgeben können was trainiert werden soll. Bei manchen Netzwerken sind das z.B. Endspiele. Das Gelernte speichert LCZero in eine Datei mit dem Namen Weights (Wichtungen). LCZero besteht somit aus drei Dateien: 1. Das ausführende Programm (Lc0.exe), 2. Das gespeicherte Neuronale Netzwerk (Weights), 3. Der Zugang zum Server (Client.exe). Die Angaben hier beziehen sich auf das Betriebssystem Windows. Die Dateien werden vor der Installation von der LCZero Homepage herunter geladen. Um mit LCZero spielen zu können, ist der Client nicht notwendig. Der ist jedoch notwendig, will man LCZero trainieren. Auf meiner Seite LCZero findet der interessierte Leser u.a. auch eine kurze Einleitung zur Installation auf dem PC unter Windows. 

Um viele andere Dinge, die man auf der LCZero Homepage sieht, habe ich mich bislang nicht gekümmert. Man sieht dort z.B. eine Grafik mit der Selfplay Elo sowie den Prozess des Spielstärke Zuwachs. Von praktischer Bedeutung ist mir das bislang nicht, ebenso die vielen Netzwerke, da ich mich auf wenige beschränke.

Über die genaue Entstehung von LCZero kann ich nicht viel sagen, weil ich mich mit dem Thema erst seit etwa zwei Monaten befasse. Wie ich las, fand die erste Publikation der Idee im TalkChess Forum statt. Das ist nicht verwunderlich, weil die meisten Schach Programmierer Mitglieder sind. Die Community ist relativ groß, und wenn es Neues gibt, dann erfährt man es da meist zuerst.

Die praxisrelevante Seite ist mir stets wichtiger. Ich habe mir daher erstmal viele Partien angeschaut und danach einige erste eigene Partien spielen lassen. Übrigens mit einer speziellen CPU Version die es inzwischen auch schon gibt! Denn die GPU Version läuft nur auf schnellen Grafikkaften gut. Eine solche habe ich derzeit aber nicht. Ein erstes Fazit kann ich dennoch ziehen: Das Projekt LCZero startete im Januar 2018. Jetzt ist Januar 2019. Bei Turnieren wo LCZero gerade mitspielt, gehört sie zu den Top 3 Engines. Sehr bemerkenswert.

Nachtrag:
Ein kurzes Wort zu Komodo MCTS. Diese Engine ist ebenfalls noch sehr jung und das Projekt startete etwa zur selben Zeit wie Lc0. Komodo ist jedoch eine kommerzielle Engine. Zum derzeitigen Zeitpunkt kann man Komodo MCTS zusammen mit dem großen Bruder Komodo (Alpha-Beta) kaufen. Komodo MCTS liegt jedoch auch auf der Überholspur, und wird vermutlich als eigenständige Engine herausgebracht werden. Der aktuelle Komodo MCTS nutzt im Gegensatz zu Lc0 kein neuronales Netzwerk. Zur Selektion der zu untersuchenden Züge wird im Programm eine verkürzte Alpha-Beta Suche vorgeschaltet. Das ist schon ein wesentlicher Unterschied zu Lc0. Dennoch, Komodo nutzt MCTS und das ist sehr interessant. Man darf sehr gespannt darauf sein, welche Ideen das Komodo Team für die Zukunft verfolgt.

TOP