Comment réfléchit une IA imbattable au morpion : Minimax et alpha-bêta, avec des chiffres réels

01Pourquoi vous ne pouvez pas la battre

Le morpion tient sur une serviette en papier, et pourtant une partie peut se dérouler de 255 168 façons différentes, coup après coup, jusqu’à une victoire ou une grille pleine. Une IA qui veut être sûre de ne jamais perdre doit tenir compte de chacune d’elles.

Quand les deux camps jouent parfaitement, toutes les parties finissent par une égalité. C’est le plafond. Une IA imbattable n’a aucune ligne perdante, et le mieux que vous puissiez obtenir contre elle est une égalité. Minimax garantit ce résultat : avant chaque coup, l’IA examine toutes les suites possibles de la partie et joue le coup dont le pire cas est le meilleur pour elle.

Dans ma version, vous jouez les O et vous commencez ; l’IA joue les X. Tout ce qui suit part de cette configuration.

02Toutes les parties, jusqu’au bout

Minimax voit le jeu comme un arbre. La grille actuelle est la racine, chaque case libre est une branche et les feuilles sont des parties terminées. Pour choisir un coup, l’IA :

1. Liste toutes les cases libres.
2. Joue chacune d’elles dans sa tête, vous laisse répondre par toutes les réponses possibles, et continue jusqu’à ce que chaque ligne soit terminée.
3. Note chaque partie terminée et fait remonter les scores dans l’arbre. À son tour, l’IA garde le maximum ; au vôtre, elle suppose que vous choisissez le minimum.
4. Joue la case dont le score est arrivé tout en haut. L’étape 3 porte tout l’algorithme. L’IA suppose que vous jouez toujours votre meilleure réponse, donc le score qu’elle retient est un score que vous ne pouvez plus faire baisser.

03Noter la fin d’une partie

Les feuilles ont besoin d’un nombre. Mon jeu utilise l’échelle la plus simple possible :

Un raffinement courant retire la profondeur du score (10 - depth pour une victoire, depth - 10 pour une défaite). L’IA préfère alors une victoire rapide à une victoire lente et, quand une défaite est inévitable, prend le chemin le plus long pour y arriver. Face à un humain, elle paraît plus affûtée. La possibilité qu’elle perde reste la même.

04Minimax en une seule fonction récursive

winner(board) renvoie 'X', 'O' ou null, et emptyCells(board) liste les cases libres :

function minimax(board, player, alpha = -Infinity, beta = Infinity) {
  const w = winner(board);
  if (w === "X") return 10;   // l’IA a gagné
  if (w === "O") return -10;  // vous avez gagné
  const cells = emptyCells(board);
  if (cells.length === 0) return 0; // égalité
 
  let best = player === "X" ? -Infinity : Infinity;
  for (const cell of cells) {
    board[cell] = player;
    const score = minimax(board, player === "X" ? "O" : "X", alpha, beta);
    board[cell] = null;
 
    if (player === "X") { best = Math.max(best, score); alpha = Math.max(alpha, best); }
    else                { best = Math.min(best, score); beta  = Math.min(beta, best); }
    if (beta <= alpha) break; // élagage : l’autre camp n’autorisera jamais cette ligne
  }
  return best;
}

Retirez alpha, beta et le break, et vous obtenez le Minimax simple : il est correct, et il explore chaque branche. Ces quelques ajouts forment l’élagage alpha-bêta. Pour choisir un coup, l’IA lance cette fonction sur chaque case libre, garde alpha d’une case à l’autre et joue la première case qui obtient le meilleur score.

05Couper l’arbre : alpha-bêta

Alpha-bêta transporte deux nombres dans l’arbre. alpha est le meilleur score dont l’IA est déjà sûre ; beta est le meilleur score dont vous êtes déjà sûr. Dès qu’une branche est prouvée moins bonne pour un camp qu’une option qu’il possède déjà, la recherche abandonne le reste de cette branche, car ce camp ne mènerait jamais la partie par là.

Un cas concret : l’IA a déjà trouvé un coup qui garantit l’égalité (alpha = 0). Elle commence à examiner un deuxième coup, et la première réponse qu’elle teste vous donne la victoire (-10). Comme vous choisirez le minimum, ce deuxième coup vaut au plus -10, ce qui est déjà pire que l’égalité qu’elle a en main. L’IA arrête d’examiner vos autres réponses à ce coup.

06Même coup, une fraction du travail

J’ai compté les positions visitées par chaque version pour la première décision de l’IA, après chacun de vos 9 coups d’ouverture possibles :

Selon votre ouverture, alpha-bêta fait de 13 à 26 fois moins de travail pour la même décision. Depuis une grille vide, l’écart est plus grand : 549 946 positions pour Minimax simple contre 18 297 avec alpha-bêta.

L’ordre dans lequel on essaie les cases décide de la part coupée. Alpha-bêta élague le plus quand le meilleur coup arrive en premier, ce qui explique la largeur de la fourchette ci-dessus : certaines ouvertures placent par hasard de bonnes réponses en début de liste. Essayer le centre d’abord, puis les coins, puis les bords ramène toutes les ouvertures entre 1 521 et 1 982 positions, et la grille vide à 7 275. L’IA ne perd toujours jamais, mais quand plusieurs cases ont le même meilleur score, elle peut en choisir une autre.

Sur une grille de 3×3, rien de tout cela n’est nécessaire pour la vitesse : Minimax simple répond instantanément dans un navigateur. Cela compte dès que le jeu grandit. Sur une grille de 4×4 ou au Puissance 4, l’arbre complet est beaucoup trop grand pour être exploré, et l’élagage alpha-bêta associé à une limite de profondeur rend possible une IA forte.