Jeux et adversaires : minimax, élagage alpha-bêta et Monte Carlo tree search

Un jeu comme problème de recherche, l’arbre de jeu, le minimax, l’élagage alpha-bêta, les fonctions d’évaluation et MCTS — sur le morpion, où tout se calcule, et le chemin de Deep Blue à AlphaZero.

14 minutes Matěj Žalmánek 2026-10-15

Série Bases de l’IA Partie 22 sur 52

1. Carte de l’intelligence artificielle : qu’est-ce qui est quoi et comment tout s’emboîte
2. Brève histoire de l’intelligence artificielle : de Turing aux modèles de langage
3. Données, modèle, entraînement, inférence : les notions de base sur un seul exemple
4. Lire la notation mathématique : symboles, indices, sommes et quantificateurs
5. Ensembles et relations : les briques dont sont faites les définitions en IA
6. Fonctions et applications : pourquoi tout modèle d’IA est une fonction
7. Logique et démonstrations : les règles selon lesquelles on raisonne en IA
8. Graphes et arbres : la structure sur laquelle reposent la recherche et les réseaux de neurones
9. Algèbre linéaire pour l’apprentissage automatique : vecteurs, matrices et pourquoi l’IA multiplie surtout
10. Dérivées, gradient et règle de dérivation en chaîne : comment un modèle sait dans quelle direction apprendre
11. Descente de gradient : comment un modèle apprend
12. Qu’est-ce que la probabilité : du lancer de dé aux axiomes de Kolmogorov
13. Probabilité conditionnelle et théorème de Bayes : comment réviser une estimation quand on apprend du nouveau
14. Variable aléatoire et fonction de répartition : une seule fonction qui dit tout de la loi
15. Fonction de densité et fonction de masse : pourquoi une variable continue a une probabilité nulle en chaque point
16. Espérance, variance et covariance : où se situe une loi, quelle est sa largeur et ce qui varie avec quoi
17. Panorama des lois de probabilité : Bernoulli, binomiale, Poisson, uniforme, normale et exponentielle
18. Loi des grands nombres et théorème central limite : pourquoi les moyennes sont si prévisibles
19. Statistique et estimation de paramètres : maximum de vraisemblance, MAP et intervalles de confiance
20. Théorie de l’information : entropie, entropie croisée et divergence KL — d’où viennent les fonctions de perte
21. Recherche dans l’espace d’états : BFS, DFS, UCS et A* en animations
22. Jeux et adversaires : minimax, élagage alpha-bêta et Monte Carlo tree search
23. Satisfaction de contraintes : backtracking, propagation de contraintes et AC-3 sur un sudoku et une carte des régions tchèques
24. Logique et systèmes à base de connaissances : chaînage avant et arrière, résolution et systèmes experts
25. Planification : STRIPS, monde des blocs, heuristiques par relaxation et planification dans les agents IA
26. Recherche locale et recuit simulé : un voyageur de commerce à travers les chefs-lieux de région tchèques
27. Algorithmes génétiques : population, croisement, mutation et sélection sur un sac à dos de randonnée
28. Stratégies d’évolution et programmation génétique : de la règle du cinquième à la loi de Kepler
29. Optimisation par colonies de fourmis : comment une piste de phéromone trouve un chemin court
30. Optimisation par essaim de particules : inertie, expérience propre et expérience de l’essaim
31. Neuroévolution : faire évoluer les poids et la forme des réseaux de neurones, et l’algorithme NEAT
32. Ensembles flous et fonctions d’appartenance : comment écrire « un peu chaud »
33. Logique floue et probabilité : pourquoi « un peu chaud » ne veut pas dire « probablement chaud »
34. Logique floue : t-normes, implications et règles SI–ALORS
35. Commande floue : Mamdani et Sugeno, du ventilateur au pendule inversé sur un chariot
36. Clustering flou : l’algorithme fuzzy c-means et les points entre les clusters
37. Systèmes neuro-flous (ANFIS) : des règles floues qui apprennent à partir des données
38. Chaînes de Markov : matrice de transition, distribution stationnaire et PageRank
39. Modèles de Markov cachés : l’algorithme de Viterbi et le casino malhonnête
40. Réseaux bayésiens : pourquoi l’herbe est mouillée et ce que cela implique pour l’arroseur
41. Le filtre de Kalman : comment estimer, à partir de mesures imprécises, où se trouve une voiture et à quelle vitesse elle roule
42. Types d’apprentissage automatique : supervisé, non supervisé, semi-supervisé et plus
43. Prompts, contexte et RAG : comment donner au modèle les bonnes informations
44. Autoencodeurs variationnels (VAE) : de nouvelles images à partir d’un espace latent continu
45. Réseaux antagonistes génératifs (GAN) : le faussaire contre le détective
46. Modèles de diffusion : comment une image naît du bruit pur
47. Processus de décision markoviens : états, actions, récompenses et équations de Bellman
48. Q-learning et DQN : apprendre la valeur des actions, du tableau au réseau de neurones
49. Policy gradient et PPO : apprendre directement la politique
50. Comment fonctionne un agent IA : un modèle de langage en boucle avec des outils
51. Programmer avec des agents IA : consigne, tests et vérification
52. Évaluation et sécurité des systèmes d’IA : comment mesurer et comment surveiller

