132
Rec herc he en meilleur d'abord pour les jeux à deux joueurs
associé à ce noeud.
Dans B * , il y a toujours un des deux joueurs qui essaye de forcer la situation. Pendant
la phase de Sélection, c 'est le joueur. Pendant la phase de Vérification, c 'est son adversaire. Le joueur qui essaye de forcer est appelé le Forceur. Quand on remonte un noeud
pour lequel le Forceur a le choix, on remonte toujours la meilleure alternative. Pour l ' autre
joueur, l ' Obstructeur, c 'est la conjonction des alternatives qui est remontée, puisqu'elles
doivent toutes être réfutées.
On remonte les valeurs comme suit :
- les RealVals sont remontées comme dans un MiniMax.
- les OptVals sont seulement calculées pour les feuilles du Forceur.
- les PessVals sont les OptVals de l ' adversaire.
- les OptProb des fils sont multipliés aux noeuds MIN pour trouver le OptProb du
père. Aux noeuds MAX le OptProb du père est le meilleur OptProb des fils.
L' algorithme est le suivant :
int ValeurCible ;
Selectionner :
tant que (RealVal (MeilleurCoupALaRac ine ) <
}
OptVal ( AutreCoup )) {
ValeurCible =(OptVal ( SecondMeilleur ) +RealVal (Best) ) / 2;
TrouverLeNoeudRacineAvecOptProbMaximal ( );
Descendre le sous arbre en selectionnant
- le fils avec OptProb max aux noeuds MAX
- le fils avec la me illeure RealVal aux noeuds MIN
Calculer RealVal pour chaque fils de la feuille
Si c'est un noeud MAX , calculer OptVal pour chaque fils
remonter les valeurs
Si plus de temp s
sortir de la boucle
ValeurCible = RealVal ( SecondMeilleurCoupALaRacine)-1
Verifier :
while ( RealVal (MeilleurCoupALaRac ine ) >= ValeurCible ) {
selectionner le noeud MIN avec le plus grand OptProb
Descendre le sous arbre en selectionnant
}
- le fils avec le OptProb max aux noeuds MIN
- le fils avec avec le me illeur RealVal aux noeuds MAX
Calculer RealVal pour chaque fils de la feuille
Si c'est un noeud MIN , calculer OptVals pour chaque fils
remonter les valeurs
Si plus de temp s
sortir de la boucle