Morpion Invincible - 4/6 - Alpha-beta ou comment l'IA arrête de réfléchir pour rien

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

La menace fantôme

Minimax fonctionne. L'IA est imbattable. Tout va bien dans le meilleur des mondes.

Sauf que si tu mesures ce qui se passe sous le capot, tu tombes sur un chiffre un peu gênant : sur un plateau vide, minimax visite plus de 500 000 noeuds avant de jouer son premier coup.

500 000 positions analysées. Pour un jeu de morpion. Sur une grille 3x3.

C'est le moment où on réalise que "ça marche" et "c'est efficace" sont deux choses très différentes.

L'arbre qui explose

Pour comprendre pourquoi, il faut visualiser ce que minimax fait réellement.

Au premier coup, l'IA a 9 cases disponibles. Pour chacune, elle simule tous les coups possibles de l'adversaire - soit 8 options. Pour chacune de ces 8 options, elle simule à nouveau tout ses coups, soit 7. Et ainsi de suite jusqu'au bout de la partie.

Dans le pire des cas, ça donne en théorie 9! = 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 362 880 parties simulées, soit autant de feuilles à notre arbre. Si on ramène cela au nombre de nœuds explorés, ça nous donne :

Profondeur 1 :	9 noeuds
Profondeur 2 : 	72 noeuds (9x8)
Profondeur 3 : 	504 noeuds (9x8x7)
...
Profondeur 9 :	362 880 noeuds (9!)
				--------------
Total max :		986 409 noeuds

En pratique, beaucoup de parties se terminent avant la case 9, donc on descend plutôt autour de 500 000 noeuds explorés en comptant tous les états intermédiaires. C'est gérable pour un morpion. Mais imaginez la même logique sur un jeu d'échecs - l'arbre explose littéralement. C'est pour ça que minimax pur, tel quel, ne passe pas à l'échelle.

Le problème n'est pas l'algorithme en lui-même, mais le fait qu'il explore bêtement des branches qu'il n'a aucune raison d'explorer.

La question qu'on aurait dû se poser plus tôt

Imaginez que vous jouiez aux échecs, par exemple, au hasard, sur chess.com. Vous réfléchissez à un coup, vous explorez mentalement la suite, comme tout bon joueur qui se respecte... et au bout de trois coups, vous réalisez que cette séquence vous fait perdre la reine !

Que faites-vous ? Vous continuez à explorer ce scénario plus avant ? Bien sûr que non ! Vous l'abandonnez immédiatement et vous passez à autre chose.

Minimax, lui, continue. Il analyse jusqu'au bout, même quand il sait que c'est déjà tout pourri.

L'alpha-beta pruning sert précisément à éviter ça : arrêter d'explorer ce qu'on sait déjà être inutile.

Alpha et Beta : deux gardes-fous

L'algorithme alpha-beta ajoute deux paramètres à Minimax :

• Alpha : le meilleur score que le joueur MAX a trouvé jusqu'ici. Il ne peut qu'augmenter.

• Beta : le pire score que le joueur MIN a trouvé jusqu'ici. Il ne peut que diminuer.

A chaque noeud, on vérifie : est-ce que continuer à explorer peut encore changer la décision finale ?

Si alpha ≥ beta -> non. On coupe. On passe à la suite.

Un exemple concret (sans maths)

Disons que MAX explore une branche et trouve un score de +1 (il gagne).

Il commence ensuite à explorer une autre branche. Dans cette branche, MIN joue, et trouve un coup qui donne -1 (MAX perd).

MIN sait qu'il peut forcer ce résultat. MAX sait donc que cette branche vaut au mieux -1 pour lui.

Mais MAX a déjà +1 ailleurs. Pourquoi s'acharner sur une branche qui ne peut pas faire mieux que -1 ?

-> On coupe. On ignore tout ce qui reste dans cette branche. On passe à la suivante.

L'impact concret : les chiffres

Voici ce que ça donne sur le premier coup d'une partie (plateau vide) :

Algorithme		Noeuds visités		Temps
Minimax pur		~ 549 000			~ 120 ms
Alpha-beta		~ 83 000				~ 15 ms

85% de noeuds en moins. 8x plus rapide.

Et ça, c'est sur un morpion 3x3. Sur un jeu plus complexe, l'écart est encore plus brutal.

Ce que ça change (et ce que ça ne change pas)

Alpha-beta ne change pas le résultat. L'IA prend exactement la même décision qu'avec Minimax pur.

Ce qu'elle change :

• La quantité de travail pour y arriver

• Le temps de calcul

• La scalabilité si on voulait aller plus loin (grille 4x4, par exemple)

C'est une optimisation pure : même sortie, moins d'effort.

Le code, en deux mots

Dans Minimax, on ajoute deux paramètres `alpha` et `beta`, initialisés respectivement à -∞ et +∞.

A chaque appel récursif :

1. On met à jour alpha (si c'est le tour de MAX) ou beta (si c'est MIN)

2. On vérifie si `alpha >= beta`

3. Si oui -> on coupe (`break` ou `return`)

A peine 8 petites lignes de modification sur un Minimax existant. Rapport effort/impact imbattable.

Conclusion

Minimax est correct. Alpha-beta est intelligent.

La différence entre les deux, c'est celle entre quelqu'un qui lit tous les livres d'une bibliothèque pour répondre à une question... et quelqu'un qui s'arrête quand il a trouvé la réponse.

Dans le prochain article, on sortira du terminal. On construira une vraie interface pour jouer - et on verra ce que change l'UX, même sur un projet exclusivement pédagogique.