Programme complet de la série 52 sur 83 sujets publiés

Dans le labyrinthe de la partie précédente, le petit bonhomme était seul. Le monde ne bougeait pas et chaque action menait là où elle devait mener. Dans un jeu, en revanche, quelqu’un est assis en face de vous et veut exactement l’inverse — et à chacun de vos coups, il répond par celui qui vous fait le plus mal. Chercher un chemin vers le but ne suffit plus : il faut chercher une stratégie qui tienne face à toutes les réponses. Les échecs, les dames et le go ont été pendant des décennies l’étalon de l’intelligence artificielle, et les algorithmes de cette partie sont derrière Deep Blue comme derrière AlphaGo.

Cette partie fait suite à Recherche dans l’espace d’états et à Graphes et arbres.

1. Un jeu comme problème de recherche

Définition — jeu à deux joueurs

Un jeu est un septuplet Γ = (S, s₀, joueur, A, T, K, U), où

• S, s₀, A(s) et T sont les états, l’état initial, les actions et la fonction de transition, comme dans un problème de recherche,
• joueur : S → {MAX, MIN} indique qui a le trait dans un état,
• K ⊆ S est l’ensemble des états terminaux — c’est là que le jeu se termine,
• U : K → ℝ est l’utilité d’un état terminal du point de vue du joueur MAX.

Le jeu est à somme nulle : ce que MAX gagne, MIN le perd, si bien que l’utilité de MIN est −U. Les joueurs jouent à tour de rôle, les coups sont déterministes et tous deux voient l’état entier (information complète).

La différence avec la recherche est fondamentale. La solution n’est plus un chemin — vous ne pouvez pas le choisir, puisqu’un coup sur deux est joué par l’adversaire. La solution est une stratégie : une règle qui dit comment répondre à chaque coup que l’adversaire peut jouer.

2. L’arbre de jeu

Définition — arbre de jeu

L’arbre de jeu est un arbre enraciné dont la racine est s₀ et dont les enfants d’un nœud s sont les successeurs {T(s, a) : a ∈ A(s)}. Les feuilles sont les états terminaux. Les nœuds où MAX a le trait sont dessinés comme des triangles pointe en haut, les nœuds MIN pointe en bas.

Si le jeu a un facteur de branchement b et dure au plus m coups, l’arbre a jusqu’à b^m feuilles.

Le morpion sur une grille de 3 × 3 est un petit jeu, et pourtant son arbre compte 549 946 nœuds et 255 168 feuilles — autant de parties différentes peuvent être jouées. Il n’y a pourtant que 5 478 positions différentes : on arrive à une même position par de nombreux ordres de coups. Aux échecs, le facteur de branchement tourne autour de 35 et une partie dure des dizaines de coups ; Claude Shannon a estimé en 1950 leur arbre à 10¹²⁰ parties. Le go, avec un facteur de branchement d’environ 250, se situe encore de nombreux ordres de grandeur au-delà. On ne parcourt donc l’arbre entier que pour les petits jeux — pour les grands, il faut apprendre quelles branches laisser de côté.

