Math
Arbre de jeu et alpha-bêta
Un arbre de jeu où chaque bloc a la hauteur de sa valeur : un nœud MAX aussi haut que son plus haut enfant, un nœud MIN aussi bas que son plus bas. Le minimax lit chaque feuille ; l'alpha-bêta saute ce qui ne peut pas changer la réponse, et combien il saute dépend de l'ordre des coups.
Ce qui se passe
Chaque bloc a la hauteur de sa valeur, donc la règle se voit avant d'être nommée : un nœud MAX est aussi haut que son plus haut enfant, un nœud MIN aussi bas que son plus bas, et la racine est la valeur du jeu. Le minimax lit les b^d feuilles. L'alpha-bêta les lit dans l'ordre et cesse de regarder un nœud dès qu'un frère déjà vu rend le reste sans importance - les branches où il n'entre jamais restent sombres. La réponse n'en change jamais, seul le compte change, et le compte dépend de l'ORDRE des coups, pas de l'arbre : avec le meilleur coup en premier à chaque nœud il faut exactement le minimum de Knuth et Moore, près de la racine carrée de b^d ; avec le pire en premier il voit chaque feuille - mais seulement jusqu'à la profondeur 3, car dès la profondeur 4 l'alpha levé à la racine descend et élague même cela. Que regarder : les branches élaguées, le chemin doré de la variante principale et les trois barres au fond - minimax, cette recherche, le minimum.
Équations du module
Équations nœud MAX : v = max sur les fils ; nœud MIN : v = min sur les fils ; le minimax lit toutes les b^d feuilles alpha-bêta : couper le reste des fils d'un nœud dès que alpha >= beta - la réponse est la même, le décompte ne l'est pas ordre parfait : N_min = 2·b^(d/2) − 1 pour d pair, b^((d+1)/2) + b^((d−1)/2) − 1 pour d impair (Knuth - Moore, 1975) pire ordre à chaque nœud : N = b^d pour d <= 3 ; dès d = 4 l'alpha de la racine atteint le troisième niveau et élague quand même ordre s dans [−1, 1] : les fils d'un nœud sont triés par valeur exacte quand son propre tirage de hachage est inférieur à |s| - le meilleur d'abord pour s > 0, le pire d'abord pour s < 0
