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.