16
Minimax, Alpha-Bêta et heuristiques associées
meilleurCoup) et mini ( int depth) qui s'appellent mutuellement pour
effectuer une recherche Minimax à la profondeur depth pour le jeu du virus.
2.2 Le Negamax
Plutôt que d'écrire deux fonctions mini et maxi, on peut inverser le signe des évaluations à chaque niveau, et toujours chercher à maximiser. On a alors l'algorithme Negamax
qui n'utilise qu' une seule fonction récursive qui maximise à tous les niveaux.
L' algorithme Negamax est en général celui qui est utilisé pour décrire des heuristiques
car il suffit d'écrire l'heuristique pour le seul niveau max.
Exercice : En utilisant les mêmes fonctions prédéfinies que pour le Minimax programmez l'algorithme Negamax.
2.3 L' Alpha-Bêta
L' Alpha-Bêta est un algorithme qui renvoie toujours la même valeur que le Minimax,
mais qui n'utilise jamais plus de noeuds pour effectuer sa recherche. En pratique, il développe beaucoup moins de noeuds car il coupe des parties entières de l'arbre. Couper une
partie de l'arbre signifie qu'il n'explore pas cette partie. Faire une coupe dans l'arbre signifie qu 'il arrête la recherche d'un noeud avant d'avoir exploré tous les fils de ce noeud.
L' Alpha-Bêta doit son nom aux deux formes de coupes qu'il emploie : les coupes alpha
et les coupes bêta.
Les coupes alpha se font aux niveaux Min. Elles sont basées sur l'observation que si
la valeur d'un noeud de niveau Min est plus petite que la valeur du noeud de niveau Max
supérieur, quelles que soient les valeurs suivantes au niveau Min, elles ne changeront pas
la valeur du niveau Max supérieur. Un exemple de coupe alpha est donné en figure 2.3.
La coupure bêta est la coupe symétrique de la coupe alpha pour les niveaux Max.
Exercice : Trouver un exemple de coupe bêta.
Exercice : Reprendre l'arbre développé avec le Minimax. Quelle est la valeur de la
racine en utilisant l'algorithme Alpha-Bêta, combien de noeuds a-t-on développé et combien d'évaluations a-t-on effectuées ?
L'ordre dans lequel sont essayés les coups dans l' Alpha-Bêta est très important. Il
faut commencer par les meilleurs. Du bon ordre des coups dépend le nombre de coupes.
Mieux les coups sont ordonnés, plus le nombre de coupes sera important, plus le nombre
de noeuds évalués sera petit et plus l'algorithme donnera une réponse rapidement.
Minimax, Alpha-Bêta et heuristiques associées
meilleurCoup) et mini ( int depth) qui s'appellent mutuellement pour
effectuer une recherche Minimax à la profondeur depth pour le jeu du virus.
2.2 Le Negamax
Plutôt que d'écrire deux fonctions mini et maxi, on peut inverser le signe des évaluations à chaque niveau, et toujours chercher à maximiser. On a alors l'algorithme Negamax
qui n'utilise qu' une seule fonction récursive qui maximise à tous les niveaux.
L' algorithme Negamax est en général celui qui est utilisé pour décrire des heuristiques
car il suffit d'écrire l'heuristique pour le seul niveau max.
Exercice : En utilisant les mêmes fonctions prédéfinies que pour le Minimax programmez l'algorithme Negamax.
2.3 L' Alpha-Bêta
L' Alpha-Bêta est un algorithme qui renvoie toujours la même valeur que le Minimax,
mais qui n'utilise jamais plus de noeuds pour effectuer sa recherche. En pratique, il développe beaucoup moins de noeuds car il coupe des parties entières de l'arbre. Couper une
partie de l'arbre signifie qu'il n'explore pas cette partie. Faire une coupe dans l'arbre signifie qu 'il arrête la recherche d'un noeud avant d'avoir exploré tous les fils de ce noeud.
L' Alpha-Bêta doit son nom aux deux formes de coupes qu'il emploie : les coupes alpha
et les coupes bêta.
Les coupes alpha se font aux niveaux Min. Elles sont basées sur l'observation que si
la valeur d'un noeud de niveau Min est plus petite que la valeur du noeud de niveau Max
supérieur, quelles que soient les valeurs suivantes au niveau Min, elles ne changeront pas
la valeur du niveau Max supérieur. Un exemple de coupe alpha est donné en figure 2.3.
La coupure bêta est la coupe symétrique de la coupe alpha pour les niveaux Max.
Exercice : Trouver un exemple de coupe bêta.
Exercice : Reprendre l'arbre développé avec le Minimax. Quelle est la valeur de la
racine en utilisant l'algorithme Alpha-Bêta, combien de noeuds a-t-on développé et combien d'évaluations a-t-on effectuées ?
L'ordre dans lequel sont essayés les coups dans l' Alpha-Bêta est très important. Il
faut commencer par les meilleurs. Du bon ordre des coups dépend le nombre de coupes.
Mieux les coups sont ordonnés, plus le nombre de coupes sera important, plus le nombre
de noeuds évalués sera petit et plus l'algorithme donnera une réponse rapidement.