3. Minimax

Définition — valeur minimax

La valeur minimax d’un état s est

• MM(s) = U(s), si s ∈ K,
• MM(s) = max_{a ∈ A(s)} MM(T(s, a)), si joueur(s) = MAX,
• MM(s) = min_{a ∈ A(s)} MM(T(s, a)), si joueur(s) = MIN.

Le coup optimal du joueur MAX dans l’état s est argmax_a MM(T(s, a)).

Le nœud MIN de gauche choisit 4 parmi les feuilles 4, 6 et 9, celui du milieu choisit 2 parmi 2, 7 et 8, celui de droite choisit 3 parmi 5, 3 et 9. MAX, à la racine, choisit alors entre 4, 2 et 3 et joue le coup de gauche, de valeur 4. Remarquez que la branche de droite cache un 9 — mais MAX ne l’atteindra jamais, car MIN jouerait le 3 à sa place.

Théorème — ce que garantit le minimax

Si MAX joue de façon optimale, il obtient au moins MM(s₀) contre n’importe quelle stratégie de MIN. Si MIN joue lui aussi de façon optimale, MAX obtient exactement MM(s₀).

Le minimax parcourt l’arbre en profondeur : temps O(b^m), mémoire O(b · m).

4. Le minimax sur le morpion

Le morpion 3 × 3 est assez petit pour que le minimax parcoure l’arbre entier. Le résultat est connu de quiconque y a joué plus de quelques minutes : la valeur minimax de la grille vide est 0 — si les deux joueurs jouent sans erreur, c’est toujours une partie nulle. Plus intéressant est ce que le minimax dit d’une position concrète. C’est à X (MAX) de jouer, et chaque case libre indique la valeur du coup qui y est joué :

Un seul coup gagne — le centre. X y crée une fourchette : il menace de compléter la ligne du milieu et la diagonale, et O ne peut pas bloquer les deux. Le coup en bas au milieu maintient la partie nulle. Les trois coups restants ont l’air innocents, mais ils perdent : O y répond par sa propre fourchette. Un humain devrait y réfléchir ; le minimax, lui, le calcule tout simplement.

def minimax(board):
    end = winner(board)                 # "X", "O", "draw" ou None
    if end:
        return {"X": 1, "O": -1, "draw": 0}[end]
    values = [minimax(play(board, move)) for move in empty_squares(board)]
    return max(values) if to_move(board) == "X" else min(values)

5. Élagage alpha-bêta

Le minimax parcourt l’arbre entier, même si la moitié en est inutile. Regardez à nouveau la branche du milieu : la première feuille a donné 2. MIN obtiendra donc dans cette branche 2 ou moins — et MAX a déjà la branche de gauche, de valeur 4, assurée. Quelles que soient les deux feuilles restantes, MAX n’ira pas dans la branche du milieu. Il n’a même pas besoin de les regarder.

Définition — alpha-bêta

La recherche en profondeur emporte avec elle deux bornes :

• α — la valeur la plus élevée que MAX s’est déjà assurée quelque part sur le chemin depuis la racine (au départ −∞),
• β — la valeur la plus basse que MIN s’est assurée (au départ +∞).

Dans un nœud MAX, après chaque enfant, on pose v ← max(v, valeur de l’enfant) et α ← max(α, v) ; dans un nœud MIN, de même, v ← min(…) et β ← min(β, v). Dès que α ≥ β, les enfants restants du nœud sont élagués — ils ne sont pas explorés.

Théorème. L’alpha-bêta renvoie à la racine la même valeur que le minimax. Avec le meilleur ordre de coups possible, il n’examine que O(b^m/2) nœuds.

