Analyse & Programmation

Introduction

Nous allons commencer par un peu de théorie. La recherche alpha-bêta est une variante de la recherche en profondeur d'abord. La recherche en profondeur d'abord est un algorithme pour parcourir un graphe ou un arbre de nœuds. En théorie, l'arbre des coups possibles à une profondeur données est un graphe et non un arbre car les positions peuvent revenir par différents ordres des coups. Et puisqu'un arbre ne doit pas posséder deux chemins différents pour rejoindre un même nœud, c'est donc un graphe. Par contre, dans le domaine, nous l'appelons toujours un arbre tout de même.

Recherche en profondeur

La recherche en profondeur d'abord est le cousin de la recherche en largeur d'abord. La différence vient de l'ordre dans lequel les noeuds sont visités. Dans la recherche en profondeur d'abord, nous générons les noeuds possibles d'un niveau et visitons le premier noeud pour passer au prochain niveau. Nous répétons ce processus jusqu'à la profondeur voulue.

Voici l'algorithme en langage pseudo:

fonction rechercher-profondeur(profondeur, échiquier)
début
 génère coups
 pour chaque coups de la liste
 jouer coup
 si on est rendu à la profondeur 0
 alors
 retourner la valeur de la position
 sinon
 valeur = rechercher(profondeur-1, echiquier)
 déjouer coup
 retourn la meilleur valeur
fin

Pour faciliter  la compréhension, voici un graphique indiquant l'ordre dans lequel les noeuds sont visités pour une recherche en profondeur:

Recherche minimax

L'algorithme au dessus est un algorithme utilisé pour trouver la meilleure valeur à une profondeur quelconque. Il est souvent utilisé pour essayer de trouver la meilleur solution à un problème. Par contre, dans le cas du jeu d'échecs, il y a deux adversaires ayant des buts opposés. Chacun essaie de faire augmenter son score personnel. Chacun regarde la position avec un but inverse. On doit donc modifier l'algorithme pour prendre en compte cette nouvelle réalité. L'algorithme minimax répond à notre problème.

Voici la nouvelle version légèrement modifiée, l'algorithme minimax de Von Neumann.

fonction minimax(profondeur, échiquier)
début
	génère coups
 	pour chaque coups de la liste
 	    jouer coup
 	    si on est rendu à la profondeur 0
 	    alors
 		retourner la valeur de la position
 	    sinon
 		valeur = rechercher(profondeur-1, echiquier)
 	    déjouer coup
 	si c'est le tour du moteur
 		retourner la meilleur valeur
 	sinon
 		retourner la pire valeur
fin

 

 

Négamax

L'algorithme connu sous le nom de Négamax est une légère variante de l'algorithme Minimax. La modification consiste simplement à inverser le résultat retourné de la recherche à la profondeur suivante. Il réduit beaucoup la quantité de code nécessaire pour l'écriture d'un moteur d'échecs.

L'algorithme en pseudo langage est le suivant:

function negamax(profondeur, échiquier, couleur)
début
        génère coups pour couleur
        pour chaque coups de la liste
            jouer coup
            si on est rendu à la profondeur 0 // Si c'est un feuille
            alors
                retourner la valeur de la position
            sinon
               valeur = -negamax(profondeur-1, échiquier, inverse(couleur))
            déjouer coup
       retourner la meilleur valeur
fin

Le principe est simple, puisque les joueurs à tour de rôle essaient d'améliorer leur propre score, nous utilisons une échelle permettant les valeurs négatives et nous gardons un seul score pour les deux joueurs. Par exemple, une valeur positive signifie que les blancs ont l'avantage et une valeur négative signifie que les noirs ont l'avantage.

Voici un exemple d'exécution à une profondeur de 2 et pour évaluer le meilleur coup des blancs.

Nous appelons la fonction négamax comme suit:

meilleur = negamax(2, position, blanc)

1. L'algorithme génère les coups possibles des blancs.

2. L'algorithme prend le premier coup de la liste et le joue sur l'échiquier.

3. Puisque que nous ne sommes pas encore à la profondeur 0, nous appelons à nouveau la fonction negamax avec une profondeur de moins et en inversant la couleur.

4. Negamax génère les coups possibles pour les noirs.

5. Pour chacun des coups, il va appeler encore une fois négamax, mais cette fois-ci avec comme valeur de profondeur à 0 ce qui aura pour effet de retourner tout simplement la valeur de la position.

6. Ensuite, negamax va retourner le meilleur score trouvé. J'espère que vous me suivez bien ici. Rendu ici, négamax va garder le score de la meilleur réplique contre le premier coup des blancs. Supposons que c'est 10.

7. La valeur retourné de negamax est 10 et nous l'inversons ce qui nous donne une valeur de -10. Donc pour le premier coup des blancs, la meilleur réplique des noirs donne un score de 10.

8. Negamax passe au deuxième coup et rappelle negamax à nouveau.

9. Si le score retourné est meilleur que le score trouvé jusqu'à présent, nous le gardons et nous recommençons pour chacun des coups possibles des blancs. Supposons qu'un des coups des blancs, la meilleur réplique des noirs ne donne qu'un score de 5, alors nous allons avoir un meilleur score de 5. En faisant cela pour chaque coup possible des blancs, nous sommes assuré de trouvé le coup ayant le meilleur score à une profondeur de 2.

