Morpion Invincible - 6/6 - Aller plus loin : quand l'IA arrête de recalculer pour rien

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

Dernière partie d'une série sur la construction d'un morpion imbattable. Si tu arrives ici directement : sache que l'idée de base, c'est un algorithme minimax qui explore tous les coups possibles pour choisir le meilleur. Je te renvoies bien entendu aux articles précédents pour de plus amples explications.

A ce stade du projet, l'IA fonctionne. Elle est imbattable, elle répond instantanément, elle tourne dans un navigateur sans serveur.

Mais il reste une question légitime : est-ce qu'on peut faire mieux ? Et si oui, pourquoi s'en donner la peine sur un jeu aussi simple que le morpion ?

La réponse courte : oui, on peut faire mieux. Et même si le gain est invisible pour l'utilisateur final - le morpion est trop petit pour que ça compte vraiment - l'exercice vaut le détour. Parce que les techniques en question s'appliquent à des problèmes beaucoup plus grands. Et parce qu'un projet de code, c'est aussi l'occasion de comprendre des idées qu'on réutilisera ailleurs.

Voilà ce qu'on va voir dans ce dernier article : comment ordonner les coups pour aider l'élagage, comment éviter de recalculer la même position deux fois, et comment les deux versions du projet - Python et JavaScript - ont finalement résolu ce problème de façons très différentes.

L'ordre dans lequel on explore les coups, ça compte

Rappel rapide sur alpha-beta : l'idée, c'est d'arrêter d'explorer une branche dès qu'on sait qu'elle ne peut plus changer le résultat. L'algorithme "élague" des sous-arbres entiers.

Mais l'efficacité de cet élagage dépend directement de l'ordre dans lequel on teste les coups. Si on trouve un bon coup en premier, on va pouvoir éliminer beaucoup de branches ensuite. Si on commence par les mauvais coups, on explore beaucoup plus avant de pouvoir couper quoi que ce soit.

En pratique : dans un morpion, tous les coups ne se valent pas intuitivement. Le centre (case 4) est stratégiquement plus fort que les bords. Les coins valent mieux que les cases du milieu des bords. Ce n'est pas une règle absolue, mais c'est une heuristique raisonnable.

Alors au lieu de parcourir les cases dans l'ordre brut (0, 1, 2, 3...), on définit un ordre préféré :

PREFERRED_ORDER = [4, 0, 2, 6, 8, 1, 3, 5, 7]
# centre -> coins -> bords

Et `ordered_legal_moves` retourne simplement les coups disponibles dans cet ordre :

def ordered_legal_moves(board):
	legal = set(get_available_moves(board))
	return [m for m in PREFERRED_ORDER if m in legal]

Et c'est tout. Pas de calcul dynamique, pas de scoring complexe. Juste une liste statique qui reflète une intuition sur la valeur des cases.

Est-ce que ça change grand chose sur un morpion ? Plutôt oui, même si l'arbre est très petit. Mais sur des jeux plus profonds, l'ordre d'exploration peut diviser le nombre de noeuds visités par plusieurs ordres de magnitude. C'est l'une des premières choses qu'on fait dans un vrai moteur d'échecs, par exemple.

Minimax, ce forceur

Deuxième problème : minimax recalcule souvent les mêmes positions. Prenons un exemple simple. La partie commence par le tour de l'IA. Elle explore donc tous les sous-arbres correspondant à chaque case afin de déterminer le meilleur premier coup. Elle joue, l'humain joue à son tour, c'est à nouveau tour. Il reste 7 cases. Elle explore donc tous les sous-arbres correspondant à... 7 cases qu'elle a déjà analysé au coup précédent, comme si elle ne les avait jamais vu.

Et bah oui, il faut prendre des notes quand on n'a aucune mémoire !

La solution : mémoriser les résultats. On garde un dictionnaire où la clé est l'état du plateau (représenté comme une chaîne), et la valeur est le score minimax calculé. Avant de récurser, on vérifie si on a déjà la réponse.

