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 :
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.
Au lieu de mener l'arbre jusqu'à la fin de partie, on peut se contenter de le mener jusqu'à une certaine profondeur. Par exemple, aux échecs, la machine calculera tous les prochains 10 coups. Mais alors, la machine devra évaluer une position non finale.
Cette évaluation sera approximative. On essaiera de déterminer ce qui fait une bonne position et d'attribuer un score.
Pour jouer, la machine doit disposer des aptitudes suivantes
C'est d'ailleurs l'origine du nom min-max de l'algorithme.
Si on a le temps…