22
Minimax, Alpha-Bêta et heuristiques associées
Exercice : Définir la bijection entre coups et nombres au jeu du Virus.
Exercice : Modifier l' Alpha-Bêta pour prendre en compte l'heuristique de l'historique. Commencer par déclarer les structures de données nécessaires. Puis écrire les fonctions d'initialisation, de mise à jour des scores, et de tri des coups. Modifier enfin l' AlphaBêta.
2.9 La re cherche aspirante
Plutôt que d'appeler l' Alpha-Bêta avec des valeurs initiales de la plus petite évaluation possible pour alpha et de la plus grande évaluation possible pour bêta, on peut lui
permettre de couper plus de branches, si on augmente (resp. diminue) la valeur initiale de
alpha (resp. bêta). Si la valeur retournée par l 'Alpha-Bêta est comprise entre les alpha et
bêta initiaux, le résultat sera tout de même juste, bien que l'on ait coupé plus de branches
inutiles qu'avec les valeurs extrêmes.
On appelle fenêtre de l' Alpha-Bêta l'ensemble des valeurs comprises entre alpha et
bêta.
Dans la recherche aspirante, les résultats de la recherche précédente permettent de régler les valeurs initiales pour alpha et bêta. Au début de chaque itération sur la profondeur,
la valeur maximale (resp. minimale) est initialisée avec le résultat remonté de l'itération
précédente, additionnée (resp. diminuée) d'une valeur fixée (par exemple aux É checs, de
la valeur d'un pion). Si la recherche avec cette fenêtre réduite échoue (le résultat n'est
pas inclus dans la fenêtre) la fenêtre de l' Alpha-Bêta est aj ustée. Si on échoue vers le bas
(résultat < alpha), elle est aj ustée à [valeur minimale, alpha] . Si on échoue vers le haut
(résultat > bêta), elle est aj ustée à [beta, valeur maximale].
La recherche aspirante est une amélioration de l'approfondissement itératif. Les résultats de la recherche à profondeur p sont généralement assez proches des résultats de la
recherche à profondeur p - 1. On peut donc centrer la fenêtre sur la valeur retournée par
la recherche précédente.
Exercice: Combiner la recherche aspirante avec l'approfondissement itératif.
2.10 La recherche ave c fe nêt re nulle
En poussant l'idée de fenêtre jusqu'au bout, on obtient la recherche avec fenêtre nulle
(Null-Window Search). Cela consiste à appeler !'Alpha-Bêta avec une fenêtre [valeur,
valeur + l], sachant que la fonction d'évaluation est entière avec des différences d'évaluation minimales de un point. Les arbres développés sont alors plus petits, et on peut
aj uster vers le haut ou vers le bas la valeur en fonction de ce que retourne l 'Alpha-Bêta. Il
a été montré que cet algorithme, qui associé aux tables de transposition s'appelle MTD(f)
Minimax, Alpha-Bêta et heuristiques associées
Exercice : Définir la bijection entre coups et nombres au jeu du Virus.
Exercice : Modifier l' Alpha-Bêta pour prendre en compte l'heuristique de l'historique. Commencer par déclarer les structures de données nécessaires. Puis écrire les fonctions d'initialisation, de mise à jour des scores, et de tri des coups. Modifier enfin l' AlphaBêta.
2.9 La re cherche aspirante
Plutôt que d'appeler l' Alpha-Bêta avec des valeurs initiales de la plus petite évaluation possible pour alpha et de la plus grande évaluation possible pour bêta, on peut lui
permettre de couper plus de branches, si on augmente (resp. diminue) la valeur initiale de
alpha (resp. bêta). Si la valeur retournée par l 'Alpha-Bêta est comprise entre les alpha et
bêta initiaux, le résultat sera tout de même juste, bien que l'on ait coupé plus de branches
inutiles qu'avec les valeurs extrêmes.
On appelle fenêtre de l' Alpha-Bêta l'ensemble des valeurs comprises entre alpha et
bêta.
Dans la recherche aspirante, les résultats de la recherche précédente permettent de régler les valeurs initiales pour alpha et bêta. Au début de chaque itération sur la profondeur,
la valeur maximale (resp. minimale) est initialisée avec le résultat remonté de l'itération
précédente, additionnée (resp. diminuée) d'une valeur fixée (par exemple aux É checs, de
la valeur d'un pion). Si la recherche avec cette fenêtre réduite échoue (le résultat n'est
pas inclus dans la fenêtre) la fenêtre de l' Alpha-Bêta est aj ustée. Si on échoue vers le bas
(résultat < alpha), elle est aj ustée à [valeur minimale, alpha] . Si on échoue vers le haut
(résultat > bêta), elle est aj ustée à [beta, valeur maximale].
La recherche aspirante est une amélioration de l'approfondissement itératif. Les résultats de la recherche à profondeur p sont généralement assez proches des résultats de la
recherche à profondeur p - 1. On peut donc centrer la fenêtre sur la valeur retournée par
la recherche précédente.
Exercice: Combiner la recherche aspirante avec l'approfondissement itératif.
2.10 La recherche ave c fe nêt re nulle
En poussant l'idée de fenêtre jusqu'au bout, on obtient la recherche avec fenêtre nulle
(Null-Window Search). Cela consiste à appeler !'Alpha-Bêta avec une fenêtre [valeur,
valeur + l], sachant que la fonction d'évaluation est entière avec des différences d'évaluation minimales de un point. Les arbres développés sont alors plus petits, et on peut
aj uster vers le haut ou vers le bas la valeur en fonction de ce que retourne l 'Alpha-Bêta. Il
a été montré que cet algorithme, qui associé aux tables de transposition s'appelle MTD(f)