4.8 Les coups qui tuent
71
et ainsi de suite. En effet la recherche >. d'ordre n fait un appel récursif à la recherche >.
d'ordre n sans limitation de profondeur. Alors que la recherche >. limitée arrêtera sa recherche après un nombre limité d'appels récursifs d'ordre n.
Exercice : Implémenter la recherche >. limitée au Phutball.
4.8 Les coups qui tuent
De même que pour l 'Alpha-Bêta il peut être intéressant pour la recherche de menaces
de mémoriser des coups qui tuent. Ainsi par exemple si un coup a permis de vérifier une
menace, c'est un coup à essayer en priorité après le coup de l'adversaire qui cherche à
parer la menace. On utilise donc deux tableaux de coups qui tuent (un pour Max et un
pour Min), et plutôt que de les indicer par la profondeur comme dans l' Alpha-Bêta on les
indice par le nombre de coups Max (respectivement Min) déjà joués de façon à réessayer
le coup Max gagnant après le coup Min.
Exercice : Ajouter les coups qui tuent à la recherche de menaces.
4.9 Les zone s pe rtinentes
Les zones pertinentes permettent d'améliorer significativement la recherche >.. Une
zone pertinente est !'ensemble des cases, ou des intersections suivant le jeu, qui interviennent dans la preuve d'un arbre >.. Les seuls coups qui peuvent invalider cet arbre >.
sont les coups sur sa zone pertinente. Ainsi lorsqu'on cherche des coups pour le défenseur à un noeud, les seuls coups à essayer sont les coups de la zone pertinente de l'arbre
>. prouvé au noeud.
4.10 Corrigés de s exercices
4.10.1 Phutball
On représente un coup comme une liste d'intersections. Si la liste ne comporte qu'une
seule intersection c'est !' emplacement de la pierre blanche qu'on pose. Si la liste comporte
plusieurs intersections, c'est un coup de prise, la première intersection est l'emplacement
initial de la balle, les intersections suivantes sauf la dernière sont les pierres blanches
prises et la dernière intersection est l'emplacement final de la balle.
#include
#include
71
et ainsi de suite. En effet la recherche >. d'ordre n fait un appel récursif à la recherche >.
d'ordre n sans limitation de profondeur. Alors que la recherche >. limitée arrêtera sa recherche après un nombre limité d'appels récursifs d'ordre n.
Exercice : Implémenter la recherche >. limitée au Phutball.
4.8 Les coups qui tuent
De même que pour l 'Alpha-Bêta il peut être intéressant pour la recherche de menaces
de mémoriser des coups qui tuent. Ainsi par exemple si un coup a permis de vérifier une
menace, c'est un coup à essayer en priorité après le coup de l'adversaire qui cherche à
parer la menace. On utilise donc deux tableaux de coups qui tuent (un pour Max et un
pour Min), et plutôt que de les indicer par la profondeur comme dans l' Alpha-Bêta on les
indice par le nombre de coups Max (respectivement Min) déjà joués de façon à réessayer
le coup Max gagnant après le coup Min.
Exercice : Ajouter les coups qui tuent à la recherche de menaces.
4.9 Les zone s pe rtinentes
Les zones pertinentes permettent d'améliorer significativement la recherche >.. Une
zone pertinente est !'ensemble des cases, ou des intersections suivant le jeu, qui interviennent dans la preuve d'un arbre >.. Les seuls coups qui peuvent invalider cet arbre >.
sont les coups sur sa zone pertinente. Ainsi lorsqu'on cherche des coups pour le défenseur à un noeud, les seuls coups à essayer sont les coups de la zone pertinente de l'arbre
>. prouvé au noeud.
4.10 Corrigés de s exercices
4.10.1 Phutball
On représente un coup comme une liste d'intersections. Si la liste ne comporte qu'une
seule intersection c'est !' emplacement de la pierre blanche qu'on pose. Si la liste comporte
plusieurs intersections, c'est un coup de prise, la première intersection est l'emplacement
initial de la balle, les intersections suivantes sauf la dernière sont les pierres blanches
prises et la dernière intersection est l'emplacement final de la balle.
#include
#include
#include