Créer un moteur d'échecs, un apprentissage automatique ou un moteur traditionnel?

17

Je suis à la fois un joueur d'échecs passionné et un programmeur informatique. Je dirais que jouer aux échecs et programmer sont les deux choses que je passe le plus de temps à faire. Naturellement, je veux créer mon propre moteur et, finalement, le bot Lichess.

À la suite des performances écrasantes d'AlphaZero contre Stockfish l'année dernière, je me demande si je devrais créer ce moteur avec l'apprentissage automatique (un certain type de réseau de neurones, éventuellement en utilisant Tensorflow) ou une heuristique traditionnelle codée en dur.

Je connais moins les réseaux de neurones que les autres types de codage en dur. Pourtant, cela pourrait être un bon moyen pour moi d'apprendre à travailler avec les réseaux de neurones.

Une autre chose que je considère est de savoir s'il est important de savoir quelle langue j'utilise pour coder le moteur. Je sais que de nombreux moteurs d'échecs utilisent C ++, que je n'ai jamais utilisé auparavant. J'ai utilisé d'autres langages basés sur C qui font beaucoup des mêmes choses, avec une syntaxe principalement variable. Je connais le mieux Swift et Javascript, mais je connais aussi Python et je pense que cela pourrait faire l'affaire pour moi.

Donc, en termes de création du moteur d'échecs le plus puissant possible, dois-je aller sur un réseau neuronal ou codé en dur?

David Chopin
la source
4
La clé des nouveaux moteurs d'IA n'est pas tant NN que l'apprentissage par renforcement. RL est un sujet complexe, mais il existe de bonnes ressources d'introduction en ligne comme les conférences RL de David Silver à l'UCL (diapositives sur son site Web et conférences sur YouTube. Il a travaillé avec Deepmind et a traditionnellement couvert l'alphago dans la dernière conférence. Vous pourriez probablement développer une IA intéressante moteur sans NN utilisant des heuristiques codées en dur et RL. C'est comme ça qu'alphago a commencé!
asac
Ce ne sont pas des échecs, mais le livre récent "Deep Learning and the Game Go" montre comment utiliser les NN pour un moteur de jeu. Alpha-Go et Alpha-Zero sont similaires sous le capot.
John Coleman
Compte tenu de votre expérience Python, il vaut peut-être la peine de regarder Nim
Darren H
Si vous voulez essayer NN, c'est intéressant: arxiv.org/abs/1509.01549 Il y a aussi du code sur github :)
Ant
@Ant notez que Giraffe n'a jamais été très forte par rapport aux meilleurs moteurs. (~ 2800 elo)
Oscar Smith

Réponses:

8

Première étape: définir vos objectifs / raisons

Je pense que c'est le facteur prédominant. Laquelle de ces options vous convient le mieux? (Choisissez un seul )

  1. Vous voulez profiter d'une tâche de codage amusante et stimulante
  2. Vous voulez créer un très bon moteur d'échecs
  3. Vous voulez en savoir plus sur le fonctionnement des moteurs d'échecs
  4. Vous souhaitez apprendre / pratiquer des compétences de codage
  5. Vous souhaitez apprendre / mettre en œuvre des concepts / théorie de l'informatique (par exemple, l'apprentissage automatique)
  6. (Autre)

OMI, c'est bien de "lancer une pièce" pour tout sauf 2. Pour tous les autres, vous atteindrez votre objectif, que vous choisissiez le ML ou le codage en dur. Cependant, vous voulez probablement une comparaison entre les choix pour vous aider à décider.

Le cas du codage en dur

