Morpion Invincible - 3/6 - Minimax

Lien vers le repo du projet : https://github.com/vohorgeez/Morpion-invincible

Bon, maintenant que l'on sait comment traduire le jeu de morpion en structure de données, reste le coeur du sujet : comment faire pour créer une IA imbattable ?

Le plus simple, pour répondre à cette question, c'est souvent de se demander : quelle stratégie j'adopterais, si j'avais une puissance de calcul illimitée ?

Quand tu joues au morpion, tu anticipes peut-être 2 ou 3 coups à l'avance. Un joueur, 4 ou 5. Un machine ? Elle peut simuler tous les coups possibles, jusqu'à la fin de la partie. Chaque branche, chaque scénario, chaque issue.

C'est exactement ce que fait Minimax.

L'idée est simple : on construit mentalement un arbre de toutes les parties possibles. A chaque noeud, c'est au tour d'un joueur de choisir. Et chaque joueur joue de façon optimale - l'IA cherche à maximiser ses chances de gagner, et à minimiser les chances de l'humain.

Résultat : l'IA ne choisit jamais un coup au hasard. Elle choisit le coup qui mène au meilleur résultat quoi que tu joues en face.

C'est pour ça qu'elle est imbattable.

Comment ça marche concrètement ?

Données incomplètes et non-contractuelles sur l'image, cela va sans dire, c'est pour illustrer...

Imaginez qu'on est en fin de partie. Il reste 3 cases vides. L'IA doit choisir où jouer.

Elle va simuler chaque coup possible. Pour chacun, elle simule la réponse du joueur. Pour chacune des réponses du joueur, elle simule son propre coup suivant. Et ainsi de suite, jusqu'à ce que la partie soit terminée (dans la simulation).

A chaque fin de partie simulée, on attribue un score :

• +1 si l'IA gagne

• -1 si l'humain gagne

• 0 si match nul

Maintenant, la question intéressante : comment ces scores remontent jusqu'au choix initial ?

C'est là que "max" et "min" entrent en jeu.

Quand c'est au tour de l'IA, elle choisit le coup qui maximise le score. Quand c'est au tour du joueur, l'algorithme suppose que ce dernier va choisir le coup qui minimise le score - c'est-à-dire le pire pour l'IA.

En remontant l'arbre de cette façon, coup par coup, le score final de chaque branche se propage jusqu'à la racine. L'IA joue le coup dont la branche a le meilleur score remonté.

Et le plus merveilleux : tout ça en quelques millisecondes...

Pourquoi c'est imbattable ?

Parce que l'algorithme ne fait aucune hypothèse optimiste sur le joueur. Il suppose toujours qu'il joue parfaitement. Donc si une victoire est possible pour lui, il la voit venir - et il l'évite.

Le seul cas où l'IA ne peut pas gagner, c'est quand mathématiquement, avec deux joueurs parfaits, la partie finit en nul. Ce qui est le cas au morpion.

Imbattable ne veut pas dire "gagne toujours". ça veut dire "ne perd jamais".

Ce que ça donne dans le code

Pour donner une idée, voici ce qu'affiche le debug quand l'IA réfléchit après que le joueur ait joué au centre :

Coup analysé : 0
Score du coup 0 : 0
Coup analysé : 2
Score du coup 2 : 0
Coup analysé : 6
Score du coup 6 : 0
Coup analysé : 8
Score du coup 8 : 0
Coup analysé : 1
Score du coup 1 : -1
Coup analysé : 3
Score du coup 3 : -1
Coup analysé : 5
Score du coup 5 : -1
Coup analysé : 7
Score du coup 7 : -1
Meilleur coup trouvé : 0 (score = 0)
[IA] joue en 0
[IA] Noeuds explorés : 6138

Les coins donnent tous un score de 0 - nul garanti si les deux jouent bien. Les bords donnent -1 - l'IA risque de perdre. Elle choisit donc un coin.

6138 noeuds explorés pour un seul coup. Et ça, c'est avec l'optimisation alpha-beta. Sans elle ? On en parle dans l'article suivant...