Comment fonctionne AlphaZero ?

Vous avez forcément déjà entendu parlé de la nouvelle terreur des programmes d'échecs : AlphaZero, celui qui a largement dominé Stockfish, le plus fort programme open-source du monde.

Les réactions de la communauté échiquéenne ont été variables : certains étaient admiratifs, d'autres incrédules.

Mais comment fonctionne réellement AlphaZero ?

Pourquoi est-il différent des autres programmes d'échecs, et surtout pourquoi est-il meilleur qu'eux ? Dans cet article en deux parties, je vais tenter d'expliquer un peu ce qui se trame sous le capot de l'incroyable programme.

Penchons-nous déjà sur les conditions de son exploit. AlphaZero a été développé par DeepMind, une filiale de Google. Son objectif était d'apprendre tout seul (en partant de "Zéro") à jouer aux jeux à deux joueurs en coups alternés. La seule chose qu'on lui ai implémenté, ce sont les règles du jeu.

Le programme a ensuite appris à jouer aux échecs en jouant contre lui-même. La première partie a du comporter des coups très étranges. Mais à son terme, le programme avait appris que le perdant avait joué des mauvais coups, et que ceux du gagnant étaient sans doute meilleurs. Il avait appris tout seul sa première leçon. La qualité de jeu fut légèrement meilleure dans la seconde partie.

Neuf heures et 44 millions de parties plus tard, AlphaZero était sans doute devenu le meilleur joueur d'échecs, humains et machines confondus, de l'histoire.

Comment est-ce possible ?

La siège de Google à Londres. Les locaux de DeepMind sont au huitième étage. | Photo : Maria Emelianova/Chess.com.

Il n'a pas calculé plus de variantes que Stockfish.

C'est même le contraire, en vérité : Stockfish examine 70 millions de positions par seconde, alors qu'AlphaZero se contente de 80 000 positions par secondes, soit un taux 99,89% inférieur. Cela me rappelle la remarque de Jonathan Rowson, après sa cuisante défaite face à Michael Adams lors d'un match en 1998 : "J'ai été impressionné par le peu qu'il voyait."

Les forts joueurs calculent en effet souvent moins de variations que les moins forts. Leur puissante intuition leur permet de se concentrer uniquement sur les lignes dignes d'attention. Et c'est exactement ce que fait AlphaZero. En apprenant à la manière d'un humain, le programme a développé une "intuition", chose qu'on avait jamais entrevu auparavant chez une machine. Il suffit ensuite de combiner ce savoir-faire à une excellente puissance de calcul, et le tour est joué...

Voyons comment il s'y est pris.

L'arbre d'analyse

Les programmes d'échecs utilisent une structure en forme d'arbre pour calculer les variantes, et utilisent une fonction d'évaluation pour estimer la fin de la variante en question. Ce qui donne des notes, par exemple, +1,5 (les blancs ont un avantage d'une valeur d'un pion et demi) ou -9,0 (les noirs ont un avantage de la valeur d'une dame). Mais l'approche de calcul et d'évaluation d'AlphaZero est radicalement différente de celle des autres programmes.

Tous les plus forts programmes d'échecs sont basés sur un algorithme minimax, un nom qui semble compliqué, mais qui signifie simplement que le programme va choisir le coup qui lui donnera le plus grand avantage selon son évaluation, sans considération pour les coups de l'adversaire. Un algorithme minimax est invariablement amélioré grâce à un élagage alpha-bêta, consistant à réduire la taille de l'arbre d'analyse à examiner. Voici un exemple extrême d'élagage : Mettons qu'un programme réfléchisse à un coup pour lequel son adversaire a 20 réponses possibles. L'une de ces réponses mène à un mat forcé. Le programme va alors abandonner le calcul de la variante en question, quelque soit son évaluation par rapport aux 19 autres coups.

Un autre problème est que si un programme élague les coups qui semblent mauvais, (par exemple, ceux qui perdent du matériel), il manquera des sacrifices intéressant. C'est en partie pour cette raison que les programmes d'échecs sont si matérialistes. Sur Stockfish, par exemple, cet élagage alpha-beta est combiné à toute une gamme d'améliorations spécifiques aux échecs, comme l'heuristique des coups gagnants (un fort coup dans une variation similaire sera surement également fort), l'heuristique de réponse directe (contre certains coups, la réponse naturelle est souvent la plus appropriée, j'imagine par exemple que vous avez souvent répondu axb5 à axb5, pas vrai ?) et d'autres...

AlphaZero, en revanche, utilise un algorithme de Monte-Carlo. Monte-Carlo est célèbre pour son casino, c'est pourquoi ce nom a été choisi. En effet, cet algorithme utilise une grande part d'aléatoire. Un programme utilisant un pur Monte-Carlo évaluera la position en générant un certain nombre de séquences aléatoires depuis la position de base, et en faisant une moyenne des score obtenus (gain/nulle/défaite). Et si cet approche vous semble somme toute un peu simpliste, détrompez-vous : c'est en fait un très bon moyen d'évaluer une position.

Le Casino de Monte-Carlo. 

AlphaZero crée ainsi 800 suites pour chaque coup. Il améliore également le pur Monte-Carlo en privilégiant les coups encore peu essayés, les suites à l'aspect le plus plausible, et les positions qui semblent "bonnes" ("bonnes" signifiant : qui reçoivent une bonne évaluation). Le logiciel crée donc des suites aléatoires, et les lignes qui semblent les plus appropriées continue à enrichir sa fonction d'évaluation. N'est-ce pas justement comme cela que nous calculons, en s'attachant en priorité aux suites les plus plausibles ?

Vous aurez remarqué que jusqu'à présent, rien dans le fonctionnement d'AlphaZero n'est spécifique aux échecs. Dans mon prochain article, nous verrons comment AlphaZero évalue les positions, et nous comprendrons qu'encore une fois, les échecs n'ont rien à voir là-dedans !

A l'instar d'un nouveau-né, AlphaZero fut crée sans connaissances, mais avec une immense capacité cognitive. L'une des faiblesses de l’algorithme de Monte-Carlo, cependant, est qu'en créant des suites aléatoires, il peut complètement se tromper dans des positions tendues, où une seule ligne précise est optimale. S'il ne sélectionne pas la ligne en question aléatoirement, il gaffera. Cet aveuglement temporaire est sans doute la raison pour laquelle le prédécesseur d'AlphaZero, AlphaGo, a perdu une partie contre Lee Sedol, 18 fois champion du monde de Go. Cependant, contre Stockfish, le programme de DeepMind ne semble pas avoir subi ce genre de contretemps.

L'algorithme de Monte-Carlo avait déjà été utilisé pour les jeux à deux joueurs auparavant, mais il s'est avéré qu'il fonctionnait beaucoup moins bien que l'approche "minmax plus alpha-beta". Pourtant, sur AlphaZero, le Monte-Carlo se combine très bien avec le réseau neuronal de la fonction d'évaluation.

Dans mon prochain article, j'expliquerai plus en détails comment ce réseau neuronal fonctionne, et surtout comme il apprend seul à évaluer les positions. J'aborderai également le sujet du matériel informatique nécessaire pour faire tourner AlphaZero, et vous livrerai mes prédictions sur son impact sur le jeu d'échecs tel que nous le connaissons.

Que pensez-vous de la manière dont AlphaZero joue aux échecs ? Dites-le-nous dans les commentaires !