24
Minimax, Alpha-Bêta et heuristiques associées
coupes bêta. Cette heuristique permet de ne pas développer des arborescences qui ont de
grandes chances d'être inutiles.
L' heuristique du coup nul permet de gagner du temps en décidant de ne pas développer
des noeuds qui amène à une coupe bêta après une recherche à une profondeur inférieure
à la profondeur courante, même après avoir passé son tour.
Un coup nul (null move) consiste à changer le tour de jeu, ce qui est équivalent pour
un joueur à passer son tour. Le coup nul est un coup légal au jeu de Go où un joueur
peut passer ; c'est même de cette façon que la fin de partie est décidée lorsque les deux
joueurs passent consécutivement. Aux É checs par contre, et dans d'autres jeux, ce n'est
pas un coup légal, or il existe des positions pour lesquelles ce serait le meilleur coup. Ce
sont les positions de zugzwang : le premier joueur qui joue dans une position de ce type
a perdu. Ces positions se retrouvent par exemple fréquemment dans les finales de pions
aux É checs.
L' hypothèse sur laquelle est fondée l'heuristique du coup nul est qu'il y a au moins
un coup qui améliore la position (ceci suppose qu'il n'y ait pas de zugzwang), et donc
qu 'il existe un coup meilleur que de passer. Pour utiliser l'heuristique le joueur passe puis
effectue une recherche à une profondeur inférieure à la profondeur courante. Si le résultat
de la recherche est supérieur à bêta, alors la position n'est pas étudiée plus profondément,
car on suppose qu'il existe un coup meilleur que le coup nul qui amènera aussi à une
coupe bêta.
L' heuristique du coup nul est associée à un facteur de réduction R qui permet de
régler la profondeur de recherche après le coup nul. Si on est dans un noeud pour lequel
on s'apprête à faire une recherche de profondeur P la profondeur de la recherche associée
au coup nul sera P - R. On choisit en général R = 2 ou R = 3.
L' heuristique du coup nul peut parfois masquer une arborescence qui, si elle avait été
explorée, aurait changé le résultat de !'Alpha-Bêta. C'est par exemple le cas lorsque la
recherche à une profondeur inférieure utilisée par l'heuristique ne permet pas de voir une
capture qui aurait été vue avec une recherche un peu plus profonde. Contrairement aux
coupes de l' Alpha-Bêta qui ne changent pas le résultat du Minimax, les coupes dues au
coup nul peuvent changer le résultat de l' Alpha-Bêta.
L' heuristique du coup nul est un compromis entre le temps passé à faire les recherches
après le coup nul et le temps gagné par les coupes qui permettent de ne pas faire les
recherches à profondeur normale quand la recherche après le coup nul renvoie une valeur
supérieure à bêta.
Exercice : Implémenter l'heuristique du coup nul pour le jeu du virus.
En pratique on veut éviter d'utiliser l'heuristique du coup nul quand on est dans une
position de zugzwang. Aux É checs une solution possible est d'éviter de l'utiliser quand :
- le joueur max est en échec,
- le joueur max n'a plus que des pions ou n'a plus que quelques pièces,
Minimax, Alpha-Bêta et heuristiques associées
coupes bêta. Cette heuristique permet de ne pas développer des arborescences qui ont de
grandes chances d'être inutiles.
L' heuristique du coup nul permet de gagner du temps en décidant de ne pas développer
des noeuds qui amène à une coupe bêta après une recherche à une profondeur inférieure
à la profondeur courante, même après avoir passé son tour.
Un coup nul (null move) consiste à changer le tour de jeu, ce qui est équivalent pour
un joueur à passer son tour. Le coup nul est un coup légal au jeu de Go où un joueur
peut passer ; c'est même de cette façon que la fin de partie est décidée lorsque les deux
joueurs passent consécutivement. Aux É checs par contre, et dans d'autres jeux, ce n'est
pas un coup légal, or il existe des positions pour lesquelles ce serait le meilleur coup. Ce
sont les positions de zugzwang : le premier joueur qui joue dans une position de ce type
a perdu. Ces positions se retrouvent par exemple fréquemment dans les finales de pions
aux É checs.
L' hypothèse sur laquelle est fondée l'heuristique du coup nul est qu'il y a au moins
un coup qui améliore la position (ceci suppose qu'il n'y ait pas de zugzwang), et donc
qu 'il existe un coup meilleur que de passer. Pour utiliser l'heuristique le joueur passe puis
effectue une recherche à une profondeur inférieure à la profondeur courante. Si le résultat
de la recherche est supérieur à bêta, alors la position n'est pas étudiée plus profondément,
car on suppose qu'il existe un coup meilleur que le coup nul qui amènera aussi à une
coupe bêta.
L' heuristique du coup nul est associée à un facteur de réduction R qui permet de
régler la profondeur de recherche après le coup nul. Si on est dans un noeud pour lequel
on s'apprête à faire une recherche de profondeur P la profondeur de la recherche associée
au coup nul sera P - R. On choisit en général R = 2 ou R = 3.
L' heuristique du coup nul peut parfois masquer une arborescence qui, si elle avait été
explorée, aurait changé le résultat de !'Alpha-Bêta. C'est par exemple le cas lorsque la
recherche à une profondeur inférieure utilisée par l'heuristique ne permet pas de voir une
capture qui aurait été vue avec une recherche un peu plus profonde. Contrairement aux
coupes de l' Alpha-Bêta qui ne changent pas le résultat du Minimax, les coupes dues au
coup nul peuvent changer le résultat de l' Alpha-Bêta.
L' heuristique du coup nul est un compromis entre le temps passé à faire les recherches
après le coup nul et le temps gagné par les coupes qui permettent de ne pas faire les
recherches à profondeur normale quand la recherche après le coup nul renvoie une valeur
supérieure à bêta.
Exercice : Implémenter l'heuristique du coup nul pour le jeu du virus.
En pratique on veut éviter d'utiliser l'heuristique du coup nul quand on est dans une
position de zugzwang. Aux É checs une solution possible est d'éviter de l'utiliser quand :
- le joueur max est en échec,
- le joueur max n'a plus que des pions ou n'a plus que quelques pièces,