L’alpha-bêta est arrivé au même résultat — MAX joue à gauche et obtient 4 — mais n’a évalué que 6 feuilles sur 9. Dans la branche du milieu, il a élagué deux feuilles juste après le 2, dans celle de droite une après le 3. Le nœud MIN élagué ne porte donc que la borne « ≤ 2 » ou « ≤ 3 » : nous ne connaissons pas la valeur exacte, et nous n’en avons pas besoin.

Sur le morpion, la différence est plus spectaculaire. Le minimax complet depuis la grille vide visite 549 946 positions, l’alpha-bêta avec le même ordre de coups seulement 18 297 — environ trente fois moins — et renvoie le même zéro. L’exposant m/2 du théorème signifie qu’en un même temps, vous voyez deux fois plus profond. C’est pourquoi l’ordre des coups compte tant : les programmes d’échecs essaient en premier les prises et les coups qui étaient bons la fois précédente.

def alphabeta(board, alpha=-inf, beta=inf):
    end = winner(board)
    if end:
        return {"X": 1, "O": -1, "draw": 0}[end]
    maximizing = to_move(board) == "X"
    v = -inf if maximizing else inf
    for move in empty_squares(board):
        h = alphabeta(play(board, move), alpha, beta)
        if maximizing:
            v = max(v, h); alpha = max(alpha, v)
        else:
            v = min(v, h); beta = min(beta, v)
        if alpha >= beta:
            break                          # élagage : le reste de la branche ne changera rien
    return v

6. Profondeur limitée et fonction d’évaluation

Même l’alpha-bêta ne parcourt pas l’arbre des échecs jusqu’à la fin de la partie. Les vrais programmes ne cherchent donc que jusqu’à une profondeur fixe et estiment la position à laquelle ils s’arrêtent.

Définition — minimax à profondeur limitée

Une fonction d’évaluation E : S → ℝ estime MM(s) et coïncide avec U sur les états terminaux. C’est généralement une somme pondérée de caractéristiques de la position : E(s) = w₁f₁(s) + … + w_nf_n(s).

Minimax à la profondeur d : MM_d(s) = E(s), si s ∈ K ou d = 0 ; sinon le max, respectivement le min, des MM_d−1 des successeurs.

La profondeur limitée a son piège : l’effet d’horizon. Quand la recherche s’arrête au milieu d’un échange de pièces — vous venez de prendre la dame, l’adversaire la reprend au coup suivant —, la fonction d’évaluation ne voit que la première moitié et surestime la position. Les programmes s’en protègent en continuant d’explorer les positions « agitées » jusqu’à ce qu’elles se calment. Et comme ils ne savent jamais de combien de temps ils disposent, ils cherchent par approfondissement itératif, vu dans la partie précédente : profondeur 1, 2, 3, … jusqu’à épuisement du temps. Les résultats des passes peu profondes servent en outre d’ordre des coups pour les plus profondes — et l’alpha-bêta élague alors beaucoup plus.

7. Monte Carlo tree search

La fonction d’évaluation des échecs, on l’a peaufinée pendant des décennies. Pour le go, on n’a pas réussi à en écrire une — une position qui a l’air calme peut être perdue vingt coups plus tard. Monte Carlo tree search (MCTS) renonce complètement à la fonction d’évaluation. Au lieu d’estimer la position, il la joue jusqu’au bout : au hasard, de nombreuses fois, et regarde combien de fois cela s’est bien terminé.

Définition — une itération de MCTS

L’arbre croît à partir de la racine s₀. Chaque nœud i retient son nombre de visites n_i et la somme des résultats w_i du point de vue du joueur qui a joué le coup menant à ce nœud (victoire 1, nul ½, défaite 0). Une itération comporte quatre étapes :

1. Sélection — depuis la racine, descends à plusieurs reprises vers l’enfant de plus grande valeur UCT, jusqu’à tomber sur un nœud qui n’a pas encore tous ses enfants.
2. Expansion — ajoute-lui un enfant pour un coup pas encore essayé.
3. Simulation — depuis le nouveau nœud, joue la partie jusqu’au bout par des coups aléatoires, jusqu’à un état terminal.
4. Rétropropagation — pour tous les nœuds du chemin de retour vers la racine, fais n ← n + 1 et ajoute à w le résultat de la partie.

