Le meilleur et le pire ordre

Les trois mesures, sur les mêmes $200$ arbres ($51200$ feuilles en tout) :

Le chiffre du meilleur ordre est exactement celui de la théorie. $6200/200=31$ feuilles par arbre, et la borne de Knuth et Moore donne

$$b^{\lceil d/2\rceil }+b^{\lfloor d/2\rfloor }-1=4^2+4^2-1=31.$$

Pas « environ $31$ » : $31$, sur chacun des $200$ arbres. C'est le $O(b^{d/2})$ du cours, atteint.

Le pire ordre n'élague presque rien : $96,2\%$. Alpha-bêta n'est donc pas une amélioration inconditionnelle — c'est un algorithme dont le gain dépend entièrement de la qualité de l'ordre. Dans le pire cas il coûte autant que minimax, à quelques coupures près.

Et l'ordre quelconque tombe au milieu, à $44\%$ : sans effort, on gagne un facteur $2$ ; avec un bon ordre, un facteur $8$. C'est ce facteur qui se transforme en profondeur : à budget de feuilles égal, explorer $b^{d/2}$ au lieu de $b^d$ permet de doubler $d$. Aux échecs, deux demi-coups de plus séparent deux niveaux de jeu.

La conséquence pratique, et elle est contre-intuitive : il est rentable de dépenser du temps à trier les coups avant de descendre, alors même que ce tri ne calcule rien d'utile au résultat. On trie par une estimation grossière (prendre une pièce d'abord, jouer au centre d'abord), et l'on utilise le résultat de la recherche précédente à profondeur $d-1$ pour ordonner celle à profondeur $d$ — c'est l'approfondissement itératif.