Pourquoi les réseaux de neurones semblent prêts à battre les meilleurs joueurs de Go humains pour la première fois

Les ordinateurs commencent rapidement à surpasser les humains dans plus ou moins tous les domaines d'activité. Par exemple, des experts en vision artificielle ont récemment dévoilé un algorithme qui surpasse les humains en matière de reconnaissance faciale. Des algorithmes similaires commencent également à correspondre aux humains lors de la reconnaissance d'objets. Et les joueurs d'échecs humains ont depuis longtemps abandonné le combat pour battre les ordinateurs.

Mais il y a un domaine où les humains triomphent encore. C'est en jouant à l'ancien jeu chinois de Go. Les ordinateurs n'ont jamais maîtrisé ce jeu. Les meilleurs algorithmes n'atteignent que le niveau de compétence d'un joueur amateur très fort que les meilleurs joueurs humains surpassent facilement.

Cela semble sur le point de changer grâce au travail de Christopher Clark et Amos Storkey de l'Université d'Édimbourg en Écosse. Ces gars-là ont appliqué les mêmes techniques d'apprentissage automatique qui ont transformé les algorithmes de reconnaissance faciale au problème de trouver le coup suivant dans un jeu de Go. Et les résultats laissent peu d'espoir que les humains continueront à dominer ce jeu.

En bref, Go est un jeu à deux joueurs généralement joué sur une grille de 19 x 19. Les joueurs placent alternativement des pierres noires et blanches sur la grille pour tenter d'occuper plus de plateau que leur adversaire à la fin de la partie. Les joueurs peuvent retirer les pierres de leur adversaire en les entourant des leurs.

Les experts pensent qu'il y a deux raisons pour lesquelles les ordinateurs n'ont pas réussi à maîtriser Go. Le premier est le nombre de coups possibles à chaque étape du jeu. Les joueurs de go ont 19 x 19 = 361 coups de départ possibles et il y a généralement des centaines de coups possibles à tout moment du jeu. En revanche, le nombre de coups aux échecs est généralement d'environ 50.

Le deuxième problème est que les ordinateurs ont du mal à évaluer les forces et les faiblesses d'un poste au conseil d'administration. Aux échecs, le simple fait d'additionner la valeur de chaque pièce laissée sur l'échiquier donne une indication raisonnable de la force de la position d'un joueur. Mais cela ne fonctionne pas en Go. Compter le nombre de pierres que possède chaque joueur est un mauvais indicateur de qui gagne, disent Clark et Storkey.

La façon dont les algorithmes Go à la pointe de la technologie s'attaquent à ce problème est de jouer le jeu entier après chaque mouvement et de le faire de différentes manières. Si l'ordinateur gagne dans la majorité de ces jeux, alors ce coup est considéré comme bon.

De toute évidence, il s'agit d'une tâche chronophage et gourmande en calculs. Même ainsi, il ne parvient généralement pas à battre les experts humains en Go qui peuvent généralement évaluer l'état d'une carte Go d'un simple coup d'œil.

De nombreux experts pensent que le secret de la maîtrise du go-play humain est la reconnaissance des formes - la capacité de repérer les forces et les faiblesses en fonction de la forme que font les pierres plutôt qu'en regardant plusieurs mouvements à l'avance.

C'est pourquoi les progrès récents des algorithmes de reconnaissance de formes pourraient aider les ordinateurs à faire beaucoup mieux. Ces avancées ont utilisé des bases de données massives d'images pour former des réseaux de neurones à convolution profonde afin de reconnaître des objets et des visages avec le type de précision qui correspond désormais aux performances humaines. Il est donc raisonnable d'imaginer que le même type d'approche pourrait faire une grande différence pour l'évaluation automatisée des cartes Go.

Et c'est exactement ce que Clark et Storkey ont fait. La question à laquelle ces gars-là ont formé un réseau de neurones convolutifs profonds pour répondre est : étant donné un instantané d'un jeu entre deux experts de Go, est-il possible de prédire le prochain mouvement du jeu ?

La façon dont ils ont abordé cela consiste à utiliser une vaste base de données de jeux de Go pour former un réseau de neurones afin de trouver le prochain mouvement. Clark et Storkey ont utilisé plus de 160 000 jeux entre experts pour générer une base de données de 16,5 millions de positions ainsi que leur prochain mouvement. Ils ont utilisé près de 15 millions de ces paires position-mouvement pour entraîner un réseau neuronal convolutif à huit couches afin de reconnaître le mouvement suivant de ces joueurs experts. C'était un processus qui a pris plusieurs jours.

Ils ont ensuite utilisé le reste de l'ensemble de données pour tester le réseau de neurones. En d'autres termes, ils ont présenté au réseau une position sur le plateau d'un jeu et lui ont demandé de choisir le coup suivant. Clark et Storkey disent que le réseau formé a pu prédire le prochain mouvement jusqu'à 44 % du temps, dépassant l'état de l'art précédent sur cette tâche avec des marges significatives.

C'est intéressant, notamment parce que la nouvelle approche n'utilise aucun des mouvements précédents pour prendre sa décision ; il n'évalue pas non plus les positions futures.

Après avoir formé le réseau de neurones, Clark et Storkey l'ont ensuite joué contre deux des meilleurs algorithmes Go du moment. Le premier s'appelle GNU Go, qui joue à un niveau équivalent à un amateur intermédiaire avec un classement de 6-8 kyu. (Les classements vont d'un débutant avec un classement de 30-20 kyu à un expert professionnel avec un classement de 1 kyu).

Le second était un programme de pointe appelé Fuego 1.1, qui a un classement d'environ 5-4 kyu. Un joueur humain prendrait généralement de nombreuses années d'études pour atteindre ce niveau.

Les résultats suggèrent clairement que l'écriture est sur le mur pour les joueurs humains de Go. Le réseau de neurones de Clark et Storkey a battu GNU Go près de 90 % du temps sur une série de 200 jeux. En d'autres termes, après quelques jours d'entraînement, le réseau neuronal a pu battre GNU Go de manière constante.

Contre Fuego 1.1, il s'en est moins bien sorti, ne remportant qu'un peu plus de 10% de ses matchs. Néanmoins, c'est une réalisation importante. Être capable de gagner ne serait-ce que quelques matchs contre cet adversaire indique qu'un haut degré de compétence a été acquis, disent Clark et Starkey.

C'est clairement très prometteur. Même si les réseaux jouent en utilisant une politique de 'zéro pas en avant' et en utilisant une fraction du temps de calcul de leurs adversaires, ils sont toujours capables de jouer mieux que GNU Go et de retirer certains jeux de Fuego, disent-ils.

Et il y a clairement un potentiel d'amélioration, par exemple en combinant cette approche avec d'autres qui utilisent les mouvements précédents et regardent vers l'avenir. Une idée suggérée par Clark et Starkey est d'exécuter le réseau neuronal convolutif en parallèle avec l'approche conventionnelle pour aider à élaguer l'arbre des mouvements possibles qui doivent être explorés.

Il n'y a aucune suggestion de Clark et Storkey que cette approche battra les meilleurs joueurs de Go au monde. Mais ce n'est sûrement qu'une question de temps avant que même les joueurs de Go n'aient à s'incliner devant leurs seigneurs informatisés.

Réf : arxiv.org/abs/1412.3409 : Enseigner les réseaux de neurones à convolution profonde pour jouer au go

cacher