Voici un graphique pour visualiser l'exemple ci-haut:

Alpha-bêta

L'algorithme de recherche alpha-bêta est en réalité l'algorithme minimax ou negamax avec des coupes. Les coupes sont des branches de l'arbre qu'il serait inutile d'explorer. L'algorithme retourne le même résultat que Negamax mais plus rapidement car le nombre de nœud exploré est réduit.

Pour comprendre comment il fonctionne prenons un exemple simple. Supposons que c'est aux blancs à jouer et que nous effectuons une recherche à une profondeur 2. L'algorithme simule le premier coup et c'est une capture de pion.

L'algorithme poursuit et simule le premier coup des noirs. Le pion n'est pas regagné. L'algorithme poursuit et c'est le temps de l'évaluation. Le score est de 100 pour les blancs. L'algorithme revient et simule le deuxième coups des noirs et le pion n'est toujours pas regagné et c'est la même chose pour toutes les répliques des noirs.

L'algorithme passe donc au deuxième coups des blancs mais maintenant, l'algorithme passe en paramètre le score d'un pion pour les blancs comme borne supérieure pour les noirs qui un coup inversé devient la perte d'un pion, donc -100. Si un coup des noirs dépasse cette borne, ils améliorent leur sort et c'est donc que le coup des blancs est moins bon.

Poursuivons pour voir.

Nous évaluons le deuxième coups des blancs. L'algorithme simule le coup et c'est un simple mouvement de pièce, aucun gain de pion. Il simule le premier coup des noirs et ensuite l'évaluation de la position. Le score est de 0. L'évaluateur donne nulle pour ce coup. L'algorithme revient et reçoit la valeur de 0. Le score des noirs est supérieur à la borne de -100 qui est la perte d'un pion. Ce qui rend inutile l'exploration du reste des coups des noirs car nous savons que le coup des blancs est moins bon que le coup précédent. La seule chose qui peut arriver, c'est que nous trouvions un coup encore pire pour les blancs.

Voici l'algorithme.

function alpha-beta(profondeur, échiquier, couleur, alpha, beta)
début
        génère coups pour couleur
        pour chaque coups de la liste
            jouer coup
            si on est rendu à la profondeur 0 // Si c'est un feuille
            alors
                retourner la valeur de la position
            sinon
		valeur = -alpha-beta(profondeur-1, échiquier, inverse(couleur), -beta, -alpha)
            déjouer coup
	si la valeur est supérieur à alpha
	alors
		alpha = valeur // Le meilleur coup jusqu'à maintenant
		si alpha est supérieur à bêta alors on retourne alpha // Inutile de poursuivre
	retourner alpha
fin

Remarquez qu'à chaque appelle d'alpha-bêta, les bornes sont inversés. Bêta devient toujours le meilleur score de l'opposant à ne pas dépasser, sinon c'est qu'il est inutile de poursuivre parce que le joueur à ce niveau a un meilleur coup.

Étudiez bien l'algorithme et faites même un trace pour bien comprendre ce qui se passe. C'est ce qui vous permettra d'améliorer votre moteur au moment venu.

 

 

Ordonnancement des coups

Si vous avez bien étudiez l'algorithme de recherche alpha-bêta, vous aurez sûrement compris qu'il est avantageux d'avoir les meilleurs coups au début de la recherche car ils vont générer plus de coupes plus rapidement. Si vous naviguez un peu dans le monde des programmeurs de moteur d'échecs vous entendrez souvent parler d'ordonnancement des coups.

Avec un bon ordonnancement des coups, les coupes peuvent augmenter exponentiellement. C'est une des raisons pourquoi nous avons parlé de deux fonctions séparés pour générer les coups. En jouant les coups de capture avant les coups normaux, vous augmentez les chances d'avoir un coup qui a un meilleur score au début de la recherche générant plus de coupes et réduisant le nombre de noeud à explorer.

Alpha-bêta par itération

La technique de recherche alpha-bêta par itération permet deux choses.

1. Un meilleur ordonnancement des coups;
2. Mieux contrôler la durée de recherche du moteur.

Nous savons qu'il faut un bon ordonnancement des coups pour que l'alpha-bêta soit efficace. De faire des recherches de plus en plus profonde est ce qui permet de bien ordonnancer les coups. Chaque itération utilise l'évaluation de la précédente pour réordonner ces coups ce qui permet à la recherche de toujours être optimal à chaque itération.

Si vous commencez la recherche du moteur avec un profondeur de 8 par exemple, vous n'avez aucun contrôle sur la durée de recherche. Et si vous interrompez la recherche à n'importe quel moment, le résultat sera hasardeux car vous ne saurez pas s'il y avait un coup meilleur plus loin dans la liste.

En y allant par itération, vous pouvez toujours utilisez le résultat de l'itération précédente qui est complète.

Au départ, pour tester votre algorithme vous allez probablement y avec une profondeur fixe et vous aurez déjà un moteur capable de bien évaluer le jeu, mais ça vous semblera long même pour une profondeur très courte.

Quiescence