Jouer aux échecs (en tant qu'humain) implique une réflexion logique. Vous explorez l'espace des actions possibles que vous et l'adversaire pouvez entreprendre. Cela a donné naissance à un domaine appelé théorie des jeux qui contient des cadres théoriques pour l'analyse des jeux en général.

Si vous aimez travailler avec les détails et être précis et raisonner sur les choses, cela pourrait bien fonctionner pour vous. En comparaison, l'apprentissage automatique implique beaucoup plus d'algorithmes de "boîte noire" qui sont flous et opaques. Vous ne savez pas exactement ce qui se passe.

Je pense également que vous aurez plus de facilité à "le découvrir par vous-même" si vous choisissez la voie du codage en dur plutôt que l'apprentissage automatique. Moins de copier-coller que vous ne comprenez pas complètement.

Le cas de l'apprentissage automatique

Il peut être passionnant de donner naissance à une création et de la voir prendre sa propre vie. Alors que le codage en dur est une question de précision et de détail, l'apprentissage automatique est flexible. Enlevez quelques neurones et le résultat sera probablement similaire.

Le codage en dur consiste à étudier les échecs. L'apprentissage automatique consiste à étudier la créature que vous avez créée.

Et l'apprentissage automatique est, bien sûr, un sujet très brûlant.

Choix de langue pour codé en dur

Je ne sais pas ce que vous entendez par "autres langages basés sur C". C ++ est le seul langage courant qui ressemble à C. L'avantage de C / C ++ est qu'il est rapide . Bien que d'autres langages aient rattrapé leur retard au fil des ans, le C ++ leur donne toujours une course pour leur argent.

C ++ n'est pas facile. Vous obtiendrez de grandes performances avec des langages compilés plus modernes comme Rust, Golang ou Swift. Mais cela ne devrait pas être bien pire si vous optez pour un langage JIT. Par exemple, n'utilisez pas l'interpréteur CPython ; utilisez IronPython ou Jython, ou Node, ou C # ou Java.

La programmation GPU nécessite une approche différente et je déconseille à ce stade.

Choix de la langue pour l'apprentissage automatique

Le problème avec TensorFlow est qu'il est de très bas niveau. Il s'agit davantage d'écrire des algorithmes de calcul des nombres (qui peuvent être développés sur du matériel parallèle) que d'une interface dédiée à l'apprentissage automatique.

Bien sûr, cela peut être une excellente expérience d'apprentissage! Et vaut certainement la peine d'apprendre aujourd'hui. Cependant, vous voudrez peut-être commencer par Keras ou PyTorch.

Artelius
la source
1
C'est une réponse phénoménale, qui touche vraiment tous les points que j'ai mentionnés. C'est un peu difficile de dire pourquoi exactement je veux faire un moteur. De manière réaliste, je ne rivaliserai probablement pas avec des gens comme Stockfish, Komodo et Leela (je ne suis qu'un étudiant après tout). Pourtant, ce serait amusant de voir mon travail affronter les autres moteurs et de ne pas être écrasé à chaque fois. Même si mon raisonnement principal est de créer un moteur puissant, j'apprendrai probablement un nouveau langage de programmation et améliorerai mes connaissances sur les échecs en tant que produit secondaire de la fabrication du moteur.
David Chopin
1
Je pense que plus que tout, je veux quelque chose que je peux faire, entretenir et affiner à long terme. Je veux aussi un projet qui me dira objectivement la qualité de mon code (Wins / Draws / Losses, ELO, etc.).
David Chopin
1
C'est une réponse très intéressante, mais recommandez-vous sérieusement Node sur Cpython pour des problèmes de performances ?
Evpok
> "C ++ est le seul langage courant qui ressemble à C." C #? Rouille? Java? Il y a beaucoup de langages qui sont au moins "quelque chose comme C"
Maaark
J'ai pris "comme C" pour être un langage compilé, hautement optimisé, implémenté à la machine avec une syntaxe de style C. C #, Java et PHP utilisent tous des machines virtuelles, avec leur code compilé en opcodes plutôt qu'en bytecode spécifique au CPU (et la compilation de PHP est complètement transparente, comme Python et Bash). Et Rust n'est pas courant. Seul C ++ est "comme C" à ces égards, malgré le partage des styles de syntaxe avec plusieurs autres langages traditionnels.
Ghedipunk
24

Si vous essayez de rendre le moteur le plus puissant possible, optez absolument pour les moteurs NN.

Les moteurs traditionnels sont excellents - Stockfish est sans doute toujours le moteur le plus puissant de la planète sur un matériel de consensus égal - mais ils sont difficiles à écrire. Ces moteurs ne sont pas arrivés là où ils étaient du jour au lendemain; ils ont pris des années et des années de travail. Le stockfish, par exemple, gagne régulièrement du terrain depuis six ans . Si vous partez de zéro, vous n'atteindrez pas rapidement la force de Stockfish; en fait, vous risquez de bloquer plusieurs centaines d'élo d'où se trouve actuellement Stockfish. À titre de comparaison, certains des moteurs à auteur unique les plus puissants en ce moment sont Ethereal , Laser et Xiphos (je néglige Houdini & Fire car ils ne sont pas open source). Ces moteurs sont tous sensiblement plus faibles que Stockfish.

