Probleme – Alpha-bêta rend la même valeur : la mesure, et la raison

1. L'expérience. On engendre des arbres aléatoires — un générateur à congruences linéaires, pour être reproductible d'une machine à l'autre —, on calcule la valeur par minimax puis par alpha-bêta appelé avec la fenêtre complète $(-\infty ,+\infty )$, et l'on compare. Sur $200$ arbres de profondeur $4$ et d'arité $4$ : $200$ valeurs identiques sur $200$. Et sur chacune des six configurations testées ci-dessous, $200$ sur $200$ également.

2. Les mesures. Feuilles évaluées, cumul sur $200$ arbres, valeurs entières tirées uniformément dans $[-100,100]$ :

Trois lectures. D'abord, la part explorée décroît quand la profondeur croît : $74\%$ à $d=2$, $32\%$ à $d=5$. Le gain n'est pas un facteur constant, il s'améliore avec $d$ — ce qui est la forme même d'un passage de $b^d$ à $b^{d/2}$.

Ensuite, l'ordre aléatoire reste loin de $b^{d/2}$ : à $d=4$, $b=4$, on mesure $22428$ contre $3200$ pour la borne optimale, soit sept fois plus. La borne $O(b^{d/2})$ est celle du meilleur ordre, et l'exercice 27.5 montre qu'on l'atteint exactement — $31$ feuilles par arbre — quand on trie parfaitement.

Enfin, le nombre exact dépend de la loi des feuilles : avec des valeurs entières tirées dans $\{0,1\}$, on descend entre $12\%$ et $18\%$ selon la graine (beaucoup d'égalités, donc beaucoup de coupures) ; avec des valeurs très étalées, la part se stabilise autour de $43\%$ à $44\%$. Une part explorée n'a de sens qu'avec son protocole : profondeur, arité, loi des feuilles, et ce que l'on compte — ici les feuilles évaluées, non le nombre total de nœuds visités, qui donne $49\%$ sur la même expérience.

3. La démonstration. On montre, par induction sur la hauteur, la propriété suivante, où $v$ est la valeur rendue par alphabeta p d alpha beta et $m$ la valeur minimax de $p$ :

$$\text{si }\alpha <m<\beta \text{ alors }v=m;\text{si }m\le \alpha \text{ alors }v\le \alpha ;\text{si }m\ge \beta \text{ alors }v\ge \beta .$$

Base. À profondeur $0$, $v=m=h(p)$, et les trois cas sont immédiats.

Hérédité, cas maximisant. Les fils sont explorés de gauche à droite, $\alpha$ ne fait que croître, et l'on maintient $v=\max$ des valeurs rendues. Par hypothèse d'induction, chaque fils rend sa valeur minimax exacte tant que celle-ci tombe dans la fenêtre courante, et rend sinon une borne du bon côté. Deux cas :

• si aucune coupure ne se produit, tous les fils ont été explorés, et ceux dont la valeur est $\le \alpha$ n'influencent pas le maximum : $v=m$ dès que $m>\alpha$ ;
• si une coupure se produit, c'est qu'un fils a rendu une valeur $\ge \beta$ ; alors $m\ge \beta$, et $v\ge \beta$ : on est dans le troisième cas, et la valeur rendue est une borne, non un résultat exact — mais l'appelant, un nœud min, l'écartera de toute façon.

Conclusion. À la racine on appelle avec $\alpha =-\infty$ et $\beta =+\infty$ : la fenêtre est complète, le premier cas s'applique, et $v=m$. C'est la fenêtre initiale complète qui garantit l'exactitude à la racine, et non l'algorithme seul — un appel racine avec une fenêtre étroite ne rendrait qu'un encadrement.

4. Le test $\beta \le \alpha$. Remplacé par $\beta <\alpha$, l'algorithme reste correct mais coupe moins : il continue d'explorer les branches où $\beta =\alpha$, qui ne peuvent pourtant rien apporter — un min qui vaut au plus $\alpha$ ne sera pas préféré à ce que le max s'est déjà assuré. On perd donc des coupures sans rien gagner. Le raisonnement ne casse nulle part, et c'est justement ce qu'il fallait vérifier : le $\le$ n'est pas une approximation, c'est l'inégalité juste, celle qui coupe le plus tôt sans jamais couper à tort.

Le renversement, en revanche, serait fatal : couper dès $\beta \le \alpha +1$ sur des valeurs entières supprimerait des branches dont la valeur est exactement $\alpha +1$ et qui pourraient être choisies. C'est l'idée des « fenêtres d'aspiration », qui acceptent délibérément ce risque et le corrigent par une nouvelle recherche quand la valeur sort de la fenêtre.