Quand l’intelligence artificielle s’attaque au jeu de Go

Ces derniers temps, Facebook semble se diversifier au-delà du simple réseau social. On a beaucoup commenté son rachat du système Oculus dédié à la réalité virtuelle, et une récente annonce du groupe affirme pouvoir utiliser cette technologie pour permettre la « téléportation » d’ici 2025 (le terme est mal choisi, il s’agit en fait de « téléprésence » : la capacité d’interagir en un lieu distant à l’aide des systèmes d’immersion propres à la réalité virtuelle). Mais nous apprenons aussi par Wired que Facebook s’attaque aujourd’hui à un domaine réputé difficile de l’intelligence artificielle (IA) : la capacité pour un programme de jouer correctement au Go, ce jeu chinois millénaire qui, contrairement aux échecs, a jusqu’ici résisté à toutes les recherches en IA.

Naturellement, en réalité, Facebook n’oublie pas son coeur de métier. Que ce soit réalité virtuelle ou intelligence artificielle, son but avoué reste de réintégrer ces technologies dans son système de réseau social.

Étrange de penser que ce jeu aux origines millénaires (le premier damier a été trouvé dans une tombe datant de 146 avant JC) résiste encore aux assauts du numérique ! Une bonne leçon pour ceux qui pensent trop naïvement que l’homme moderne possède plus de capacités cognitives que nos ancêtres éloignés. Le Go semble être la démonstration du contraire : plus c’est ancien, plus c’est abstrait, complexe, intellectuel.

Le jeu se joue sur un damier, le Goban, composé de 19×19 intersections (mais les débutants ou les gens pressés peuvent utiliser un damier de 9×9 ou 13×13). Chaque joueur dispose de pions blancs ou noirs (des « pierres ») et chacun dépose, tour à tour, un pion sur une intersection. Ceux-ci ne bougent pas tout au long de la partie. Lorsqu’un pion ou un groupe de pions peut accéder à ces intersections vides, il est en sécurité. Mais si un pion ou un groupe se retrouve intégralement entouré par les pièces de l’adversaire, il est capturé. Le but n’est pas de ramasser le plus grand nombre de pièces ennemies, mais d’accumuler la plus importante quantité possible de territoire : des espaces « sanctuarisés » entourés par les pièces du joueur où l’adversaire n’a aucune chance de pénétrer sans y perdre la vie. Il y a quelque chose de profondément taoïste dans le Go. Ce qui compte, c’est le vide. Le vainqueur est celui qui possède le plus d’espaces vides.

Des obstacles mathématiques et cognitifs

2014.03.25_TokyoNewcomerComme on le voit, les règles sont très simples, bien plus que les échecs. Qu’est-ce qui empêche donc les intelligences artificielles de rivaliser les grands maîtres ? Il existe deux raisons à cela : mathématiques et cognitives.

L’explosion combinatoire est énorme dans le Go. Imaginez simplement le premier coup d’une partie. Vous avez 20 possibilités aux échecs, pas une de plus : les 8 pions qui peuvent avancer d’une ou deux cases, ce qui fait 16, et les quatre mouvements possibles des cavaliers. En Go il y en a 361.

Comme le rappelle Peter Shotwell dans son excellent ouvrage Go : bien plus qu’un jeu : « Le nombre de positions possible par rapport aux échecs est supérieur au rapport entre la taille du noyau d’un atome et celle de l’univers« . Voilà qui complique singulièrement les choses !

Il est tout simplement impossible de gagner un match de Go par la force brute du calcul. D’où la nécessité de s’intéresser au cerveau humain et à sa manière d’attaquer le problème.

Mais si les recherches sur les sciences cognitives des échecs se sont poursuivies et ont porté leurs fruits ces dernières années, notre réflexion sur le Go patine. Au centre de notre compréhension sur le jeu d’échecs se trouve la chunk theory. C’est cette même théorie qui se trouve d’ailleurs être un des fondements de la méthode de Barbara Oakley sur les techniques de l’apprentissage. Elle se base en gros sur la découverte que les grands joueurs d’échecs ne raisonnent pas sur les pions individuels, mais sur des configurations, des groupes. On a en effet demandé à ceux-ci de se rappeler les positions d’une partie d’échecs. Il leur arrivait de faire des erreurs, comme les débutants, mais lorsqu’il se trompaient, c’est tout un groupe de pièces qui se trouvait mal placé, et surtout, le résultat donnait la même évaluation stratégique que la partie originelle. De plus, les grands joueurs éprouvaient autant de difficultés que les débutants à se rappeler les positions des pièces lorsqu’elles avaient été placées aléatoirement sur l’échiquier. De cela on pouvait déduire que les champions ne raisonnaient pas sur les pièces matérielles, qu’on pourrait comparer à des « mots », mais sur des phrases entières dotées de signification. S’ils se trompaient, c’était qu’ils utilisaient une phrase possédant la même signification. En revanche, dans le cas d’un échiquier peuplé aléatoirement, il s’agissait plus de se souvenir d’une liste de mots sans liens entre eux, ce qui devenait un pur exercice de mémoire.

Malheureusement, les choses ne sont pas si simples avec le jeu de Go. Des recherches effectuées avec la collaboration du champion de Go James Kerwin auraient montré qu’en réalité, s’il existe des « chunks » en Go, ceux-ci sont enchevêtrés : au lieu d’être des configurations de positions bien précises, une même « pierre » peut se trouver membre de plus d’un « chunk » : au final, cela forme des structures hiérarchiques bien plus complexes à analyser.

