Journal d'un terrien

Web log de Serge Boisse

On line depuis 1992 !

Recherche personnalisée

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.

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). Le jeu se déroule sur un quadrillage, généralement de 19x19 appelé Goban.  Chaque joueur (en commençant par noir) pose tour à tour une pierre sur une des intersections du quadrillage. Les pierres ne bougent jamais. Plusieurs pierres de la même couleur situées côte à côte (horizontalement ou verticalement) forment une chaîne.  Les intersections vides situées à coté d'une chaîne sont appelés ses libertés.  Une chaîne qui n'a plus de liberté est  prise (elle est retirée du jeu). Dans la situation de l'image ci-contre, la pierre blanche est en Atari : elle n'a plus qu'une liberté, et noir peut la prendre en jouant juste en dessous.  Si c'est blanc qui joue en dessous, la chaîne résultante aura 3 libertés et sera plus bien dure à capturer. Il est interdit de poser une pierre sur une intersection qui n'a aucune liberté (sauf si la pierre peut en acquérir en capturant d'autres pierres en ce faisant) , et il est aussi interdit de poser une pierre si cela recrée la situation du coup précédent.  Voila, c'est tout.

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".

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 !

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.  Les humains peuvent d'ailleurs le vaincre. Lors de sa quatrième partie contre le programme,  Lee Sedol a d'ailleurs joué un coup complètement innatendu, mais génial, qui a pris au dépourvu le programme et lui a donné une victoire.

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. Cependant, construire une vraie IA, 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.




Home Mes livres Mes tableaux Plan du site

Partagez / votez pour cette page :

Journal d'un terrien

Commentaires (2) :

Page : [1] 

Juiced
Le 30/06/2016 à 16h28
Salut je suis joueur d'échecs et j'aime aussi le jeu de go(mais il est très statique contrairement aux échecs),je pense que c'est une bonne nouvelle pour le monde du go ce qui s'est passé avec Lee sedol ,à l'avenir les joueurs de go comme aux échecs auront des logiciels performants sur quoi s'entraîner et travailler ,le niveau relatif des joueurs augmentera car ils pourront tester des nouveautés chez eux .Le monde des échecs a vraiment bénéficier des machines aujourd'hui le niveau a considérablement augmenté les parties sont plus serrés les machines sont des outils avant tout voilà je voulais réagir étant donné que je m'intéresse aux échecs et au go pour moi la machine est plus un allié.
Fred
Le 28/03/2016 à 23h51
Super clair. Bravo Serge, je t'embrasse xm


Ajouter un commentaire (pas besoin de s'enregistrer)

Pseudo :
Message :


image de protection
En cliquant sur le bouton "Envoyer" vous acceptez les conditions suivantes : Ne pas poster de message injurieux, obscène ou contraire à la loi, ni de liens vers de tels sites. Respecter la "netiquette", ne pas usurper le pseudo d'une autre personne, respecter les posts fait par les autres. L'auteur du site se réserve le droit de supprimer un ou plusieurs posts à tout moment. Merci !
Ah oui : le html genre <a href=...>, <b>b etc. ne fonctionne pas dans les commentaires. C'est voulu.
< Retour en haut de la page