La meilleure approche pour écrire un moteur d'échecs? [fermé]

Je suis un passionné d'échecs et un programmeur. J'ai récemment décidé de commencer à créer un moteur d'échecs en utilisant mes connaissances en matière d'échecs et de programmation. Voici donc ma question:

Quel langage (je connais Java, C ++ et Python) et quelle méthodologie dois-je adapter lors de l'écriture d'un moteur d'échecs?

Un petit conseil serait très apprécié.

Éditer:

J'ai donc décidé de le faire en JavaScript. Je télécharge cette interface utilisateur d'échecs depuis github et maintenant je suis prêt! Ma première étape serait d'écrire des mouvements légaux pour cela. Alors, quelqu'un peut-il m'orienter dans la bonne direction? (Je suis nouveau sur jQuery mais j'ai beaucoup d'expérience en programmation).

PS: Je n'essaie pas de faire un moteur très efficace (je sais que c'est trop difficile), je veux juste me familiariser avec le processus et apprendre de nouvelles techniques en cours de route.

Joueur d'échecs classé 2072 ici. J'ai réalisé ce site en pur JavaScript pendant un week-end. Ce n'est pas un moteur d'échecs (je l'ai conçu pour créer des positions d'ouverture divertissantes comme une sorte de moteur Chess960 pervers), mais c'est un point de départ. Le code source est ici .

Il y a beaucoup de complications impliquées dans la fabrication d'une carte fonctionnelle. Ceux-ci inclus:

