6.6 L'algorithme B*
131
est celle qui demande le moins de conspirateurs pour avoir tmax. On choisit donc
la branche qui a le nombre minimum de conspirateurs, et la plus à gauche en cas
d'égalité.
- pour un noeud Min : On choisit, parmi toutes les branches qui doivent augmenter
leur valeur jusqu'à tmax pour changer la valeur du noeud, celle qui est la plus à
gauche.
Lorsqu'on atteint une feuille celle ci est développée. Comme chaque fils peut amener à
un résultat favorable ou défavorable, les fils sont ordonnés en fonction de leur évaluation.
En mettant les fils les plus favorables en premier, cela accroît les chances que le fils le
plus à gauche soit le meilleur, et favorise donc le choix du fils le plus à gauche dans
l'algorithme. Les valeurs minimax et les nombres conspirants sont alors remontés dans
l'arbre.
Si en développant cette feuille, on augmente sa valeur à tmax, le nombre de conspirateurs pour cette valeur est diminuée de 1, et les autres éléments de cet ensemble de
conspirateurs sont à leur tour développés. Si la valeur du noeud est inférieure à tmax, et
que le noeud développé est un noeud Min, on a alors peut être augmenté le nombre de
conspirateurs à la racine ; dans ce cas le nombre de conspirateurs peut avoir atteint SC ; on
élimine alors tmax de l'ensemble des valeurs possibles à la racine. Pour un noeud Max, si
la valeur est inférieure à tmax, on n'a pas fait évoluer le nombre de conspirateurs de tmax.
6.6 L'algorithme B *
B * (7, 9] cherche à prouver qu'un coup est meilleur que les autres. Il utilise deux
bornes sur la valeur heuristique de la position, une valeur pessimiste et une valeur optimiste. B * se termine lorsqu'il a prouvé que la valeur pessimiste d'un coup est supérieure
aux valeurs optimistes de tous les autres coups. H. Berliner a utilisé B * pour les É checs.
L' idée à la base de l'algorithme B * est qu'il n'est pas nécessaire de connaître les
valeurs minimax exactes des fils de la racine pour trouver le meilleur coup. Si on peut
trouver des limites pour les valeurs minimax de ces successeurs, puis prouver que la limite
inférieure du meilleur successeur est plus grande ou égale aux limites supérieures des
autres coups, cela suffit pour prouver qu'il est le meilleur.
Remonter uniquement les bornes d'évaluation fait perdre des informations vitales,
comme par exemple le risque associé à ces bornes. C'est pourquoi on peut améliorer B *
en lui adjoignant des probabilités.
Dans ce cas, un noeud de recherche contient :
- Real Val qui est la meilleure estimation de la vraie valeur du noeud.
- OptVal qui est la valeur optimiste du noeud pour la couleur de celui qui joue.
- Pess Val qui est la valeur optimiste pour la couleur qui ne joue pas.
- OptProb qui est la probabilité qu'un valeur cible peut être atteinte dans le sous-arbre
131
est celle qui demande le moins de conspirateurs pour avoir tmax. On choisit donc
la branche qui a le nombre minimum de conspirateurs, et la plus à gauche en cas
d'égalité.
- pour un noeud Min : On choisit, parmi toutes les branches qui doivent augmenter
leur valeur jusqu'à tmax pour changer la valeur du noeud, celle qui est la plus à
gauche.
Lorsqu'on atteint une feuille celle ci est développée. Comme chaque fils peut amener à
un résultat favorable ou défavorable, les fils sont ordonnés en fonction de leur évaluation.
En mettant les fils les plus favorables en premier, cela accroît les chances que le fils le
plus à gauche soit le meilleur, et favorise donc le choix du fils le plus à gauche dans
l'algorithme. Les valeurs minimax et les nombres conspirants sont alors remontés dans
l'arbre.
Si en développant cette feuille, on augmente sa valeur à tmax, le nombre de conspirateurs pour cette valeur est diminuée de 1, et les autres éléments de cet ensemble de
conspirateurs sont à leur tour développés. Si la valeur du noeud est inférieure à tmax, et
que le noeud développé est un noeud Min, on a alors peut être augmenté le nombre de
conspirateurs à la racine ; dans ce cas le nombre de conspirateurs peut avoir atteint SC ; on
élimine alors tmax de l'ensemble des valeurs possibles à la racine. Pour un noeud Max, si
la valeur est inférieure à tmax, on n'a pas fait évoluer le nombre de conspirateurs de tmax.
6.6 L'algorithme B *
B * (7, 9] cherche à prouver qu'un coup est meilleur que les autres. Il utilise deux
bornes sur la valeur heuristique de la position, une valeur pessimiste et une valeur optimiste. B * se termine lorsqu'il a prouvé que la valeur pessimiste d'un coup est supérieure
aux valeurs optimistes de tous les autres coups. H. Berliner a utilisé B * pour les É checs.
L' idée à la base de l'algorithme B * est qu'il n'est pas nécessaire de connaître les
valeurs minimax exactes des fils de la racine pour trouver le meilleur coup. Si on peut
trouver des limites pour les valeurs minimax de ces successeurs, puis prouver que la limite
inférieure du meilleur successeur est plus grande ou égale aux limites supérieures des
autres coups, cela suffit pour prouver qu'il est le meilleur.
Remonter uniquement les bornes d'évaluation fait perdre des informations vitales,
comme par exemple le risque associé à ces bornes. C'est pourquoi on peut améliorer B *
en lui adjoignant des probabilités.
Dans ce cas, un noeud de recherche contient :
- Real Val qui est la meilleure estimation de la vraie valeur du noeud.
- OptVal qui est la valeur optimiste du noeud pour la couleur de celui qui joue.
- Pess Val qui est la valeur optimiste pour la couleur qui ne joue pas.
- OptProb qui est la probabilité qu'un valeur cible peut être atteinte dans le sous-arbre