Go : une belle victoire… des informaticiens !
Serge Abiteboul, ENS Cachan – Université Paris-Saclay et Tristan Cazenave, Université Paris Dauphine – PSL
Cet article est publié en collaboration avec le Blog Binaire.
Après les échecs et la victoire de Deep Blue d’IBM sur Kasparov en 1996, après Jeopardy ! et la victoire de Watson d’IBM en 2011, le jeu de Go résistait parmi les rares jeux où les humains dominaient encore les machines.
Lee Sedol, star du Go.
Wikipédia, CC BY-SA
En mars 2016, un match en cinq manches a opposé une star du Go, le sud coréen Lee Sedol à AlphaGo, le logiciel de Google DeepMind. AlphaGo a gagné ses trois premières parties et a perdu la quatrième.
Score final : AlphaGo 4 – Lee Sedol 1. AlphaGo se voit décerner le titre de Grand Maître du Go, quatrième dans le classement de Go mondial devant Lee Sedol.
L’événement est surtout symbolique pour le monde de la recherche en informatique qui s’attendait à ce que cette frontière tombe un jour. Certains pensaient que les champions de Go résisteraient plus longtemps : le jeu avec son nombre considérable de positions possibles pose des difficultés à des algorithmes qui gagnent surtout par leur capacité de considérer d’innombrables alternatives. C’était sans compter sur les énormes progrès des ordinateurs, de leurs processeurs toujours plus nombreux, plus rapides, de leurs mémoires toujours plus massives, et sans compter surtout sur les avancées considérables de la recherche en intelligence artificielle.
Le mot Go, idéogramme japonais (kanji).
Lee Sedol a été battu par une batterie de techniques super sophistiquées notamment : l’apprentissage profond (deep learning), des techniques de recherche Monte-Carlo (Monte Carlo tree search) et des techniques d’analyse massive de données (big data).
L’apprentissage profond
L’apprentissage profond est une technique qui permet d’entraîner des réseaux de neurones comprenant de nombreuses couches cachées (c’est à dire des modèles de calcul dont la conception est très schématiquement inspirée du fonctionnement des neurones biologiques, les différentes couches correspondant à différents niveaux d’abstraction des données). Ces techniques ont tout d’abord été utilisées pour la reconnaissance de formes. Yann le Cun (Chaire Informatique et Sciences du Numérique cette année au Collège de France) a par exemple utilisé cette technique pour la reconnaissance de caractères manuscrits. Des développements plus récents ont permis des applications en classification d’images et de voix.
Les réseaux de neurones profonds allient la simplicité et la généralité. Ils sont capables de créer leurs propres représentations des caractéristiques du problème pour arriver à des taux de réussites bien meilleurs que les autres méthodes proposées. Ils reposent sur des apprentissages qui demandent des temps assez longs pour les plus gros réseaux. Pour accélérer l’apprentissage, les concepteurs de réseaux profonds utilisent des cartes graphiques puissantes comme celles de Nvidia qui permettent de réaliser très rapidement des multiplications de grandes matrices. Malgré cela, le temps d’apprentissage d’un gros réseau peut se compter en jours voire en semaines.
Plateau de jeu de Go.
Wikipédia, CC BY-SA
Les réseaux utilisés pour AlphaGo sont par exemple composés de 13 couches et de 128 à 256 plans de caractéristiques. Pour les spécialistes : ils sont « convolutionnels » avec des filtres de taille 3×3, et utilisent le langage Torch, basé sur le langage Lua. Pour les autres : ils sont très complexes. AlphaGo utilise l’apprentissage profond en plusieurs phases. Il commence par apprendre à retrouver les coups d’excellents joueurs à partir de dizaines de milliers de parties. Il arrive à un taux de reconnaissance de 57 %. Il joue ensuite des millions de parties contre différentes versions de lui même pour améliorer ce premier réseau. Cela lui permet de générer de nouvelles données qu’il va utiliser pour apprendre à un second réseau à évaluer des positions du jeu de Go. Une difficulté est ensuite de combiner ces deux réseaux avec une technique plus classique de « recherche Monte-Carlo » pour guider le jeu de l’ordinateur.
La recherche Monte-Carlo
Le principe de la recherche Monte-Carlo est de faire des statistiques sur les coups possibles à partir de parties jouées aléatoirement. En fait, les parties ne sont pas complètement aléatoires et décident des coups avec des probabilités qui dépendent d’une forme, le contexte du coup. Tous les états rencontrés lors des parties aléatoires sont mémorisés et les statistiques sur les coups joués dans les états sont aussi mémorisées. Cela permet lorsqu’on revient sur un état déjà visité de choisir les coups qui ont les meilleures statistiques. AlphaGo combine l’apprentissage profond avec la recherche Monte-Carlo de deux façons. Tout d’abord, il utilise le premier réseau qui prévoit les coups pour essayer en premier ces coups lors des parties aléatoires. Ensuite il utilise le second réseau qui évalue les positions pour corriger les statistiques qui proviennent des parties aléatoires.
L’analyse massive de données
AlphaGo fait appel à des techniques récentes de gestion et d’analyse massive de données. Un gros volume de données consiste d’abord dans les très nombreuses parties d’excellents joueurs disponibles sur Internet ; ces données sont utilisées pour amorcer l’apprentissage : AlphaGo commence par apprendre à imiter le comportement humain. Un autre volume considérable de données est généré par les parties qu’AlphaGo joue contre lui-même pour continuer à s’améliorer et finalement atteindre un niveau superhumain.
Bravo !
La défaite de Lee Sedol doit être interprétée comme une victoire de l’humanité. Ce sont des avancées de la recherche en informatique qui ont permis cela, ce sont des logiciels écrits par des humains qui ont gagné.
Les techniques utilisées dans AlphaGo sont très générales et peuvent être utilisées pour de nombreux problèmes. On pense en particulier aux problèmes d’optimisation rencontrés par exemple en logistique, ou dans l’alignement de séquences génomiques. L’apprentissage profond est déjà utilisé pour reconnaître des sons et des images. AlphaGo a montré qu’il pourrait être utilisé pour bien d’autres problèmes.
Émerveillons-nous de la performance d’AlphaGo. Il a fallu s’appuyer sur les résultats de chercheurs géniaux, utiliser les talents d’ingénieurs, de joueurs de Go brillants pour concevoir le logiciel d’AlphaGo, et disposer de matériels très puissants. Tout cela pour vaincre un seul homme.
Émerveillons-nous donc aussi de la performance du champion Lee Sedol ! Il a posé d’énormes difficultés à l’équipe de Google et a même gagné la quatrième partie. Il était quand même bien seul face aux moyens financiers de Google, à tous les processeurs d’AlphaGo.
Les humains réalisent quotidiennement des tâches extrêmement complexes comme de comprendre une image. Prenons une de ces tâches très emblématiques, la traduction. Si les logiciels de traduction automatique s’améliorent sans cesse, ils sont encore bien loin d’atteindre les niveaux des meilleurs humains, sans même aller jusqu’à un Baudelaire traduisant Les histoires extraordinaires d’Edgar Allan Poe. Il reste encore bien des défis à l’intelligence artificielle.
Serge Abiteboul, Directeur de recherche à Inria, membre de l’Académie des Sciences, professeur affilié , ENS Cachan – Université Paris-Saclay et Tristan Cazenave, Professeur LAMSADE – Université Paris-Dauphine , Université Paris Dauphine – PSL
La version originale de cet article a été publiée sur The Conversation.