Comment fonctionne le moteur

Deux parties : recherche et évaluation

Un moteur d'échecs, ce sont deux programmes qui travaillent ensemble. La recherche regarde devant : « si je joue ceci, il peut répondre cela, puis je joue ceci… ». L'évaluation regarde une seule position, sans rien déplacer, et lui donne un seul nombre : qui est mieux, et de combien.

Les deux ont besoin l'une de l'autre. Plus la recherche est profonde, moins une évaluation faible a d'importance ; meilleure est l'évaluation, moins il faut de profondeur. Comme l'évaluation tourne au bout de chaque ligne — des centaines de milliers de fois par seconde —, elle doit être à la fois bonne et très rapide.

La recherche

Le moteur réfléchit un niveau plus loin à chaque fois (approfondissement itératif), si bien qu'il a toujours un coup prêt quand la pendule tombe. Examiner chaque coup à chaque profondeur prendrait une éternité ; l'essentiel du travail consiste donc à ne pas regarder les coups qui ne peuvent pas compter :

• Alpha-bêta. Dès qu'une réponse réfute un coup, le moteur cesse d'examiner ce coup. Avec un bon ordre des coups, cela permet d'ignorer la majeure partie de l'arbre sans changer le résultat.
• Les meilleurs coups d'abord. Le coup qui était le meilleur la dernière fois que cette position a été vue, les prises de pièces de valeur et les coups tranquilles qui ont fonctionné dans des positions semblables (coups killer et table d'historique) sont essayés en premier.
• La mémoire. Une table de transposition retient les positions déjà analysées, car on atteint souvent la même position par des ordres de coups différents.
• Des raccourcis raisonnés. Les derniers coups peu prometteurs sont analysés moins profondément (late move reductions) ; une position si bonne que même passer son tour conserverait l'avantage est écourtée (null move pruning) ; les échecs sont analysés un coup plus loin.
• Seulement des positions calmes. La recherche ne s'arrête jamais au milieu d'un échange : au bout de chaque ligne, elle continue de suivre les prises jusqu'à ce que la position se calme (recherche de quiescence), si bien que l'évaluation ne voit jamais une dame sur le point d'être reprise.
• Plusieurs cœurs. Le moteur peut chercher avec plusieurs threads à la fois, qui partagent tous une même table de transposition (Lazy SMP).

L'échiquier

À l'intérieur du moteur, l'échiquier est un ensemble de nombres de 64 bits, un bit par case (bitboards) : un nombre pour les cavaliers blancs, un pour les tours noires, et ainsi de suite. Les coups et les attaques se réduisent à quelques opérations sur les bits, et les pièces à longue portée trouvent leurs attaques dans des tables précalculées (magic bitboards). Les pièces composées de la variante — le Maharaja, l'Archevêque et le Chancelier — se déplacent comme la réunion de leurs composantes, et réutilisent donc les mêmes tables.

Juger une position à la main

L'évaluation d'origine du moteur est une liste de règles empiriques des échecs, chacune avec un poids : le matériel, la place de chaque pièce, le nombre de cases qu'elle contrôle, les pions passés et isolés, la paire de fous, les tours sur les colonnes ouvertes, le bouclier de pions devant le roi. Les poids évoluent progressivement de l'ouverture à la finale.

Elle fonctionne, et c'est elle qui joue dans l'application aujourd'hui, mais elle ne sait que ce que quelqu'un a pensé à écrire. Tout le reste lui est invisible.

Le réseau de neurones

Le réseau de neurones ne remplace que l'évaluation. La recherche reste exactement la même — le réseau ne choisit pas les coups, il répond à une seule question, de nombreuses fois par seconde : cette position est-elle bonne, et à quel point ?

• L'entrée, c'est l'échiquier lui-même. Il existe 18 sortes de pièces — pion, cavalier, fou, tour, dame, roi et les trois pièces composées, en deux couleurs — et 64 cases : 18 × 64 = 1152 questions fermées comme « y a-t-il un cavalier blanc en f3 ? ». Dans une position normale, environ 32 d'entre elles valent « oui ». Les pièces composées ont leurs propres entrées, ce ne sont pas des mélanges d'autres pièces : le réseau apprend donc ce que vaut un Maharaja en tant que tel.
• Les deux points de vue. L'échiquier entre deux fois : tel que le voit le camp au trait et, en miroir, tel que le voit l'adversaire. Le réseau n'a jamais besoin d'apprendre les échecs deux fois, une fois pour les Blancs et une fois pour les Noirs.
• Les neurones ne sont pas programmés. Personne ne dit à un neurone quoi chercher. Pendant l'entraînement, ils deviennent d'eux-mêmes des détecteurs — quelque chose comme « un roi sans abri de pions » ou « une tour arrivée sur la septième rangée ».

Pourquoi c'est rapide

Le nom du réseau, NNUE, signifie Efficiently Updatable Neural Network, un réseau de neurones efficacement actualisable. La première couche est une table avec une colonne de nombres par entrée, et les neurones sont simplement la somme des colonnes des entrées qui valent « oui ». Un coup ne modifie que deux à quatre entrées, donc la somme n'est jamais recalculée — elle est mise à jour :

Tout est calculé en petits entiers, beaucoup à la fois, grâce aux instructions vectorielles du processeur. Selon nos mesures, le moteur avec le réseau atteint la même profondeur de recherche environ deux fois plus vite qu'avec l'évaluation écrite à la main (0,95 contre 2,0 secondes sur nos positions de test, sur un cœur de notre machine de test).

Comment il apprend

Chaque exemple d'entraînement est une position avec deux étiquettes : le score que lui a donné une recherche de quelques coups de profondeur, et la façon dont la partie s'est finalement terminée. Le réseau apprend à deviner les deux d'un coup d'œil. Tout le secret est là : quand la recherche interroge le réseau sur une position, la réponse contient déjà ce qu'une analyse plus profonde aurait trouvé, comme si la recherche était allée plus loin gratuitement.

Le moteur apprend uniquement de ses propres parties, pièces composées et armées sur mesure comprises — aucune analyse d'un autre moteur n'y entre. Un nouveau réseau n'est conservé que s'il bat le précédent dans un match de plusieurs centaines de parties. Jusqu'ici, chaque génération a été nettement plus forte que la précédente :

Ces chiffres proviennent de parties jouées dans des ouvertures classiques entre des versions de notre propre moteur, 600 parties par match. Les parties d'un moteur contre lui-même ont tendance à exagérer les progrès ; la mesure face à un moteur extérieur se trouve sur la page sur la force du moteur.

Où il en est

• Le quatrième réseau est intégré au moteur. Face à Fairy-Stockfish réglé sur une force de 2500, il marque 55 %, soit environ 2535 sur cette échelle ; l'évaluation écrite à la main atteint environ 2210 dans le même test.
• Le réseau connaît moins bien la variante que les échecs classiques. Chaque armée sur mesure sur laquelle il s'est entraîné vient de notre générateur, pas d'un joueur : ces positions de départ sont donc un peu artificielles. Quelles armées de vrais joueurs composeraient, nous ne le savons pas encore. La variante est aussi tout simplement plus difficile : plus de types de pièces, et une nouvelle position de départ presque à chaque partie.
• Les parties des joueurs ne sont pas encore collectées. L'idée est que le serveur conserve les parties où un joueur a choisi le niveau 5 et battu le moteur avec une armée sur mesure. Ce n'est pas encore possible. Un réseau a besoin de dizaines de millions de positions d'entraînement — le quatrième a appris sur 68 millions — et les joueurs sont encore loin d'avoir joué assez de parties en variante pour les fournir.