next up previous contents index
Next: Diviser pour régner Up: Algorithmes Previous: Graphes de jeu et

   
L'algorithme $\alpha \beta $

 

L'algorithme minimax effectue une exploration complète de l'arbre de recherche jusqu'à un niveau donné, alors qu'une exploration partielle de l'arbre pourrait suffire. Il suffit en effet, dans l'exploration en profondeur d'abord et de gauche à droite, d'éviter d'examiner des sous-arbres qui conduiront à des configurations dont la valeur ne contribuera sûrement pas au calcul du gain à la racine de l'arbre.

Dans les exemples de la figure 2.28 certains n\oeuds ont une valeur définitive alors que les autres (étiquetés avec un nom de variable) n'en ont pas encore reçu. D'après la définition de la fonction minimax() la valeur de la configuration racine de l'arbre (a) est obtenue par

\begin{displaymath}u=\mathrm{max}\{5,v\} \mbox{, où } v = \mathrm{min}\{4,\dots\}.
\end{displaymath}

Il est clair que u=5 indépendamment de la valeur de v. Il en résulte que l'exploration des branches filles du n\oeud étiqueté par v peut être omise : on réalise ainsi une coupure superficielle. En appliquant récursivement le même raisonnement à l'arbre (b), on en déduit que la valeur de u peut être obtenue sans connaître la valeur finale de y. De même que précédemment, l'exploration des branches filles du n\oeud étiqueté par y n'est pas nécessaire : on parle alors de coupure profonde.


 \begin{figurette}% latex2html id marker 5785
\begin{center}
\leavevmode
\fbox{...
...aption{Coupure superficielle (a) et profonde (b).}
\end{center} \end{figurette}

Plus généralement, lorsque dans le parcours de l'arbre minimax il y a modification de la valeur courante d'un n\oeud, si cette valeur franchit un certain seuil, il devient inutile d'explorer la descendance encore inexplorée de ce n\oeud. On distingue deux seuils, appelés $\alpha$ (pour les n\oeuds Min) et $\beta$ (pour les n\oeuds Max) :

L'algorithme $\alpha \beta $ peut être décrit informellement par la fonction suivante, qui maintient ces deux seuils pendant le parcours de l'arbre. Une invocation de alphabeta(s, $-\infty$, $+\infty$) détermine une évaluation du jeu issu de la configuration s.

static int alphabeta (Configuration s, int \(\alpha\), int \(\beta\)) {
if (s.estFeuille()) return s.h();
Iterator i = s.succs();
switch(s.type()) {
case Configuration.MAX : {
int m =
\(\alpha\);
while(i.hasNext()) {
Configuration s1 = (Configuration)i.next();
int t = alphabeta(s1, m,
\(\beta\));
if (t > m) m = t;
if (m >=
\(\beta\)) return m;
}
return m;
}
case Configuration.MIN : {
int m =
\(\beta\);
while(i.hasNext()) {
Configuration s1 = (Configuration)i.next();
int t = alphabeta(s1,
\(\alpha\), m);
if (t < m) m = t;
if (m <=
\(\alpha\)) return m;
}
return m;
}
}
}

Contrairement aux fonctions p et minimax() (§ 2.24), le calcul des valeurs de alphabeta() se fait de façon à la fois ascendante et descendante. Chaque noeud de l'arbre se trouve affecté de trois attributs : la valeur m de la configuration et les seuils $\alpha$ et $\beta$. L'attribut m est synthétisé, c'est-à-dire calculé de façon ascendante à partir des successeurs s' de s. Par contre, les seuils sont des attributs hérités , c'est-à-dire calculés de façon descendante, à partir des parents : par exemple, si s est un noeud de maximisation avec deux successeurs, soit $s\to s_1, s_2$, alors le seuil $\alpha$ de s2 est la valeur m de s qui a été calculée à partir de s1. L'information a donc circulé de s1 à s, puis de s à s2.

La construction d'arbres comportant des attributs et l'évaluation de ces attributs sont des techniques importantes utilisées, non seulement dans les arbres de jeu, mais aussi dans la compilation des programmes.


next up previous contents index
Next: Diviser pour régner Up: Algorithmes Previous: Graphes de jeu et
R. Lalement
2000-10-23