36
Minimax, Alpha-Bêta et heuristiques associées
2.14.9 Quiescence
Pour aj outer la recherche de quiescence au jeu du virus, il faut tout d'abord modifier la
classe Virus de façon à ce qu'elle puisse sélectionner les coups de quiescence. On aj oute
donc dans la classe Virus une fonction qui teste le nombre de cases modifiées par un coup
et une fonction qui renvoie la liste des coups qui modifient plus de cinq cases :
in t n bCasesModi fiees (Coup & m) {
int nb = 1 .
'
char autre = adversaire (m. couleur );
int debutx ·- m. x - 1 '
finx = m. x + 1 ;
int debuty = m. y - 1 '
fin y = m. y + 1 .
'
if ( debutx < 0) debutx = o· '
if ( debuty < 0) debuty = O;
if (fin X > Taille - 1) finx = Taille
1 ;
if (fin y > Taille - 1) fin y = Taille
1 .
'
for (int i = debutx ; i <= finx ; i++)
fo r (in t j = debuty ; j <= finy ; j ++)
if (damier [ i ] [ j ] -- autre )
nb++;
return nb ;
}
list coupsQuiescence (char couleur ) {
list liste , 1 = coupsLegaux (couleur );
for (list :: iterator it = l.begin ();
}
i t ! = 1 . end (); ++ i t )
if (nbCasesModifiees (* it) > 4)
liste . push_back (* it );
return liste ;
Une fois ces fonctions aj outées, on écrit une fonction qui fait une recherche AlphaBêta uniquement pour les coups de quiescence et on modifie I' Alpha-Bêta pour qu'il
appelle la fonction de quiescence à la place de lévaluation statique :
int quiescence ( int alpha , int beta , char joueur ) {
1 i s t coups = virus . coupsQuiescence (joueur );
if (coups . empty ())
return virus . evaluation (joueur );
char autre = virus . adversaire (joueur );
fo r (list :: iterator it = coups .begin ();
it != coups .en d(); ++ it ) {
virus . joue (* Ît );
int eval =- quiescence (-beta , -alpha , autre );
virus . dejoue (* it );