Graphes de jeu et arbres minimax

Certains jeux (échecs, Othello, Awélé) peuvent être décrits à l'aide d'un graphe dont les sommets sont les configurations possibles (positions des pièces, etc) du jeu et les arcs sont les coups permis par les règles du jeu ; on notera $s\to s'$ s'il existe un coup changeant la configuration s en s'. On s'intéressera aux jeux à deux joueurs à information complète : on suppose qu'ils jouent à tour de rôle, que chacun connaît la configuration du jeu et que le hasard n'intervient pas.

Une configuration est finale si aucun coup n'est permis à partir de celle-ci. Dans un certain nombre de jeux, une configuration finale est perdante pour le joueur qui s'y trouve. Si l'on connaît l'intégralité du graphe du jeu, on peut décider de proche en proche, à partir des configurations finales, si une configuration est gagnante ou perdante, en appliquant les deux règles suivantes :

• une configuration est gagnante s'il existe un coup menant à une configuration perdante,
• une configuration est perdante si tout coup mène à une configuration gagnante.

Un jeu est à somme nulle si les gains d'un joueur représentent exactement les pertes de l'autre joueur. Supposons maintenant que la perte du joueur qui se trouve dans la configuration finale s est donnée par l'entier $p_f(s)\in \mathbf{Z}$. Appelons les deux joueurs Xavier et Yvette : si Xavier perd p_f(s), Yvette perd -p_f(s), c'est-à-dire gagne p_f(s). Toujours si l'on connaît l'intégralité du graphe du jeu, on peut étendre p_f en une fonction p définie pour toutes les configurations, par les règles suivantes :

• si s est une configuration finale, p(s)=p_f(s),
• si s est une configuration gagnante, $p(s)=\max_{s\to s'\ \mathrm{perdante}}p(s')$,
• si s est une configuration perdante, $p(s)=\min_{s\to s'\ \mathrm{gagnante}}p(s')$.

La fonction p est une évaluation complète du jeu, pour des joueurs cherchant à maximiser leurs gains et minimiser leurs pertes. La construction de p se fait donc de façon ascendante, en remontant à partir des feuilles du graphe : chaque noeud s se trouve affecté d'un attribut p(s), qui est synthétisé , c'est-à-dire calculé de façon ascendante à partir des attributs p(s') des successeurs s' de s.

      

L'exploration exhaustive d'un graphe de jeu n'est généralement pas faisable, du moins pour les jeux << intéressants >>. La plupart des joueurs ne décident pas du coup à jouer en remontant à partir des configurations finales, mais en descendant à partir de la configuration courante. Au lieu de construire le graphe du jeu, on va travailler avec un arbre de recherche qui représente une exploration de ce graphe jusqu'à une certaine profondeur P. Plus Pest grand, plus l'arbre de recherche est grand et donc long à explorer et meilleur (en principe) est le coup joué.

Au lieu de mesurer la perte du joueur en configuration finale, on utilise une mesure heuristique h indiquant l'intérêt d'une configuration quelconque pour Xavier : h peut prendre en compte le nombre des pièces, leurs positions, etc. (plus h(s) est grand, plus la configuration s est bonne). Si c'est au tour de Xavier de jouer et que le jeu est dans la configuration s, il est dans l'intérêt immédiat de Xavier de choisir le coup qui fera passer le jeu dans la configuration s', telle que h(s') est maximale parmi les configurations accessibles en un coup à partir de s. Si c'est au tour d'Yvette, elle cherchera au contraire s' telle que h(s') est minimale.

Un arbre minimax de profondeur P a pour racine la configuration courante et des noeuds qui sont, par niveaux alternants, des noeuds de maximisation et des noeuds de minimisation. La figure 2.27 montre un arbre minimax de profondeur 2. L'évaluation avec la fonction h se fait aux feuilles à la profondeur P.

 

Nous supposons que le type Configuration offre les méthodes :

• boolean estFeuille(), qui teste si la configuration est finale ;
• int type() qui détermine le type, minimisant ou maximisant de la configuration, sous forme d'une des deux constantes de classe Configuration.MIN ou Configuration.MAX ;
• Iterator succs(), qui retourne un itérateur sur les configurations accessibles en un coup ;
• int h(), qui retourne une évaluation heuristique d'une configuration en position de feuille.

La fonction minimax() remonte la meilleure valeur jusqu'à la racine ce qui détermine le meilleur coup à jouer :

static int minimax(Configuration s) {
if (s.estFeuille()) return s.h();
switch(s.type()) {
case Configuration.MAX :
return ;
case Configuration.MIN :
return ;
}
}

La fonction minimax() est une évaluation heuristique du jeu, pour des joueurs cherchant à maximiser leurs gains et minimiser leurs pertes. La construction de minimax(), comme celle de p se fait donc de façon ascendante, en remontant à partir des feuilles de l'arbre : h(s) est également un attribut synthétisé .