Un guide étape par étape pour créer une IA d'échecs simple

Explorons quelques concepts de base qui nous aideront à créer une IA d'échecs simple:

  • génération de mouvements
  • évaluation du conseil
  • minimax
  • et la taille alpha bêta.

À chaque étape, nous améliorerons notre algorithme avec l'une de ces techniques de programmation d'échecs éprouvées. Je vais vous montrer comment chacun affecte le style de jeu de l'algorithme.

Vous pouvez voir l'algorithme IA final ici sur GitHub.

Étape 1: Génération de déplacement et visualisation du tableau

Nous utiliserons la bibliothèque chess.js pour la génération de mouvements et chessboard.js pour visualiser le tableau. La bibliothèque de génération de mouvements implémente essentiellement toutes les règles des échecs. Sur cette base, nous pouvons calculer tous les mouvements légaux pour un état du conseil donné.

L'utilisation de ces bibliothèques nous aidera à nous concentrer uniquement sur la tâche la plus intéressante: créer l'algorithme qui trouve le meilleur coup.

Nous allons commencer par créer une fonction qui renvoie simplement un mouvement aléatoire de tous les mouvements possibles:

Bien que cet algorithme ne soit pas un joueur d'échecs très solide, c'est un bon point de départ, car nous pouvons jouer contre lui:

Étape 2: Évaluation de la position

Essayons maintenant de comprendre quel côté est le plus fort dans une certaine position. Le moyen le plus simple d'y parvenir est de compter la résistance relative des pièces sur le plateau en utilisant le tableau suivant:

Avec la fonction d'évaluation, nous pouvons créer un algorithme qui choisit le coup qui donne l'évaluation la plus élevée:

La seule amélioration tangible est que notre algorithme capturera désormais un morceau s'il le peut.

Étape 3: Rechercher dans l'arborescence à l'aide de Minimax

Ensuite, nous allons créer un arbre de recherche à partir duquel l'algorithme peut choisir le meilleur coup. Cela se fait en utilisant l'algorithme Minimax.

Dans cet algorithme, l'arbre récursif de tous les mouvements possibles est exploré à une profondeur donnée, et la position est évaluée aux «feuilles» de fin de l'arbre.

Après cela, nous renvoyons la valeur la plus petite ou la plus grande de l'enfant au nœud parent, selon qu'il s'agit d'un blanc ou d'un noir à déplacer. (Autrement dit, nous essayons de minimiser ou de maximiser le résultat à chaque niveau.)

Avec minimax en place, notre algorithme commence à comprendre certaines tactiques de base des échecs:

L'efficacité de l'algorithme minimax est fortement basée sur la profondeur de recherche que nous pouvons atteindre. C'est quelque chose que nous améliorerons à l'étape suivante.

Étape 4: Taille alpha-bêta

L'élagage alpha-bêta est une méthode d'optimisation de l'algorithme minimax qui nous permet de ne pas tenir compte de certaines branches de l'arbre de recherche. Cela nous aide à évaluer l'arbre de recherche minimax beaucoup plus profondément, tout en utilisant les mêmes ressources.

L'élagage alpha-bêta est basé sur la situation où nous pouvons arrêter d'évaluer une partie de l'arbre de recherche si nous trouvons un mouvement qui conduit à une situation pire qu'un mouvement découvert précédemment.

L'élagage alpha-bêta n'influence pas le résultat de l'algorithme minimax - il le rend seulement plus rapide.

L'algorithme alpha-bêta est également plus efficace s'il nous arrive de visiter d' abord les chemins qui mènent à de bons mouvements.

Avec alpha-beta, nous obtenons une amélioration significative de l'algorithme minimax, comme le montre l'exemple suivant:

Suivez ce lien pour essayer la version améliorée alpha-beta de l'IA d'échecs.

Étape 5: Fonction d'évaluation améliorée

La fonction d'évaluation initiale est assez naïve car on ne compte que le matériel qui se trouve sur le plateau. Pour améliorer cela, nous ajoutons à l'évaluation un facteur qui tient compte de la position des pièces. Par exemple, un chevalier au centre du plateau est meilleur (car il a plus d'options et est donc plus actif) qu'un chevalier sur le bord du plateau.

Nous utiliserons une version légèrement ajustée des tables de pièces carrées qui sont à l'origine décrites dans le chess-programmation-wiki.

Avec l'amélioration suivante, nous commençons à obtenir un algorithme qui joue des échecs «décents», au moins du point de vue d'un joueur occasionnel:

Conclusions

La force même d'un simple algorithme de jeu d'échecs est qu'il ne fait pas d'erreurs stupides. Cela dit, il manque encore de compréhension stratégique.

Avec les méthodes que j'ai présentées ici, nous avons pu programmer un algorithme de jeu d'échecs capable de jouer aux échecs de base. La «partie AI» (génération de mouvement exclue) de l'algorithme final ne comprend que 200 lignes de code, ce qui signifie que les concepts de base sont assez simples à mettre en œuvre. Vous pouvez vérifier que la version finale est sur GitHub.

Certaines améliorations supplémentaires que nous pourrions apporter à l'algorithme seraient par exemple:

  • ordre de déplacement
  • génération de mouvements plus rapide
  • et évaluation spécifique de fin de partie.

Si vous voulez en savoir plus, consultez le wiki de programmation d'échecs. C'est une ressource utile pour explorer au-delà de ces concepts de base que j'ai présentés ici.

Merci d'avoir lu!