70
Recherche avec menaces
gnants) sont toujours des coups qui déplacent la balle. Par induction on peut déduire que
les coups d'ordre un ne sont jamais des coups qui déplacent la balle (sinon ils pourraient
être gagnants directement).
Exercice : Modifier la recherche de menaces au Phutball de façon à ne tester pour le
joueur Max que les coups qui étendent Je chemin de la balle ou la déplacent. Prendre en
compte l'ordre de la menace pour restreindre les coups à envisager.
De façon plus générale, les heuristiques admissibles permettent d'améliorer significativement la recherche avec menaces [22]. Une heuristique admissible donne un minorant
sur le nombre de coups de l'attaquant restant à jouer avant de gagner. Il est clair que si
l'heuristique admissible donne une valeur h, il ne sera pas possible de vérifier des arbres
À d'ordre strictement inférieur à h.
De même que les heuristiques admissibles les connaissances sur les coups qui peuvent
atteindre un but sont très utiles. Par exemple, au Go, le nombre de libertés d'une chaîne
est une heuristique admissible pour la capture : il faudra au moins autant de coups pour
la capturer que son nombre de libertés. Une connaissance pour sélectionner les coups
d'ordre n de capture d'une chaîne à n libertés est que seuls les coups sur les libertés de la
chaîne sont à envisager.
4.6 L' élargisseme nt itératif
L'élargissement itératif [ 18, 20] consiste à effectuer une recherche complète pour Max
pour un ordre donné avant d'accroître l'ordre de la recherche. En pratique on essaie une
recherche d'ordre un ; si elle échoue on essaie une recherche d'ordre deux ; si elle échoue
on essaie une recherche d'ordre trois ; et ainsi de suite jusqu'à ce que Je problème soit
résolu ou jusqu'à ce que le temps alloué soit dépassé.
Exercice : Intégrer l'élargissement itératif à la recherche À au Phutball.
4. 7 La limitation du nomb re de coups de chaque ord re
Un problème de la recherche À est qu'elle peut exploser en temps à cause du grand
nombre de menaces possibles qui peuvent être vérifiées pour un ordre donné. C'est par
exemple Je cas au Phutball où il est difficile de vérifier une recherche À d'ordre deux.
Une façon de limiter la recherche À est de limiter Je nombre de coups et de menaces
d'un ordre donné. On va représenter cette limitation par un tableau, Je nombre à l'indice
n représentera le nombre de coups d'ordre n qu'on a Je droit de jouer pour vérifier la
menace.
La recherche À classique peut être modélisée avec les menaces limitées. Par exemple
développer un arbre À1 est équivalent à vérifier une menace ( oo,oo,O), À2 avec ( 00,00,00,0)
Recherche avec menaces
gnants) sont toujours des coups qui déplacent la balle. Par induction on peut déduire que
les coups d'ordre un ne sont jamais des coups qui déplacent la balle (sinon ils pourraient
être gagnants directement).
Exercice : Modifier la recherche de menaces au Phutball de façon à ne tester pour le
joueur Max que les coups qui étendent Je chemin de la balle ou la déplacent. Prendre en
compte l'ordre de la menace pour restreindre les coups à envisager.
De façon plus générale, les heuristiques admissibles permettent d'améliorer significativement la recherche avec menaces [22]. Une heuristique admissible donne un minorant
sur le nombre de coups de l'attaquant restant à jouer avant de gagner. Il est clair que si
l'heuristique admissible donne une valeur h, il ne sera pas possible de vérifier des arbres
À d'ordre strictement inférieur à h.
De même que les heuristiques admissibles les connaissances sur les coups qui peuvent
atteindre un but sont très utiles. Par exemple, au Go, le nombre de libertés d'une chaîne
est une heuristique admissible pour la capture : il faudra au moins autant de coups pour
la capturer que son nombre de libertés. Une connaissance pour sélectionner les coups
d'ordre n de capture d'une chaîne à n libertés est que seuls les coups sur les libertés de la
chaîne sont à envisager.
4.6 L' élargisseme nt itératif
L'élargissement itératif [ 18, 20] consiste à effectuer une recherche complète pour Max
pour un ordre donné avant d'accroître l'ordre de la recherche. En pratique on essaie une
recherche d'ordre un ; si elle échoue on essaie une recherche d'ordre deux ; si elle échoue
on essaie une recherche d'ordre trois ; et ainsi de suite jusqu'à ce que Je problème soit
résolu ou jusqu'à ce que le temps alloué soit dépassé.
Exercice : Intégrer l'élargissement itératif à la recherche À au Phutball.
4. 7 La limitation du nomb re de coups de chaque ord re
Un problème de la recherche À est qu'elle peut exploser en temps à cause du grand
nombre de menaces possibles qui peuvent être vérifiées pour un ordre donné. C'est par
exemple Je cas au Phutball où il est difficile de vérifier une recherche À d'ordre deux.
Une façon de limiter la recherche À est de limiter Je nombre de coups et de menaces
d'un ordre donné. On va représenter cette limitation par un tableau, Je nombre à l'indice
n représentera le nombre de coups d'ordre n qu'on a Je droit de jouer pour vérifier la
menace.
La recherche À classique peut être modélisée avec les menaces limitées. Par exemple
développer un arbre À1 est équivalent à vérifier une menace ( oo,oo,O), À2 avec ( 00,00,00,0)