Auteur: Serge Boisse
Date: Le 31/03/2023 à 17:03
Type: web/MOC
Tags: 
pub: oui
commentaires: ouiCopier

Comment fonctionne AlphaGo, le meilleur programme de Go du monde

Google n'est pas très bavard sur le fonctionnement interne de son programme AlphaGo,  se contentant de l'aura que lui procurent ses récentes victoires contre le champion d'Europe Fan Hui Octobre 2015, puis contre le 4ieme joueur du monde, neuvième dan pro Lee Sedol (mars 2016, 4 parties à 1).  J'ai tenté pendant 30 ans de créer un programme de Go au top niveau, et je ne sens donc légitimement un peu frustré. Je vais donc tenter, à la lumière de ma modeste expérience, de vous dire comment je crois qu'AlphaGo fonctionne réellement, et ce que cela implique pour l'IA en général.

le jeu de Go

Je suppose que vous savez (un peu) jouer au Go. si nous le le savez pas, en voici les règles, elles sont très simples (La beauté du jeu vient de la complexité incroyable des situations que l'on peut obtenir à partir de ces règles très simples).

On pourrait croire que le jeu consiste à capturer les pierres ennemies, mais on se rend vite compte que certaines pierres seront impossibles à capturer parce qu'elles auront au moins deux libertés dans lesquelles il est interdit de jouer (on les appelle les yeux). La meilleure façon de jouer consiste donc à créer ce genre de chaînes ou de groupes imprenables, délimitant des territoires dans lequel l'adversaire ne peut pas jouer, ou n'a pas intérêt à le faire parce que ses pierres seront inévitablement capturées plus tard. Plus on joue, plus on aime ce jeu, et plus on apprécie son incroyable subtilité.

Sur un Goban de 19x19, il y a 361 intersections, et cela constitue autant de coups possibles. Même en milieu de partie, lorsqu'une centaines de pierres auront été posées,  il y a 200 coups possibles ! C'est l'une des raisons qui rend le jeu de Go si difficile à programmer sur ordinateur, et la raison (plus la subtilité...) pour laquelle on a parfois dit que le jeu de Go est "le graal de l'intelligence artificielle".

AlphaGo : La base

Alors, comment fonctionne AlphaGo ? L'algorithme de base est celui de tout programme de jeu : on cherche les coups possibles, on les évalue, et on sélectionne le meilleur. Éventuellement, on répète à partir de chaque position résultante. Mais cela ne fonctionne pas au Go, car le nombre de coups possibles à chaque étape est très élevé et dès qu'on atteint une "profondeur" de six ou sept coups le temps de calcul devient énorme, même sur un super-ordinateur. (Il est multiplié à chaque niveau par le nombre de coups possibles,soit environ 150 en milieu de partie !) Les programmes de jeu "classiques"  se bornent donc à envisager quelques coups à l'avance et reposent sur une fonction d'évaluation, qui est une analyse statique (généralement très complexe) de la positon obtenue, et qui donne un score sensé évaluer l'avantage du programme.

AlphaGo possède bien une fonction d'évaluation, mais elle n'est pas utilisée ainsi.  La première chose à comprendre est qu'il utilise une méthode de Monte-Carlo. On donne ce nom à une méthode basée sur le hasard : au lieu d'évaluer les positions à une profondeur fixe, AlphaGo joue un coup, puis simule un grand nombre de parties à partir de  la position obtenue, en choisissant les coups au hasard. Ces parties sont simulées jusqu'à la fin, c'est à dire au Go jusqu'à ce que qu'une seconde fonction d'évaluation (simple et rapide, celle-là) permette de calculer précisément le score final., sans risque d'erreur : ce qui est le cas en fin de partie, où le comptage des points est simple. (Même si au Go c'est bien plus subtil qu'aux échecs !)  Dans une méthode de Monte-Carlo, on va donc simuler des millions de parties au hasard à partir de chaque position à une profondeur un. Le coup qui donne le plus grand nombre de parties gagnantes est celui que l'on va jouer.

AlphaGo utilise un raffinement de cette méthode, une idée que j'avais eue il y a une dizaine d'années, mais sans la publier (je sais que cela fait très prétentieux de dire cela, mais c'est pourtant vrai). Les coups jouées lors de chaque simulation de partie seront ne seront pas choisis au hasard,mais "presque au hasard". L'idée est de simuler des coups qui sont aléatoires, mais pas stupides. On munit donc le programme  d'une  autre fonction d'évaluation (encore une), le "policy network", dont le rôle est de sélectionner à chaque étape des coups pas forcément optimaux mais pas trop mauvais a priori.

Cela fonctionne très bien, mais n'est pas suffisant pour battre un champion humain.  Et puis simuler toutes les parties jusqu'au bout est très souvent une perte de temps car dans beaucoup de cas l'avantage d'un joueur à partir d'un certain moment est tel que la victoire (ou la défaite) est quasi certaine. AlphaGo utilise donc une fonction d'évaluation,le "value network", qui fera une évaluation statique (sans jouer les coups), détectera ce genre de situation et permettra au programme de ne pas continuer dans ce cas.

 Plus précisément, imaginons que nous soyons arrivés à une position P, à partir de laquelle le "policy network"  aura sélectionné, disons une dizaine de coups C1,...,C10 qui sont a priori "pas trop mauvais. Chacun de ces coups aura un score (donné par le value network)  S1,...,S10. On simule quelques milliers de parties au hasard (mais pas tout à fait puisqu'on utilise le policy network) jusqu'à la fin, à partir de chacune des positions obtenues P1,...,P10.  Le score final de chaque coup Ci sera un mélange savant du score "dynamique" donné par ces simulations guidés par le policy network, et du score "statique" donnée par la fonction d'évaluation elle-même (le "value network").  

Cet algorithme peut-être utilisé récursivement, c'est à dire que ces scores finaux seront utilisés pour évaluer les coups à la profondeur 2, puis 3, etc.

Tout cela est très gourmand en temps de calcul, et AlphaGo utilise jusqu'à 1202 CPU en parallèle, ainsi que 176 GPU (Graphic processing units) ! L'algorithme décrit ci-dessus est en effet très facilement parallélisable puisqu'on peut jouer des centaines de simulations en même temps sur des CPU différents...

Le coeur du programme

On comprend que pour que le programme joue au top niveau, il nous faut deux fonctions très perfectionnées : le value network pour l'évaluation statique des positions, et le policy network pour la sélection des coups "pas trop mauvais".  Le coup de génie de Google,  c'est d'avoir réalisé ces deux fonctions à l'aide de réseaux de neurones formels ( "network" signifie réseau).

Qu'est ce qu'un réseau de neurones formel ?  c'est un réseau formé de centaines (ou de milliers, voire de millions) de petites boîtes identiques, les "neurones", possédant chacune des dizaines "d'entrées" (qui seront des nombres), et une seule sortie (qui est aussi un nombre).  Chaque neurone effectue un calcul très simple pour déterminer la valeur de sortie à partir des valeurs d'entrée (par exemple en calculer la moyenne, ou le nombre d'entrée qui sont supérieures à un certain seuil) . La sortie d'un "neurone" peut alimenter à son tour  des dizaines d'autres neurones. Le calcul effectué par chaque neurone peut être différent, mais généralement  dans un réseau tous les neurones font le même calcul, à un détail prés : chaque neurone possède une petite mémoire individuelle qui contient des coefficients qui seront utilisés par le calcul.  Par exemple, les neurones peuvent faire des "somme pondérées"  de leurs n entrées, en multipliant  d'abord chaque entrée i par un un coefficient Ci, puis en faisant la somme finale, et enfin en bidouillant un peu cette somme (par exemple en la faisant passer à travers ce que l'on appelle une fonction sigmoïde). On comprend que le choix et l'ajustement de tous ces coefficients sera essentiel pour le bon fonctionnement du réseau.

Les réseaux de neurones formels ont été très étudiés depuis une trentaine d'années par des mathématiciens et des informaticiens, et ont prouvé leur efficacité, en particulier dans des applications de reconnaissance de de formes. C'est notamment un réseau de neurones formels qui permet à l'algorithme de reconnaissance de voix de Google de fonctionner, ainsi que son algorithme de reconnaissance d'images. Les GPU des micro-ordinateurs sont très performants pour ce genre de calculs simples, et c'est pourquoi AlphaGo les utilise abondamment.

L'architecture du "cerveau" formé par le réseau est importante.  Le réseau "policy network" d'AlphaGo est formé de 13 couches successives, chaque couche alimentant les entrées de la couche suivante. Google donne très peu de détails sur cette architecture, hélas.  Pour le "Value network", Google est encore moins prolixe ! Secret, quand tu nous tiens....

Dans ces deux réseaux, les entrées de la première couche de neurones sont directement obtenues à partir de la position courante du jeu à évaluer (par exemple +1 pour une intersection contenant une pierre blanche, -1 pour une pierre noire et  0 pour une intersection vide).  En fait, comme l'élément principal du Go est constitué par les chaînes et non les pierres, et que les chaînes sont formées de pierres reliées horizontalement ou verticalement, on va utiliser des algorithmes de traitement d'image pour accentuer les liaisons verticales ou horizontales sur "l'image" du Goban.  Les premières couches du réseau sont donc dédiées à ce genre de traitement, que l'on appelle convolution en mathématiques.  Il y a aussi quelques neurones chargés de reconnaître certaines formes caractéristiques (des configurations fréquentes de pierres proches) qui sont importantes dans la littérature consacrée au Go. Les dernières couches donneront, pour chaque intersection, une évaluation de la probabilité que jouer "ici" conduisent à une victoire.  Les couches intermédiaires.... Et bien c'est bien là qu'est le problème.

L'apprentissage

En effet, tout cela est bel et bon, mais cela ne suffit toujours pas pour battre un joueur du niveau de Lee Sedol. Comment déterminer les bons coefficients pour chaque neurone ? Par l'apprentissage ! Les ingénieurs de Google ont amélioré une méthode qui  permet d'affiner progressivement ces dizaines (centaines ?) de milliers de coefficients , en procédant couche après couche. Ils ont tout d'abord "instruit" AlphaGo en le testant sur des millions de situations réelles rencontrées par des professionnels au cours de partie réelles (il existe d'énormes bases de données gratuites sur le web consacrées au jeu de Go), et en demandant au programme de "deviner" le coup joué par l'expert humain dans cette situation.. Si le réseau ne trouve pas le bon coup, on ajuste les coeffiscent menant à ce coup dans la dernière couche du réseau, puis dans les couches précédentes (en ajustant un peu moins, car  les neurones de la couche n-1 alimentent plusieurs neurones de sortie, etc.  C'est ce que l'on appelle le Deep Learning,  ou apprentissage profond.

Après cette phase d'apprentissage profond par ajustement progressif des coefficients, AlphaGo était déjà au niveau pro, soit meilleur que les meilleurs programmes existants.  Mais était-il au niveau d'un champion du monde ? Pour le savoir, les ingénieurs de Google ont appliqué une autre stratégie : le reinforcement learning, ou  apprentissage par renforcement. Il s'agit tout simplement de faire jouer le programme contre une autre version de lui même, avec des coefficients légèrement modifiés.  Si la version modifiée gagne, on recommence à partir de celle-ci. Après des millions de parties ainsi jouées contre lui même, AlphaGo devint capable de battre Lee Sedol !

et soudain... Alphago zero !

Dernières nouvelles : Google ne s'est pas arrété là.. En janvier 2017, une amélioration, "Alphago Master",  a été opposée à 60 joueurs de Go parmi les meilleurs du monde... et a remporté 60 victoires ! Mais les programmeurs de Google ont eu une autre idée : repenser complètement l'architecture du programme et supprimer l'étape d'apprentissage humain. Pour cela, la nouvelle version, alphaGo zero (sans accent sur le zéro : c'est un nom anglais), ne comporte plus qu'un seul réseau de neurones, et tout le code informatique liée aux simulations de parties "au hasard" (ce que l'on appelle la méthode de Monte-Carlo) a été supprimé.

Au lieu de cela, alphaGo zero se base uniquement sur le value network : il évalue donc les positions statiquement.  Ce réseau a été entrainé (il a appris) uniquement en jouant contre lui même, des milliers de parties, en temps limité (5 secondes par coup).. AlphaGo zero apprend donc tout seul, à partir des seules règles élémentaires; sans aucune intervention humaine !

Après quelques semaines, alphaGo zero devint capable de battre la version "alphaGo tout court" à chaque partie, devenant donc probablement le meilleur joueur de Go du monde ! fin 2017, son classement ELO (une échelle internationale permettant de classer les meileurs joueurs) est de plus de 5000, un score jamais atteint par un humain.

AlphaGo zero a "redécouvert" un grand nombre de techniques utilisées par les joueurs humains professionnels, et en particulier de nombreux joseki (des séquences de coups forcés dans les coins du goban) et fuseki (des séquences d'ouvertures), mais il en a également inventé de nouvelles, très intéressantes, prouvant sans aucun doute qu'un programme peut faire preuve de créativité. Les professionnels humains commencent maintenant à utiliser ces coups dans leurs propres parties !

Qu'en conclure ?

Alpha Go est un programme très spécialisé, conçu pour jouer au Go et rien d'autre. Ce n'est pas une vraie IA. Les millions de données accumulées au cours de sa création, les coefficients laborieusement ajustés, tout cela ne permet que de jouer au Go. Alpha Go ne sait pas jouer aux échecs et pour appliquer la même méthode aux échecs il faudrait le modifier complètement. Donc, non, alphaGo ne représente pas une avancée décisive de l'intelligence artificielle.  Mais il est devenu, pourtant, meilleur que n'importe quel joueur humain. 

Et pourtant... Le succès d'AlphaGo contre Fan Hui puis Lee Sedol a surpris tout le monde, y compris moi.  Les joueurs de Go professionnels ont une telle maîtrise, leurs coups sont tellement subtils que les joueurs amateurs (comme moi) ne peuvent espérer en comprendre qu'une faible partie. Qu'un programme y parvienne, quel accomplissement ! Mais AlphaGo comprend-il ce qu'il joue, au sens que nous les humains nous comprenons ce que nous faisons ? Non, pas vraiment en tout cas. Il peut pourtant se montrer créatif, mais  créativité et intelligence sont deux choses différentes.

AlphaGo a portant prouvé une chose  : La technique du Deep Learning est extrêmement performante. Elle peut conduire les ordinateurs à être, dans certains cas, supérieurs à tous les humains, dans certaines tâches et le nombre de ces tâches inclut maintenant des tâches que l'on croyait impossible, comme la créativité et maîtrise du jeu de Go. Il ne fait nul doute que la liste de ces tâches va augmenter.

C'est la grande tendance de la fin des années 2010 et probablement 2020 : les programmes basés sur l'apprentissage profond (deep learning) deviennent meilleur que les humains dans beaucoup de tâches. Je pense qu'il serait sage de prendre en compte cette évolution, et de laisser ces programmes créer et décider à notre place des meilleures stratégies, non seulement dans les domaines techniques, mais aussi politique, socio-économique, etc. Le monde n'en deviendra que meilleur.

Cependant, construire une vraie IA, consciente, intelligente et sensible, exigera une approche un peu différente, car pour reproduire l'esprit humain il ne suffit pas de simuler le fonctionnement de ses neurones..

Ce n'est pas impossible : lisez mon livre pour en être convaincu !

A voir aussi : le jeu de Go.