9. Élagage Alpha-Bêta
Alpha-Bêta conserve le résultat de Minimax tout en arrêtant l’exploration d’une branche lorsque celle-ci ne peut plus modifier une décision déjà garantie.
9.1 Bornes
α: meilleure valeur que MAX peut déjà garantir le long du chemin; elle ne diminue jamais.β: meilleure limite que MIN peut déjà imposer; elle n’augmente jamais.
9.2 Règles du cours
- R1 : arrêter sous un nœud MAX si sa valeur
αest supérieure ou égale auβd’un ancêtre MIN. - R2 : arrêter sous un nœud MIN si sa valeur
βest inférieure ou égale auαd’un ancêtre MAX.
La forme compacte est une coupure dès que α ≥ β.
9.3 Intuition
Si MIN dispose déjà d’une branche garantissant une valeur au plus égale à β, il ne choisira pas une autre branche où MAX garantit déjà α ≥ β. Symétriquement, MAX ignorera une branche où MIN peut imposer β ≤ α, puisqu’un autre choix garantit déjà au moins α.
9.4 Propriétés
- Le choix et la valeur finale sont les mêmes que pour Minimax complet.
- L’ordre d’exploration détermine combien de branches peuvent être coupées.
- Dans le pire cas, aucune coupure n’est possible.
- Dans l’exemple du cours, trois branches sont élaguées et la racine reste
3, avec le coupB.
La page officielle avertit que la diapositive 22 a été corrigée dans le PDF, mais pas dans la vidéo. Le PDF doit donc être privilégié en cas d’écart visuel; les explications orales restent annoncées comme valides.
R MAX→A,B MIN→A1,A2,B1,B2 MAX→feuilles. A1=(3,5),A2=(6,9),B1=(2,4),B2=(7,8). Minimax exact : A1=5,A2=9,A=5; B1=4,B2=8,B=4; R=5. À gauche d’abord, A2 coupe 9 après 6≥β=5; B coupe B2 après 4≤α=5. Feuilles visitées 3,5,6,2,4. La valeur exacte d’A2=9 n’est pas connue du parcours élagué, seulement une borne ≥6.
Source : Schéma original du portail, données autonomes; consolidation du 16 octobre 2026. · Maître S04 : 9.1 Bornes