Le Morpion et l’apprentissage automatique : comment une machine apprend à jouer sans qu’on lui dise les règles
Quand on parle d’intelligence artificielle au Morpion, on pense immédiatement à l’algorithme Minimax : un programme qui explore toutes les possibilités, calcule le meilleur coup et joue de manière parfaite. Mais Minimax est un algorithme « classique » - il connaît les règles du jeu, sait ce qu’est une victoire et évalue chaque position avec une logique programmée par un humain. Et si une machine pouvait apprendre à jouer au Morpion sans qu’on lui explique quoi que ce soit ? C’est exactement ce que permet l’apprentissage par renforcement.
Minimax vs. apprentissage par renforcement : deux philosophies
La différence fondamentale entre Minimax et l’apprentissage par renforcement tient en une phrase : Minimax calcule, le renforcement apprend.
Avec Minimax, le programmeur code explicitement les règles du jeu, la définition de la victoire et une fonction d’évaluation. L’algorithme parcourt l’arbre des possibilités et choisit le chemin optimal. C’est puissant, mais rigide : changez les règles, et il faut tout reprogrammer.
Avec l’apprentissage par renforcement, on donne à la machine trois choses seulement : un environnement (la grille 3×3), des actions possibles (placer un symbole dans une case vide) et un signal de récompense (+1 pour une victoire, -1 pour une défaite, 0 pour un match nul). Aucune règle stratégique. Aucune connaissance préalable. La machine doit tout découvrir par elle-même, partie après partie.
Le Q-Learning : apprendre par essais et erreurs
L’algorithme de Q-Learning est l’une des méthodes les plus célèbres d’apprentissage par renforcement. Son principe est désarmant de simplicité : la machine associe à chaque paire (situation, action) une valeur Q qui représente « la qualité estimée de cette action dans cette situation ».
Au début, toutes les valeurs Q sont à zéro. La machine ne sait rien. Elle joue au hasard. Elle perd, beaucoup. Mais à chaque défaite, elle ajuste les valeurs Q des actions qui ont conduit à la perte - elle les diminue. À chaque victoire, elle augmente les valeurs des actions qui ont mené au succès.
Après quelques milliers de parties, un phénomène fascinant se produit : la machine commence à jouer intelligemment. Elle découvre d’elle-même qu’il faut prendre le centre, qu’il faut bloquer l’adversaire quand il a deux symboles alignés, qu’il faut créer des menaces doubles. Personne ne lui a enseigné ces stratégies - elles ont émergé de l’expérience pure.
L’exploration contre l’exploitation
Un défi central du Q-Learning est le dilemme exploration/exploitation. Faut-il jouer le coup qui semble le meilleur selon les valeurs Q actuelles (exploitation) ? Ou faut-il essayer un coup inconnu pour découvrir s’il est encore meilleur (exploration) ?
Si la machine exploite trop tôt, elle reste bloquée dans une stratégie médiocre. Si elle explore trop longtemps, elle ne converge jamais. La solution classique est la stratégie epsilon-greedy : la machine joue le meilleur coup connu avec une probabilité (1 - ε) et un coup aléatoire avec une probabilité ε. Ce paramètre ε décroît avec le temps - la machine explore beaucoup au début et exploite de plus en plus à mesure qu’elle apprend.
Ce dilemme n’est pas propre aux machines. Les humains y font face constamment : faut-il commander son plat préféré au restaurant ou essayer quelque chose de nouveau ? Faut-il répéter sa stratégie gagnante au Morpion ou tenter un coup surprenant ?
Le Morpion comme laboratoire idéal
Pourquoi le Morpion est-il le terrain de jeu favori des chercheurs en apprentissage automatique ? Pour plusieurs raisons qui en font un problème parfaitement calibré :
- Espace d’états limité : le Morpion possède environ 5 478 positions légales distinctes. C’est assez pour être intéressant, mais assez peu pour qu’un algorithme de Q-Learning converge en quelques milliers de parties.
- Résultat vérifiable : on sait qu’un joueur parfait ne perd jamais au Morpion. Si l’agent apprend à ne jamais perdre, on peut vérifier qu’il a atteint le niveau optimal.
- Règles simples, stratégies subtiles : malgré sa simplicité apparente, le Morpion contient des notions de contrôle du centre, de menaces doubles et de symétries qui témoignent d’une réelle profondeur stratégique.
Ces caractéristiques en font le « Hello World » de l’apprentissage par renforcement - le premier problème que tout étudiant en IA résout avant de s’attaquer à des jeux plus complexes comme les échecs ou le Go.
Les réseaux de neurones entrent en scène
Le Q-Learning classique stocke ses valeurs dans un tableau : une ligne par état, une colonne par action. Cela fonctionne pour le Morpion, mais devient impossible pour des jeux plus complexes. C’est là qu’intervient le Deep Q-Learning : au lieu d’un tableau, on utilise un réseau de neurones pour estimer les valeurs Q.
Le réseau reçoit en entrée l’état de la grille (9 cases, chacune vide, X ou O) et produit en sortie une valeur Q pour chaque action possible. Il apprend en ajustant ses poids à chaque partie, exactement comme le Q-Learning classique ajuste son tableau.
Pour le Morpion, un réseau de neurones est excessif - un simple tableau suffit. Mais cette approche est celle qui a permis à DeepMind de créer AlphaGo, le programme qui a battu le champion du monde de Go en 2016. Le principe est identique : apprentissage par renforcement, mais à une échelle astronomiquement plus grande.
Ce que la machine découvre par elle-même
Le plus fascinant dans l’apprentissage par renforcement au Morpion, c’est d’observer ce que la machine découvre et dans quel ordre. Les chercheurs constatent généralement la progression suivante :
- Phase 1 (0-500 parties) : jeu complètement aléatoire. L’agent perd la majorité de ses parties.
- Phase 2 (500-2 000 parties) : l’agent apprend à compléter ses propres alignements. Il commence à gagner quand l’adversaire fait des erreurs.
- Phase 3 (2 000-5 000 parties) : l’agent apprend à bloquer l’adversaire. Le taux de défaite chute drastiquement.
- Phase 4 (5 000-10 000 parties) : l’agent découvre la valeur stratégique du centre et des coins. Les match nuls deviennent le résultat dominant.
- Phase 5 (10 000+ parties) : l’agent converge vers le jeu parfait - il ne perd plus jamais.
Cette progression rappelle celle d’un enfant qui apprend le Morpion. D’abord le chaos, puis la compréhension de l’attaque, puis la défense, puis la stratégie positionnelle. La machine réinvente, en accéléré, des siècles de sagesse humaine.
Du Morpion à l’IA générale
L’apprentissage par renforcement au Morpion est bien plus qu’un exercice académique. Les mêmes principes sont aujourd’hui utilisés pour entraîner des robots à marcher, des voitures autonomes à conduire et des modèles de langage à générer du texte cohérent. Le RLHF (Reinforcement Learning from Human Feedback) qui affine les grands modèles d’IA est un descendant direct des techniques testées sur notre humble grille 3×3.
Des jeux comme le Morpion ou l’Othello - un autre jeu de plateau où l’IA excelle - servent de bancs d’essai pour des algorithmes qui, une fois raffinés, sont déployés dans des domaines bien plus critiques.
La prochaine fois que vous affronterez l’ordinateur au Morpion, posez-vous la question : l’IA en face a-t-elle été programmée pour jouer, ou a-t-elle appris à jouer ? La réponse change tout - parce qu’un programme qui apprend est un programme qui peut s’améliorer indéfiniment, bien au-delà de ce que son créateur avait imaginé.