def minimax_ab(board, is_maximizing, alpha, beta, cache: dict):
	if is_terminal(board):
		return evaluate(board)

	legal_moves = ordered_legal_moves(board)

	if is_maximizing:
		key = ''.join(board) + '1'
		if key in cache:
			return cache[key]
		value = float("-inf")
		for move in legal_moves:
			board[move] = AI
			value = max(value, minimax_ab(board, False, alpha, beta, cache))
			board[move] = EMPTY
			alpha = max(alpha, value)
			if beta <= alpha:
				break
		cache[key] = value
		return value
	# idem pour is_minimizing...

La clé inclut `'1'` ou `'0'` pour distinguer les positions identiques selon que c'est au tour du maximiseur ou du minimiseur - une même configuration de plateau peut avoir des scores différents selon qui joue.

Cette technique s'appelle une table de transposition. Dans les moteurs d'échecs sérieux, elle peut stocker des millions d'entrées et représente une part importante des performances. Ici, on s'en sort avec un simple dictionnaire Python.

Le moment où j'ai poussé l'idée plus loin parce qu'on n'est pas là pour faire les choses à moitié ici

Après avoir implémenté la table de transposition dans minimax, j'ai réalisé quelque chose : si le cache mémorise toutes les positions possibles, alors il contient en fait la solution complète du jeu.

Ce n'est plus un cache temporaire - c'est une encyclopédie de tous les états du morpion, avec le score optimal associé à chacun.

Et si c'est une encyclopédie, pourquoi ne pas la sauvegarder une bonne fois pour toutes ?

# generate_table.py
from engine import minimax_pure, create_board
import json

table = {}
board = create_board()
minimax_pure(board, True, table) # minimax_pure remplit `table`
minimax_pure(board, False, table)

with open("table.json", "w") as json_file:
	json.dump(table, json_file)

On utilise minimax_pure et non la version avec alpha-beta, parce que cette fois-ci, on VEUT explorer la totalité de l'arbre. On lance ce script une seule fois. Il explore tout l'arbre du morpion, remplit le dictionnaire, et le sérialise en JSON. Résultat : un fichier de quelques centaines de kilooctets qui contient toutes les réponses.

Ensuite, jouer le meilleur coup devient une simple consultation :

def read_best_move(board):
	legal_moves = ordered_legal_moves(board)
	best_move = legal_moves[0]
	best_score = float("-inf")

	for move in legal_moves:
		board[move] = AI
		if is_terminal(board):
			score = evaluate(board)
		else:
			score = table[''.json(board) + '0']
		board[move] = EMPTY
		if best_score < score:
			best_score = score
			best_move = move
	return best_move

Pas de récursion. Pas de noeuds visités. Juste une lecture dans un dictionnaire. Si ça, c'est pas de l'optimisation.

Les fonctions `minimax_pure` et `minimax_ab` sont toujours dans le code - elles servent de référence pédagogique et permettent de comprendre comment la table a été générée. Mais en production, Python n'y touche plus.

Et côté JavaScript, j'ai fait autre chose

La version web aurait pu charger `table.json` et faire la même chose. Techniquement, c'est faisable.

Mais je ne l'ai pas fait - et ce n'est pas un oubli.

Le navigateur fait tourner minimax avec alpha-beta sans difficulté visible. Le morpion est un jeu avec un arbre de décision relativement petit - l'algo répond en quelques millisecondes même en JS non optimisé. Charger un JSON externe pour remplacer, ça n'aurait rien apporté à l'expérience utilisateur (qui est la raison d'être de cette version).

En revanche, la version web a quelque chose que Python n'a pas : un curseur de difficulté.

function getAiMove(board, difficulty) {
	nodesVisited = 0;
	let tirage = Math.random() * 10;
	if (difficulty > tirage) {
		return chooseBestMove(board); // minimax
	} else {
		return getRandomMove(board); // aléatoire
	}
}

