2.3 L' Alpha-Bêta
>=1 8
18
FIGURE 2.3 - Une coupe alpha.
17
Propriété: Lorsque le Minimax trouve un coup en n noeuds, !' Alpha-Bêta peut trouver ce même coup en 2fo, - 1 noeuds si les coups sont ordonnés du meilleur au moins
bon [5 1]. En pratique cela permet à temps constant de faire une recherche deux fois plus
profonde.
Algorithm 1 Alpha-Bêta
a(3 (depth, a, (3, joueur)
if depth = 0 then
retourner l'évaluation de la position courante pour joueur
end if
for tous les coups possibles pour joueur do
jouer le coup
eval = -a(3 (depth - l,-(3, - a, adversaire (joueur))
if eval > a then
a= eval
end if
retirer le coup
if a;::: (3 then
retourner (3
end if
end for
retourner a
L'algorithme 1 décrit l'algorithme Alpha-Bêta.
Exercice : Modifiez le programme pour le Negamax de façon à implémenter l' algorithme Alpha-Bêta pour le jeu du virus.