Jeu de Go : les développeurs s'imposent face à Lee Sedol

L'IA de Google terrasse la star du Go par un score de 4-1

Une intelligence artificielle réussira-t-elle à battre le meilleur joueur du monde au jeu de go ?
AlphaGo a réussi à battre le champion d'Europe

Né il y a plusieurs milliers d'années en Chine et très populaire en Extrême-Orient (Japon, Chine et Corée, essentiellement), le jeu de go est un jeu où s'opposent deux joueurs qui vont s'affronter sur un plateau (le goban) armés de jetons noirs et blancs (les pierres). Tour à tour, les joueurs posent leurs pierres sur les intersections du goban, composé de 19 lignes sur 19, le but étant de contrôler avec ces pierres la plus grande surface possible du plateau.

Des règles qui s'avèrent donc plutôt simples même si, pour un ordinateur, la faculté d'en maîtriser les mécanismes, notamment via une résolution formelle par une recherche arborescente (qui est à la base de la plupart des algorithmes utilisés pour les programmes de jeux à deux joueurs) va s'avérer plus complexe par exemple que s'il s'agissait d'un jeu du morpion, de dames anglaises ou d'échecs. Pour quelle raison ? Le nombre de configurations possibles : il y en a 10 puissance 3 pour le jeu du morpion (sur une grille de 10×10 au lieu de 3×3, avec l'objectif d'aligner 6 pions au lieu de 3), 10 puissance 20 pour le jeu des dames anglaises, 10 puissance 50 pour le jeu d'échecs et 10 puissance 171 pour le jeu de go.

Si en 1997, Deep Blue, un super-ordinateur construit par IBM, a battu aux échecs le champion du monde, Garry Kasparov, l'histoire n'est pas la même pour le jeu de go. Malgré les énormes progrès faits en intelligence artificielle, le programme japonais Zen était considéré comme le meilleur au monde bien qu'il restait très loin du niveau des meilleurs joueurs professionnels. Cette intelligence artificielle se basait sur l’évaluation de la pertinence des coups en simulant des milliers de parties, approche qui a été améliorée grâce à la recherche arborescente Monte-Carlo.

Cette méthode consiste à systématiquement explorer les branches de l'arbre jusqu'à une position terminale pour contourner l'une des difficultés essentielles du go : la définition d'une bonne fonction d'évaluation heuristique. Cependant, étant donné le grand nombre de parties possibles, cette approche ne peut pas explorer exhaustivement toutes les possibilités : il faut donc choisir un sous-ensemble des parties possibles. Se posent alors deux problèmes essentiels : comment choisir celles qu'on explore parmi toutes les possibilités ? Étant donné les séquences observées et leur résultat (gagné ou perdu, dans le cas du go), comment déterminer le meilleur coup ?

Un des algorithmes les plus primitifs consiste à simplement choisir les coups aléatoirement, et à évaluer chaque position par la moyenne du résultat de toutes les parties aléatoires qui passent par cette position. Pour chacun des coups possibles, la moyenne des résultats des parties obtenues après avoir joué ce coup donne une estimation de sa valeur. Il suffit ensuite de choisir le coup qui mène vers la position qui a la meilleure moyenne. Pour donner un ordre de grandeur, les meilleurs programmes actuels parviennent à générer plusieurs dizaines de milliers de parties aléatoires par seconde sur un PC puissant.

En octobre 2015, pour la première fois, une intelligence artificielle a battu un joueur professionnel sur un plateau de taille normal : AlphaGo, un programme développé par la filiale DeepMind (une entreprise britannique créée en 2010 et qui a été rachetée en 2014 par Google) a battu par 5 parties à 0 le joueur professionnel français Fan Hui, 2e dan (sur 9 au maximum) et meilleur joueur d’Europe. Il n’a en outre perdu qu’une partie sur 500 contre les meilleurs programmes déjà sur le marché. C'est dans les parties rapides Fan Hui a mieux résisté, perdant 3 à 2. Les progrès liés à la victoire d’AlphaGo n’étaient pas attendus avant une dizaine d’années dans le milieu de l’intelligence artificielle.

AlphaGo se sert également de cette technique d'exploration, mais la combine à deux autres ingrédients secrets : les deep learning (réseaux de neurones profonds) et l’apprentissage renforcé. Le deep learning est une fonction mathématique aux paramètres ajustables de manière à fournir la meilleure réponse possible. En réalité, cette fonction est en fait la combinaison de milliers de variables reliées entre elles comme un réseau de neurones biologiques. L'apprentissage renforcé, qui est une spécialité de DeepMind, consiste à faire jouer l’algorithme contre lui-même pour améliorer le réseau neuronal.

L’équivalent pour le go de la rencontre mythique qui a opposé l'ordinateur d'IBM Deep Blue au meilleur joueur d'échecs du monde en 1997, le Russe Garry Kasparov, est annoncé par Google DeepMind le 9 mars prochain à Séoul où il affrontera le meilleur joueur du monde actuel : le Sud-Coréen, Lee Sedol, 9e dan.

« J’aurai le privilège d’affronter pour la première fois un ordinateur. J’ai entendu dire qu’AlphaGo est étonnamment fort et s’améliorera encore, mais je suis confiant que je pourrai gagner, au moins cette fois-ci », a déclaré Lee Sedol par l’entremise de la revue Nature.

Si la victoire contre Fan Hui est impressionnante, ce joueur est classé 633^e meilleur joueur au monde, bien loin donc du meilleur niveau mondial.

Source : Nature (maîtriser le jeu de Go avec les réseaux neuronaux profonds et l'exploration des arbres), le jeu de go et la révolution de Monte-Carlo

Et vous ?

Quels sont vos pronostics ? Pour quelles raisons ?

Voir aussi :

forum Intelligence Artificielle