Comment les dés ont aidé un ordinateur à apprendre le backgammon

Un logiciel qui apprend en jouant contre lui-même doit trouver une expérience utile quelque part. Si sa stratégie initiale produit toujours les mêmes situations, il peut progresser contre ses propres faiblesses sans apprendre grand-chose du reste du jeu. Au backgammon, les dés modifient continuellement l’exercice.

Au début des années 1990, Gerald Tesauro, chercheur chez IBM, a développé TD-Gammon, qui apprenait à évaluer les positions en jouant contre lui-même. Son article de 1992 rapportait que le système initial avait appris un jeu utile à partir des résultats des parties, sans collection de coups d’experts à copier. Il fallait toujours lui fournir les règles des coups légaux et les résultats : apprendre « à partir de zéro » ne signifiait pas découvrir les règles.

Apprendre une espérance à partir d’un résultat incertain

L’évaluateur devait estimer un résultat futur à partir du plateau. Une partie terminée fournit un résultat unique, alors que la valeur de la position concerne l’ensemble de ses suites possibles. Les deux peuvent différer sans que le joueur commette la moindre erreur.

Même un évaluateur parfait peut perdre cette partie

Vous jouez les ivoire. Chaque joueur a déjà sorti quatorze pions. Vous gagnez si vous sortez votre dernier pion sur ce jet ; sinon, Rouge sortira le sien au tour suivant. On compte seulement les victoires, sans videau.

Voir les chances exactes

Vous gagnez sur 27 jets parmi 36, soit 75 %. Les neuf jets perdants sont 1–1 et les deux ordres de 1–2, 1–3, 1–4 et 2–3. Ils ne suffisent pas à parcourir six points, même en jouant quatre fois le 1 de 1–1. Une défaite sur l’un d’eux ne prouve aucune erreur de l’évaluateur ou du joueur.

Lire la position

Ivoire, point : nombre de pions. 6: 1. Rouge : 24: 1. À la barre : ivoire 0, rouge 0. Sortis : ivoire 14, rouge 14.

Dans cette petite course, on peut compter tous les jets et connaître la réponse exacte. Un évaluateur annonçant 75 % de chances de gagner aurait raison avant les dés, y compris dans le quart des cas qui se terminent par une défaite. Lui apprendre à considérer chaque défaite comme la preuve que la position était mauvaise reviendrait à confondre un résultat avec une espérance.

Dans une partie entière, compter toutes les suites devient impraticable. Le système doit combiner de nombreuses observations et transférer ce qu’il apprend entre des positions proches. L’objectif est une prévision utile dans ces situations, pas un verdict selon lequel le vainqueur aurait pris les meilleures décisions dans chaque partie.

L’apprentissage par différence temporelle utilise les changements entre les prévisions successives pour guider ces ajustements, le résultat réel apportant le signal final. Si une position était jugée prometteuse et que sa suite est régulièrement jugée moins bonne, cette divergence peut corriger l’estimation initiale sans attendre la fin de chaque partie.

Comment les dés apportaient de l’expérience

Dans son analyse de 1995, Tesauro présentait les dés comme une source de variété pendant l’apprentissage. Il observait aussi que la dynamique du backgammon aidait les premières parties contre soi-même à atteindre une fin, donc un résultat permettant d’apprendre. C’étaient des explications du succès obtenu dans ce jeu, pas un théorème selon lequel les jeux aléatoires seraient faciles à apprendre.

Un jet légal peut changer le cours d’une partie d’entraînement. Un joueur qui espérait attaquer reçoit un jet qui rend la fuite plus urgente ; une position prometteuse devient une défense difficile. Même si le logiciel applique toujours la même règle de décision devant un plateau et un jet donnés, des suites de dés différentes l’amènent dans des régions différentes du jeu.

Cette variété n’est utile que si l’apprentissage en fait de meilleures décisions. Des positions plus inhabituelles peuvent aussi multiplier les erreurs possibles, et le hasard rend chaque résultat moins fiable comme indice. Les dés apportent à la fois de l’expérience et du bruit.

Une autre équipe a essayé une méthode beaucoup plus simple

Jordan Pollack et Alan Blair ont ensuite obtenu un évaluateur de backgammon compétitif par une autre méthode : modifier légèrement un réseau, opposer ce candidat au réseau en place et utiliser leurs résultats pour guider l’amélioration. Leur article de 1998 défendait l’importance de la dynamique du jeu et de l’adversaire qui évolue au fil de l’apprentissage.

Ils ne prétendaient pas reproduire tout le niveau de TD-Gammon. Leur expérience montrait qu’il fallait examiner l’environnement d’apprentissage autant que l’algorithme de mise à jour. Une méthode apprend à travers les situations qu’elle reçoit, lesquelles dépendent du jeu et de l’adversaire qu’elle produit.

Le coût demeure dans la recherche

Quand le joueur entraîné doit choisir un coup, les futurs dés restent coûteux à examiner. Chaque jet possible peut donner un ensemble différent de réponses légales. Ce qui variait ses exercices élargit aussi la recherche nécessaire pour calculer loin.

Les méthodes d’apprentissage peuvent également apporter de l’exploration aux jeux déterministes. Les travaux d’AlphaZero sur les échecs, le shogi et le go montrent que les dés ne sont pas indispensables à un apprentissage puissant contre soi-même. L’histoire du backgammon est plus précise : le hasard a été un ingrédient utile dans l’environnement où un système précoce a réussi.

C’est une autre question que de savoir quel jeu possède le plus grand arbre de recherche. Cela explique aussi pourquoi la contribution de TD-Gammon à la théorie des ouvertures venait d’un joueur qui avait appris à juger les positions, sans calculer le jeu entier.