Schach-Engine erstellen, maschinelles Lernen vs. traditionelle Engine?

17

Ich bin sowohl ein begeisterter Schachspieler als auch ein Computerprogrammierer. Ich würde sagen, dass Schachspielen und Programmieren die beiden Dinge sind, die ich am meisten tue. Natürlich möchte ich meinen eigenen Motor und letztendlich Lichess-Bot entwickeln.

Nach AlphaZeros Crushing-Performance gegen Stockfish im letzten Jahr überlege ich, ob ich diese Engine mit maschinellem Lernen (eine Art neuronales Netzwerk, möglicherweise unter Verwendung von Tensorflow) oder mit traditionellen, hartcodierten Heuristiken erstellen soll.

Ich bin mit neuronalen Netzen weniger vertraut als mit anderen Arten der Hardcodierung. Trotzdem könnte es für mich eine gute Möglichkeit sein, den Umgang mit neuronalen Netzen zu lernen.

Ich überlege auch, ob es wichtig ist, in welcher Sprache ich die Engine codiere. Ich weiß, dass viele Schachengines C ++ verwenden, das ich noch nie zuvor verwendet habe. Ich habe andere C-basierte Sprachen verwendet, die viele der gleichen Aufgaben mit meist unterschiedlicher Syntax ausführen. Ich kenne mich am besten mit Swift und Javascript aus, kenne mich aber auch mit Python aus und bin der Meinung, dass es den Trick für mich tun könnte.

Soll ich, um die bestmögliche Schachengine zu erstellen, ein neuronales Netzwerk oder eine fest codierte Version verwenden?

David Chopin
quelle
4
Der Schlüssel zu den neuen KI-Motoren ist nicht so sehr NN, sondern das Erlernen von Verstärkung. RL ist ein komplexes Thema, aber es gibt gute Online-Einführungsressourcen wie David Silvers RL-Vorlesungen an der UCL (Folien auf seiner Website und Vorlesungen auf YouTube. Er hat in der letzten Vorlesung mit Deepmind und traditionell behandeltem Alphago gearbeitet. Sie könnten wahrscheinlich eine interessante KI entwickeln engine without NN using hard coded heuristics and RL. So startete alphago!
asac - Monica
Es ist kein Schach, aber das kürzlich erschienene Buch "Deep Learning and the Game Go" zeigt, wie man NNs für eine Game-Engine verwendet. Alpha-Go und Alpha-Zero sind unter der Haube ähnlich.
John Coleman
Angesichts Ihrer Python Erfahrung könnte es sich lohnen, bei Nim suchen
Darren H
Wenn Sie NN ausprobieren möchten, ist dies interessant: arxiv.org/abs/1509.01549 Es gibt auch Code auf github :)
Ant
@Ant beachten Sie, dass Giraffe im Vergleich zu Top-Motoren nie sehr stark war. (~ 2800 elo)
Oscar Smith

Antworten:

8

Erster Schritt: Definieren Sie Ihre Ziele / Gründe

Ich denke, das ist der vorherrschende Faktor. Welches passt am besten zu Ihnen? (Wähle nur eine )

  1. Sie möchten eine unterhaltsame, herausfordernde Codierungsaufgabe genießen
  2. Sie möchten eine extrem gute Schachengine erstellen
  3. Sie möchten wissen, wie Schachengines funktionieren
  4. Sie möchten Codierfähigkeiten erlernen / üben
  5. Sie wollen Informatikkonzepte / Theorie erlernen / umsetzen (zB maschinelles Lernen)
  6. (Andere)

IMO ist es in Ordnung, eine Münze für etwas anderes als 2 zu werfen. Für alle anderen wirst du dein Ziel erreichen, egal ob du ML oder Hardcodierung wählst. Allerdings möchten Sie wahrscheinlich einen Vergleich zwischen den Auswahlmöglichkeiten, um sich zu entscheiden.

Der Fall für die Hardcodierung

