La guerre sainte électronique
25 Mars 2014
Au jeu d’origine chinoise, le Go, cela aura pris 84 ans de moins que prévu pour que les ordinateurs battent les humains.
En Mai 1997, le supercalculateur d’IBM « Deep Blue » a pris le dessus sur Garry Kasparov dans une série de 6 parties d’échecs, devenant ainsi le premier ordinateur à vaincre un champion du monde des échecs. Deux mois plus tard, le Times a proposé aux machines un autre défi à l’humanité blessé : le jeu chinois de Wei Qi, vieux de deux mille ans, connu en occident sou le nom de Go. L’article disait que les ordinateurs avaient peu de chance de succès : « Il pourrait se passer une centaine d’année – et peut-être même plus – avant qu’un ordinateur batte des humains au Go.
En Mars 2013, seize ans plus tard, un programme informatique nommé Crazy Stone a vaincu Yoshio Ishida, un joueur professionnel de go, cinq fois champion japonais. Le match a eu lieu au cours du premier Densei-sen annuel, ou "guerre sainte électronique", tournoi qui s’est déroulé à Tokyo, où les meilleurs programmes de Go dans le monde jouent contre l'un des meilleurs êtres humains. Ishida, qui avait gagné le surnom d' « ordinateur » dans les années soixante-dix en raison de son style de jeu précis et calculateur, décrit Crazy Stone comme un "génie".
Crazy Stone a reçu un petit handicap, et Ishida n'est plus aussi affuté qu’autrefois, mais cela reste un exploit impressionnant. Comme pour les échecs par ordinateur dans les années quatre-vingt, le Go sur ordinateur est dominé par des programmeurs individuels ou par des petites équipes. Crazy Stone, par exemple, est programmé par une seule personne, Rémi Coulom, professeur de sciences informatiques en France à l'Université Lille 3 .
Aucune grande entreprise n’a encore investi dans le go sur ordinateur à la façon dont IBM a fait avec les échecs. Peter Norvig, directeur de recherche chez Google et l'un des fondateurs de l'IA moderne, m'a dit que, même si Google ou IBM embauchait un groupe d'experts, investissait « dans du matériel cent fois plus puissant que celui déjà utilisé par quiconque sur ce problème», était « très intelligent sur l'architecture, sur la conception du système, sur les algorithmes d'apprentissage par les machines et sur les avancées en neuroscience » , il ne savait pas si ce serait suffisant pour égaler Deep Blue pour le Go.
Le jeu de go semble simple. Le plateau est un carré avec dix-neuf lignes verticales et horizontales qui se croisent, créant 361 points d'intersection. Il commence vide ; deux joueurs à tour de rôle plaçant des pierres circulaires sur les intersections vacantes jusqu'à ce que le jeu soit fini, soit parce que les deux joueurs sont d'accord pour déclarer la fin ou parce qu’un des joueurs abandonne. Les joueurs marquent des points en entourant des intersections ou en capturant les pièces de l'adversaire, chacune ayant une valeur de un point. Pourquoi est-ce si difficile pour les ordinateurs? Aux échecs, il faut quinze coups pour que le nombre d'états possibles du jeu puisse égaler le nombre d'étoiles dans l'univers. Au go, on y arrive en dix coups. À ce moment, une partie moyenne d'échecs est presque à moitié finie, mais au Go cela ne fait que commencer: pour une partie moyenne, il reste encore cent quarante coups, chacun ajoutant un nouvel univers de possibilités.
Cependant, dire que le Go est plus complexe que les échecs, c'est un peu comme dire qu’un infini est plus grand que l'autre. Bien que techniquement vrai, et mathématiquement possible, il n'explique pas entièrement pourquoi les ordinateurs, qui ne peuvent pas calculer entièrement les échecs ou le Go, sont devenus bons à l'un et pas à l'autre. "Quelques centaines d’ordre de grandeur n'ont pas d'importance quand vous comparez dix à cent vingt," m'a dit Murray Campbell, un membre de l'équipe Deep Blue d'IBM. La clé réside dans la structure du Go. Deep Blue a été en mesure d'exploiter une faiblesse dans l'armure du jeu d'échecs: au niveau d’un grand maître, pour dire qui est en train de gagner, vous ajoutez la valeur des pièces sur le jeu et vous prenez en considération leurs positions. Campbell a expliqué que, pour gagner, il vous suffit de rester en tête tout le temps, ce qui réduit considérablement le nombre de coups à considérer pour les ordinateurs.
Wei Qi se traduit par « jeu d’encerclement », et l'une de ses quelques règles est que, quand une pièce est entourée par l’adversaire, elle est retirée du jeu. La règle est transitive ; ainsi de grands groupes de pièces peuvent entourer d'autres grands groupes, qui peuvent eux-mêmes être entourés. Une partie de la difficulté pour les ordinateurs et les humains est qu’il est souvent difficile de déterminer à tout moment si un groupe de pièces est entouré ou si c’est lui qui entoure, et donc qui est en avance. Feng-Hsiung Hsu, un autre membre de l'équipe Deep Blue, écrit que la distinction est particulièrement difficile pour les ordinateurs à saisir parce que « le statut d'un groupe peut affecter ceux de ses voisins – de même qu’un cow-boy qui pointerait son revolver sur un autre cow-boy, qui se retrouverait lui-même couvert par un tireur sur un toit. » Sans une compréhension claire de qui est en avance, des programmes comme Deep Blue bégaient. « Toutes la machinerie qui a été construit pour les échecs par ordinateur est assez inutile », a déclaré Campbell.
Les premiers essais de go par ordinateur étaient basés sur ce que l’on pourrait décrire comme une exégèse calculée. Les stratégies du jeu de go ont été collectées depuis des millénaires sous forme de proverbes ou d’aphorisme et certains d’entre eux comme « Ne jamais couper un nœud de bambou », « N’aller pas à la pèche quand votre maison est en feu » ou « Ne chassez jamais un dragon » peuvent aisément être traduites en lignes de code. Par exemple, « N’aller pas à la pèche quand votre maison est en feu » est interprété selon David Fotland qui a écrit des programmes de Go depuis 1981 comme « Donner la priorité aux réponses locales plutôt qu’à une recherche globale ». D’autre programmes du début utilisent le cerveau humain pour s’en inspirer : des savants en neuroscience au Japon, en Chine et en Corée ont examiné au scanner les cerveaux des professionnels de go mais les tâches dans lesquelles le cerveau humain excelle – reconnaissance des formes, apprentissage, intuition – sont parmi les plus difficiles des problèmes non résolus d’intelligence artificielle (IA). Les vingt premières années d’effort ont abouti à des programmes qui étaient peu efficaces sinon à petite échelle, pour les combats tactiques.
Le programme Crazy Stone de Coulom a été le premier à utiliser avec succès ce qui est connu sous le nom d’algorithme de “Monte Carlo”, développé initialement il y a 70 ans dans le cadre du projet Manhattan.
Monte Carlo, comme son homonyme de casino, la roulette, utilise le hasard pour simuler des mondes possibles: lorsque l'on considère un coup de Go, il commence par celui-ci et joue des centaines de millions de parties aléatoires qui pourraient suivre. Le programme sélectionne alors le coup qui est le plus susceptible de conduire à l'une des victoires simulées. Norvig de Google m'a expliqué pourquoi les algorithmes de Monte Carlo sont une innovation aussi importante: « Nous ne pouvons pas arrêter une partie de Go après vingt coups et dire qui est le gagnant avec certitude. Donc, nous utilisons la méthode de Monte Carlo pour simuler le jeu jusqu’à la fin. Alors, nous savons de façon sûre qui a gagné. Nous répétons ce processus des millions de fois, et chaque fois, les choix que nous faisons sur le chemin sont meilleurs car ils prennent en compte les succès ou les échecs des fois précédentes. "
Crazy Stone a remporté le premier tournoi auquel il a participé. La méthode de Monte-Carlo est devenue l'algorithme de facto pour les meilleurs programmes de go par ordinateur, dépassant rapidement ceux de la génération précédente basés sur l’implémentation des proverbes du jeu de go. Plus les programmes obtenaient des résultats, moins ils ressemblaient à la façon dont les humains jouent: pendant la partie avec Ishida, par exemple, Crazy Stone a joué, du début à la fin, environ 360 000 000 parties aléatoires. A ce rythme, il faut juste quelques jours à Crazy Stone pour jouer plus de parties de go que les humains en ont jamais collectivement jouées. « Je dois être honnête: je trouve toujours magique que cela fonctionne aussi bien", a déclaré Campbell. « Il y a dix ans, a-t-il ajouté, si quelqu'un m’avait décrit la méthode de Monte Carlo, j’aurai dit que cela ne marcherait jamais. »
|
CrazyStone - Yoda |
Yoda Norimoto 9 Dan, Rémi Coulom ( CrazyStone), Hideki Kato (Zen) |
La «guerre sainte électronique » se déroulera une fois par an à Tokyo jusqu'en 2017. Le week-end dernier, lors de la deuxième édition du tournoi, Crazy Stone a affronté Norimoto Yoda, un professionnel japonais qui a la réputation de claquer les pierres sur le plateau de jeu, parfois jusqu’à les briser, pour intimider son adversaire. Crazy Stone a reçu un handicap de quatre pierres d’avance et, n'ayant ni les yeux ni les oreilles d’un joueur humain qui aurait pu être intimidé, a gagné de deux points et demi. Après le match, Yoda, au travers du traducteur, m'a dit qu'il était reconnaissant à Crazy Stone de s’être relâché sur la fin et de permettre ainsi à la partie d'être plus serrée qu'elle ne l'était réellement: le résultat du hasard ou, peut-être, le début de la pitié.
La partie entre CrazyStone et Yoda.
