Samedi-sciences (198): un programme de Google, nouveau maître de go

Pour la première fois, un ordinateur a battu un champion de go, jeu que l’on pensait jusqu’ici trop complexe pour être maîtrisé par une machine. Dix-huit ans après la défaite de Garry Kasparov contre Deep Blue aux échecs, ce match marque une nouvelle avancée de l’intelligence artificielle.

Fan Hui, champion d'Europe de go, battu en 2015 par le programme AlphaGo © Google Deepmind Fan Hui, champion d'Europe de go, battu en 2015 par le programme AlphaGo © Google Deepmind

Pour la première fois, un ordinateur a battu un champion de go, jeu de stratégie traditionnel originaire de Chine, que l’on pensait jusqu’ici trop complexe pour être maîtrisé par une machine. Pourtant, le programme AlphaGo, mis au point par l’entreprise britannique Deepmind, qui appartient à Google, a battu à plates coutures le champion d’Europe Fan Hui. Ce dernier, né en Chine en 1981, installé en France depuis 2000 et naturalisé Français, a disputé un match en cinq parties contre AlphaGo en octobre 2015. La machine a gagné sur le score sans appel de 5-0.

Dix-huit ans après la défaite de Garry Kasparov contre Deep Blue aux échecs, ce match marque une nouvelle avancée de l’intelligence artificielle. Les spécialistes n’imaginaient pas qu’un joueur de go professionnel soit battu par un programme avant une décennie. Fan Hui lui-même ne cache pas sa surprise, d’autant qu’un match préliminaire avait été plus équilibré (3-2 pour la machine). « Avant de jouer contre AlphaGo, je pensais que je gagnerais, confie Fan Hui à la revue britannique Nature, qui consacre sa couverture à l’événement. Après la première partie, j’ai changé de stratégie et j’ai mieux résisté, mais j’ai perdu. Le problème est que les humains font quelquefois de très grosses erreurs, parce qu’ils sont humains. Nous pouvons être fatigués, ou avoir trop envie de gagner, nous mettre la pression. Le programme n’est pas comme ça. Il est très fort et stable, comme un mur. Pour moi cela fait une grande différence. Je sais qu’AlphaGo est un ordinateur, mais si je ne l’avais pas su, j’aurais peut-être pensé que le joueur était un peu étrange, mais je l’aurais pris pour un joueur très fort, une vraie personne. »

C’est toutefois grâce à la qualité de son jeu, et pas seulement du fait de l’avantage psychologique d’être infatigable et sans émotion, qu’AlphaGo a surclassé Fan Hui. Et là réside l’intérêt de l’histoire. Si le jeu de go a résisté jusqu’ici aux machines, c’est qu’il est d’une extrême complexité, même si ses règles sont simples : sur un plateau quadrillé, comportant 19 lignes horizontales et 19 verticales, soit 361 intersection, deux joueurs placent à tour de rôle des jetons appelés « pierres », respectivement noires ou blanches ; chacun des deux joueurs s’efforce d’encercler une ou plusieurs pierres de l’autre, et s’il y parvient, il capture ces pierres et conquiert la zone qu’elles occupaient; le but du jeu est de contrôler plus de territoire que l’adversaire lorsqu’il n’y a plus de place sur la grille pour poser de nouvelles pierres.

Malgré l’apparente simplicité du jeu, un programme de go ne peut pas reposer sur la seule puissance de calcul, sur la « force brute » : le nombre de configurations possibles est largement plus grand que le nombre d’atomes dans l’univers. Aux échecs aussi, le nombre de combinaisons est trop élevé pour résoudre le problème par la force brute, mais un programme peut explorer quelques coups à l’avant pour évaluer la position résultante et voir quel joueur a l’avantage, en tenant compte de la valeur des pièces de chacun et de leurs positions relatives.

Au go, il est beaucoup plus difficile d’identifier les positions gagnantes ou perdantes : toutes les pierres ont la même valeur et de subtiles différences de position peuvent avoir des conséquences très importantes mais qu’on ne peut pas évaluer simplement.

Comment transmettre à un programme l’intuition d’un joueur expérimenté ? Les concepteurs d’AlphaGo ont utilisé des techniques dites d’apprentissage automatique et des réseaux de neurones artificiels (voir les explications des concepteurs dans la vidéo ci-dessous). Le programme est construit comme un réseau de cellules, organisées en plusieurs couches, dont les connexions se renforcent quand il produit une bonne réponse et s’affaiblit quand la réponse est mauvaise. La couche inférieure représente l’état du jeu à un moment donné, la couche supérieure montre les possibilités pour le coup suivant, et entre les deux s’interposent 11 couches.

 © Nature © Nature

Entraîner le réseau consiste à ajuster les connexions pour qu’il sélectionne un bon coup. Pour amorcer cet apprentissage, les chercheurs ont fourni au programme un ensemble de 30 millions de configurations de jeu, avec pour chacune la continuation choisie par un bon joueur. Les connexions du réseau ont été ajustées pour intégrer ces données. Puis le programme a continué à s’entraîner en jouant contre lui-même, de très nombreuses parties, en utilisant 50 ordinateurs. À chaque itération, le programme s’est amélioré en intégrant les coups donnant la meilleure issue.

AlphaGo s’est ainsi construit une expérience du jeu. « Nous avons développé ce système d’une telle manière qu’il joue plus comme un être humain » que comme une machine, estime Demis Hassabis, qui a dirigé avec David Silver le développement d’AlphaGo. Ce dernier a même un style de jeu, qualifié de « plus conservateur qu’agressif » par Toby Manning, un joueur de go qui a arbitré le match entre le programme et Fan Hui.

La prochaine étape est pour le mois de mars. AlphaGo doit disputer un match contre le Sud-Coréen Lee Sedol, l’un des tout meilleurs joueurs de la décennie, que Silver compare, dans la revue Science, à un « Roger Federer du go ». David Silver dit qu’il n’a pas parié un centime sur la victoire de son champion, mais sera « très décu » si le programme perd, tout en jugeant que tout est possible : « Les êtres humains ont inévitablement plus d’un tour dans leur sac que nous ne pouvons pas nous entraîner à déjouer. »

 

 

Le Club est l'espace de libre expression des abonnés de Mediapart. Ses contenus n'engagent pas la rédaction.