Schach spielen (als Mensch) erfordert logisches Denken. Sie erkunden den Raum möglicher Aktionen, die Sie und der Gegner ausführen können. Dies hat ein Feld hervorgebracht, das als Spieltheorie bezeichnet wird und theoretische Rahmenbedingungen für die Analyse von Spielen im Allgemeinen enthält.

Wenn Sie Spaß daran haben, mit Details zu arbeiten, spezifisch zu sein und über Dinge nachzudenken, könnte dies für Sie gut funktionieren. Im Vergleich dazu beinhaltet maschinelles Lernen viel mehr "Black-Box" -Algorithmen, die unscharf und undurchsichtig sind. Sie wissen nicht genau, was los ist.

Ich gehe auch davon aus, dass Sie es leichter haben werden, "es selbst herauszufinden", wenn Sie sich für die Hardcodierung entscheiden, anstatt maschinell zu lernen. Weniger Copy-Paste-Sachen, die Sie nicht vollständig verstehen.

Der Fall für maschinelles Lernen

Es kann aufregend sein, eine Kreation zu gebären und zu beobachten, wie sie ein Eigenleben aufnimmt. Während bei der Hardcodierung Präzision und Detailgenauigkeit im Vordergrund stehen, ist das maschinelle Lernen flexibel. Nehmen Sie einige Neuronen weg und das Ergebnis wird wahrscheinlich ähnlich sein.

Beim Hardcodieren geht es darum, Schach zu lernen. Beim maschinellen Lernen geht es darum, die Kreatur zu studieren, die Sie erstellt haben.

Und maschinelles Lernen ist natürlich ein sehr heißes Thema.

Sprachauswahl für Hardcodierung

Ich bin mir nicht sicher, was Sie mit "anderen C-basierten Sprachen" meinen. C ++ ist die einzige Standardsprache, die C ähnelt. Der Vorteil von C / C ++ ist, dass sie schnell sind . Obwohl andere Sprachen im Laufe der Jahre aufgeholt haben, gibt C ++ ihnen immer noch einen Lauf um ihr Geld.

C ++ ist nicht einfach. Mit moderneren kompilierten Sprachen wie Rust, Golang oder Swift werden Sie großartige Leistungen erzielen. Aber es sollte nicht viel schlimmer sein, wenn Sie sich für eine JIT-Sprache entscheiden. Dh nicht die CPython Interpreter verwenden ; Verwenden Sie IronPython oder Jython oder Node oder C # oder Java.

Die GPU-Programmierung erfordert einen anderen Ansatz und ich würde an dieser Stelle davon abraten.

Sprachwahl für maschinelles Lernen

Das Problem mit TensorFlow ist, dass es sehr niedrig ist. Es geht mehr um das Schreiben von Algorithmen zum Knacken von Zahlen (die auf parallele Hardware übertragen werden können) als um eine Schnittstelle, die dem maschinellen Lernen gewidmet ist.

Natürlich kann es eine großartige Lernerfahrung sein! Und es lohnt sich auf jeden Fall, heute zu lernen. Möglicherweise möchten Sie jedoch mit Keras oder PyTorch beginnen.

