Élagage alpha-bêta

En informatique, plus précisément en intelligence artificielle et en théorie des jeux, l’élagage alpha-bêta (abrégé élagage αβ) 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 à 2 joueurs, comme les échecs ou les dames. 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. Dit autrement, 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 à un nœud déjà évalué. Il importe de comprendre à ce stade qu'une fonction d'évaluation parfaite (comme au Marienbad) ne demanderait aucune exploration d'arbre et qu'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 ne soit 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( , -β, -α))) où les 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.