• Tout d'abord, trouver comment représenter les mouvements juridiques de base. Vous devez faire des calculs avec les coordonnées de début et de fin. Par exemple, avec les mouvements de tour, l'une des coordonnées doit être la même avant et après. Avec les mouvements de chevalier, la somme de la valeur absolue des changements de coordonnées doit être de 3, et les deux coordonnées doivent changer. Avec les mouvements d'évêque, soit la somme des coordonnées reste la même, soit elles augmentent toutes les deux du même montant. Les pions sont les plus délicats car vous devez non seulement déterminer s'ils peuvent déplacer deux carrés ou un (vérifiez la ligne et la couleur au lieu de stocker le nombre de mouvements qu'ils ont effectués), mais vous devez également gérer l'ensemble de la capture en diagonale, déplacer -avant.
• La capture est un défi à cause des pions et des chèques. Vous ne pouvez pas simplement dire que si un morceau se déplace vers le carré d'un autre morceau, alors c'est une capture. Après tout, les pions ne peuvent pas se déplacer vers la case d'une autre pièce pour capturer - ils ont leur propre façon de capturer.
• Vous devez trouver un moyen efficace de voir si les pièces ennemies entravent le déplacement d'une pièce afin de décider si elle est légale ou non.
• Vérifier est difficile à gérer. Après chaque mouvement, vous devez vérifier toutes les cases vers lesquelles les pièces ennemies peuvent aller et voir si l'une d'elles implique votre roi et, si c'est le cas, c'est un mouvement illégal.
• Roque, en passant, promotion, impasse, tirages forcés, répétition - aucun de ces éléments n'est trivial à gérer étant donné l'ampleur du problème.

Tous les moteurs d'échecs fonctionnent en regardant tous (éventuellement un sous-ensemble déterminé de manière heuristique) des mouvements légaux dans une position et en évaluant les nombres pour représenter leurs valeurs relatives en effectuant ces mouvements et en faisant récursivement la même chose pour les positions résultantes. Vos problèmes jumeaux ici sont

• Comment stocker ces données efficacement
• Comment procéder avec cette recherche récursive - après tout, vous ne pouvez pas la laisser continuer indéfiniment, vous devez donc mettre une limite, puis trouver comment concevoir votre algorithme pour effectuer la recherche la plus optimale et approfondie dans cette limite. Par exemple, vous voulez vous assurer qu'il propose au moins une évaluation pour chaque coup de départ possible, mais vous pouvez également vouloir passer plus de temps à évaluer des coups plus prometteurs au lieu de donner un temps égal à chaque coup.

Tout cela en plus de la conception de l'algorithme en premier lieu, sur lequel de nombreuses informations sont disponibles.

Quant à la langue à utiliser (même si je suppose que vous avez déjà décidé de JavaScript), je pense que cela dépend plus de votre objectif que de toute autre chose. Je voulais créer le mien en ligne (et m'améliorer avec JavaScript), alors JavaScript était mon choix. N'importe quel langage de programmation orienté objet fera l'affaire.

Une fois que vous serez à l'aise avec ce que vous faites, les ressources suivantes s'avéreront probablement très utiles:

• Wiki de programmation d'échecs
• Forum de programmation d'échecs
• StockFish sur Github

Bonne chance!

Le problème avec le "programme d'échecs" en tant que concept est qu'il existe de nombreuses pièces qui peuvent absorber beaucoup de temps et ne vous intéressent pas nécessairement pour le moment. Vous pouvez passer des années à travailler uniquement sur des graphiques, ou une recherche alpha-bêta, ou une visualisation pour aider à développer pour le moteur de recherche, ou ... eh bien, il y a beaucoup de morceaux.

Je recommande de trouver un programme d'échecs open source (il doit y en avoir plusieurs) et de m'atteler à en améliorer les parties qui vous intéressent le plus. Vous pouvez éventuellement remplacer l'intégralité du programme, une fonction à la fois, ou vous pouvez en apprendre suffisamment et être motivé à le jeter et à concevoir votre propre programme à partir de zéro. Dans tous les cas, la clé est de démarrer "light" et d'apprendre les cordes avant d'essayer de concevoir un programme entier.

Si vous connaissez les règles des échecs, un bon point de départ sur les techniques de base est http://www.frayn.net/beowulf/theory.html Une vaste collection de matériaux et de liens que vous pouvez trouver ici: http: // chessprogramming .wikispaces.com / Et troisièmement: Apprenez du code des autres. Jetez un œil aux sources de Crafty . C'est le premier moteur open source. Il sera très important de penser aux cas de test, pour voir si vous apportez des améliorations: commencez par exemple avec des positions de fin de jeu simples et faciles avec 3 ou 4 chiffres.

Comme mentionné, il n'y a rien de vraiment difficile à construire un moteur d'échecs. Peut-être devriez-vous vous concentrer sur la façon d'utiliser et de déployer (potentiellement) cette application, car cela déterminera probablement votre choix de langue.

Si ce n'est qu'un exercice amusant, vous pouvez le coder en Javascript et le déployer en tant que page Web. Si vous ne voulez jamais en faire un jeu d'échecs expert, au moins d'autres pourront jouer avec lui et son code source.

Si vous souhaitez apprendre une technologie particulière en même temps, par exemple WPF, cela pourrait être un bon moyen de tuer deux oiseaux avec une pierre. MVVM pourrait être exagéré pour cette application, mais vous l'apprendriez au moins.

Si vous souhaitez cibler des appareils Android, Java serait un bon choix. De même, Objective-C pour les appareils iOS.

Long et court, le choix de la langue n'existe pas dans le vide.

Je suppose que vous connaissez déjà le concept de Min-Max, les arbres et l'élagage, l'heuristique et d'autres bases et ce que j'écris ici ne sont que quelques détails qui auraient pu être sous-estimés.

En compagnie d'un ami, j'ai écrit notre propre moteur d'échecs il y a parfois. Je partage quelques problèmes et idées que nous avions et j'espère que vous les trouverez utiles.

Comme nous étions tous les deux des programmeurs java, notre langage s'est transformé en Java et nous avons commencé avec une approche orientée objet. Les pièces étaient des objets, le tableau était un objet, les fichiers et les rangs (rangées et colonnes dans la littérature d'échecs) étaient des objets. Et c'était faux. Les frais généraux étaient énormes et le programme avait du mal à aller plus loin que 2 mouvements (4 plis) dans l'arbre de recherche.

Donc, avec quelques recherches, nous nous sommes retrouvés avec une idée brillante (pas la nôtre cependant!): Représenter les pièces et le tableau comme des entiers longs (64 bits). Cela a du sens car un échiquier a 64 cases. Le reste était des opérations peu judicieuses (fonctionnant très près de cpu = extrêmement rapide). Par exemple, considérons un entier binaire 64 bits dans lequel ceux-ci présentent les carrés du tableau que votre pièce peut attaquer. Maintenant, si vous exécutez un "ET" logique entre deux nombres comme celui-ci, un résultat différent de zéro indique que vous avez un carré avec des attaquants. Il y a plusieurs façons de présenter l'échiquier et les pièces, donc:

1 - Décidez de la présentation de votre conseil

Ensuite, vous avez besoin et l'ouverture de la base de données. L'ouverture des échecs est en quelque sorte résolue et il est fortement recommandé d'avoir un livre d'ouverture. Dans ce cas, vous avez beaucoup de temps supplémentaire dans les jeux Blitz.

2 - Trouvez-vous un livre d'ouverture.

Nous l'avons fait, mais nous étions encore loin d'être bons:

3 - Un bon moteur d'échecs devrait pouvoir voir 6 coups (12 plis) devant.

Donc ce que nous avons fait alors, c'était d'utiliser le temps mort (si c'est un moteur humain vs ordinateur).

4 - Utilisez le temps où l'adversaire pense à créer certains niveaux de votre arbre.

Et pourtant nous étions loin de 12 plis. Par plus d'étude, nous découvrons quelques astuces! Par exemple, il a été suggéré de sauter un pli de l'arbre et de commencer par le pli suivant (comme s'il n'y avait pas d'adversaire). L'idée est que si un mouvement est extrêmement idiot, alors pourquoi perdre du temps et voir quelles sont les réponses des adversaires à ce mouvement. Cependant, un bon moteur devrait être capable de faire la distinction entre le mouvement idiot et le sacrifice de la reine du génie.

5 - Apprenez les astuces de programmation pour ce problème spécifique (échecs).

Mon ami et moi, dans cet état, étions encore mauvais: / Ce que nous pouvions faire - et nous l'avons fait en partie - était de sauvegarder les positions calculées. Si vous calculez une position, enregistrez-la pour l'avenir! Il en va de même pour les boucles dans l'arborescence de recherche. Le but était de sauvegarder / récupérer efficacement:

6 - Sauvegardez les données que vous générez ... efficacement!

et enfin:

7 - Code avec optimisation maximale.

Ce problème est extrêmement coûteux à la fois en temps CPU et en mémoire. Il est très important d'écrire votre code très efficacement. N'oubliez pas que nous parlons du facteur de branche de 35. Cela signifie qu'un "si" inutile quelque part dans votre heuristique, peut être transformé en 3.3792205e+18"si" inutile quelque part au fond de votre arbre de recherche.

La programmation des échecs est un défi très très intéressant et c'est le moment où vous pouvez mettre vos capacités de programmation à rude épreuve. Il y a quelques autres points que je peux suggérer, mais je suis sûr que vous les découvrirez par vous-même. Il y a bien d'autres points que je ne connais pas mais vous pouvez les trouver sur internet!

Bonne chance et amusez-vous bien!

ps Je ne connais pas très bien javascript mais quelque chose me dit en fonction de la difficulté du problème, peut-être, compte tenu de tout ce que C ++ peut offrir, il serait préférable de supprimer javascript et de le faire en C ++.

Selon votre modification, vous êtes au stade de la définition des mouvements «légaux».

Il existe deux façons de décrire les mouvements aux échecs. Notation descriptive et notation algébrique . Ce que vous voulez probablement, c'est une fonction qui prend la pièce, la position de départ et la position de fin comme paramètres. par exemple. Knight de QN1 à QB2 n'est pas valide, mais Knight de QN1 à Q2 est valide. En y réfléchissant, la notation algébrique peut être plus simple en raison de la capacité de calculer facilement le positionnement «relatif».

Pour vous assurer que vous écrivez le montant minimum de code requis, je commence par écrire des tests pour cette fonction première . Si vous utilisez la notation algébrique, vous n'avez probablement pas besoin d'un test par morceau / début / fin. Faites fonctionner chaque test et refactorisez la duplication avant de passer au prochain «déménagement». Votre code finira plus propre.

Une fois que vous avez suffisamment couvert les mouvements légaux et illégaux pour chaque pièce, je commencerais à ajouter des vérifications pour d'autres variables (telles que le déplacement d'un roi dans les conditions de `` contrôle '' et de `` partenaire '').

Je recommande qunit pour les tests unitaires et jasmine pour les tests de comportement en JavaScript.

J'ai en fait écrit un moteur d'échecs. Préparez-vous à la fois pour une gâterie et un cauchemar. Quand mes amis et moi l'avons fait, c'était dans un concours de programmation chronométré et le langage avec lequel nous avons décidé d'aller était Java. Je pense que Java ou C est votre meilleur choix, mais je vois que vous avez décidé d'utiliser Javascript. Je ne peux pas vraiment le frapper parce que je ne le connais pas.

Le problème principal ici sera qu'il y a tellement de scénarios déplacer / gagner avec chaque morceau que vous devez prendre en compte, donc je vous recommande d'écrire toutes ces situations possibles pour chaque morceau avant de commencer à coder. Le simple fait de sauter sans planification transformera ce projet amusant en corvée répétitive. Mais c'est vraiment l'essentiel. Planifiez d'abord en dehors du code et assurez-vous d'obtenir chaque scénario pour une pièce à la fois.

Bonne chance

Pour la partie du jeu qui prend des décisions sur ordinateur, je ne saurais trop recommander le livre "Intelligence artificielle: une approche moderne" (site Web du livre http://aima.cs.berkeley.edu/ ). Selon votre formation en mathématiques (la théorie des graphes aide), cela peut être un peu élevé, mais il est écrit aussi simplement que ces trucs académiques peuvent contenir un aperçu très à jour (et une certaine profondeur) des techniques à faire en sorte que les programmes décident des choses.

Il vous indiquera des choses telles que la définition d'un objectif (c'est-à-dire échec et mat), l'évaluation de la proximité d'un état particulier (disposition du tableau) avec cet objectif, comment générer les différents états suivants possibles à partir de l'actuel, et comment traverser ce qui est un immense espace problématique.

Une chose qui pourrait aider à concevoir un algorithme d'intelligence artificielle est de comprendre comment décider quel mouvement jouer ensuite comme si vous aviez tout le temps du monde, à partir d'une situation très proche d'une partie gagnée. Vous l'optimisez afin qu'il trouve une solution dans un délai raisonnable (heures), puis trouvez des moyens de choisir une voie gagnante même si vous n'avez pas encore exploré tous les résultats, afin que vous puissiez réellement interrompre la «réflexion» pour la valeur d'un tour de temps.

Ce n'est qu'alors que je chercherais à optimiser la représentation de pour rendre les calculs individuels plus rapides, comme l'utilisation de longs entiers comme cela a été suggéré. Quelle que soit la vitesse à laquelle vous pouvez faire une seule comparaison, si la façon dont vous parcourez l'espace du problème n'a pas une bonne heuristique, cela prendra du temps.

Vous pouvez vraiment aller comme vous voulez, mais voici mes réflexions sur le sujet:

J'utiliserais Java car cela vous permet d'être de très haut niveau et d'avoir des bibliothèques d'interface utilisateur (AWT, Swing) à votre disposition directe. Vous pouvez utiliser une approche orientée objet pour modéliser l'échiquier et les pièces. D'autres objets pourraient remplacer l'historique des mouvements et le score. Même les joueurs pourraient être des objets, et vous pourriez à l'avenir étendre votre Playerclasse pour fournir un lecteur d'ordinateur intelligent artificiel.

Vous voudrez peut-être jeter un œil à model-view-controller (MVC) car c'est une très bonne approche dans ce cas pour lier vos objets de modèle (modèle de domaine) à l'interface utilisateur (vue) et permettre à l'utilisateur de manipuler le modèle (via le contrôleur).

Vous pouvez également appliquer le développement piloté par les tests , qui non seulement garantit que toutes les méthodes se comportent comme vous le souhaitez, mais vous oblige également à écrire du code modulaire testable.

Les règles des échecs sont elles-mêmes assez simples. Il vous suffit de pouvoir créer une matrice (tableau bidimensionnel) pour le plateau, et de trouver un moyen d'encoder les concepts des pièces, les règles de mouvement pour chaque pièce, la validation qu'un mouvement est légal et les conditions qui signalent la fin de la partie. Rien de particulièrement difficile à ce sujet. Vous devez utiliser la langue que vous connaissez le mieux.

Maintenant, si vous voulez créer une IA jouant aux échecs qui jouera le rôle de l'un des joueurs, c'est là que les choses deviennent délicates. Mais encore une fois, le choix de la langue n'est pas le plus gros problème ici; comprendre les principes de l'IA impliqués est. Ce sera un facteur beaucoup plus important.

(Cela dit, ce type de prise de décision peut être extrêmement intensif en calcul, et vous voudrez probablement utiliser quelque chose qui se compile en code natif plutôt qu'un langage de script. Et C ++ est un très mauvais choix, non pas parce qu'il n'est pas bien -Convient à ce problème, mais simplement parce que c'est un très mauvais langage en général, et essayer d'implémenter des choses complexes est un bon moyen de coder toutes sortes de maux de tête par vous-même.)