Artelius
quelle
1
Dies ist eine phänomenale Reaktion, die wirklich alle Punkte trifft, die ich erwähnt habe. Es ist schwer zu sagen, warum genau ich einen Motor bauen will. Realistisch gesehen werde ich wahrscheinlich nicht mit Leuten wie Stockfish, Komodo und Leela konkurrieren (ich bin schließlich nur ein Student). Trotzdem würde es Spaß machen zu sehen, wie sich meine Arbeit gegen andere Motoren schlägt und nicht jedes Mal zermalmt wird. Selbst wenn meine Hauptüberlegung darin besteht, eine starke Engine zu entwickeln, werde ich wahrscheinlich eine neue Programmiersprache lernen und meine Schachkenntnisse als Nebenprodukt der Entwicklung der Engine verbessern.
David Chopin
1
Ich denke, mehr als alles andere möchte ich etwas, das ich langfristig herstellen, pflegen und optimieren kann. Ich möchte auch ein Projekt, das mir objektiv sagt, wie gut mein Code ist (Gewinne / Unentschieden / Verluste, ELO usw.).
David Chopin
1
Dies ist eine sehr interessante Antwort, aber empfehlen Sie Node over Cpython ernsthaft aus Gründen der Leistung ?
Evpok
> "C ++ ist die einzige Standardsprache, die etwas mit C zu tun hat." C #? Rost? Java? Es gibt viele Sprachen, die mindestens "so etwas wie C" sind
Maaark,
Ich habe "like C" als kompilierte, hochoptimierte, maschinensprachlich implementierte Sprache mit C-Syntax angesehen. C #, Java und PHP verwenden alle virtuelle Maschinen, deren Code eher zu Opcodes als zu CPU-spezifischem Bytecode kompiliert wurde (und die Kompilierung von PHP ist wie bei Python und Bash vollständig transparent). Und Rust ist kein Mainstream. Nur C ++ ist in dieser Hinsicht "wie C", obwohl es Syntaxstile mit mehreren anderen Mainstream-Sprachen teilt.
Ghedipunk
24

Wenn Sie versuchen, den stärksten Motor zu entwickeln, entscheiden Sie sich unbedingt für NN-Motoren.

Herkömmliche Motoren sind großartig - Stockfish ist wohl immer noch der stärkste Motor auf dem Planeten, wenn man sich mit gleicher Hardware einverstanden erklärt - aber sie sind schwer zu schreiben. Diese Motoren kamen über Nacht nicht dort an, wo sie waren. Sie haben jahrelange Arbeit gekostet. Stockfisch zum Beispiel gewinnt seit sechs Jahren stetig an Elo . Wenn Sie bei Null anfangen, werden Sie nicht schnell an die Stärke von Stockfish herankommen. Tatsächlich werden Sie wahrscheinlich mehrere hundert Elo von dem Punkt abhalten, an dem sich Stockfish gerade befindet. Zum Vergleich: Einige der derzeit stärksten Single-Author-Engines sind Ethereal , Laser und Xiphos (ich vernachlässige Houdini & Fire, da sie keine Open Source -Engines sind ). Diese Motoren sind alle wesentlich schwächer als Stockfish.

Warum sind sie so viel schwächer? Zwei Gründe:

  1. Auf dieser Ebene erfordert die Entwicklung eines Motors viel Rechenleistung. Was Sie tun, ist, durch Ihren Code zu schauen und eine Idee zu identifizieren, die elo gewinnen könnte. Eine Beispielidee ist: "Wenn wir wissen, dass dieser Schritt wahrscheinlich gut ist, suchen Sie keine Zweige, die diesen Schritt umkehren." Sie schreiben dann einen Patch, der die Idee implementiert, und testen die geänderte Engine gegen die vorherige Version. Auf dieser Ebene werden Zehntausende von Spielen benötigt, um eine ausreichend große Stichprobengröße zu erhalten, um festzustellen, ob der Patch wirksam ist. Das Spielen dieser Spiele erfordert sehr viel Rechenleistung. Stockfish hat Zugriff auf Super-Hardware: Ab dem Zeitpunkt der Veröffentlichung ist das Stockfish-Testgelände Fishtestingläuft mit 1038 Kernen. Zum Vergleich könnte ein typischer Desktop-Computer 4-8 Kerne haben.

  2. Der andere Grund ist, dass Stockfisch von vielen Köpfen unterstützt wird. Zum Zeitpunkt des Schreibens wurden 8 Patches von 5 Personen getestet. Wenn Sie die Patch-Historien durchsehen, werden Sie viele weitere Entwickler finden, die Patches geschrieben haben. Ich weiß nicht, wie viele aktive Stockfish-Entwickler es gibt, aber es ist sicherlich> 20.

