Comment un ordinateur peut-il apprendre le go en jouant au hasard ?

En jouant une position jusqu'au bout, de nombreuses fois, avec des coups tirés au hasard, et en comptant quels coups ont tendance à gagner. Cette méthode, la recherche arborescente Monte-Carlo, consacre ensuite plus d'efforts aux coups qui ont le plus souvent gagné : son arbre de recherche pousse de façon inégale, vers les branches prometteuses, et c'est pourquoi elle fait mieux que la recherche classique dans les jeux où chaque tour offre beaucoup de coups possibles, comme le go. AlphaGo, de Google DeepMind, l'a associée à des réseaux de neurones qui jugent les coups et les positions, et il est devenu en octobre 2015 le premier programme à battre un joueur de go professionnel sur un plateau complet de 19x19, sans handicap.

L'idée remonte plus loin que le go. En 1987, Bruce Abramson a combiné la recherche classique dans un arbre de jeu avec un modèle de résultat attendu fondé sur des parties jouées au hasard jusqu'à la fin, plutôt qu'une formule d'évaluation figée. En 1992, B. Brügmann a été le premier à utiliser cette idée de parties aléatoires dans un programme de go. En 2006, Rémi Coulom a formellement nommé la technique recherche arborescente Monte-Carlo, et la même année Kocsis et Szepesvári ont présenté UCT, une formule qui équilibre les coups au fort taux de victoire et ceux qu'on a encore à peine essayés.

Chaque tour de la recherche suit quatre étapes : la sélection, où l'algorithme descend dans l'arbre en choisissant les positions enfants les plus prometteuses ; l'expansion, où il ajoute une nouvelle position à explorer ; la simulation, où il joue une partie au hasard jusqu'à la toute fin depuis cette nouvelle position ; et la rétropropagation, où le résultat met à jour les statistiques de victoire de chaque position le long du chemin parcouru. Les positions qui ont gagné plus souvent sont revisitées plus souvent, si bien que la recherche concentre naturellement son effort sur les coups qui semblent les meilleurs, sans jamais avoir besoin d'analyser la partie entière.

En mars 2016, AlphaGo a reçu un rang honorifique de 9e dan après avoir battu le champion Lee Sedol quatre parties à une. Ce qui a fait d'AlphaGo une véritable avancée, c'est la combinaison de la recherche arborescente Monte-Carlo avec des réseaux de neurones, permettant au programme de juger quels coups et quelles positions étaient prometteurs bien plus efficacement que de simples parties aléatoires.