Arbres et algorithme minimax

L'exploration exhaustive d'un graphe de jeu (§ 76) 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 $P$ est grand, plus l'arbre de recherche est grand et donc long à explorer et meilleur (en principe) est le coup joué ; $P$ sera de l'ordre de 4 ou 6 coups pour Othello.

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 22 montre un arbre minimax de profondeur 2. L'évaluation avec la fonction $h$ se fait aux feuilles à la profondeur $P$. La fonction minimax remonte la meilleure valeur jusqu'à la racine ce qui détermine le meilleur coup à jouer :

int minimax(configuration s) {
  if (feuille(s)) return h(s);
  if (type(s) == MAX) return ;
  if (type(s) == 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é.