Programmation de jeu 2D : Le morpion, Septième partie

L'amélioration faite par l'algorithme Alpha-Beta consiste à limiter le nombre de configurations visitées lors du calcul du prochain coup. En effet, il n'est pas toujours nécessaire d'évaluer toutes les configurations.

Pour expliquer comment fonctionne l'algorithme Alpha-Beta, nous allons le faire en présentant rapidement les changements dans les fonctions calcIA, calcMin et calcMax et, ensuite, en montrant le déroulement de l'algorithme sur un exemple. Je pense que ce sera plus clair et plus facile à assimiler.

Pour montrer les modifications de l'algorithme Alpha-Beta, nous allons remontrer la version de calcMax :

Fonction calcMax(Jeu *j, int prof)
{
Soit max = MINIMUM;
 
Si la partie est terminée ou si la profondeur == 0 alors
    retourner eval(n);
Sinon 
    Pour chaque coup possible
        Faire
            Jouer le coup
            tmp = calcMin(j, prof-1);
            Si tmp > max alors
                max = tmp;
            FinSi
            Annuler le coup
        FinPour
    Retourner max;
}

Voici la version pour l'Alpha-Beta :

Fonction calcMax (Jeu *j, int prof, int alpha, int beta)
{
Soit max = MINIMUM;
 
Si la partie est terminée ou si la profondeur==0 alors
    retourner eval(n);
Sinon
    Pour chaque coup possible
        Faire
            Jouer le coup
            alpha = max (alpha, calcIA(j, prof-1, alpha, beta))
            Si beta <= alpha alors
                retourner alpha
            Fin Si
            Annuler le coup
        Fin Pour
   retourner alpha
Fin Si

Quelle est donc la grande différence ? C'est le test dans la boucle qui fait la grande différence. En effet, la partie :

            Si beta <= alpha alors
                retourner alpha
            Fin Si

Ceci permet donc de ne pas étudier toutes les configurations possibles. Pour mieux comprendre les implications de ces ajouts, la prochaine partie montre un exemple concret de parcours d'arbre. Il devrait vous illustrer comment on peut savoir s'il est nécessaire ou non d'étudier un sous-arbre.

Pourquoi est-ce que ceci fait une si grande différence? Je m'excuse par avance de la longueur de cette sous-section. L'algorithme alpha-beta n'est pas difficile à mettre en place et pas difficile à comprendre lorsqu'on a un exemple. Cet exemple montre le déroulement de l'algorithme en 8 étapes. Voici l'arbre des configurations :

Comme pour l'algorithme du Min-Max, on commence par parcourir l'arbre. Rappelons que la racine de l'arbre est un nœud Max, ses fils sont des nœuds Min et ses petits fils sont des nœuds Max… Regardons l'image suivante :

Lors de la première descente, on regarde les trois fils 5, 1 et 9. Étant donné que leur père est un nœud Max, sa valeur devient donc 9. Cette valeur devient donc la valeur intermédiaire de son propre père, c'est ce que montre l'image suivante :

Ensuite, l'algorithme recommence la descente vers les nœuds 2, 12 et 9. Lorsque le nœud 2 est évalué, cette valeur intermédiaire remonte à son père. On le voit ici :

Or lorsqu'on regarde le prochain nœud, la valeur 12 est rencontrée. Étant donné que son père est un nœud Max, il prend la valeur 12 (puisque 12>2).

C'est à ce moment que l'algorithme Alpha-Beta réagit différemment que l'algorithme Min-Max. En effet, est-il nécessaire de regarder le troisième fils ?

Le petit-fils 12 ne peut que monter. En effet, puisque c'est un nœud max, l'évaluation ne peut que monter. Mais son père est un nœud min, donc pour le moment, il choisira le nœud 9. Donc peu importe l'évolution de la valeur du petit-fils droit, le fils gauche choisira de toute façon le sous-fils gauche. Il est donc inutile de regarder le troisième nœud.

On a donc terminé l'évaluation du sous-arbre gauche. La racine récupère donc la valeur temporaire 9, comme le montre la prochaine image :

On commence donc l'évaluation du sous-arbre droit. Le premier sous-fils prend la valeur temporaire 5.

Donc la valeur remonte au fils droit qui prend cette valeur temporaire, comme le montre cette dernière image :

Maintenant est-ce la peine de continuer les évaluations ? La réponse est bien sûr non ! L'évaluation du fils droit ne peut que descendre (puisque c'est un nœud Min). Donc la racine aura un choix entre l'évaluation 9 du fils gauche et le fils droit qui aura une évaluation forcément plus petite que 5. Puisque la racine est un nœud Max, il prendra donc la valeur 9. Il est donc inutile de regarder les autres nœuds.

