TD-Gammon est un programme informatique de backgammon développé dans les années 1990 par Gerald Tesauro au Thomas J. Watson Research Center d'IBM. Son nom provient de son utilisation d'un réseau de neurones artificiel entraîné par apprentissage par différences temporelles, plus précisément TD-Lambda. Il a exploré des stratégies que les humains n'avaient pas poursuivies et a conduit à des avancées dans la théorie du jeu de backgammon correct. En 1993, TD-Gammon (version 2.1) a été entraîné avec 1,5 million de parties en auto-jeu et a atteint un niveau de jeu légèrement inférieur à celui des meilleurs joueurs humains de backgammon de l'époque. En 1998, lors d'une série de 100 parties, il a été battu par le champion du monde par une simple marge de 8 points. Son évaluation non conventionnelle de certaines stratégies d'ouverture a été acceptée et adoptée par les joueurs experts. TD-Gammon est couramment cité comme un succès précoce de l'apprentissage par renforcement et des réseaux de neurones, et a été référencé dans des articles sur le deep Q-learning et AlphaGo.
Algorithme de jeu et d'apprentissage
Pendant le jeu, TD-Gammon examine à chaque tour toutes les actions légales possibles et toutes leurs réponses possibles (recherche par anticipation), alimente chaque position de plateau résultante dans sa fonction d'évaluation, et choisit l'action qui mène à la position de plateau ayant obtenu le score le plus élevé. À cet égard, TD-Gammon ne diffère pas de presque tout autre programme informatique de jeu de plateau. L'innovation de TD-Gammon résidait dans la manière dont il apprenait sa fonction d'évaluation.
L'algorithme d'apprentissage de TD-Gammon consiste à mettre à jour les poids de son réseau de neurones après chaque tour afin de réduire la différence entre son évaluation des positions de plateau des tours précédents et son évaluation de la position de plateau du tour actuel - d'où le terme "apprentissage par différences temporelles". Le score de toute position de plateau est un ensemble de quatre nombres reflétant l'estimation par le programme de la probabilité de chaque résultat possible du jeu : victoire normale de Blanc, victoire normale de Noir, victoire par gammon de Blanc, victoire par gammon de Noir. Pour la position finale du plateau du jeu, l'algorithme compare avec le résultat réel du jeu plutôt qu'avec sa propre évaluation de la position.
Le cœur de TD-Gammon est un réseau de neurones à 3 couches. La couche d'entrée comporte deux types de neurones. Un type code la position du plateau : des entiers non négatifs allant de 0 à 15, indiquant le nombre de pions blancs ou noirs à chaque emplacement du plateau, avec 99 neurones d'entrée pour chaque, totalisant 198 neurones. Un autre type code des caractéristiques conçues manuellement précédemment utilisées dans Neurogammon, encodant des concepts standard utilisés par les experts humains tels que "ancre avancée", "force du blocus", "force du plateau de maison", et la probabilité qu'un "blot" (pion isolé) soit frappé. La couche cachée contient des neurones cachés, les versions ultérieures en ayant davantage. La couche de sortie contient 4 neurones, représentant l'estimation par le réseau de la probabilité ("équité") que le plateau actuel mène à : victoire normale de Blanc, victoire par gammon de Blanc, victoire normale de Noir, victoire par gammon de Noir. La victoire par backgammon est si rare que Tesauro a choisi de ne pas la représenter.
Après chaque tour, l'algorithme d'apprentissage met à jour chaque poids selon la règle : w_{t+1} - w_t = alpha (Y_{t+1} - Y_t) sum_{k=1}^{t} lambda^{t-k} grad_w Y_k, où alpha est le taux d'apprentissage, Y_t est l'évaluation au tour t, et lambda est le paramètre de décroissance. Il a été constaté que choisir un petit lambda offrait des performances à peu près équivalentes, et qu'un grand lambda dégradait les performances. Pour cette raison, après 1992, TD-Gammon a été entraîné avec lambda = 0, dégénérant en apprentissage TD standard, ce qui économisait un facteur 2 en calcul.
Historique du développement
La version 1.0 utilisait une recherche simple à 1-ply : chaque prochain coup est évalué par le réseau de neurones, et le coup ayant le score le plus élevé est sélectionné. Les versions 2.0 et 2.1 utilisaient une recherche à 2-ply : d'abord une analyse à 1-ply pour éliminer les coups improbables ("élagage avant"), puis une analyse minimax à 2-ply pour seulement les coups probables, choisissant le meilleur coup pondéré par la probabilité de chacun des 21 lancers de dés possibles de l'adversaire (pondérant les doubles deux fois moins que les non-doubles). Les versions 3.0 et 3.1 utilisaient une recherche à 3-ply, utilisant 21^2 = 441 lancers de dés possibles au lieu de 21. La dernière version, 3.1, a été entraînée spécifiquement pour un match d'exhibition contre Malcolm Davis au AAAI Hall of Champions de 1998. Il a perdu à -8 points, principalement en raison d'une seule bévue, où TD-Gammon a choisi de doubler et a subi un gammon à -32 points.
Expériences et étapes de l'entraînement
Contrairement aux programmes de backgammon à réseau de neurones précédents tels que Neurogammon (également écrit par Tesauro), où un expert entraînait le programme en fournissant l'évaluation "correcte" de chaque position, TD-Gammon a d'abord été programmé "sans connaissance". Dans les premières expérimentations, en utilisant uniquement un encodage brut du plateau sans caractéristiques conçues par l'homme, TD-Gammon a atteint un niveau de jeu comparable à Neurogammon : celui d'un joueur humain de backgammon de niveau intermédiaire.
Même si TD-Gammon a découvert des caractéristiques perspicaces par lui-même, Tesauro s'est demandé si son jeu pouvait être amélioré en utilisant des caractéristiques conçues manuellement comme celles de Neurogammon. En effet, le TD-Gammon auto-entraîné avec des caractéristiques conçues par des experts a rapidement surpassé tous les programmes informatiques de backgammon précédents. Il a cessé de s'améliorer après environ 1 500 000 parties (auto-jeu) en utilisant un réseau de neurones à trois couches, avec 198 unités d'entrée encodant des caractéristiques conçues par des experts, 80 unités cachées, et une unité de sortie représentant la probabilité prédite de victoire.
Avancées dans la théorie du backgammon
L'entraînement exclusif de TD-Gammon par auto-jeu (plutôt que par apprentissage par imitation) lui a permis d'explorer des stratégies que les humains n'avaient pas envisagées auparavant ou avaient écartées à tort. Son succès avec des stratégies non conventionnelles a eu un impact significatif sur la communauté du backgammon. Fin 1991, Bill Robertie, Paul Magriel et Malcolm Davis ont été invités à jouer contre TD-Gammon (version 1.0). Un total de 51 parties ont été jouées, TD-Gammon perdant à -0,25 ppg. Robertie a trouvé que TD-Gammon était au niveau d'un joueur humain fort, et ses coups non conventionnels ont ensuite été adoptés par les experts, changeant la compréhension de la stratégie d'ouverture.
Héritage et influence
TD-Gammon est largement reconnu comme une étape marquante dans l'apprentissage automatique et l'intelligence artificielle, démontrant qu'un réseau de neurones pouvait apprendre des jeux stratégiques complexes par auto-jeu et apprentissage par différences temporelles. Son succès a inspiré des travaux ultérieurs en apprentissage par renforcement, y compris le développement des deep Q-networks et d'AlphaGo. La capacité du programme à découvrir des stratégies novatrices que les humains avaient manquées a mis en évidence le potentiel des réseaux de neurones à dépasser l'intuition humaine dans le jeu, et il reste un exemple classique dans l'histoire de la recherche en IA.