Une fois le temps écoulé, on joue le coup de la racine qui a le plus grand n.

Définition — UCT

Lors de la sélection, parmi les enfants d’un nœud ayant N visites, on choisit l’enfant i de plus grande valeur

UCT(i) = w_i / n_i + c · √(ln N / n_i),

où c > 0 est la constante d’exploration, habituellement √2. Quand le nombre d’itérations augmente, le coup recommandé se rapproche du coup minimax.

Lançons MCTS sur la position que le minimax a résolue plus haut. Les nombres dans les cases sont les visites après 100, 300 et 1000 itérations, et en dessous le résultat moyen pour X :

Après 100 itérations, le centre a 47 visites et les autres coups en ont davantage à eux tous. Après mille, il en a 856, avec un résultat moyen de 0,94 ; le coup nul en bas au milieu a reçu 52 visites, les coups perdants encore moins. MCTS ne connaît pourtant ni la notion de fourchette, ni aucune fonction d’évaluation — seulement les règles et le hasard. Et malgré cela, il a trouvé le même coup que le minimax, qui a dû parcourir tout le reste de l’arbre.

8. De Deep Blue à AlphaZero

• Deep Blue (1997) a battu le champion du monde Garry Kasparov. À l’intérieur, il y avait l’alpha-bêta avec une fonction d’évaluation écrite à la main et un matériel spécialisé capable de traiter environ 200 millions de positions par seconde.
• Chinook jouait aux dames contre des champions du monde dès les années 1990, et en 2007 ses auteurs ont résolu le jeu : ils ont parcouru tant de positions qu’ils ont prouvé qu’une partie sans erreur se termine par une nulle — tout comme le morpion 3 × 3.
• AlphaGo (2016) a battu Lee Se-dol 4 : 1. Il combinait MCTS et réseaux de neurones : un réseau proposait des coups prometteurs (au lieu d’un choix aléatoire), un autre estimait la valeur de la position (au lieu d’une partie aléatoire jouée jusqu’au bout).
• AlphaZero (2017) s’est passé même des parties humaines. Il a appris les échecs, le shogi et le go uniquement en jouant contre lui-même — par apprentissage par renforcement — et a battu dans chacun de ces jeux le meilleur programme existant.
• Les jeux avec hasard et information cachée demandent davantage. Au backgammon, le dé décide, si bien qu’on ajoute à l’arbre des nœuds de hasard qui prennent l’espérance (expectiminimax). Au poker, vous ne voyez pas les cartes de l’adversaire ; le programme Libratus (2017) a pourtant battu des professionnels au poker à deux joueurs.

L’idée « regarde en avant avant d’agir » n’a pas disparu avec les échiquiers. Les agents fondés sur des modèles de langage qui planifient essaient plusieurs variantes de démarche, les évaluent et poursuivent avec la plus prometteuse — simplement, au lieu de coups de pièces, ils choisissent des étapes de résolution.

9. Résumé

• Un jeu à deux joueurs à somme nulle est un problème de recherche dans lequel vous partagez les coups avec l’adversaire ; la solution est une stratégie, pas un chemin.
• Le minimax calcule la valeur à rebours : MAX prend le maximum, MIN le minimum. Le résultat est garanti contre n’importe quel adversaire.
• L’alpha-bêta renvoie la même valeur, mais élague les branches qui ne peuvent pas changer le résultat ; avec un bon ordre des coups, il voit deux fois plus profond.
• Les grands jeux sont explorés jusqu’à une profondeur limitée avec une fonction d’évaluation — et gare à l’effet d’horizon.
• Au lieu d’évaluer une position, MCTS la joue de nombreuses fois au hasard jusqu’au bout et développe l’arbre là où c’est prometteur ; combiné aux réseaux de neurones, il a donné AlphaGo.

Envie de mettre la main à la pâte ? Demandez à un agent IA d’écrire un morpion avec le minimax, puis comptez combien de positions l’alpha-bêta économise quand vous ordonnez les coups du centre vers les bords.

Vous voyez les choses autrement ? Écrivez à support@coden-app.com.