N° 045 · ●●●

Unbeatable tic-tac-toe

Tic-tac-toe against an AI that explores every possible game and never loses. The right exercise to discover minimax, the algorithm behind the first game AIs.

What you'll learn

Explore a game tree with recursion
Pick the best move with minimax
Cut useless branches with alpha-beta pruning

Why this language

Pourquoi un morpion imbattable ? Le morpion est assez petit pour qu'un ordinateur examine toutes les parties possibles. C'est le terrain idéal pour comprendre comment une machine « réfléchit ».

L'idée de minimax : pour chaque coup possible, on imagine la suite. L'IA cherche le score le plus haut, et suppose que vous cherchez le plus bas. On remonte les scores depuis les fins de partie : victoire, défaite ou nul. Le meilleur coup est celui qui garantit le meilleur résultat, même contre un joueur parfait.

L'élagage alpha-bêta évite d'explorer les branches qui ne changeront rien. Le compteur affiche le nombre de positions vraiment examinées.

Pourquoi en JavaScript simple ? Une fonction récursive de dix lignes. Essayez de gagner : au mieux, ce sera un match nul.

How it works

LES LIGNES GAGNANTES

const LIGNES = [[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]];
function gagnant(g) {
  for (const [a, b, c] of LIGNES) if (g[a] && g[a] === g[b] && g[a] === g[c]) return g[a];
  return null;
}

MINIMAX

L'IA (O) cherche le score le plus haut, le joueur (X) le plus bas. On soustrait la profondeur : gagner vite vaut mieux que gagner tard.

function minimax(g, profondeur, tourIA, alpha = -Infinity, beta = Infinity) {
  const w = gagnant(g);
  if (w === 'O') return 10 - profondeur;
  if (w === 'X') return profondeur - 10;
  if (g.every(Boolean)) return 0;          // grille pleine : nul

  let meilleur = tourIA ? -Infinity : Infinity;
  for (let i = 0; i < 9; i++) {
    if (g[i]) continue;
    g[i] = tourIA ? 'O' : 'X';             // on essaie le coup
    const v = minimax(g, profondeur + 1, !tourIA, alpha, beta);
    g[i] = null;                           // on l'annule
    if (tourIA) { meilleur = Math.max(meilleur, v); alpha = Math.max(alpha, v); }
    else { meilleur = Math.min(meilleur, v); beta = Math.min(beta, v); }

L'ÉLAGAGE
L'adversaire n'ira jamais dans cette branche : inutile de continuer.
```
    if (beta <= alpha) break;
  }
  return meilleur;
}
```

LE COUP DE L'IA

On garde tous les coups qui ont le meilleur score, et on en tire un au hasard.

function coupIA(g) {
  let max = -Infinity, coups = [];
  for (let i = 0; i < 9; i++) {
    if (g[i]) continue;
    g[i] = 'O';
    const v = minimax(g, 1, false);
    g[i] = null;
    if (v > max) { max = v; coups = [i]; } else if (v === max) coups.push(i);
  }
  return coups[Math.floor(Math.random() * coups.length)];
}

Pitfalls

PIÈGE 1 : Oublier d'annuler le coup essayé

Pitfall

Mauvais : g[i] = 'O' puis appeler minimax sans remettre la case à null. La grille se remplit de coups fantômes.

Fix

Correct : jouer, explorer, annuler, toujours dans cet ordre. Ou travailler sur une copie.

PIÈGE 2 : Ignorer la profondeur

Pitfall

Mauvais : renvoyer 10 pour toute victoire. L'IA peut retarder une victoire certaine, ou se laisser battre plus vite que nécessaire.

Fix

Correct : 10 moins la profondeur pour gagner, la profondeur moins 10 pour perdre.

PIÈGE 3 : Une IA trop prévisible

Pitfall

Mauvais : toujours jouer le premier meilleur coup trouvé. Toutes les parties se ressemblent.

Fix

Correct : garder tous les coups de même valeur et en tirer un au hasard.

PERSONNALISER

Des niveaux de difficulté : l'IA joue un coup au hasard une fois sur trois en mode facile.
Afficher le score de chaque case libre, pour voir ce que l'IA « pense ».
Un morpion 4 × 4, où il faut limiter la profondeur de recherche.

OPTIMISATION

Gardez les positions déjà calculées dans une Map : la même grille revient par plusieurs chemins.
Utilisez les symétries : une grille tournée de 90 degrés a la même valeur.

VERS REACT

La grille est un useState ; minimax vit dans un fichier pur, sans React.

Le coup de l'IA se joue dans un useEffect quand c'est son tour, avec un petit délai pour l'œil.

Pour une recherche longue, déplacez minimax dans un Web Worker afin de ne pas figer l'interface.

Comments

Loading comments…