130
Recherche en meilleur d'abord pour les jeux à deux joueurs
FIGURE 6.4 - Quel sont les nombres conspirants à la racine ?
Exercice : En supposant que les valeurs possibles pour l'évaluation vont de -2 à 2,
calculer les nombre conspirants de la racine de l'arbre de la figure 6.4. Combien de feuilles
faut il changer pour que la racine prenne la valeur -2 ?
Les nombres conspirants représentent la difficulté de changer la valeur d'un noeud.
Ils peuvent donc être utilisés pour évaluer la précision de la valeur de la racine tracine.
Un Seuil de Conspiration SC permet de déterminer le nombre minimum de noeuds pour
qu'une valeur soit considérée comme improbable à atteindre et qu'elle ne soit plus cherchée.
L' algorithme continue jusqu'à ce qu'il n'y ait plus qu'une seule valeur possible. C'est
à dire quand on pense que plus de recherche ne changera pas la valeur de la racine. Plus
le seuil est grand, plus on peut avoir confiance dans la valeur finale de la racine.
É tant donné un ensemble de valeurs possibles pour la racine, comment les élimine+
on toutes sauf une ? La façon la plus simple est de les ôter une par une en commençant
soit par tmax la plus grande valeur encore possible à la racine, soit par tmin la plus petite
valeur encore possible. Pour éliminer tmax, l'algorithme essaie soit de changer la valeur
de la racine à tmax, soit d'augmenter le nombre conspirant de tmax jusqu'à SC (AugmenterRacine), ce qui est fait en prouvant qu'un élément de l'ensemble conspirant minimal ne
conspirera pas avec les autres éléments de l'ensemble pour changer la valeur de la racine
vers tmax. Une stratégie similaire est utilisée pour éliminer tmin (DiminuerRacine).
A chaque étape du développement de l'arbre, l'algorithme doit choisir soit de AugmenterRacine ou de DiminuerRacine. Il choisit d'éliminer la valeur qui est la plus éloignée de tracine. Si les valeurs sont à égales distances de tracine, il choisit DiminuerRacine. Si on a choisit d'éliminer tmax, par exemple, une feuille de l'ensemble minimal de
conspirateurs doit être développée un coup de plus. Pour trouver cette feuille à développer,
l'algorithme descend de la racine en utilisant la procédure suivante :
- pour un noeud Max : Seul un successeur doit augmenter sa valeur à tmax pour
que le noeud père en fasse autant. La branche la plus à même de changer la valeur
Recherche en meilleur d'abord pour les jeux à deux joueurs
FIGURE 6.4 - Quel sont les nombres conspirants à la racine ?
Exercice : En supposant que les valeurs possibles pour l'évaluation vont de -2 à 2,
calculer les nombre conspirants de la racine de l'arbre de la figure 6.4. Combien de feuilles
faut il changer pour que la racine prenne la valeur -2 ?
Les nombres conspirants représentent la difficulté de changer la valeur d'un noeud.
Ils peuvent donc être utilisés pour évaluer la précision de la valeur de la racine tracine.
Un Seuil de Conspiration SC permet de déterminer le nombre minimum de noeuds pour
qu'une valeur soit considérée comme improbable à atteindre et qu'elle ne soit plus cherchée.
L' algorithme continue jusqu'à ce qu'il n'y ait plus qu'une seule valeur possible. C'est
à dire quand on pense que plus de recherche ne changera pas la valeur de la racine. Plus
le seuil est grand, plus on peut avoir confiance dans la valeur finale de la racine.
É tant donné un ensemble de valeurs possibles pour la racine, comment les élimine+
on toutes sauf une ? La façon la plus simple est de les ôter une par une en commençant
soit par tmax la plus grande valeur encore possible à la racine, soit par tmin la plus petite
valeur encore possible. Pour éliminer tmax, l'algorithme essaie soit de changer la valeur
de la racine à tmax, soit d'augmenter le nombre conspirant de tmax jusqu'à SC (AugmenterRacine), ce qui est fait en prouvant qu'un élément de l'ensemble conspirant minimal ne
conspirera pas avec les autres éléments de l'ensemble pour changer la valeur de la racine
vers tmax. Une stratégie similaire est utilisée pour éliminer tmin (DiminuerRacine).
A chaque étape du développement de l'arbre, l'algorithme doit choisir soit de AugmenterRacine ou de DiminuerRacine. Il choisit d'éliminer la valeur qui est la plus éloignée de tracine. Si les valeurs sont à égales distances de tracine, il choisit DiminuerRacine. Si on a choisit d'éliminer tmax, par exemple, une feuille de l'ensemble minimal de
conspirateurs doit être développée un coup de plus. Pour trouver cette feuille à développer,
l'algorithme descend de la racine en utilisant la procédure suivante :
- pour un noeud Max : Seul un successeur doit augmenter sa valeur à tmax pour
que le noeud père en fasse autant. La branche la plus à même de changer la valeur