Pourquoi sont-ils tellement plus faibles? Deux raisons:

  1. À ce niveau, le développement d'un moteur demande beaucoup de puissance de calcul. Ce que vous faites est de parcourir votre code et d'identifier une idée qui pourrait gagner en elo. Un exemple d'idée est: "si nous savons que ce mouvement est probablement bon, ne recherchez pas les branches qui inversent ce mouvement" (si cela n'a pas de sens pour vous, cela signifie qu'il y aura également une courbe d'apprentissage élevée). Vous écrivez ensuite un correctif qui implémente l'idée et testez le moteur modifié par rapport à la version précédente. À ce niveau, il faut des dizaines de milliers de jeux pour obtenir un échantillon suffisamment grand pour savoir si le patch est efficace. Jouer à ces jeux demande une énorme puissance de calcul. Stockfish a accès à du super matériel: au moment de la rédaction du présent document, le stock de test de Fishfishfonctionne avec 1038 cœurs. A titre de comparaison, un ordinateur de bureau typique peut avoir 4 à 8 cœurs.

  2. L'autre raison est que Stockfish est soutenu par de nombreux cerveaux. Au moment de la rédaction, 8 correctifs ont été écrits par 5 personnes en cours de test. Si vous parcourez l'historique des correctifs, vous trouverez de nombreux autres développeurs qui ont écrit des correctifs. Je ne sais pas combien il y a de développeurs Stockfish actifs, mais c'est certainement> 20.

D'un autre côté, les moteurs NN atteignent (relativement) facilement une force bien supérieure à Ethereal / Laser / Xiphos. Voyez par vous-même dans le dernier tournoi Top Chess Engine Championship . Ethereal / Laser / Xiphos sont en Ligue 1, ce qui est assez crédible, mais les moteurs de la division supérieure (Division P) sont:

  • Stockfish (moteur traditionnel soutenu par la communauté, fonctionne avec Fishtesting)
  • Komodo (moteur traditionnel commercial, a des développeurs à plein temps)
  • Komodo MCTS (moteur commercial semi-traditionnel, a des développeurs à plein temps)
  • Houdini (moteur traditionnel commercial, est un effort individuel, n'a pas été mis à jour depuis deux ans)
  • Leela Chess Zero (moteur NN soutenu par la communauté, fonctionne avec l'analogue de Fishtesting alias une tonne de matériel)
  • AllieStein (moteur NN pour 2 personnes)
  • Stoofvlees (moteur NN)
  • ScorpioNN (moteur NN)

Les trois derniers moteurs - AllieStein, Stoofvlees et ScorpioNN - sont tous de petites collaborations de personnes qui, à ma connaissance, sont des passionnés comme vous et non des développeurs à temps plein. Ils ont atteint la force Div P après moins de deux ans d'essais (tous ces moteurs NN ne sont apparus qu'après AlphaZero). À titre de comparaison, dans l'histoire récente des échecs informatiques, une seule personne a déjà écrit un moteur traditionnel qui a concurrencé avec succès Stockfish & Komodo par lui-même (Robert Houdart, l'auteur de Houdini).

Il est vrai que vous n'aurez probablement pas le matériel pour rivaliser avec Lc0, mais Lc0 prend autant de puissance de calcul car c'est un moteur "zéro" - il est censé jouer aux échecs sans aucune sorte de connaissance humaine à l'exception des règles. Vous n'avez pas besoin d'utiliser la même méthodologie. Vous pouvez par exemple utiliser la méthodologie Stein qui utilise l'apprentissage supervisé. C'est sans doute encore mieux que d'aller à «zéro» - après tout, c'est AllieStein qui joue en superfinale, pas Lc0.

Le résultat est le suivant: si votre objectif est de rivaliser avec les meilleurs moteurs du monde, vous avez beaucoup plus de chances de réussir avec des moteurs NN qu'avec des moteurs traditionnels.

