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 . Plus
est grand, plus l'arbre de recherche est grand et donc long à explorer
et meilleur (en principe) est le coup joué ;
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 indiquant l'intérêt d'une
configuration quelconque pour Xavier :
peut prendre en
compte le nombre des pièces, leurs positions, etc (plus
est
grand, plus la configuration
est bonne).
Si c'est au tour de Xavier de jouer et que le jeu est dans la
configuration , il est dans l'intérêt immédiat de Xavier de choisir
le coup qui fera passer le jeu dans la configuration
, telle que
est maximale parmi les configurations accessibles en un coup à
partir de
. Si c'est au tour d'Yvette, elle cherchera au contraire
telle que
est minimale.
Un arbre minimax de profondeur 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
se fait aux feuilles à la profondeur
. La fonction
minimax remonte la meilleure valeur jusqu'à la racine ce qui
détermine le meilleur coup à jouer :
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 se fait donc de
façon ascendante, en remontant à partir des feuilles de l'arbre :
est également un attribut synthétisé.