Comment AlphaGo est-il devenu le premier programme à battre un joueur professionnel de go?

Pendant des décennies, l’ancien jeu de go a été le jeu que les ordinateurs n’arrivaient pas à percer. Des programmes avaient battu les meilleurs humains aux dames et, en 1997, aux échecs. Au go, les programmes les plus forts du début des années 2010 jouaient comme de bons amateurs, et bien des experts pensaient qu’il faudrait au moins dix ans avant de battre un professionnel.

Puis, le 27 janvier 2016, l’entreprise d’IA londonienne DeepMind, propriété de Google, a annoncé que son programme AlphaGo y était déjà parvenu. Trois mois et demi plus tôt, à huis clos, AlphaGo avait battu le champion d’Europe, Fan Hui, dans les cinq parties d’un match officiel. Le même jour, la revue scientifique Nature publiait un article qui expliquait comment.

Ce qui s’est passé, quand et où

Fan Hui était un joueur professionnel 2e dan (les grades professionnels vont jusqu’à 9e dan) et avait remporté le championnat d’Europe de go en 2013, 2014 et 2015. DeepMind l’a invité à ses bureaux de Londres, et le match s’est déroulé sur cinq jours, du 5 au 9 octobre 2015. AlphaGo a remporté la première partie par 2,5 points; Fan Hui a abandonné les quatre autres.

Fan Hui a lui-même choisi les limites de temps avant le match. Chaque partie officielle donnait à chaque joueur une heure, plus trois périodes de prolongation de 30 secondes appelées byo-yomi. En plus des parties officielles, les deux ont aussi joué cinq parties informelles avec des contrôles de temps beaucoup plus rapides. Celles-là ont été plus serrées : AlphaGo en a gagné trois et Fan Hui, deux.

DeepMind a gardé le résultat secret jusqu’à ce que son article, « Mastering the game of Go with deep neural networks and tree search », soit prêt. La revue l’a reçu le 11 novembre 2015 et l’a accepté le 5 janvier 2016. Ses vingt auteurs étaient dirigés par David Silver et Aja Huang; on y trouvait le cofondateur de DeepMind, Demis Hassabis, ainsi qu’Ilya Sutskever, de Google. Le programme qui a affronté Fan Hui tournait sur un réseau d’ordinateurs comptant 1 202 processeurs ordinaires et 176 processeurs graphiques.

Comment fonctionnait AlphaGo

Le go se joue sur une grille de 19 sur 19. Deux joueurs placent à tour de rôle des pierres noires et blanches, en cherchant à encercler du territoire et à capturer les pierres de l’adversaire. Les règles sont simples, mais le nombre de parties possibles est astronomique, de sorte qu’un programme ne peut pas simplement tout essayer (nous y revenons plus bas).

AlphaGo combinait trois ingrédients :

• Un réseau de politique (policy network) qui examine le plateau et suggère les coups qui valent la peine d’être envisagés. Il réduit des centaines de coups permis à une poignée de coups prometteurs.
• Un réseau de valeur (value network) qui examine une position et estime qui a le plus de chances de gagner à partir de là, sans jouer la partie jusqu’au bout.
• La recherche arborescente Monte-Carlo, une méthode qui explore les coups futurs possibles, guidée par les deux réseaux, et retient le coup qui mène aux meilleurs résultats.

Les réseaux ont appris par étapes :

Un réseau de neurones, ici, est un programme doté de millions de connexions ajustables qui apprend des régularités à partir d’exemples; le plateau y entre sous forme de grille de nombres, et il en sort un coup ou une probabilité de victoire. L’apprentissage par renforcement consiste à apprendre par essais et erreurs à partir de récompenses, ici tout simplement gagner ou perdre.

Pourquoi c’était important

AlphaGo a été le premier programme à battre un professionnel humain au go sur un plateau de taille normale, sans pierres de handicap. La manière dont il a gagné comptait tout autant. L’article souligne que, contre Fan Hui, AlphaGo a examiné des milliers de fois moins de positions que Deep Blue d’IBM contre Garry Kasparov aux échecs. Il compensait en choisissant plus habilement les positions à examiner et en les jugeant plus précisément, une approche qui, selon les auteurs, se rapproche davantage de la façon dont jouent les humains. Et contrairement à Deep Blue, dont les règles d’évaluation étaient faites à la main, AlphaGo tirait ses connaissances de méthodes d’apprentissage générales.

Tout le monde n’était pas encore convaincu qu’il s’agissait d’un « moment Deep Blue ». Fan Hui était un professionnel solide, mais loin d’être le meilleur au monde. Le champion coréen Lee Sedol a jugé qu’AlphaGo jouait comme un amateur de haut niveau plutôt que comme un professionnel. L’annonce de DeepMind nommait déjà le prochain test : un match de cinq parties contre Lee à Séoul en mars, qu’AlphaGo allait remporter quatre parties à une.

Pourquoi le jeu de go était-il tellement plus difficile que les échecs pour les ordinateurs?

La réponse courte, c’est la taille de la recherche. Aux échecs, un joueur a habituellement environ 35 coups permis, et une partie dure environ 80 coups. Au go, il y a environ 250 coups permis par tour, et les parties durent environ 150 coups. Multipliez ces choix et l’arbre de jeu du go écrase celui des échecs. L’annonce de DeepMind l’a dit de façon frappante : le go compte plus de positions possibles qu’il n’y a d’atomes dans l’univers.

Le second problème, c’est de juger une position. Aux échecs, compter le matériel (une dame vaut environ neuf pions, et ainsi de suite) donne une idée approximative de qui mène, et Deep Blue s’appuyait sur des règles de ce genre réglées à la main. Au go, toutes les pierres sont égales, et la force ou la faiblesse d’un groupe dépend de régularités subtiles sur l’ensemble du plateau. Les joueurs forts décrivent souvent leurs jugements comme de l’intuition.

C’est pourquoi les deux réseaux d’AlphaGo étaient si importants. Le réseau de politique réduisait le nombre de coups à envisager, et le réseau de valeur fournissait une sorte d’intuition apprise sur qui est en train de gagner. Ensemble, ils ont transformé une recherche sans espoir par la force brute en une recherche qu’un ordinateur pouvait mener.