Séduire
la source
6
Mentionnez peut-être l'autre côté de votre conclusion: si votre objectif est d'approfondir votre compréhension des échecs tout en faisant de la programmation, optez pour le traditionnel.
blues
1
Je suis d'accord avec votre conclusion, mais je recommanderais également d'utiliser un réseau récent à partir d'un moteur puissant (avec la permission bien sûr) comme point de départ plutôt que de partir de zéro (mais continuez d'une manière différente de "s'entraîner via le jeu automatique et la mise à jour poids ", soit en ajoutant ou en supprimant des couches, en ajoutant des fonctions d'entrée, en exigeant des sorties supplémentaires, etc.). Je ne me souviens pas si Lc0 est simple tête ou double tête, mais je pense que 3 têtes ( ijcai.org/proceedings/2018/0523.pdf ) n'est actuellement pas implémenté par les moteurs d'échecs, et pourrait finir par s'améliorer sur l'état de -L'art.
Steven Jackson
Je pense que la recherche d'Allie le rend plus fort contre les moteurs les plus faibles (KMCST, Stoofvlees), pas contre le réseau Stein.
moi le
@blues Je pense que la programmation d'un moteur d'échecs ne fait pas vraiment un meilleur joueur d'échecs - à l'exception de Larry Kaufman (l'un des développeurs de Komodo), aucun des meilleurs moteurs n'a nommé des joueurs en tant que développeurs, ou que leurs développeurs sont devenus joueurs titrés.
Allure
@me 'c'est possible mais Leelenstein est le réseau Stein utilisant le binaire Lc0, et c'est bien fait au championnat d'échecs informatique de chess.com, donc les réseaux Stein sont au moins comparables aux réseaux Lc0.
Allure
9

Donc, en termes de création du moteur d'échecs le plus puissant possible, dois-je aller sur un réseau neuronal ou codé en dur?

Ne choisissez pas un NN à moins d'avoir accès à des ridicules (quelques centaines de Nvidia V100). Entraîner un NN à jouer aux échecs demande beaucoup de matériel. Découvrez les personnes qui contribuent à Lc0 pour former plus de 200 millions de jeux. Puisque vous aurez probablement du mal à accéder au matériel (vous pouvez essayer d'en obtenir chez Google Colabatory , mais avec seulement cela, la formation sera très lente).

Edit: en utilisant un NN avec apprentissage supervisé, vous POUVEZ vous en tirer avec seulement Google Colab et éventuellement un GPU puissant (2080, 2080Ti, Radeon VII).

Une autre chose que je considère est de savoir s'il est important de savoir quelle langue j'utilise pour coder le moteur. Je sais que de nombreux moteurs d'échecs utilisent C ++, que je n'ai jamais utilisé auparavant. J'ai utilisé d'autres langages basés sur C qui font beaucoup des mêmes choses, avec une syntaxe principalement variable. Je connais le mieux Swift et Javascript, mais je connais aussi Python et je pense que cela pourrait faire l'affaire pour moi.

Python et Javascript sont probablement trop lents pour un moteur d'échecs puissant. Je n'ai pas utilisé Swift mais il n'aimera probablement pas les plates-formes autres que macOS, il est donc préférable d'utiliser C ou C ++. Vous pouvez également utiliser Rust, mais cela a de nombreuses fonctionnalités de sécurité qui deviennent ennuyeuses et dont vous n'avez pas vraiment besoin, ce qui peut devenir ennuyeux. Il sera également plus difficile d'en tirer de bonnes performances, car certaines optimisations de bas niveau sont difficiles à réaliser. Bien sûr, vous pouvez toujours l'écrire en assembleur mais cela va probablement être trop de travail. voir https://www.chessprogramming.org/Languages/

moi'
la source
1
Génial, merci beaucoup pour l'info! J'essaierai probablement de créer une API qui prend une position FEN et génère le mouvement calculé. Je pense que c'est la meilleure façon de s'intégrer aux bots Lichess.
David Chopin
1
Est-ce une option pour implémenter un moteur NN différent qui utilise simplement le réseau de lc0?
RemcoGerlich
1
@RemcoGerlich si je comprends bien, les moteurs NN utilisent deux choses: le binaire et le réseau neuronal. Écrire un binaire n'est pas facile, mais former un réseau neuronal est relativement facile. En ce sens, les dérivés Lc0 existent déjà - Leelenstein & Deus X (aka. Fat Fritz) sont de tels dérivés.
Allure
@RemcoGerlich dans ce cas, ce ne serait pas vraiment un moteur différent, ce serait le moteur Ic0 avec juste un habillage / une interface / quelque chose de différent.
Peteris
3

J'ai construit un moteur d'échecs purement jouet en utilisant: les échecs en python, c'était vraiment bien de ne pas avoir à coder les règles du jeu moi-même et de me concentrer uniquement sur la logique; cependant, le nombre de postes que j'ai pu évaluer par seconde est très faible. Cela pourrait être un bon point de départ.

Akavall
la source