Donc finalement, en connaissant quelques valeurs clés, il est possible de savoir si l'évaluation d'un nœud ou même d'un sous-arbre est nécessaire ou pas.

La beauté de l'algorithme Alpha-Beta est sa simplicité pour permettre un tel mécanisme. La suite de cet article va donc montrer ce qui change dans le code.

Puisque nous avons présenté le code de la fonction calcMax, nous allons montrer le code de la fonction calcMin. Je ne vais pas mettre tout le code puisque le début du code est exactement le même que l'algorithme Min-Max.

for(i=0;i<3; i++)
  for(j=0;j<3;j++)
    {
    if(jeu->estVide(i,j))
      {
      jeu->joue(i,j);
 
      tmp = calcMin(jeu, prof-1,alpha,beta);
 
      jeu->annuleCoup(i,j);
 
      //Mis a jour de la valeur de alpha
      if(alpha<tmp)
        {
        alpha = tmp;
        }
 
      if(beta <= alpha)
        {
        return alpha;
        }
      }
    }
 
return alpha;

Si vous faites une comparaison avec la version de l'algorithme Min-Max, on ne fait qu'ajouter deux tests. La mise à jour de la variable alpha se fait comme la variable max de la version Min-Max. La grande différence est l'ajout du deuxième test qui permet de sortir du parcours des configurations. Si beta devient inférieur à la variable alpha, on sait qu'on peut sortir de la fonction.

La seule nouveauté de la fonction calcIA de la version Alpha-Beta se retrouve dans le corps du nid de boucles. Voici les différences :

//On appelle la fonction calcMin pour lancer l'IA
tmp = calcMin(jeu, prof-1,alpha,beta);
 
//Si ce score est plus grand
if(alpha<tmp)
  {
  //On le choisit
  alpha = tmp;
  maxi = i;
  maxj = j;
  }

Donc finalement, la seule différence est de passer la valeur de la variable alpha à la fonction calcMin. Ceci permet de réduire le nombre de configurations étudiées.

Voilà, c'est tout! Je me doute que cela semble un peu magique. Il suffit de relire la deuxième section pour comprendre le principe et revoir cette section pour bien regarder comment l'ajout de ces quelques instructions permet de limiter le nombre de configurations.

Enfin, je pensais que ce serait intéressant de regarder le nombre de configurations étudiées lors du premier coup (l'IA jouera donc le premier coup) :

Je pense que le tableau montre bien l'intérêt de l'algorithme Alpha-Beta.

À cause de la spécificité de l'algorithme Alpha-Beta, nous ne pouvons plus utiliser l'amélioration de l'algorithme Min-Max pour avoir un jeu plus aléatoire. Rappelons cette modification :

if((tmp>max)||((tmp==max)&&(Rand::randi(2))))

Ceci permet de choisir un coup parmi d'autres de la même valeur. Le problème dans l'algorithme Alpha-Beta est que ceci n'est plus possible puisque le retour des fonctions calcMin et calcMax n'est plus vraiment la valeur de l'évaluation du fils. Ce n'est donc pas forcément l'évaluation du nœud, mais le retour de la valeur alpha ou beta.

La seule solution pour permettre de remettre cette possibilité d'aléatoire est d'enlever cette gestion de la valeur alpha et donc de perdre un peu l'efficacité de l'algorithme.

Voici donc le nouveau code de la fonction calcIA :

//Si ce score est plus grand
if(max<tmp)
  {
  //On le choisit
  max = tmp;
  maxi = i;
  maxj = j;
  }

Donc finalement le code ressemble plus à la version Min-Max (honnêtement, c'est le code du Min-Max, à part le passage des variables alpha et beta à la fonction calcMax). Nous pouvons montrer le tableau qui compare les deux versions :

Ce tableau confirme donc qu'on perd un peu de performances avec cette nouvelle méthode, mais on gagne en aléatoire.