Un jeu minuscule, résolu de bout en bout
Le morpion tient sur une grille 3×3, mais il cache un vrai sujet d'ingénierie : une IA qui ne perd jamais. Ici, l'adversaire indigo ne suit pas une recette de coups « intelligents » écrite à la main. Il calcule le meilleur coup en explorant l'intégralité des parties possibles à partir de la position courante. C'est le prétexte idéal pour montrer, en quelques dizaines de lignes de JavaScript, un algorithme de décision optimal.
Minimax, ou l'exploration exhaustive de l'arbre de jeu
À chaque tour de l'IA, j'imagine tous les coups jouables, puis toutes les
réponses possibles à ces coups, et ainsi de suite jusqu'à la fin de chaque
partie. Cet arbre de possibilités est parcouru par la fonction
minimax, appelée récursivement. Chaque position terminale
(victoire, défaite ou match nul) reçoit un score : positif quand l'IA gagne,
négatif quand elle perd, nul en cas d'égalité.
Maximiser son score, minimiser celui de l'adversaire
Le nom de l'algorithme vient de sa logique : à son tour, l'IA choisit le coup qui maximise son score ; mais elle suppose qu'en face, le joueur choisira toujours le coup qui le minimise. En remontant l'arbre, chaque nœud hérite donc de la meilleure valeur atteignable pour celui qui joue. Résultat : l'IA anticipe la défense parfaite et ne se laisse jamais piéger. Je pondère aussi les scores par la profondeur, pour qu'elle préfère gagner vite et retarder une défaite inévitable — un détail qui rend son jeu plus naturel.
Pourquoi elle est réellement imbattable
Comme l'exploration est exhaustive, aucune combinaison ne lui échappe : il n'existe pas de coup surprise qu'elle n'ait pas déjà simulé. Le morpion étant un jeu « résolu », le meilleur résultat possible face à un jeu parfait est le match nul. Contre cette IA, vous ne pouvez donc pas gagner — au mieux, arracher l'égalité en ne commettant aucune erreur. C'est frustrant, et c'est exactement le comportement attendu.
Un coût de calcul négligeable, un principe qui passe à l'échelle
Sur une grille 3×3, l'arbre complet ne compte que quelques centaines de milliers de positions au premier coup, et fond à chaque case remplie : le calcul est instantané, sans la moindre optimisation. Ce même principe — modéliser un problème, en explorer les issues, choisir l'option optimale — est au cœur de bien des décisions logicielles sérieuses. Savoir quand une résolution exhaustive suffit, et quand il faut au contraire l'élaguer ou l'approximer, c'est le genre d'arbitrage que j'apporte à vos projets : la juste dose d'algorithme, calibrée sur l'enjeu réel, pour un résultat fiable et prévisible.
