On veut concevoir un jeu qui se joue tour par tour et on souhaite pouvoir faire jouer la machine. La machine doit donc choisir ses coups et, autant que possible, jouer correctement pour rendre le jeu plus intéressant.

Il s'agit donc de trouver une méthode d'évaluation pour la machine, pour qu'elle sache si tel coup est meilleur qu'un autre et lequel elle devrait jouer.

Au lieu d'évaluation, on pourra parler de score.

Au morpion le premier joueur fait des O, le second joueur fait des X.

Chacun place à son tour, soit O, soit X dans une grille 3×3, un seul symbole par case.

Si un joueur arrive à créer un alignement de 3 symboles identiques, il a gagné.

Si la grille devient pleine sans qu'aucun alignement ne soit réalisé, c'est un match nul (c'est la situation la plus courante au morpion)

Ci-dessous, une partie gagnante pour O.

Supposons que ce soit à O de jouer dans la situation ci-dessous

O peut jouer à 3 positions et on peut donc s'intéresser au résultat dans les 3 cas.

Les deux positions de gauche ne sont pas gagnantes. Difficile pour la machine de dire si elles sont bonnes ou non. En revanche, le position de droite est gagnante. C'est forcément une bonne position qui doit être récompensée.

On décide par exemple que la victoire vaut 100. Quand nous allons évaluer si une position est bonne ou non, 100 sera le score d'une position victorieuse.

Ci-dessus, deux autres cas de positions finales :

• O achève sur un match nul, cette position a un score de 0.
• X gagne. Du point de vue de O, cette position a un score de -100.

Bien sûr, un algorithme qui ne permettrait de juger que des positions finales serait peu intéressant. Nous devons trouver le moyen d'évaluer les positions non finales.

À partir d'une position, nous allons déployer un arbre des possibles.

Dans cet arbre, seul les nœuds terminaux, les feuilles, peuvent recevoir une évaluation.

Mais pour certains nœuds, comme sur la ligne du haut,

On voit que le destin obligatoire du nœud de gauche et d'aboutir à celui de droite dont le score est 0. Il est donc naturel d'associer le score 0 au nœud de gauche et alors on peut attribuer les évaluations suivantes

Au moment de jouer, il est naturel de penser que X choisira le coup le plus avantageux pour lui. Il cherchera donc à minimiser le score pour O. Par exemple, dans l'alternative du haut, X choisira celle qui l'amène à un score de 0 ce qui est préférable que 100 (le score est calculé du point de vue de O)

À retenir : on part du principe que X fait toujours le choix qui minimise le score.

Puisque O peut anticiper que X choisira la position du haut qui vaut 0, ce chemin peut être considéré comme obligatoire et donc il est naturel d'associer le score 0 à la position d'origine (à gauche).

De la sorte, on peut faire remonter les scores d'un étage vers les nœuds parents.

Maintenant que O peut évaluer les scores de tous les choix disponibles, il est naturel de considérer qu'il doit choisir le score le plus élevé, donc le chemin du haut. Le chemin s'impose donc comme un destin obligatoire à partir du nœud initial, ce qui permet d'évaluer le score du nœud initial à 0.

Pour faire son évaluation, la machine a besoin de dérouler en suivant tous les coups possibles.

• La machine doit donc avoir la possibilité de créer des parties virtuelles, clones de la partie en cours, pour pouvoir les mener jusqu'au bout, comme si elle imaginait ces parties dans « sa tête ».
• Si la machine joue contre elle-même, ses coups seront entièrement déterminés et elle jouera toujours la même partie.
• Créer toutes les parties possibles peut nécessiter beaucoup de ressources en temps et en mémoire. Un tel calcul peut-être impossible. On sait par exemple qu'aux échecs ou au go, un tel calcul n'est pas faisable par une machine car le nombre de coups possibles est beaucoup trop grand.

Pour jouer, la machine doit disposer des aptitudes suivantes

• déterminer les coups possibles à partir d'une position,
• décider si la partie est terminée et qui gagne le cas échéant,
• créer un clone d'une situation de jeu afin d'envisager les coups suivants,
• déployer un arbre des positions possibles à partir d'une position donnée, soit jusqu'au bout soit jusqu'à une certaine profondeur,
• évaluer le score des nœuds terminaux de l'arbre, soit par une évaluation victoire / défaite comme celle vue dans le cas du morpion, soit une évaluation estimant un score pour une position de jeu non finale,
• faire remonter les scores dans l'arbre depuis les feuilles jusqu'à la racine en appliquant la règle suivante :
  • choisir le score minimum parmi les nœuds enfants quand il s'agit d'un coup de l'adversaire,
  • choisir le score maximum parmi les nœuds enfants quand il s'agit d'un coup de la machine.

C'est d'ailleurs l'origine du nom min-max de l'algorithme.

Si on a le temps…

• Le morpion
• Le nim
• Othello
• Puissance 4
• …