Une technique d'élagage d'arbre de recherche appliquée aux recherches adversariales de type minimax qui maintient deux bornes (alpha et bêta) pour éliminer les branches qui ne peuvent pas influer sur la décision racine, réduisant ainsi le nombre de nœuds évalués sans modifier le résultat minimax optimal si elle est correctement appliquée.

Principe

Maintenir et propager des bornes inférieure (alpha) et supérieure (bêta) des valeurs réalisables le long de l'arbre ; élaguer tout sous-arbre dont la borne ne peut améliorer l'option courante aux nœuds ancêtres.

Démonstration

Dans un arbre de jeu à deux joueurs, lors de l'exploration d'un nœud pour le joueur maximisant avec une valeur meilleure actuelle alpha, si un sous-arbre enfant de l'adversaire minimisant donne une valeur ≤ alpha, ce sous-arbre peut être ignoré car le maximisant l'éviterait ; cela peut supprimer de larges portions de l'arbre en pratique.

Mauvaise application

Élagage fondé sur des bornes incorrectes ou mal initialisées, application d'alpha–bêta à des problèmes non à somme nulle ou non minimax sans adaptation, ou supposer qu'il donne toujours des accélérations linéaires quelle que soit l'ordonnancement des coups.

Conséquence

Employée correctement, elle réduit le temps et la mémoire de recherche — souvent de façon spectaculaire avec un bon ordonnancement des coups — tout en préservant la décision minimax exacte ; cependant, la complexité pire cas reste exponentielle si les opportunités d'élagage sont limitées.

Inversion

Développer tous les nœuds sans élagage (minimax complet) inverse la technique, garantissant l'évaluation de toutes les feuilles et produisant la même décision mais avec un coût de calcul maximal et sans raccourcis basés sur des bornes.

Limite

S'applique aux problèmes déterministes, d'information parfaite et alternance de tours ; exclut les nœuds stochastiques, les jeux partiellement observables et les situations nécessitant des critères non minimax sauf adaptation (par exemple expectiminimax ou évaluations heuristiques).

Tension sémantique

Souvent confondu avec les heuristiques d'ordonnancement des coups et d'autres méthodes d'élagage (p. ex. null-move) ; l'alpha–bêta est spécifiquement la règle d'élagage par propagation de bornes dans minimax, pas une stratégie d'ordonnancement, bien que l'ordonnancement influence fortement son efficacité.

Synthèse

L'élagage alpha–bêta utilise de façon rigoureuse des bornes alpha et bêta propagées pour omettre en toute sécurité des parties d'un arbre minimax : une règle d'élagage exacte qui sacrifie l'exploration redondante tout en conservant les décisions optimales, ses gains pratiques dépendant de la structure du problème et de l'ordonnancement.