Comment TD-Gammon a-t-il appris seul à jouer au backgammon au niveau d’un maître?

Avant les années 1990, la plupart des programmes de jeu étaient instruits par des humains. Des programmeurs s’asseyaient avec des experts, transformaient leurs conseils en règles et en pointages, et espéraient que l’ordinateur jouerait comme un maître. Gerald Tesauro, chercheur au centre de recherche Thomas J. Watson d’IBM, dans l’État de New York, a essayé autre chose avec le backgammon. Il a donné les règles à un réseau de neurones, l’a laissé jouer contre lui-même et l’a laissé découvrir seul à quoi ressemble une bonne position.

Le résultat, TD-Gammon, est l’un des premiers exemples les plus clairs d’une machine qui apprend une compétence difficile à partir de sa propre expérience. Tesauro l’a présenté pour la première fois en 1992 et l’a décrit en détail dans Communications of the ACM en mars 1995.

Pourquoi le backgammon était-il difficile pour les ordinateurs?

Le backgammon est une course. Deux joueurs lancent les dés et déplacent leurs pions en sens opposés sur un parcours; le premier à ramener tous ses pions à la maison et à les sortir du plateau gagne. Deux caractéristiques le rendent subtil. Un pion isolé (un « blot ») peut être frappé et renvoyé au départ, et les joueurs peuvent bâtir des murs de pions qui bloquent l’adversaire. Il y a aussi un « videau » (doubling cube), qui permet à un joueur de faire monter les enjeux.

Les dés sont le véritable obstacle pour un ordinateur. Aux échecs, un programme peut prévoir de nombreux coups à l’avance. Au backgammon, chaque tour offre 21 lancers de dés possibles, avec environ 20 coups permis pour chacun; il y a donc plusieurs centaines de possibilités par coup, et regarder loin devant est hors de portée. Un programme doit plutôt bien juger les positions, comme un joueur humain fort le fait d’instinct.

Tesauro avait déjà essayé d’enseigner cet instinct de la façon classique. Son programme précédent, Neurogammon, apprenait à partir d’une base de données de parties d’experts et a remporté l’épreuve de backgammon de la Computer Olympiad de 1989, mais il n’atteignait qu’un bon niveau intermédiaire.

Comment TD-Gammon a-t-il appris?

Le cerveau de TD-Gammon est un réseau de neurones : des couches d’unités simples reliées par des connexions ajustables appelées poids. Il reçoit une description du plateau et produit quatre nombres, ses estimations des chances que les Blancs ou les Noirs gagnent normalement ou gagnent double (un « gammon »).

L’entraînement suivait une boucle simple :

1. Partir de poids aléatoires, si bien que le jugement du réseau n’est que du bruit.
2. À chaque coup, évaluer chaque option permise avec le réseau et choisir celle qu’il juge la meilleure, pour le camp qui joue.
3. Après chaque coup, comparer la nouvelle estimation de la position par le réseau avec la précédente, et ajuster légèrement les poids pour que l’estimation précédente se rapproche de la suivante.
4. À la fin de la partie, rapprocher la dernière estimation du résultat réel.
5. Recommencer pendant des centaines de milliers de parties.

L’étape 3, c’est l’apprentissage par différence temporelle, une famille de méthodes nommée par Richard Sutton; la version utilisée ici s’appelle TD(lambda). Au début, les parties étaient absurdes. Avec un jeu aléatoire, une partie pouvait s’étirer sur des centaines ou des milliers de coups, contre 50 à 60 chez les humains. Pourtant, en quelques milliers de parties, le réseau a saisi des notions de base comme frapper l’adversaire et jouer prudemment, et des idées plus profondes sont apparues après des dizaines de milliers.

Voici comment le programme a progressé :

Qu’est-ce que cela a changé?

Robertie, ancien champion du monde, a jugé que la version 2.1 jouait à un niveau de maître solide, à quelques centièmes de point par partie des meilleurs humains, et que sa constance pourrait en faire le favori sur une longue séance. Ses points faibles étaient les fins de partie et les décisions de doublement; la stratégie de doublement a été ajoutée après l’entraînement plutôt qu’apprise.

L’effet le plus frappant a touché le jeu humain. Pendant environ 30 ans, quand le premier lancer d’une partie était 2-1, 4-1 ou 5-1, les experts avaient presque toujours déplacé un seul pion de leur point 6 vers leur point 5, un coup risqué appelé « slotting ». TD-Gammon préférait plutôt séparer ses pions arrière. Après que Robertie eut publié l’analyse du programme en 1992, les meilleurs joueurs ont essayé cette séparation, ont gagné avec elle, et le « slotting » a pratiquement disparu des tournois. Kit Woolsey, l’un des grands analystes du jeu, a trouvé son jugement positionnel meilleur que le sien.

Tesauro a aussi souligné ce que TD-Gammon signifiait pour la recherche en IA. L’apprentissage par renforcement, où un apprenant progresse grâce à des récompenses plutôt qu’aux bonnes réponses d’un enseignant, avait connu peu de grands succès avant lui. TD-Gammon a montré que le combiner avec un réseau de neurones pouvait fonctionner sur un problème réel et complexe. Des travaux ultérieurs sur les réseaux qui jouent à des jeux, dont les articles de DeepMind sur AlphaGo, le citent.

Qu’est-ce que l’apprentissage par différence temporelle, en mots simples?

Imaginez que vous prévoyez la météo de samedi. Le lundi, vous annoncez 70 % de chances de soleil. Le mardi, la prévision passe à 50 %. Vous n’avez pas besoin d’attendre samedi pour apprendre quelque chose : la prévision du mardi, faite avec plus d’information, vous dit déjà que celle du lundi était un peu trop optimiste. L’apprentissage par différence temporelle ajuste chaque estimation vers l’estimation suivante, mieux informée, et seule la dernière est comparée à ce qui s’est réellement passé.

Cela résout une énigme classique appelée l’attribution du mérite. Dans une longue partie, le seul signal clair est le résultat à la fin. Lequel des cinquante coups mérite le crédit ou le blâme? En comparant l’estimation de chaque position avec la suivante, la méthode fait remonter le résultat final à rebours à travers la partie, un peu à la fois.

Le « lambda » de TD(lambda) détermine jusqu’où chaque correction remonte. Un lambda plus grand répartit une surprise sur un plus grand nombre de positions antérieures; un lambda de zéro ne corrige que la position immédiatement précédente. TD-Gammon a montré que cette règle simple, répétée sur assez de parties jouées contre soi-même, peut faire naître un jugement qui rivalise avec celui des experts humains.