Andererseits erreichen NN-Motoren (relativ) leicht eine Stärke, die weit über der von Ethereal / Laser / Xiphos liegt. Überzeugen Sie sich vom neuesten Top Chess Engine Championship-Turnier . Ethereal / Laser / Xiphos sind in der Liga 1, was glaubwürdig genug ist, aber die Motoren in der obersten Liga (Division P) sind:

  • Stockfish (von der Community unterstützte traditionelle Engine, läuft mit Fishtesting)
  • Komodo (kommerzieller traditioneller Motor, hat Vollzeitentwickler)
  • Komodo MCTS (kommerzieller semi-traditioneller Motor, hat hauptberufliche Entwickler)
  • Houdini (kommerzieller traditioneller Motor, ein Ein-Mann-Einsatz, seit zwei Jahren nicht mehr aktualisiert)
  • Leela Chess Zero (von der Community unterstützte NN-Engine, läuft mit dem Analogon von Fishtesting, auch bekannt als eine Tonne Hardware)
  • AllieStein (2-Mann-NN-Motor)
  • Stoofvlees (NN Motor)
  • ScorpioNN (NN-Motor)

Die letzten drei Motoren - AllieStein, Stoofvlees und ScorpioNN - sind alles kleine Kooperationen von Leuten, die, soweit ich weiß, Enthusiasten wie Sie und keine Vollzeitentwickler sind. Sie haben nach weniger als zwei Jahren des Versuchs Div P-Stärke erreicht (alle diese NN-Motoren erschienen erst nach AlphaZero). Zum Vergleich: In der jüngsten Geschichte des Computerschachs gab es nur eine Person, die jemals eine traditionelle Engine geschrieben hat, die erfolgreich mit Stockfish & Komodo allein konkurrierte (Robert Houdart, der Autor von Houdini).

Es ist wahr, dass Sie wahrscheinlich nicht die Hardware haben, um mit Lc0 zu konkurrieren, aber Lc0 benötigt so viel Rechenleistung, weil es eine "Null" -Engine ist - es soll Schach spielen, ohne menschliche Kenntnisse außer Regeln. Sie müssen nicht dieselbe Methode anwenden. Sie können beispielsweise die Stein-Methode verwenden , die überwachtes Lernen verwendet. Es ist wohl sogar besser als "Null" zu werden - schließlich spielt AllieStein im Superfinale, nicht Lc0.

Das Fazit ist: Wenn Sie mit den besten Motoren der Welt mithalten wollen, sind Sie mit NN-Motoren weitaus erfolgreicher als mit herkömmlichen Motoren.

Locken
quelle
6
Erwähnen Sie vielleicht die andere Seite Ihrer Schlussfolgerung: Wenn Sie Ihr Schachverständnis während des Programmierens vertiefen möchten, entscheiden Sie sich für traditionelles Schach.
Blues
1
Ich stimme Ihrer Schlussfolgerung zu, würde aber auch empfehlen, ein aktuelles Netzwerk von einer starken Engine (mit Erlaubnis natürlich) als Ausgangspunkt zu verwenden, anstatt von vorne zu beginnen (aber auf eine andere Weise fortzufahren als "Trainieren über Selfplay und Update" durch Hinzufügen oder Entfernen von Ebenen, Hinzufügen von Eingabemerkmalen, Anfordern zusätzlicher Ausgaben usw.). Ich kann mich nicht erinnern, ob Lc0 ein Einzelkopf oder ein Doppelkopf ist, aber ich glaube, dass 3-Kopf ( ijcai.org/proceedings/2018/0523.pdf ) derzeit von keiner Schachengine implementiert wird und sich möglicherweise verbessert -die Kunst.
Steven Jackson
Ich denke, Allies Suche macht es stärker gegen die schwächeren Motoren (KMCST, Stoofvlees), nicht gegen das Stein-Netzwerk.
Ich
@blues Ich denke, das Programmieren einer Schachengine macht eine nicht wirklich zu einem besseren Schachspieler - mit Ausnahme von Larry Kaufman (einem der Entwickler von Komodo) hat keine der Top-Engines Spieler als Entwickler benannt oder wurden deren Entwickler betitelte Spieler.
Allure
@me 'das ist möglich, aber Leelenstein ist das Stein-Netzwerk, das die Lc0-Binärdatei verwendet, und es ist bei der Computerschachmeisterschaft von chess.com gut gelungen, sodass die Stein-Netzwerke zumindest mit den Lc0-Netzwerken vergleichbar sind.
Allure
9

