3 La visite alpha-beta
L'algorithme alpha-beta est une optimisation du MiniMax, qui «coupe»
des sousarbres dès que leur valeur devient inintéressante aux fins du
calcul de la valeur MiniMax du jeu.
On s'intéressera donc, sur chaque
noeud, en plus de la valeur, à deux autres quantités, nommées alpha
et beta, qui seront utilisées pour calculer la valeur du noeud.
-
alpha d'un noeud
- est une approximation par le bas de la vraie
valeur du noeud. Elle est égale à la valeur sur les feuilles, et est
initialisée à -infini ailleurs. Ensuite, sur les noeuds joueur elle
est maintenue égale à la plus grande valeur obtenue sur les fils visités
jusque là, et elle est égale à la valeur alpha de son prédécesseur sur
les noeuds opposant.
- beta d'un noeud
- est une approximation par le haut de la vraie
valeur du noeud. Elle est égale à la valeur sur les feuilles, et est
initialisée à +infini ailleurs. Ensuite, sur les noeuds opposant
elle est maintenue égale à la plus petite valeur obtenue sur les fils
visités jusque là, et elle est égale à la valeur beta de son
prédécesseur sur les noeuds joueur.
L'algorithme ALPHA-BETA peut être décrit par le pseudo-code suivant :
fonnction ALPHA-BETA(P, A, B) /* ici A est toujours inférieur à B */
si P est une feuille alors
retourner la valeur de P
sinon
initialiser Alpha de P à -infini et Beta de P à +infini
si P est un noeud Min alors
pour tout fils Pi de P faire
Val = ALPHA-BETA(Pi, A, Min(B,Beta de P))
Beta de P = Min(Beta de P, Val)
Si A >= Beta de P /*ceci est la coupure alpha */
alors retourner Beta de P
finfaire
retourner Beta de P
sinon
pour tout fils Pi de P faire
Val = ALPHA-BETA(Pi, Max(A,Alpha de P), B)
Alpha de P = Max(Alpha de P, Val)
Si Alpha de P >= B /*ceci est la coupure beta */
alors retourner Alpha de P
finfaire
retourner Alpha de P
On sait que la véritable valeur MiniMax v d'un noeud est encadrée par
alpha et beta (i.e. alpha <= v <= beta), et si on appelle
la fonction ALPHA-BETA avec les valeurs (P,-infini,+infini) on obtient
précisément MiniMax(P). ALPHA-BETA permets assez souvent de doubler la
profondeur d'exploration d'un arbre à parité de ressources, par rapport à
MiniMax.