2.13 L'approfondissement sélectif
25
- le coup précédent était aussi un coup nul.
Une autre façon de se prémunir contre les zugzwangs est de faire une recherche réduite même quand l'heuristique du coup nul amène à une coupe bêta [39, 69]. En plus
de détecter les zugzwangs, faire une recherche normale à profondeur réduite, après que
l'heuristique du coup nul ait été vérifiée, peut aussi aider à contrer l'effet d'horizon en
détectant des menaces tactiques que la recherche avec coup nul n'avait pas détectées.
To utefois faire cette recherche de vérification en milieu de partie quand il n'y a pas ou
peu de zugzwangs paraît trop coûteux. Une solution à ce problème est l'heuristique du
coup nul vérifié [86] . Une recherche avec coup nul avec un facteur de réduction R = 3
est essayée à chaque noeud. Si cette recherche renvoie une valeur supérieure à bêta on
continue la recherche normale à une profondeur de moins. Pour cette recherche normale à
profondeur réduite l'heuristique du coup nul simple est utilisée. Si la recherche à profondeur réduite ne renvoie pas une valeur supérieure à bêta c'est que le coup nul est meilleur
que tous les autres, on est donc en présence d'un zugzwang. Dans ce cas l'heuristique du
coup nul vérifié refait une recherche normale à la profondeur normale pour renvoyer une
valeur précise de la position en zugzwang. Aux É checs, l'heuristique du coup nul vérifié
avec R = 3 développe moins de noeuds que l'heuristique du coup nul avec R = 2 et
résout correctement plus de problèmes [86] .
Exercice : Implémenter l'heuristique du coup nul vérifié pour le jeu du virus.
2.13 L' approfondisse me nt séle ctif
L'approfondissement sélectif permet de ne pas étudier toutes les parties de l'arbre à
la même profondeur. Si un coup semble intéressant on continue à chercher à une plus
grande profondeur que la profondeur habituelle. Si un coup semble mauvais on arrête de
chercher à une profondeur plus petite que la profondeur habituelle.
Par exemple, si Chinook analyse un coup qui perd 3 pions, plutôt que de continuer
à analyser la position jusqu 'à une profondeur 10 il va réduire son analyse à seulement 5
coups à l'avance en faisant l'hypothèse qu 'il y a de bonnes chances que le coup soit très
mauvais. Par contre, si le programme joue un coup qui paraît très bon, il augmentera la
profondeur de l'analyse de 10 à 12 coups à l'avance.
D'après J. Schaeffer [78], c'est une décision d'investissement : on investit son capital (le temps d'analyse) là où on espère avoir le meilleur bénéfice (on cherche le plus
d'information possible).
Un autre mécanisme d'approfondissement sélectif est utilisé dans Deep Blue. Il analyse la structure de l'arborescence pour savoir si un noeud de l'arbre est uniforme ou pas.
Ainsi un noeud dans lequel beaucoup de coups sont bons est considéré comme ayant une
évaluation sûre. Alors qu'un noeud pour lequel un seul coup parmi de nombreux coups
est bon, est considéré comme peu sûr. Deep Blue développe alors plus que les autres la
partie de l'arborescence qui ne contient qu'un seul bon coup.
25
- le coup précédent était aussi un coup nul.
Une autre façon de se prémunir contre les zugzwangs est de faire une recherche réduite même quand l'heuristique du coup nul amène à une coupe bêta [39, 69]. En plus
de détecter les zugzwangs, faire une recherche normale à profondeur réduite, après que
l'heuristique du coup nul ait été vérifiée, peut aussi aider à contrer l'effet d'horizon en
détectant des menaces tactiques que la recherche avec coup nul n'avait pas détectées.
To utefois faire cette recherche de vérification en milieu de partie quand il n'y a pas ou
peu de zugzwangs paraît trop coûteux. Une solution à ce problème est l'heuristique du
coup nul vérifié [86] . Une recherche avec coup nul avec un facteur de réduction R = 3
est essayée à chaque noeud. Si cette recherche renvoie une valeur supérieure à bêta on
continue la recherche normale à une profondeur de moins. Pour cette recherche normale à
profondeur réduite l'heuristique du coup nul simple est utilisée. Si la recherche à profondeur réduite ne renvoie pas une valeur supérieure à bêta c'est que le coup nul est meilleur
que tous les autres, on est donc en présence d'un zugzwang. Dans ce cas l'heuristique du
coup nul vérifié refait une recherche normale à la profondeur normale pour renvoyer une
valeur précise de la position en zugzwang. Aux É checs, l'heuristique du coup nul vérifié
avec R = 3 développe moins de noeuds que l'heuristique du coup nul avec R = 2 et
résout correctement plus de problèmes [86] .
Exercice : Implémenter l'heuristique du coup nul vérifié pour le jeu du virus.
2.13 L' approfondisse me nt séle ctif
L'approfondissement sélectif permet de ne pas étudier toutes les parties de l'arbre à
la même profondeur. Si un coup semble intéressant on continue à chercher à une plus
grande profondeur que la profondeur habituelle. Si un coup semble mauvais on arrête de
chercher à une profondeur plus petite que la profondeur habituelle.
Par exemple, si Chinook analyse un coup qui perd 3 pions, plutôt que de continuer
à analyser la position jusqu 'à une profondeur 10 il va réduire son analyse à seulement 5
coups à l'avance en faisant l'hypothèse qu 'il y a de bonnes chances que le coup soit très
mauvais. Par contre, si le programme joue un coup qui paraît très bon, il augmentera la
profondeur de l'analyse de 10 à 12 coups à l'avance.
D'après J. Schaeffer [78], c'est une décision d'investissement : on investit son capital (le temps d'analyse) là où on espère avoir le meilleur bénéfice (on cherche le plus
d'information possible).
Un autre mécanisme d'approfondissement sélectif est utilisé dans Deep Blue. Il analyse la structure de l'arborescence pour savoir si un noeud de l'arbre est uniforme ou pas.
Ainsi un noeud dans lequel beaucoup de coups sont bons est considéré comme ayant une
évaluation sûre. Alors qu'un noeud pour lequel un seul coup parmi de nombreux coups
est bon, est considéré comme peu sûr. Deep Blue développe alors plus que les autres la
partie de l'arborescence qui ne contient qu'un seul bon coup.