2.6 L' approfondissement itératif
19
joueur) qui ne sélectionne que les coups liés à la quiescence (par exemple les coups
qui modifient plus de cinq cases au jeu du virus). Programmer ensuite une fonction qui
effectue une recherche de quiescence au jeu du virus. À chaque feuille de l'arborescence
Alpha-Bêta principale, appeler la fonction quiescence pour évaluer la position.
Attention : La recherche de quiescence n'est pas limitée en profondeur. Il faut
faire attention à ne pas sélectionner trop de coups dans la fonction list
coupsQuiescence (char joueur) si on ne veut pas risquer une explosion combinatoire de la fonction de quiescence. Par exemple, aux É checs, on n'essaiera pas toutes
les captures, mais seulement les captures de pièces importantes. D'une manière plus générale, il y a un équilibre à trouver entre le temps passé dans la recherche de quiescence et
le temps passé dans la recherche Alpha-Bêta principale. De plus il est préférable d'utiliser
une fonction d'évaluation qui ne dépend pas de la profondeur à laquelle on l'appelle car
on va comparer des évaluations à des profondeurs différentes.
2.6 L' approfondissement itératif
L'approfondissement itératif commence par effectuer une recherche de profondeur 1,
puis recommence avec une recherche complète à profondeur 2, et continue ainsi à faire
des recherches à des profondeurs de plus en plus grandes jusqu'à ce qu' une solution soit
trouvée ou que le temps imparti à la recherche soit écoulé.
Questions : Quelle est la complexité de l'approfondissement itératif jusqu'à la profondeur d par rapport à une recherche directe en profondeur d'abord à la profondeur d?
Pourquoi est-il intéressant d'effectuer un approfondissement itératif ?
Réponses :
A priori, l'approfondissement itératif perd du temps dans les itérations précédant la
dernière itération. To utefois, ce travail supplémentaire est généralement beaucoup plus
petit que la dernière itération. S'il y an coups explorés pour chaque position, le nombre
de feuilles à la profondeur k est n k . Le nombre de feuilles engendrées par un approfondissement itératif jusqu 'à la profondeur d est donc de n d + n d · I + n d - 2 + n d · 3 + ... + n. Ce qui
est en O(n d ). Si n est assez grand, le premier terme est nettement plus grand que tous les
autres, c'est donc la dernière itération qui prend la plus grande partie du temps. La complexité en espace de l'approfondissement itératif est linéaire en fonction de la profondeur
de recherche. Si on considère l'asymptote, l'approfondissement itératif est un algorithme
de recherche optimal aussi bien en temps qu'en espace [52].
L'approfondissement itératif est intéressant car il permet de contrôler le temps alloué
à une recherche. C'est un algorithme temps réel. A tout moment, il peut être arrêté et
donner la meilleur solution trouvée dans le temps imparti.
Enfin l'intérêt principal pour la programmation des jeux est qu'il permet de récupérer
des informations de la recherche à la profondeur précédente. Ces informations sont très
19
joueur) qui ne sélectionne que les coups liés à la quiescence (par exemple les coups
qui modifient plus de cinq cases au jeu du virus). Programmer ensuite une fonction qui
effectue une recherche de quiescence au jeu du virus. À chaque feuille de l'arborescence
Alpha-Bêta principale, appeler la fonction quiescence pour évaluer la position.
Attention : La recherche de quiescence n'est pas limitée en profondeur. Il faut
faire attention à ne pas sélectionner trop de coups dans la fonction list
coupsQuiescence (char joueur) si on ne veut pas risquer une explosion combinatoire de la fonction de quiescence. Par exemple, aux É checs, on n'essaiera pas toutes
les captures, mais seulement les captures de pièces importantes. D'une manière plus générale, il y a un équilibre à trouver entre le temps passé dans la recherche de quiescence et
le temps passé dans la recherche Alpha-Bêta principale. De plus il est préférable d'utiliser
une fonction d'évaluation qui ne dépend pas de la profondeur à laquelle on l'appelle car
on va comparer des évaluations à des profondeurs différentes.
2.6 L' approfondissement itératif
L'approfondissement itératif commence par effectuer une recherche de profondeur 1,
puis recommence avec une recherche complète à profondeur 2, et continue ainsi à faire
des recherches à des profondeurs de plus en plus grandes jusqu'à ce qu' une solution soit
trouvée ou que le temps imparti à la recherche soit écoulé.
Questions : Quelle est la complexité de l'approfondissement itératif jusqu'à la profondeur d par rapport à une recherche directe en profondeur d'abord à la profondeur d?
Pourquoi est-il intéressant d'effectuer un approfondissement itératif ?
Réponses :
A priori, l'approfondissement itératif perd du temps dans les itérations précédant la
dernière itération. To utefois, ce travail supplémentaire est généralement beaucoup plus
petit que la dernière itération. S'il y an coups explorés pour chaque position, le nombre
de feuilles à la profondeur k est n k . Le nombre de feuilles engendrées par un approfondissement itératif jusqu 'à la profondeur d est donc de n d + n d · I + n d - 2 + n d · 3 + ... + n. Ce qui
est en O(n d ). Si n est assez grand, le premier terme est nettement plus grand que tous les
autres, c'est donc la dernière itération qui prend la plus grande partie du temps. La complexité en espace de l'approfondissement itératif est linéaire en fonction de la profondeur
de recherche. Si on considère l'asymptote, l'approfondissement itératif est un algorithme
de recherche optimal aussi bien en temps qu'en espace [52].
L'approfondissement itératif est intéressant car il permet de contrôler le temps alloué
à une recherche. C'est un algorithme temps réel. A tout moment, il peut être arrêté et
donner la meilleur solution trouvée dans le temps imparti.
Enfin l'intérêt principal pour la programmation des jeux est qu'il permet de récupérer
des informations de la recherche à la profondeur précédente. Ces informations sont très