A chaque coup, on tire un nombre entre 0 et 10. Si la difficulté choisie (entre 1 et 10) est supérieure au tirage, l'IA joue parfaitement. Sinon, elle joue au hasard. Plus la difficulté est haute, plus l'IA joue bien - mais jamais de façon garantie, ce qui donne une sensation de progression plutôt qu'un mur impénétrable.

C'est une décision de product design autant que de code : une IA toujours parfaite n'est pas forcément agréable à jouer. L'imprévisibilité contrôlée, c'est plus intéressant pour l'utilisateur.

Résultat : deux implémentations aux mêmes racines mais qui ont divergé. Python utilise une lookup table précalculée, JS calcule à la volée avec un biais probabiliste. Ce n'est pas une incohérence - ce sont deux contextes différents qui ont appelé deux solutions différentes.

Ce qui aurait mérité plus d'attention (la partie où je m'auto-flagelle)

Rien ni personne n'est parfait, c'est bien connu. (Mais le mieux est l'ennemi du bien, on ne le dira jamais assez)

Il aurait été mieux d'inclure un tableau comparatif propre : minimax pur VS minimax + cache VS lookup table, nombre de noeuds, temps de calcul. Le code de benchmark existe (`benchmark.py`), mais je n'ai pas produit de résultats assez propres pour les publier. Un biais de "c'est trop petit pour que ça compte" qui m'a desservi...

`engine.py` fait trop de choses. Le fichier contient à la fois la logique du jeu, les deux variantes de minimax, le mécanisme de lookup table, et une petite API pour le CLI. Ce serait plus propre en plusieurs modules : `game.py`, `minimax.py`, `lookup.py`. Je ne l'ai pas refactorisé parce que la série d'articles était organisée autour de ce fichier - le découper aurait cassé les références. Compromis assumé, mais compromis quand même.

La couverture de tests est incomplète. Les fonctions de bases sont testées, le premier coup optimal est validé. Mais `read_best_move` n'est pas testée en isolation, et la difficulté JS ne l'est pas du tout. Pour un projet pédagogique, c'est acceptable. Pour un projet en production, non.

La suite logique

Le morpion est un jeu résolu. Maintenant que l'architecture est en place - moteur de jeu, algorithme de décision, interface - la vraie question est : qu'est-ce qu'on peut faire avec des jeux plus intéressants ?

Puissance 4 : des arbres beaucoup plus profonds, où minimax seul devient inutilisable et où les optimisations deviennent vraiment nécessaires. Move ordering dynamique, tables de transposition avec Zobrist hashing, profondeur limitée avec fonction d'évaluation heuristique. Je vous renvoie naturellement vers le travail d'une estimée collègue qui s'est essayée (avec succès) au puissance 4.

Les échecs : un ordre de magnitude au-dessus en complexité. Les mêmes idées, poussées à l'extrême. Stockfish, le meilleur moteur open source, implémente tout ce qu'on a vu ici - mais à une échelle et avec une sophistication sans commune mesure.

AlphaZero : une rupture conceptuelle. Pas de minimax exhaustif, pas de table de transposition explicite - un réseau de neurones qui apprend à évaluer les positions et à guider la recherche. Le papier original de DeepMind (2017) est accessible et remarquablement lisible pour ce qu'il décrit.

Bilan

Ce projet a commencé par une question volontairement naïve : est-ce qu'un morpion imbattable, c'est vraiment compliqué à coder ?

La réponse, après six articles : non, mais il y a beaucoup à apprendre en chemin. La modélisation d'un problème de décision, la logique de minimax, l'impact concret de l'élagage, le passage d'un prototype CLI à une interface utilisable - chaque étape a une vraie substance.

Ce qui m'intéresse le plus, en regardant en arrière, c'est moins le morpion lui-même que les questions qu'il permet de poser proprement : comment on représente un état, comment on explore un espace de possibles, comment on choisit entre calculer et mémoriser. Des questions qui reviennent dans des contextes très différents.

N'hésite pas à faire un tour sur GitHub pour faire tourner ce petit jeu !