Pour les articles homonymes, voir élagage et élagage synaptique.

L’élagage alpha-bêta (abrégé élagage αβ), en informatique, plus précisément en intelligence artificielle et en théorie des jeux, est une technique permettant de réduire le nombre de nœuds évalués par l'algorithme minimax.

Il est utilisé dans des programmes informatiques qui jouent à des jeux à deux joueurs, tels que le tic-tac-toe, les échecs ou les dames^{[réf. souhaitée]}.

L'algorithme minimax effectue une exploration complète de l'arbre de recherche jusqu'à un niveau donné. L'élagage alpha-beta permet d'optimiser grandement l'algorithme minimax sans en modifier le résultat. Pour cela, il ne réalise qu'une exploration partielle de l'arbre. Lors de l'exploration, il n'est pas nécessaire d'examiner les sous-arbres qui conduisent à des configurations dont la valeur ne contribuera pas au calcul du gain à la racine de l'arbre. Autrement dit, l'élagage αβ n'évalue pas des nœuds dont on peut penser, si la fonction d'évaluation est à peu près correcte, que leur qualité sera inférieure à celle d'un nœud déjà évalué.

Une fonction d'évaluation parfaite (comme au Marienbad) ne demanderait aucune exploration d'arbre, et une exploration d'arbre exhaustive (comme au morpion) ne demanderait aucune fonction d'évaluation. Il s'agit donc de combiner au mieux l'heuristique (fonction d'évaluation, plus ou moins arbitraire, mais de portée globale) et la logique dure (exploration de l'arbre des possibilités), qui n'est possible que sur un domaine qu'on a au préalable restreint.

On va combiner les deux pour accélérer l'exploration sous l'hypothèse que la fonction d'évaluation n'est pas trop mauvaise. Prenons α 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( ${\displaystyle O_{i}}$ , -β, -α))) où les ${\displaystyle O_{i}}$ sont les enfants 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 : (-∞, β) avec β ≠ +∞
• Nœud de type 3 : fenêtre d’appel : (α, +∞) avec α ≠ -∞

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 enfants (et respectivement maximum pour les nœuds Max).

Coupure Alpha : le premier enfant 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 Bêta : le premier enfant 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).

Ci-dessous le pseudocode de l'algorithme alpha-bêta :

α est initialisé à -∞. β est initialisé à +∞.

fonction alphabeta(nœud, α, β) /* α est toujours inférieur à β */
   si nœud est une feuille alors
       retourner la valeur de nœud
   sinon 
            si nœud est de type Min alors
                       v = +∞
                       pour tout fils de nœud faire
                           v = min(v, alphabeta(fils, α, β))                
                           si α ≥ v alors  /* coupure alpha */
                             retourner v
                           β = min(β, v)           
             sinon
                       v = -∞
                       pour tout fils de nœud faire
                           v = max(v, alphabeta(fils, α, β))                
                           si v ≥ β alors /* coupure beta */
                               retourner v
                           α = max(α, v)
    retourner v

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

fonction alphabeta(nœud, α, β) /* α < β */
   si nœud est une feuille alors
       retourner la valeur de nœud
   sinon
       v = -∞
       pour tout fils de nœud faire
           v = max(v, -alphabeta(fils, -β, -α))     
           si v ≥ β alors
               retourner v
           α = max(α, v)
       retourner v

L’algorithme est illustré sur l’arbre ci-dessous déjà étiqueté avec les valeurs d’un minimax. Le résultat obtenu est le schéma ci-dessous.

Plusieurs coupures ont pu être réalisées. De gauche à droite :

1. Le nœud MIN vient de mettre à jour sa valeur courante à 4. Celle-ci, qui ne peut que baisser, est déjà inférieure à α=5, la valeur actuelle du nœud MAX précédent. Celui-ci cherchant la valeur la plus grande possible, ne la choisira donc de toute façon pas.
2. Le nœud MIN vient de mettre à jour sa valeur courante à 6. Celle-ci, qui ne peut que baisser, est déjà égale à α=6, la valeur actuelle du nœud MAX précédent. Celui-ci cherchant une valeur supérieure, il ne mettra de toute façon pas à jour sa valeur que ce nœud vaille 6 ou moins.
3. Le nœud MIN vient de mettre à jour sa valeur courante à 5. Celle-ci, qui ne peut que baisser, est déjà inférieure à α=6, la valeur actuelle du nœud MAX précédent. Celui-ci cherchant la valeur la plus grande possible, ne la choisira donc de toute façon pas.

La plupart des améliorations d'alpha-bêta sont destinées à augmenter le nombre de coupes pour augmenter les nœuds qui ne sont pas examinés. Cela s'obtient grâce à des heuristiques comme l'exploration en premier des coups qui ont permis d'effectuer des coupes dans des nœuds du même niveau (killer move) ; d'autres améliorations permettent de rétrécir l'intervalle de départ entre les valeurs alpha et bêta utilisées dans le nœud racine et débouchent sur des améliorations comme Negascout ou MTD-F.

On peut trier les positions à tester à chaque profondeur testée, pour améliorer le temps ou la profondeur totale de calcul à chaque demi-coup, selon la limitation en profondeur totale ou en temps de calcul à chaque demi-coup.

L'élagage alpha-bêta est largement utilisé par les programmes qui jouent aux jeux de réflexion.

• A. Aho, J. Hopcroft, J. Ullman (trad. de l'anglais), Structures de données et algorithmes, Paris, InterEditions, 1987, 450 p. (ISBN 2-7296-0194-5), « Conceptions et stratégies algorithmiques »

• Séparation et évaluation

• Tristan Cazenave, « Des optimisations de l'Alpha-Beta », Actes du colloque de Berder,‎ 2000 (lire en ligne [PDF])

• Portail de l'informatique théorique