Un article de Wikipédia, l'encyclopédie libre.

L'élagage alpha-beta est une technique permettant de réduire le nombre de nœuds évalués par l'algorithme MinMax.

L'algorithme MinMax effectue en effet une exploration complète de l'arbre de recherche jusqu'à un niveau donné, alors qu'une exploration partielle de l'arbre est généralement suffisante : lors de l'exploration, il n'est pas nécessaire d'examiner les sous-arbres qui conduisent à des configurations dont la valeur ne contribuera sûrement pas au calcul du gain à la racine de l'arbre. L’élagage αβ nous permet de réaliser ceci.

Plus simplement, l'élagage αβ évite d'évaluer des nœuds de l'arbre de recherche dont on est sûr que leur qualité sera inférieure à un nœud déjà évalué.

L'élagage αβ permet d'optimiser grandement l'algorithme MinMax sans en modifier le résultat.

Il est très utilisé dans le cas des jeux à 2 joueurs comme par exemple le jeu de Go ou les échecs.

[modifier] Principe

On prend α et β appartenant au domaine d’arrivée de la fonction d’évaluation tel que α < β. On définit la fonction AlphaBeta ainsi :

• AlphaBeta(P, α, β) = g(P) si P est une feuille de l'arbre et g la fonction d'évaluation du nœud
• AlphaBeta(P, α, β) = min(β, max(-AlphaBeta(O_i, -β, -α))) où les O_i sont les fils du nœud P

On appelle fenêtre αβ le couple [α, β] où α et β sont les deux paramètres d’appel de la fonction. Les nœuds élagués sont ceux qui seraient appelés avec une fenêtre tel que α ≥ β. Il existe 3 types de nœuds ne pouvant donc pas être élagués :

• Nœud de type 1 : fenêtre d’appel : [-∞, +∞]
• Nœud de type 2 : fenêtre d’appel : [-∞, b] avec b ≠ +∞
• Nœud de type 3 : fenêtre d’appel : [a, +∞] avec a ≠ -∞

Le schéma ci-dessus présente les deux types de coupures possibles. Les nœuds Min sont représentés par un rond bleu et les nœuds Max par un carré gris. Rappel : les nœuds Min prennent la valeur minimum de leurs fils (et respectivement maximum pour les nœuds Max).

Coupure Alpha : le premier fils du nœud Min V vaut 4 donc V vaudra au plus 4. Le nœud Max U prendra donc la valeur 5 (maximum entre 5 et une valeur inférieure ou égale à 4).

Coupure Beta : le premier fils du nœud Max V vaut 4 donc V vaudra au minimum 4. Le nœud Min U prendra donc la valeur 3 (minimum entre 3 et une valeur supérieure ou égale à 4).

[modifier] Pseudocode

Ci-dessous une implémentation en pseudocode de l'algorithme alpha-beta : alpha est initialisé à -INFINI et beta à +INFINI

fonction ALPHABETA(P, alpha, beta) /* alpha est toujours inférieur à beta */
   si P est une feuille alors
       retourner la valeur de P
   sinon
       si P est un nœud Min alors
           pour tout fils Pi de P faire
               Val = ALPHABETA(Pi, alpha, beta)
               beta = Min(beta, Val)
               si alpha >= beta alors  /* coupure alpha */
                   retourner beta
           finpour
           retourner beta
       sinon
           pour tout fils Pi de P faire
               Val = ALPHABETA(Pi, alpha, beta)
               alpha = Max(alpha, Val)
               si alpha >= beta alors /* coupure beta */
                   retourner alpha
           finpour
           retourner alpha
       finsi
   finsi
fin

De la même manière que l'algorithme MinMax peut être remplacé par NegaMax, on simplifie Alpha-Beta. Cela donne l’algorithme suivant :

fonction ALPHABETA(P, A, B) /* A < B */
   si P est une feuille alors
       retourner la valeur de P
   sinon
       Meilleur = –INFINI
       pour tout fils Pi de P faire
           Val = -ALPHABETA(Pi,-B,-A)
           si Val > Meilleur alors
               Meilleur = Valeur
               si Meilleur > A alors
                   A = Meilleur
                   si A > B alors
                       retourner Meilleur
       finpour 
       retourner Meilleur

[modifier] Exemple

Nous allons illustrer l’algorithme sur l’arbre ci-dessous déjà étiqueté avec les valeurs d’un negamax.

Le résultat obtenu est le schéma ci-dessous. Plusieurs coupures ont pu être réalisées. Par exemple, après l’évaluation du nœud B, on sait que la valeur negamax du nœud B sera supérieure à 0. Or on sait que le nœud A choisira un fils dont la valeur negamax est inférieure à -1. Il est donc inutile d’analyser les autres fils de B car le meilleur fils de A ne pourra en aucun cas être B. Attention nous avons relevé une erreur dans l'arbre : le noeud fils droit de la racine n'a pas un Negamax = 0, mais = 4.

Pour les deux autres coupures, le fonctionnement est identique. Sur cet arbre, l’algorithme αβ nous a permis d’économiser le traitement de 9 nœuds. L’arbre contient 33 nœuds. Nous avons donc élagué quasiment un tiers de l’arbre. L’avantage d’αβ est flagrant.