Alpha-beta pruning
Publié le 2025-12-22 20:25
Si minimax explore toutes les branches, il devient vite inutilisable. Alpha-beta pruning est une idée simple mais extrêmement puissante : pendant la recherche, on maintient des bornes qui représentent ce qu’on sait déjà être atteignable. Et dès qu’une branche ne peut plus dépasser ce qu’on a déjà, on peut l’abandonner immédiatement.
Exemple avec l'excellent vidéo Algorithms Explained - minimax and alpha-beta pruning https://www.youtube.com/watch?v=l-hh51ncgDI
Ici le nœud vaut >= 5 car les blancs vont choisir le max(5, ?), ils veulent l'évaluation qui tend le plus vers l'infini, pour rappel +infini, les blancs ont une meilleure position, -infini, les noirs ont une meilleure position.
Mais au dessus, les noirs vont choisir min(3, >=5) donc ils vont forcément choisir 3, donc la feuille "?" n'a pas besoin d'être évaluée.
Idem ici, les noirs vont choisir min(-4, ?) donc ce nœud vaudra <= -4, et les blanc vont choisir le max(3, <= -4) donc 3.
Voici une version avec le code en python et les valeurs alpha et beta
Intuitivement, alpha-beta repose sur un raisonnement : “si j’ai déjà trouvé une option qui me donne au moins X, pourquoi continuer à explorer une branche qui, même dans le meilleur des cas, ne pourra jamais dépasser X ?” Le moteur ne perd rien en précision à profondeur égale, mais il économise une quantité énorme de calcul.
Ce qui surprend souvent, c’est que l’efficacité d’alpha-beta dépend énormément de l’ordre dans lequel on examine les coups. Si je commence par tester de bons coups, je resserre très vite les bornes, donc je coupe tôt. Si je commence par des coups faibles, je mets trop de temps à trouver des bons scores, et je coupe moins.
C’est pour ça que les moteurs appliquent du move ordering : souvent les captures et promotions d’abord, parfois les échecs, parfois des heuristiques plus évoluées. Et c’est aussi pour ça que l’iterative deepening est précieux : le meilleur coup trouvé à profondeur 2 est souvent un bon candidat à tester en premier à profondeur 3, ce qui aide alpha-beta à élague encore davantage.
Enfin, il y a un problème classique quand on coupe à profondeur fixe : l’effet d’horizon. Si une tactique importante commence juste après la limite de profondeur, une position peut sembler “calme” alors qu’elle est en réalité instable. C’est la raison d’être de la quiescence search : prolonger la recherche uniquement sur les coups tactiques, afin de ne pas évaluer une position “au mauvais moment”.