Schéma de l'Algorithme AlpaBeta

Alpha-Beta
Idée
Élaguer des branches qu'il est inutile d'explorer

Si la valeur d'un noeud atteint un seuil , il est inutile de continuer à explorer les descendants de ce noeud

-> leur valeur n'interviendra pas

Coupe Alpha
n noeud min
Seuil Alpha = Max des ancêtres Max de n

si n devient inférieur à Alpha -> fini

Coupe Beta
n noeud Max
Seuil Beta = min des ancêtres min de n

si n devient supérieur à Beta -> fini

Alpha-Beta

Valeur-noeud(n, alpha, beta)
si n est terminal alors retourner eval(n)
sinon
soient f1, ... , fj les fils de n
si n est max
alors
pour i de 1 à j et tant que alpha < beta faire
alpha <- max(alpha,Valeur-noeud(fi, alpha, beta))
retourner alpha
sinon
pour i de 1 à j et tant que alpha < beta faire
beta <- min(alpha,Valeur-noeud(fi, alpha, beta))
retourner beta
fsi
fsi

Exemple