68
Recherche avec menaces
4.3 Les me naces di re ctes
On peut définir formellement la notion de menace directe [21]. Dans le reste du chapitre, le joueur Max est l'attaquant qui essaie de gagner le jeu en faisant des menaces. Soit
une position Pet un joueur J, on définit par induction le prédicat gagnantk (P, J) de la
manière suivante :
gagnant0 (P, J) : J peut gagner si c'est à lui de jouer.
gagnek (P, J) est vrai si pour tous les coups de l'adversaire de J amenant chacun à
une position P ' , on peut vérifier après le coup que gagnantk' ( P' , J) avec k' < k.
gagnantk (P, J) est vrai s'il existe un coup pour J tel qu' après ce coup menant à une
position P', gagnek ( P' , J) soit vrai.
Exercice : Trouver des positions au Go-Moku (on rappelle que le but du jeu est
d'être le premier à aligner cinq croix horizontalement, verticalement ou en diagonale sur
une grille) qui sont prouvées avec des recherches gagnant0, gagnant1, gagnant2 puis
gagnant3.
Définies comme cela les fonctions n'utilisent pas de menaces et correspondent à un
Minimax classique. To utefois on peut observer que si un coup est gagnant au niveau k, la
position une fois le coup joué contient forcément un coup gagnant au niveau k - 1. Donc
gagnantk (P, J) ne peut être vrai que si gagnantk - I (P' , J) est aussi vrai après le coup
gagnant. Donc si gagnantk - i(P' , J) n'est pas vrai après un coup, ce n'est pas la peine
d'essayer de vérifier gagnantk (P, J) et on peut couper la vérification.
Exercice : É crire un fonction qui détecte les menaces directes d'ordre n au Phutball
en coupant les vérifications inutiles.
4.4 La recherche À
La recherche >. (,\ search) [89] fait appel à des arbres lambda et des coups lambda. Un
arbre lambda d'ordre n est une arbre de recherche qui contient des coups lambda d'ordre
n. Un coup lambda d'ordre n pour l'attaquant est un coup qui implique qu'il existe au
moins un arbre lambda d'ordre strictement inférieur à n qui suit le coup. Un coup d'ordre
n pour le défenseur est un coup qui implique qu'il n'y a aucun arbre gagnant d'ordre
strictement inférieur à n après le coup.
La recherche ,\ est une recherche qui est adaptée aux jeux qui contiennent de nombreuses menaces. Elle joue plusieurs coups de suite de la même couleur et ne continue la
recherche que si la position est gagnante après ces plusieurs coups. De manière générale,
elle ne fait une recherche à l'ordre n que s'il existe un coup de Max qui est gagnant quand
il est suivi d'une recherche à l'ordre n - 1. Un coup de Min d'ordre n n'est envisagé que
Recherche avec menaces
4.3 Les me naces di re ctes
On peut définir formellement la notion de menace directe [21]. Dans le reste du chapitre, le joueur Max est l'attaquant qui essaie de gagner le jeu en faisant des menaces. Soit
une position Pet un joueur J, on définit par induction le prédicat gagnantk (P, J) de la
manière suivante :
gagnant0 (P, J) : J peut gagner si c'est à lui de jouer.
gagnek (P, J) est vrai si pour tous les coups de l'adversaire de J amenant chacun à
une position P ' , on peut vérifier après le coup que gagnantk' ( P' , J) avec k' < k.
gagnantk (P, J) est vrai s'il existe un coup pour J tel qu' après ce coup menant à une
position P', gagnek ( P' , J) soit vrai.
Exercice : Trouver des positions au Go-Moku (on rappelle que le but du jeu est
d'être le premier à aligner cinq croix horizontalement, verticalement ou en diagonale sur
une grille) qui sont prouvées avec des recherches gagnant0, gagnant1, gagnant2 puis
gagnant3.
Définies comme cela les fonctions n'utilisent pas de menaces et correspondent à un
Minimax classique. To utefois on peut observer que si un coup est gagnant au niveau k, la
position une fois le coup joué contient forcément un coup gagnant au niveau k - 1. Donc
gagnantk (P, J) ne peut être vrai que si gagnantk - I (P' , J) est aussi vrai après le coup
gagnant. Donc si gagnantk - i(P' , J) n'est pas vrai après un coup, ce n'est pas la peine
d'essayer de vérifier gagnantk (P, J) et on peut couper la vérification.
Exercice : É crire un fonction qui détecte les menaces directes d'ordre n au Phutball
en coupant les vérifications inutiles.
4.4 La recherche À
La recherche >. (,\ search) [89] fait appel à des arbres lambda et des coups lambda. Un
arbre lambda d'ordre n est une arbre de recherche qui contient des coups lambda d'ordre
n. Un coup lambda d'ordre n pour l'attaquant est un coup qui implique qu'il existe au
moins un arbre lambda d'ordre strictement inférieur à n qui suit le coup. Un coup d'ordre
n pour le défenseur est un coup qui implique qu'il n'y a aucun arbre gagnant d'ordre
strictement inférieur à n après le coup.
La recherche ,\ est une recherche qui est adaptée aux jeux qui contiennent de nombreuses menaces. Elle joue plusieurs coups de suite de la même couleur et ne continue la
recherche que si la position est gagnante après ces plusieurs coups. De manière générale,
elle ne fait une recherche à l'ordre n que s'il existe un coup de Max qui est gagnant quand
il est suivi d'une recherche à l'ordre n - 1. Un coup de Min d'ordre n n'est envisagé que