Le Morpion et l'apprentissage par renforcement : comment une IA découvre seule la stratégie optimale
Imaginez un programme informatique qui ne connaît rien du Morpion. On ne lui a pas expliqué les règles, on ne lui a pas montré de stratégie, on ne lui a même pas dit que le centre est la meilleure case pour commencer. Tout ce qu'il sait, c'est qu'il peut placer un symbole dans une case vide, et qu'à la fin de la partie, il reçoit un signal : victoire, défaite ou match nul. À partir de cette seule information, ce programme va jouer des millions de parties contre lui-même et, progressivement, découvrir la stratégie parfaite du Morpion. C'est le principe de l'apprentissage par renforcement, et le Morpion est son terrain de jeu idéal.
Le "Hello World" de l'intelligence artificielle
Dans le monde de la programmation, le premier programme que l'on écrit affiche traditionnellement "Hello World" à l'écran. Dans le monde de l'intelligence artificielle, le premier problème que l'on résout est souvent le Morpion. Ce n'est pas un hasard. Le Morpion possède des caractéristiques qui en font le candidat parfait pour l'apprentissage automatique.
D'abord, son espace d'états est remarquablement petit. Une grille de Morpion peut se trouver dans environ 5 478 positions distinctes si l'on tient compte des symétries, et environ 765 positions terminales (victoire, défaite ou match nul). C'est suffisamment petit pour qu'un ordinateur puisse explorer toutes les possibilités en quelques secondes. Aux échecs, l'espace d'états dépasse les 10 puissance 44 - un nombre si grand qu'aucun ordinateur ne peut l'explorer entièrement. Au Go, c'est encore pire : 10 puissance 170. Le Morpion, avec ses quelques milliers d'états, est un microcosme parfaitement gérable.
Ensuite, les règles sont binaires et sans ambiguïté. Chaque action est soit légale (placer un symbole dans une case vide), soit illégale. Le résultat d'une partie est soit une victoire, soit une défaite, soit un match nul. Il n'y a pas de zones grises, pas de scores partiels, pas de situations floues. Pour un algorithme d'apprentissage, cette clarté est un cadeau.
Enfin, le Morpion est un jeu résolu. On sait mathématiquement que deux joueurs parfaits finissent toujours par un match nul. Cela signifie qu'on peut vérifier objectivement si l'IA a atteint la stratégie optimale : si elle ne perd jamais, elle a réussi. Ce critère de validation précis est rare dans les problèmes d'IA plus complexes.
Le principe de l'apprentissage par renforcement
L'apprentissage par renforcement (ou RL, pour Reinforcement Learning) repose sur une idée simple empruntée à la psychologie comportementale : un agent apprend en interagissant avec son environnement et en recevant des récompenses ou des punitions. C'est exactement comme dresser un animal. Quand le chien s'assoit sur commande, il reçoit une friandise. Quand il fait une bêtise, il n'en reçoit pas. Avec le temps, le chien apprend quels comportements sont récompensés.
Dans le contexte du Morpion, l'agent est le programme qui joue. L'environnement est le plateau de jeu. Les actions sont les coups possibles. Et les récompenses sont attribuées en fin de partie : +1 pour une victoire, -1 pour une défaite, 0 pour un match nul. L'objectif de l'agent est de maximiser sa récompense cumulée sur le long terme.
Le défi, c'est que la récompense n'arrive qu'à la fin. Quand l'IA perd une partie, elle sait qu'elle a fait au moins une erreur, mais elle ne sait pas quel coup précis était mauvais. Était-ce le premier coup ? Le troisième ? Le dernier ? C'est ce qu'on appelle le problème de l'attribution du crédit, et c'est l'un des défis fondamentaux de l'apprentissage par renforcement.
La Q-table : une carte de la valeur de chaque action
Pour résoudre ce problème, l'une des méthodes les plus classiques est le Q-learning. L'idée est de construire un tableau géant - la Q-table - qui associe à chaque paire (état du plateau, action possible) une valeur numérique appelée valeur Q. Cette valeur représente la "qualité" attendue d'une action dans une situation donnée : plus elle est élevée, plus l'action est censée mener vers la victoire.
Au début, toutes les valeurs Q sont initialisées à zéro. L'agent ne sait rien - pour lui, jouer au centre, dans un coin ou sur un bord se vaut. Puis il commence à jouer. À chaque partie, il choisit des coups, observe le résultat, et met à jour les valeurs Q en conséquence.
La mise à jour suit une formule simple mais puissante. Quand l'agent joue un coup et observe ce qui se passe ensuite, il ajuste la valeur Q de ce coup en fonction de la récompense reçue et de la meilleure valeur Q accessible depuis le nouvel état. C'est comme remonter l'information du futur vers le passé : si un coup mène à un état depuis lequel toutes les options sont mauvaises, la valeur Q de ce coup diminue. Si un coup mène à un état prometteur, sa valeur augmente.
Pour le Morpion, la Q-table est parfaitement dimensionnée. Avec environ 5 478 états possibles et au maximum 9 actions par état, la table contient au plus quelques dizaines de milliers d'entrées. C'est trivial pour un ordinateur moderne. Pour les échecs ou le Go, cette approche serait impossible - la table ne tiendrait dans la mémoire d'aucune machine existante.
Exploration contre exploitation : le dilemme permanent
L'un des aspects les plus fascinants de l'apprentissage par renforcement est le dilemme exploration-exploitation. À chaque coup, l'agent fait face à un choix : doit-il jouer le coup qui semble le meilleur selon sa Q-table actuelle (exploitation), ou doit-il essayer un coup différent pour découvrir s'il existe une meilleure option (exploration) ?
Si l'agent exploite toujours, il risque de rester bloqué sur une stratégie sous-optimale. Par exemple, il pourrait découvrir tôt que jouer dans un coin est "assez bon" et ne jamais explorer le centre - passant à côté de la stratégie optimale. C'est comme un restaurant : si vous commandez toujours le même plat parce qu'il est bon, vous ne découvrirez jamais que le plat du voisin est meilleur.
Si l'agent explore toujours, il ne capitalise jamais sur ce qu'il a appris. Il joue de manière aléatoire en permanence, ce qui n'est guère mieux que de ne pas apprendre du tout.
La solution classique est la stratégie epsilon-greedy. L'agent choisit un nombre epsilon entre 0 et 1 (par exemple 0,1). À chaque coup, il tire un nombre aléatoire. Si ce nombre est inférieur à epsilon (10 % des cas), il joue un coup au hasard (exploration). Sinon (90 % des cas), il joue le meilleur coup selon sa Q-table (exploitation). Au fil du temps, on réduit progressivement epsilon, passant d'une phase d'exploration intense à une phase d'exploitation de plus en plus pure. C'est comme un enfant qui essaie beaucoup de choses en grandissant, puis se spécialise à l'âge adulte.
L'auto-apprentissage : jouer contre soi-même
La méthode la plus élégante pour entraîner une IA au Morpion est le self-play - l'auto-apprentissage. Deux copies de l'agent jouent l'une contre l'autre, et les deux apprennent simultanément. Au début, les parties ressemblent à du jeu aléatoire : des coups absurdes, des occasions manquées, des victoires accidentelles. Mais progressivement, les deux agents s'améliorent mutuellement.
Ce processus crée une course aux armements cognitive. Quand l'agent X découvre une stratégie gagnante, l'agent Y finit par perdre suffisamment de parties pour apprendre à la contrer. Alors X doit trouver une nouvelle approche, que Y apprend à contrer à son tour, et ainsi de suite. Cette escalade progressive pousse les deux agents vers un jeu de plus en plus sophistiqué.
Après quelques dizaines de milliers de parties, un schéma émerge. Les agents commencent à privilégier le centre. Ils apprennent à bloquer les alignements de l'adversaire. Ils découvrent les fourchettes - ces configurations où un seul coup crée deux menaces simultanées. Personne ne leur a enseigné ces concepts. Ils les ont découverts seuls, par essai et erreur, guidés uniquement par le signal binaire victoire/défaite.
Après quelques centaines de milliers de parties, les deux agents atteignent le jeu parfait. Chaque partie se termine par un match nul. La stratégie optimale a été découverte - sans aucune connaissance humaine préalable.
Du Morpion aux problèmes complexes
Le Morpion est un point de départ, pas une destination. Les mêmes principes d'apprentissage par renforcement qui permettent à une IA de maîtriser le Morpion ont été étendus à des problèmes incomparablement plus complexes.
En 2013, DeepMind a utilisé le Deep Q-Network (DQN) pour apprendre à jouer à des jeux Atari à partir des pixels affichés à l'écran. Le principe est le même que pour le Morpion - récompense en fin de partie, Q-values pour évaluer les actions - mais la Q-table a été remplacée par un réseau de neurones capable de généraliser à des états jamais rencontrés.
En 2016, AlphaGo a battu le champion du monde de Go en combinant apprentissage par renforcement et réseaux de neurones profonds. En 2017, AlphaGo Zero est allé plus loin : comme notre agent de Morpion, il a appris entièrement par self-play, sans aucune connaissance humaine du jeu. En trois jours d'entraînement, il a surpassé la version qui avait battu le champion du monde.
Aujourd'hui, l'apprentissage par renforcement pilote des robots, optimise des centres de données, gère des portefeuilles financiers et découvre de nouvelles molécules. Mais le principe fondamental reste celui du Morpion : un agent qui interagit avec son environnement, reçoit des récompenses, et ajuste progressivement son comportement.
Ce que le Morpion nous enseigne sur l'apprentissage
L'histoire de l'IA qui apprend le Morpion par renforcement contient une leçon profonde sur la nature de l'apprentissage lui-même. L'agent n'a reçu aucune instruction, aucun conseil, aucun exemple de "bon jeu". Il a simplement joué, échoué, ajusté, rejoué. Et il a fini par maîtriser le jeu.
Les joueurs humains suivent un parcours étonnamment similaire. Un enfant qui découvre le Morpion ne lit pas de guide stratégique. Il joue, perd, comprend intuitivement pourquoi il a perdu, et s'améliore. Le centre lui paraît naturellement attirant après quelques parties. Les fourchettes émergent dans son jeu sans qu'on les lui ait nommées. La récompense (gagner) et la punition (perdre) façonnent son comportement exactement comme elles façonnent la Q-table de l'IA.
La différence, c'est la vitesse. Là où un humain a besoin de quelques dizaines de parties pour devenir compétent au Morpion, l'IA en joue des millions. Mais elle part de plus loin : elle n'a pas les milliards d'années d'évolution qui ont doté le cerveau humain d'une capacité innée à reconnaître les patterns spatiaux. L'IA doit construire cette capacité à partir de zéro, une partie à la fois.
Le Morpion reste, en ce sens, une fenêtre fascinante sur les mécanismes de l'intelligence - qu'elle soit artificielle ou humaine. Un jeu si simple qu'un enfant de cinq ans peut y jouer, mais suffisamment riche pour illustrer les principes fondamentaux par lesquels toute forme d'intelligence apprend à naviguer dans le monde. La prochaine fois que vous jouerez au Morpion et que vous choisirez instinctivement le centre, rappelez-vous qu'une IA, partie de rien, a découvert exactement la même chose - simplement en jouant encore et encore, récompensée par ses victoires, instruite par ses défaites.