15.3. Réalisation d'une procédure MiniMax

Soit un jeu hypothétique :

2 joueurs :

type Joueurs = (Premier,Second);

des mouvements :

type Mouvement = {type énuméré ou intervalle,suivant le jeu }; var Mvmt : Mouvement;

(Mvmt définit un mouvement possible respectant les règles du jeu).

des procédures de jeu :

procedure Jouer (Joueur: Joueurs; Mvmt: Mouvement); {modifie la situation avec Mvmt} procedure Defaire (Joueur: Joueurs; Mvmt: Mouvement); {revient à la situation d'avant Mvmt}

une procédure basée sur les règles du jeu et déterminant toutes les configurations possibles à partir d'une configuration donnée. Chaque configuration est définie par les mouvements qui la produisent à partir de la configuration de départ.

procedure Possible(Joueur:Joueurs; var MvtPossibles:Liste; var Val:Valeur);

avec MvtPossibles = liste des mouvements possibles (paramètre de sortie),
Val = valeur associée à la configuration courante par lafonction d'évaluation.

La structure de la liste des mouvements possibles dépend fortement du jeu qui est simulé (jeu à base de pièces sur un damier, jeu de dés, jeu de cartes, etc...). On peut toutefois imaginer que des procédures annexes permettent de gérer cette liste et d'accéder à ses éléments.

Par exemple :
procedure PremierElement( var MvtPossibles:Liste; var Mvmt:Mouvement);

permet d'extraire le premier mouvement de la liste MvtPossibles (Mvmt <- car(MvtPossibles) et MvtPossibles <- cdr(MvtPossibles) ).

procedure ElementSuivant( var MvtPossibles:Liste; var Mvmt:Mouvement);

permet d'obtenir l'élément suivant (Mvmt <- car(MvtPossibles) et MvtPossibles <- cdr(MvtPossibles)).

Function Taille (MvtPossibles:Liste) : integer;

détermine le nombre de mouvements contenu dans la liste. Function Vide (MvtPossibles:Liste) : boolean;

détermine si la liste contient encore des mouvements.

Une première ébauche d'une procédure de jeu selon la méthode Mi niMax peut être la suivante (en prenant beaucoup de liberté avec la syntaxe) :

     procedure MiniMax (Profondeur : integer;
                        Joueur : Joueurs;
     var Mvmt : Mouvement; var Val : Valeur);

     { cette procédure explore jusqu'à
       "Profondeur" niveaux l'arbre de jeu :
       elle donne comme résultat le mouvement
       Mvmt pour le joueur et la valeur Val
       associée à la situation actuelle. }

     begin
       Possible(Joueur,MvtPossibles,Val);
       if MvtPossibles ne contient qu'un mouv.
         then réponse = (Mvmt,Val)
       else begin
         for chaque mouvement possible do begin
           jouer ce mouvement;
           minimax (Profondeur-1,autre joueur,
                   ...);
           défaire ce mouvement
           end; { for }
         sélectionner la meilleure valeur pour
         le Joueur parmi les valeurs produites
         dans la boucle ci-dessus;
         réponse := (Mvmt,Val);
         end; { else }
     end; { MiniMax }

A partir de cette ébauche, et avec les procédures de base définies avant, on peut proposer une formulation plus rigoureuse pour la procédure minimax.

     procedure MiniMax (Profondeur : integer;
                        Joueur : Joueurs;
                        var Mvmt : Mouvement;
                        var Val : Valeur);
     { Pour l'algorithme qui suit, on suppose
       que la situation du jeu est maintenu
       globalement en dehors de la procédure }
   
     const Infini = MaxInt;

     var Adversaire : Joueurs;
         MAdv: Mouvement; { mouvement de
                            l'adversaire }
         VAdv: Valeur; {valeur associée au
                        mouvement de l'adversaire }
         MvtPossibles: Liste;
           { mouvements possibles pour Joueur }
         MEssai: Mouvement;
            { un mouvement possible à essayer }
   
     begin { MiniMax }
       Possible(Joueur,MvtPossibles,Val);
       if Taille(MvtPossibles) <= 0 then
         "forfait"
       else if (Taille(MvtPossibles) = 1) or
               (Profondeur = 0) then
         PremierElement (MvtPossibles,Mvmt)
       else begin
         if Joueur = Premier then begin
           Adversaire := Second;
           Val := -Infini; {la plus petite }
           end {valeur possible}
         else begin
           Adversaire := Premier;
           Val := Infini; {la plus grande }
           end; {valeur possible}

         PremierElement (MvtPossibles,MEssai);

         while not Vide(MvtPossibles) do begin
           Jouer(Joueur, MEssai);
           MiniMax(Profondeur-1, Adversaire,
                   MAdv, VAdv);
           Defaire(Joueur, MEssai);
         
           if (Joueur = Premier) and
              (VAdv > Val) then begin

       {max} Val := VAdv; Mvmt := MEssai;
              end

           else if (Joueur=Second) and
                    (VAdv < Val) then begin
       {min} Val := VAdv; Mvmt := MEssai;
              end;
           ElementSuivant(MvtPossibles, MEssai)
           end; { while }
         end; { if }
     end; { MiniMax }

15.3.1. Variante de la méthode MiniMax : l'élagage alpha-bêta

Si l'on applique la méthode du MiniMax, on se rend vite compte qu'il n'est pas toujours nécessaire de parcourir la totalité de l'arbre de jeu pour trouver le chemin optimal : on "coupe" des branches que l'on sait inutiles. Ainsi, soit l'arbre de jeu de la figure 15.14,

Au niveau 0 la racine prend la valeur maximale des descendants,
au niveau 1 chaque noeud prend la valeur minimale des descendants,
au niveau 2 chaque noeud prend la valeur maximale des descendants,
au niveau 3 chaque noeud prend la valeur minimale des descendants,
etc.

Si l'on propage, selon l'algorithme du MiniMax, les valeurs de la fonction d'évaluation associée à chaque feuille, on obtient l'arbre de décision de la fi gure 15.15.

Fig. 15.14. Arbre de jeu avec valeur des situations terminales.

Fig. 15.15. Evaluation des situations non-terminales.

Les deux sous-arbres de la figure 15.15 qui ont été entourés peuvent ne pas être évalués car :

après l'évaluation des deux branches de gauche qui ont amené les valeurs 7 et 5 aux noeuds de niveau 1 on sait que :
1. le passage au niveau 0 se fera par recherche du maximum,
2. le maximum courant est 7.

lors de la construction de la deuxième branche de droite le passage du niveau 2 au niveau 1 se fait par recherche du minimum. La valeur 3 est associée au descendant gauche du noeud de niveau 1; par conséquent, il est impossible que le noeud de niveau 1 ait une valeur supérieure à 3 (car, à ce niveau, on recherche le minimum). On peut donc "supprimer" la branche dans sa totalité, c'est-à-dire ne pas l'évaluer.

Il en va de même pour la première branche de droite.

C'est la méthode de l'élagage alpha-bêta. Les lettres grecques alpha et bêta sont souvent utilisées pour marquer les points d'élagage, alpha pour max et bêta pour min.

Table des matières.

Site Hosting: Bronco