par Lauri Hartikka

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

• génération de mouvements
• évaluation de la carte
• minimax
• et élagage alpha bêta.

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

Vous pouvez voir l’algorithme d’IA final ici sur GitHub.

Étape 1 : Génération de mouvements et visualisation du plateau

Nous utiliserons les échecs.bibliothèque js pour la génération de mouvements et l’échiquier.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 de 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 coup aléatoire de tous les coups 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 réellement jouer contre lui:

Étape 2 : Évaluation de 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 force relative des pièces sur la carte en utilisant le tableau suivant:

Avec la fonction d’évaluation, nous sommes en mesure de créer un algorithme qui choisit le mouvement qui donne l’évaluation la plus élevée:

La seule amélioration tangible est que notre algorithme va maintenant capturer une pièce s’il le peut.

Étape 3: Arbre de recherche en utilisant 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 à la fin des « feuilles » de l’arbre.

Après cela, nous renvoyons la plus petite ou la plus grande valeur de l’enfant au nœud parent, selon qu’il s’agit d’un nœud blanc ou noir à déplacer. (C’est-à-dire que 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: Élagage 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 en profondeur, 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 précédemment découvert.

L’élagage alpha-bêta n’influence pas le résultat de l’algorithme minimax — il ne fait que le rendre plus rapide.

L’algorithme alpha-bêta est également plus efficace si nous visitons d’abord les chemins qui mènent à de bons mouvements.

Avec alpha-beta, nous obtenons un coup de pouce significatif à l’algorithme minimax, comme le montre l’exemple suivant:

Suivez ce lien pour essayer la version améliorée alpha-bêta de l’IA d’échecs.

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

La fonction d’évaluation initiale est assez naïve car nous ne comptons que le matériel qui se trouve sur la carte. Pour améliorer cela, nous ajoutons à l’évaluation un facteur qui prend en compte 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 piece-square décrites à l’origine dans le wiki chess-programming.

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

Conclusions

La force même d’un algorithme de jeu d’échecs simple 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 IA » (génération de mouvements exclue) de l’algorithme final ne compte que 200 lignes de code, ce qui signifie que les concepts de base sont assez simples à mettre en œuvre. Vous pouvez consulter la version finale sur GitHub.

D’autres améliorations que nous pourrions apporter à l’algorithme seraient par exemple:

• commande de mouvements
• génération de mouvements plus rapide
• et évaluation spécifique à la fin du jeu.