L'algorithme minimax effectue une exploration complète de l'arbre de recherche jusqu'à un niveau donné, alors qu'une exploration partielle de l'arbre pourrait suffire. Il suffit en effet, dans l'exploration en profondeur d'abord et de gauche à droite, d'éviter d'examiner des sous-arbres qui conduiront à des configurations dont la valeur ne contribuera sûrement pas au calcul du gain à la racine de l'arbre.
Dans les exemples de la figure 23 certains nuds ont
une valeur définitive alors que les autres (étiquetés avec un nom de
variable) n'en ont pas encore reçu. D'après la définition de
la fonction minimax la valeur de la configuration racine de l'arbre
(a) est obtenue par
Il est clair que indépendamment de la valeur de
. Il en résulte
que l'exploration des branches filles du n
ud étiqueté par
peut
être omise : on réalise ainsi une coupure superficielle. En
appliquant récursivement le même raisonnement à l'arbre (b), on en
déduit que la valeur de
peut être obtenue sans connaître la valeur
finale de
. De même que précédemment, l'exploration des branches
filles du n
ud étiqueté par
n'est pas nécessaire : on parle
alors de coupure profonde.
Plus généralement, lorsque dans le parcours de l'arbre minimax il y a
modification de la valeur courante d'un nud, si cette valeur
franchit un certain seuil, il devient inutile d'explorer la descendance
encore inexplorée de ce n
ud. On distingue deux seuils, appelés
(pour les n
uds Min) et
(pour les n
uds Max) :
L'algorithme peut être décrit informellement par la fonction
suivante, qui maintient ces deux seuils pendant le
parcours de l'arbre. Un appel à alphabeta(s,
,
) détermine une évaluation du jeu issu de la configuration
.
Contrairement aux fonctions (§ 76) et minimax
(§ 77), le calcul des valeurs de alphabeta se
fait de façon à la fois ascendante et descendante.
Chaque noeud de l'arbre se trouve affecté de trois attributs : la valeur
de la configuration et les seuils
et
. L'attribut
est synthétisé, c'est-à-dire calculé de façon ascendante à
partir des successeurs
de
. Par contre, les seuils sont des
attributs hérités, c'est-à-dire calculés
de façon descendante, à partir des parents : par exemple, si
est un
noeud de maximisation avec deux successeurs, soit
, alors
le seuil
de
est la valeur
de
qui a été calculée à
partir de
. L'information a donc circulé de
à
, puis de
à
.
La construction d'arbres comportant des attributs et l'évaluation de ces attributs sont des techniques importantes utilisées, non seulement dans les arbres de jeu, mais aussi dans la compilation des programmes.