Les « chunks » ne sont pas utilisés par les programmes d’échecs modernes qui préfèrent de toutes façon recourir à la « force brute ». Mais des progrès ont quand même été obtenus. Au cours de la dernière décennie, divers programmes ont pu se hisser à un haut niveau sur le damier 9×9 en utilisant une technique dite « méthode de Monte-Carlo« . Comme son nom peut le laisser supposer, ce système repose largement sur le hasard si important dans les jeux de casino. Appliquée au Go, la méthode consiste à sélectionner un coup au hasard, puis à simuler des centaines de parties se continuant après ce coup. Est sélectionné le coup qui semble avoir le plus de conséquences positives après avoir été joué. Une technique qui demande des ordinateurs très puissants, multi-coeurs, pour faciliter la parallélisation, et qui reste quand même limitée. Sur un damier 19×19, l’humain reste le maître à bord. Toutefois, des recherches perfectionnent constamment la méthode, en permettant par exemple d’éliminer la simulation de branches de l’arbre des possibles qui ne présentent guère d’intérêt possible pour la victoire.

Les promesses du Deep Learning

513HooylclLLes ingénieurs de Facebook, eux, comptent sur une autre technique : le Deep Learning, cette forme de réseau neuronal qui a actuellement le vent en poupe. (et dont vous trouverez une présentation dans cet article).

La théorie derrière la méthode de Facebook serait que la perception visuelle jouerait un bien plus grand rôle dans le Go que dans les échecs. D’où la nécessité, affirment-ils de recourir aux capacités de reconnaissance des formes que permet le Deep Learning. Selon Wired :

« Nous sommes assez sûrs que les meilleurs joueurs humains recherchent des motifs visuels, et que regarder le damier les aide à comprendre de manière intuitive quelles sont les bonnes et mauvaises configurations », a déclaré le CTO de Facebook, « Schrep » Schroepfer (…). « Donc, nous avons pris certaines des bases d’un système de jeu d’IA et y avons associé un système visuel, de sorte que nous utilisons les patterns sur le damier – un système de reconnaissance visuelle – pour sélectionner les mouvements possibles du programme. » Bien que cette technique ne soit pas âgée de plus de trois mois (…), elle peut déjà battre des systèmes construits uniquement avec des techniques plus traditionnelles d’IA. »

Cette théorie est elle juste ? Il est probable que la perception visuelle joue un plus grand rôle dans le Go que dans les échecs, mais la situation est elle aussi claire et simple que cela ? En fait, peut être pas, si l’on en croit encore Peter Shotwell.

Dans un article publié sur le web (mais apparemment disponible uniquement via Archive.org), Shotwell cite ainsi une recherche particulièrement intéressante sur l’étude IRM comparée de joueurs d’échecs(.pdf) et de Go(.pdf), effectuée par des chercheurs Chinois :

« Pour résumer brièvement les résultats, à une exception près, ni les joueurs de Go ni ceux d’échecs n’ont montré de latéralisation dans leur pensée, ce qui peut démentir les idées selon lesquelles le Go est plus « spatial » et « visuel » et serait donc une activité plus « cerveau droit ». Toutefois, l’unique différence serait que les zones de la parole situées dans l’hémisphère droit seraient plus actives chez les joueurs de Go. Les chercheurs
ont suggéré que c’est peut-être parce que les joueurs vont nommer le plus souvent leurs concepts stratégiques. (…) L’équipe chinoise a également ajouté que les programmes informatiques de Go ne tiennent pas compte des fonctions exercées par cette région du cortex pariétal droit. »

Dans un autre article, Shotwell nous éclaire sur cet aspect verbal typique du go. « … avant même de considérer les mouvements qui mettent en jeu les facteurs fondamentaux de la vie, de la mort [des pions] et de leur connectivité – ce qui impliquerait plus directement la reconnaissance des formes – [le joueur] envisage les possibilités offertes par des concepts de méta-niveau. Ceux-ci comprennent l' »influence » et le « territoire » ou Frukiwari (dans ce cas, la présente bataille sera abandonnée), Meai (l’échange de coups), et surtout, Atsumi, « épaisseur », pour lesquels il n’existe pas de patterns bien définies. »

Suffira-t-il donc d’associer un système de reconnaissance visuelle à une IA plus classique pour enfin créer un programme champion de Go ? Ou au contraire, le Go met-il en jeu toute une variété de fonctions mentales que les ordinateurs ont, pour l’instant, bien de la peine à émuler ?

Rémi Sussan

À lire aussi sur internetactu.net

1 commentaire

  1. Monte-carlo, c’est intéressant il me semble pour les jeux où une partie de l’information est cachée, notamment les jeux de cartes.
    Au bridge, par exemple, en fonction des enchères on a des informations sur les mains cachées, on tire au sort 100 distributions qui correspondent, le programme résout ces 100 situations « à cartes ouvertes » (ce qui est rapide), et en déduit l’enchère finale, ou le jeu à la carte. Le programme wbridge 5 utilise cela notamment.
    http://www.wbridge5.com/

    Au jeu de go, ce que vous décrivez (Appliquée au Go, la méthode consiste à sélectionner un coup au hasard, puis à simuler des centaines de parties se continuant après ce coup) ressemble à de la force brute. Mais j’u du mal comprendre.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *