Quand nous demandons au coach de CUBE Backgammon s’il vaut mieux frapper ou faire une porte, générer les coups légaux n’est que le début. La question plus difficile est ce que ces coups rapporteront après la réponse adverse et les prochains dés.
Un évaluateur est une fonction qui transforme une description du jeu en estimation de son résultat futur. Au backgammon, l’équité exprime une valeur dans des conditions de score précises. Pour une partie simple à mise fixe d’un point, c’est l’espérance de points gagnés ou perdus. Un moteur a besoin de ce jugement lorsqu’il arrête sa recherche avant la fin de la partie.
Que signifie une équité de +0,50 ?
Pour comprendre le nombre, prenons une position dont tout l’avenir tient dans un jet. On peut ici compter les résultats exactement, avant de demander comment un réseau de neurones estimerait un plateau plus compliqué.
Passer de 75 % de victoires à +0,50 point
Reprenons la petite course de notre article sur les dés et l’apprentissage. Chaque joueur a sorti quatorze pions ; les ivoire ont leur dernier pion en 6 et jouent avant Rouge, dont le dernier pion est sur son propre point 1. Les ivoire gagnent sur 27 des 36 jets, et perdent sur les neuf autres.
Calculer l’équité avant le jet
| Résultat | Nombre de jets | Points reçus par les ivoire |
|---|---|---|
| Gain simple | 27 | +1 |
| Perte simple | 9 | −1 |
(27 × 1 − 9 × 1) ÷ 36 = +0,50 point. C’est la moyenne de 27 points gagnés et neuf perdus sur les 36 résultats possibles. Le 75 % décrit la fréquence des victoires ; le +0,50 décrit les points attendus par partie.
Sur une partie, cette position rapporte soit +1, soit −1. Son équité avant le jet vaut +0,50 en raison des probabilités de ces résultats. L’estimation ne prédit pas quel jet va arriver.
Si chaque gain et perte valait un point, l’équité serait deux fois la probabilité de victoire moins un. Les gammons et backgammons empêchent d’appliquer ce raccourci aux positions ordinaires.
Pourquoi notre évaluateur conserve six probabilités
L’évaluateur présenté dans notre article sur le moteur estime six résultats distincts : gains simples, gammons gagnés, backgammons gagnés et les trois pertes correspondantes. Leurs probabilités s’additionnent pour donner un. Les garder séparés permet au calcul de score de donner une autre valeur au gammon qu’au gain simple.
À mise fixe d’un point, avec des gammons à deux points et des backgammons à trois, on multiplie la probabilité de chaque résultat par ce qu’il rapporte, puis on additionne : gains simples, deux fois les gammons gagnés et trois fois les backgammons gagnés, moins les pertes correspondantes. Le coup qui gagne le plus souvent peut rapporter moins de points s’il perd aussi trop de gammons.
Le videau et le score du match ajoutent du contexte. Un gammon qui gagne le match n’a pas la même conséquence qu’un gammon apportant des points inutiles. Un futur videau peut aussi terminer la partie avant la sortie des pions. Une fonction de valeur utile demande donc un objectif et un modèle de score explicites, pas seulement un plateau sans contexte.
D’où viennent les estimations ?
Dans une petite sortie, un calcul ou une base peut fournir des réponses exactes. Pour couvrir beaucoup de positions, un évaluateur appris utilise des poids numériques ajustés à partir d’exemples. Les entrées décrivent la position ; la cible d’apprentissage fournit un résultat ou une analyse à apprendre. Le modèle devient utile s’il applique cet apprentissage à des positions absentes des exemples.
Ces cibles peuvent venir de plusieurs méthodes. TD-Gammon apprenait contre lui-même, en utilisant l’évolution des prévisions et les parties terminées pour améliorer son évaluateur. Notre présentation de CUBE Backgammon décrit aussi l’apprentissage sur des positions analysées par un moteur professeur plus fort, suivant l’idée établie de distillation de connaissances. Cet apprentissage a lieu en amont ; le téléphone utilise les poids appris pendant que vous jouez.
La cible compte. Une estimation apprise sur les parties d’un joueur ou les analyses d’un moteur reflète leur façon de jouer ou d’analyser. Un réseau qui l’apprend ne la transforme pas en vérité du jeu parfait. Des tests sur des positions nouvelles et une analyse indépendante aident à vérifier les progrès réels.
Comment une valeur devient un coup
Pour chaque coup candidat, le moteur peut évaluer la position obtenue du point de vue du même joueur et préférer la valeur la plus élevée. Chercher plus loin lui permet de confronter cette première impression aux futurs dés et réponses, puis d’évaluer les positions atteintes ensuite.
On fait la moyenne des branches de hasard selon leurs probabilités. Pour les réponses adverses, il faut tenir compte d’un adversaire qui choisit une réponse forte. Combiner ces valeurs futures affine la comparaison au départ. Si chaque action disponible avait déjà une valeur exacte pour l’objectif joué, choisir la meilleure serait simple ; obtenir ces valeurs constitue le travail difficile.
Un réseau plus grand est une manière de chercher de meilleures estimations ; un réseau plus rapide peut laisser plus de temps à la recherche. Nous testons l’ensemble à travers les décisions obtenues. Lors d’un essai, un réseau imitait mieux son professeur mais jouait moins bien dans un test séparé de continuations, ce qui nous a conduits à rétablir la version précédente.
Le même rôle aux échecs et au go
Les échecs et le go demandent aussi de juger des positions inachevées. Leurs règles n’ont pas de dés, pourtant un réseau de valeur peut estimer un résultat attendu parce que le logiciel ne connaît pas parfaitement la suite. Une probabilité de victoire prédite n’indique pas du hasard dans les règles.
AlphaZero associait une estimation de valeur à une politique de coups. La valeur jugeait les positions ; la politique orientait la recherche vers les choix prometteurs. L’objectif de score et les entrées changeaient selon le jeu, mais le besoin de décider utilement sans terminer toutes les suites possibles était commun.
Au bridge, l’évaluateur doit aussi respecter les informations du joueur : la valeur parfaite d’une donne exposée peut être inutilisable pour celui qui ne voit pas les mains adverses. Au blackjack, les règles fixes du croupier peuvent rendre abordable un calcul direct d’espérance. Le réseau de neurones est un outil d’approximation de valeur, pas une condition nécessaire à tous les jeux.
Cela explique le rôle de l’évaluation dans notre classement de difficulté. Compter les futurs possibles décrit la croissance de la recherche. Apprendre à évaluer les positions où elle doit s’arrêter aide à comprendre si l’on peut construire un joueur fort sans tout explorer.
Sources : Gerald Tesauro, Temporal Difference Learning and TD-Gammon (1995) ; Silver et ses coauteurs, l’article sur AlphaZero (2018) ; Hinton, Vinyals et Dean, Distilling the Knowledge in a Neural Network (2015) ; le manuel de GNU Backgammon. La course exacte reprend notre position originale de l’article sur l’apprentissage et son décompte indépendant de 27 jets gagnants sur 36. On évalue une partie à mise fixe d’un point, sans videau, où seule la victoire compte. La description de CUBE Backgammon suit notre présentation publique existante et n’introduit aucune nouvelle mesure de niveau ou de taille de modèle.