Soll ich, um die bestmögliche Schachengine zu erstellen, ein neuronales Netzwerk oder eine fest codierte Version verwenden?

Wählen Sie keine NN, es sei denn, Sie haben Zugriff auf lächerliche (Ein paar hundert Nvidia V100). Das Training eines NN zum Schachspielen erfordert so viel Hardware. Sehen Sie, wie die Leute, die zu Lc0 beitragen, über 200 Millionen Spiele trainieren. Da Sie wahrscheinlich Probleme haben werden, auf die Hardware zuzugreifen (Sie könnten versuchen, bei Google Colabatory welche zu bekommen , aber nur mit diesen Mitteln wird das Training sehr langsam sein).

Bearbeiten: Verwenden eines NN Mit Supervised Learning erhalten Sie möglicherweise nur Google Colab und möglicherweise eine starke GPU (2080, 2080Ti, Radeon VII).

Ich überlege auch, ob es wichtig ist, in welcher Sprache ich die Engine codiere. Ich weiß, dass viele Schachengines C ++ verwenden, das ich noch nie zuvor verwendet habe. Ich habe andere C-basierte Sprachen verwendet, die viele der gleichen Aufgaben mit meist unterschiedlicher Syntax ausführen. Ich kenne mich am besten mit Swift und Javascript aus, kenne mich aber auch mit Python aus und bin der Meinung, dass es den Trick für mich tun könnte.

Python und Javascript sind wahrscheinlich zu langsam für eine starke Schachengine. Ich habe Swift noch nicht verwendet, aber es wird wahrscheinlich keine anderen Plattformen als macOS mögen, daher ist es wahrscheinlich besser, C oder C ++ zu verwenden. Sie könnten möglicherweise auch Rust verwenden, aber das hat viele Sicherheitsmerkmale, die ärgerlich werden und die Sie nicht wirklich brauchen, was ärgerlich werden kann. Es wird auch schwieriger sein, eine gute Leistung zu erzielen, da bestimmte Optimierungen auf niedriger Ebene schwierig durchzuführen sind. Natürlich können Sie es immer in Assembler schreiben, aber das wird wahrscheinlich zu viel Arbeit sein. siehe https://www.chessprogramming.org/Languages/

mir'
quelle
1
Super, vielen Dank für die Infos! Ich werde wahrscheinlich versuchen, eine API zu erstellen, die eine FEN-Position einnimmt und die berechnete Bewegung ausgibt. Ich denke, dies ist der beste Weg, um sich in Lichess-Bots zu integrieren.
David Chopin
1
Ist es eine Option, eine andere NN-Engine zu implementieren, die nur das lc0-Netzwerk verwendet?
RemcoGerlich
1
@RemcoGerlich, wie ich es verstehe, verwenden NN-Engines zwei Dinge: das binäre und das neuronale Netzwerk. Das Schreiben einer Binärdatei ist nicht einfach, aber das Trainieren eines neuronalen Netzwerks ist relativ einfach. In diesem Sinne existieren bereits Lc0-Derivate - Leelenstein & Deus X (alias Fat Fritz) sind solche Derivate.
Verführen Sie den
@RemcoGerlich in diesem Fall wäre das nicht wirklich eine andere Engine, das wäre die Ic0-Engine mit nur einer anderen Verpackung / Schnittstelle / was auch immer.
Peteris
3

Ich habe eine reine Spielzeug-Schach-Engine gebaut, die Folgendes verwendet: Python-Schach. Es war wirklich schön, die Spielregeln nicht selbst zu programmieren und mich nur auf die Logik zu konzentrieren. Die Anzahl der Positionen, die ich pro Sekunde auswerten konnte, ist jedoch sehr gering. Dies könnte ein guter Ausgangspunkt sein.

Akavall
quelle