Les feuilles qu'alpha-bêta ne regarde pas

On note $(\alpha ,\beta )$ la fenêtre transmise.

• Racine max, fenêtre $(-\infty ,+\infty )$. Elle appelle le nœud min de gauche.
• Ce min appelle le max qui porte $3$ et $5$ : il évalue les deux, rend $5$. Le min pose alors $\beta =5$.
• Il appelle le max qui porte $6$ et $9$, avec la fenêtre $(-\infty ,5)$. Ce nœud évalue $6$, ce qui lui donne $\alpha =6\ge \beta =5$ : coupure. La feuille $9$ n'est jamais lue.
• Le min de gauche rend $\min (5,6)=5$. La racine pose $\alpha =5$.
• Elle appelle le min de droite avec $(5,+\infty )$. Celui-ci appelle le max portant $1$ et $2$, qui les évalue tous deux et rend $2$. Le min pose $\beta =2\le \alpha =5$ : coupure. Les feuilles $0$ et $-1$ ne sont jamais lues.

Bilan mesuré : minimax évalue les $8$ feuilles, alpha-bêta en évalue $5$ ($3,5,6,1,2$) et rend la même valeur $5$.

Pourquoi les trois coupures sont légitimes. La feuille $9$ est sous un max qui vaut déjà au moins $6$ ; or le min au-dessus a déjà $5$ en main, et ne prendra jamais une branche qui vaut $\ge 6$. Que la branche vaille $6$, $9$ ou $10^9$ ne change rien : elle est écartée par le min. Même chose à droite : le min vaut au plus $2$, et la racine s'est déjà assuré $5$ ; les deux dernières feuilles ne peuvent que faire baisser une valeur déjà écartée.

Ce que l'exercice montre du théorème. Alpha-bêta ne « devine » rien. Chaque coupure repose sur une preuve — un encadrement — que la branche coupée ne peut pas influencer la racine. C'est pourquoi la valeur est exacte, et c'est aussi pourquoi la coupure ne dispense pas de la valeur exacte des branches non coupées.