L'algorithme fondamental est, dans sa forme la plus simple, quelque chose comme Negamax - Wikipedia. En mots, c'est comme ceci :
- Calculer tous les coups légaux dans la position actuelle.
- Regarder tous mes coups possibles. Dessinez un arbre où la racine est la position actuelle, et chaque mouvement possible est une branche menant à un autre nœud - ce sont les positions suivantes possibles.
- Tentez chaque mouvement possible - imaginez faire ce mouvement et calculez la nouvelle position. Maintenant, revenez à l'étape 1 et continuez à étendre l'arbre.
Vous remarquerez que cela nous permet de regarder toutes les parties d'échecs possibles, mais cela prendra fondamentalement une éternité. Donc, nous devons modifier l'étape 1 en limitant la profondeur à un certain # de coups, D:
- Calculer tous les coups légaux dans la position actuelle. MAIS si nous avons déjà atteint la profondeur D dans l'arbre, évaluer la position actuelle. Enregistrer le résultat dans l'arbre.
Je vais gloser sur la partie critique maintenant puisque c'est bien expliqué ailleurs : à chaque niveau de l'arbre avant les nœuds " feuilles " de profondeur D terminaux, nous regardons toutes les évaluations à la position suivante. Nous supposons que la personne dont c'est le tour fera le meilleur coup possible pour elle, donc nous enregistrons ce score d'évaluation (et le meilleur coup à jouer) et le propageons (récursivement) à travers l'arbre jusqu'à la racine. Le résultat final est que nous avons imaginé que dans toutes les positions possibles, le joueur à déplacer effectue le meilleur déplacement possible (en supposant qu'il puisse voir les évaluations à la profondeur D). Le meilleur coup possible à la position initiale de la racine est le coup que vous feriez, en supposant que votre adversaire fera les meilleurs coups possibles. L'algorithme Negamax est une manière récursive super élégante d'implémenter cet algorithme en quelques lignes de code.
Pour évaluer une position et lui attribuer un score : vous pouvez simplement calculer la quantité de matériel pour chaque côté, et attribuer, disons, +4 si les blancs sont en avance d'un chevalier et d'un pion. Vous pouvez également calculer des facteurs positionnels (sécurité du roi, placement des pièces mineures, structure des pions, etc.) et les ajouter au score.
Il existe de nombreux raffinements de l'algorithme de base de Negamax. Le principal d'entre eux est la recherche alpha-bêta, qui aide à élaguer les branches de l'arbre de jeu manifestement inutiles. D'autres, comme la recherche de quiescence, permettent d'éviter l'"effet d'horizon", lorsqu'un ordinateur effectue des mouvements qui semblent excellents jusqu'à la profondeur D, mais perd ensuite une reine, disons, à la profondeur D+1 (sans solution pour l'effet d'horizon, les ordinateurs deviennent souvent fous en donnant des pièces, car ils pensent que la partie se termine à la profondeur D). Dans la recherche de quiescence, l'arbre est étendu lorsqu'une position est pleine de coups critiques comme les contrôles de roi et les captures.
Enfin, il y a des tonnes d'astuces de vitesse (hashtables pour se souvenir des positions vues précédemment ; tableaux de bits pour un calcul follement efficace des coups légaux - des trucs vraiment beaux et étonnants ici, avec des tableaux représentés en utilisant des schémas binaires avec 1 bit pour chacune des 64 cases, ce qui fonctionne bien avec les processeurs 64 bits modernes !; des tableaux de fin de partie qui ont des fins pour 5 ou 6 pièces complètement précalculées, des tableaux d'ouverture avec les meilleurs coups sélectionnés à partir de la pratique des grands maîtres, etc etc.)
Si vous êtes un programmeur, il est amusant de coder 1) le générateur de coups légaux, et 2) l'algorithme Negamax, avec une fonction d'évaluation simple. C'est tout ce dont vous avez besoin pour faire un moteur d'échecs de base !
Mise à jour : AlphaZero est apparu après que j'ai initialement répondu à cette question. La configuration de la recherche d'arbre monte carlo et de l'apprentissage par renforcement profond est différente de ce que j'ai décrit ci-dessus et mérite une réponse quora distincte, bien que les bases de la recherche d'arbre soient toujours importantes. Je recommanderais d'apprendre la recherche traditionnelle Negamax/alpha-beta d'abord, puis d'apprendre AlphaZero.