Nouvel Obs – Blog Rue89

Un pro du go battu par un algorithme : pourquoi ça change tout

Par Oscar Barda Game designer. Publié initialement le 28/01/2016

Les faits : DeepMind est un petit labo anglais d’intelligence artificielle fondé en 2011, racheté par Google en 2014, qui l’arrose depuis de moyens impressionnants pour faire avancer ce champ de recherche.

Premier coup d’éclat de DeepMind : une intelligence artificielle capable de gagner à tous les jeux de la vieille console Atari un à un.

Cette fois, DeepMind vient de battre Fan Hui, le champion d’Europe de jeu de go, à l’aide de son programme AlphaGo – en octobre, ce que vient seulement de révéler la revue Nature.

Jeu de go

Une partie de go sur son plateau, le goban - Xchen27/Wikimedia Commons/CC

Un peu vieux jeu mais toutes ses dents

Le jeu de go est l’un des plus anciens jeux de plateau stratégiques du monde dont nous connaissons encore les règles. Joué en Chine depuis 2 500 ans au moins, il est doté de règles simples dont émerge une très grande complexité.

Comme d’autres jeux célèbres, il répond à l’adage (sinon le Graal) des faiseurs de jeu : « Un instant pour l’apprendre, une vie pour le maîtriser. » La partie se déroule sur le goban (le plateau de jeu quadrillé de 19x19 lignes) où les joueurs placent à tour de rôle des pierres blanches et noires pour capturer des territoires, s’encercler ou se capturer l’un l’autre.

Encore extrêmement populaire en Chine, en Corée et au Japon, le go joua même un rôle déterminant dans l’histoire de ce dernier pays à travers une partie célèbre racontée dans le roman « Le Maître ou le tournoi de go » de Yasunari Kawabata (Nobel de littérature 1968) où Kitani Minoru, jeune supporter de l’ouverture du Japon affronta en 1938 le Meijin (maître de go du Japon) Honinbo Shusai, tenant de la tradition, en une illustration grandiose des tensions politiques d’avant-guerre.

Tournoi de go

La partie de go légendaire du Meijin contre Minoru - Gobooks.info

Ce qu’il faut pour la suite retenir de l’essence de ce jeu c’est que s’il possède une composante stratégique analytique comme les échecs, le déroulé d’une partie de go est beaucoup plus fluide, habile et agile que les froids calculs.

Au go, il y a rarement une seule bonne réponse et les joueurs expriment ainsi fortement leurs caractère en jouant. Il y a quelque chose d’étrangement humain dans cet enchaînement de pierres noires et blanches ; il faut réagir aux émotions, aux envies de l’adversaire, le faire tomber dans des pièges non pas parce qu’il ne les a pas vu venir, mais parce que vous jouez sur une faille de son comportement, de sa personnalité plutôt que de son raisonnement. 

Pour résumer, le go permet aux joueurs une grande créativité et les erreurs et caractères des joueurs sont souvent des facteurs bien plus déterminants qu’aux échecs (il va de soi qu’aucun des deux jeux n’est meilleur que l’autre, ils sont juste différents mais nous y reviendrons !).

Voici donc un premier point à comprendre sur le go : c’est un jeu très humain.

10 puissance 170

Le nombre de coups légitimes sur un plateau de go est de 10 puissance 170 c’est à dire 1 avec 170 zéros derrière.

Impossible à se représenter ? On peut calculer par approximation combien il y a d’atomes dans nos corps (environ 7x10 puissance 27). Puis combien d’atomes composent la terre en fonction de sa masse complète, puis faire de même pour les planètes avoisinantes puis inclure le soleil, puis les étoiles et les galaxies qui nous entourent dans le vide puis enfin faire une estimation du nombre d’atomes dans l’univers… Au total il y en aurait entre 10 puissance 78 et 10 puissance 82 dans l’univers visible.

Il y a donc plus de possibilités de parties de go que d’atomes dans tout l’univers. Combien de fois plus ? Un milliard de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de fois plus.

Ça fait beaucoup de parties de go possible (même si nos cerveaux sont peu équipés pour comprendre l’ampleur de ces ordres de grandeur). A titre de comparaison, il y a aux échecs moins de 10 puissance 50 positions légitimes possibles.

Kasparov

Kasparov contre le programme X3D Fritz en 2003 - SMSI/Wikimedia Commons/CC

Par ailleurs alors qu’aux échecs il y a en moyenne environ 20 coups possibles à chaque tour, au go il y environ 200. Au tour suivant ? Encore 200. Et au tour d’après 200 et autant au tour d’après, etc.

Ce que cela veut dire c’est que pour calculer tous les coups possibles à partir d’une position, si aux échecs un ordinateur peut facilement voir 4 ou 5 coups en avance (20 x 20 x 20 x 20…), au go cela devient très vite impossible.

Si je vous donne des nombres un peu abstraits et très grands c’est pour vous expliquer un deuxième concept : le go est quasi incommensurable.

Mais quelle différence avec Deep Blue contre Kasparov ?

En 1996, l’ordinateur Deep Blue affronte aux échecs le champion du monde Garry Kasparov en deux parties, une gagnée par la machine et une par l’humain. Puis en 1997 l’ordinateur Deeper Blue amélioré revient et gagne cette fois-ci 3 parties sur 5 (les deux parties restantes étant deux matchs nuls). Mais quelle différence avec le jeu de go finalement ? C’est la même chose non ? Un ordinateur qui bat un humain à un jeu de stratégie…

Connaissez-vous le morpion ou tic-tac-toe ? Mais si, la grille de 3 x 3 cases dans laquelle un joueur joue les croix et l’autre les cercles ! Eh bien on peut à peu près tous, avec un peu d’entraînement, résoudre le morpion.

Résoudre un jeu c’est être au courant de toutes ses possibilités et pouvoir à chaque instant choisir la meilleure chose à faire mathématiquement pour finir gagnant à tous les coups. Car si le morpion a quelque chose comme 20 000 parties possibles, elles se ressemblent toutes : la partie se finit toujours en 9 coups et après le premier il n’y a plus que 8 possibilités, puis 7, et l’on voit bien vite où l’adversaire veut en venir, permettant de prédire très facilement les coups à chaque instant et de l’empêcher d’aligner les trois symboles qui donnent la victoire.

TicTacToe

Exemple de grille de morpion - Symode09/Wikimedia Commons/domaine public

Dans les années 70, le morpion est bien vite résolu par les ordinateurs, c’est à dire qu’un ordinateur fera toujours victoire ou match nul contre vous. Comment ? Par une méthode qu’on appelle le bruteforcing (la force brute), c’est-à-dire en prévoyant tous les coups possibles à tous les instants et tous les coups possibles après ceux-là et en choisissant parmi eux la meilleur option pour aller vers la victoire.

A mesure que la capacité de calcul des ordinateur augmentait, peu à peu les jeux sont tombés sous les coups toujours plus rapides et puissants de l’informatique ces 30 dernières années (le Puissance 4, Nim, Quarto, l’awalé) jusqu’à ce qu’on arrive justement à Deep Blue en 1996 qui tente de montrer que l’informatique peut battre un joueur d’échecs…

Alors comment est-ce que Deep Blue gagne un match contre Kasparov ? Bon, c’est un peu plus compliqué que ce que je vais dire là, mais pour simplifier : Deep Blue apprend par cœur les parties que Kasparov a perdues et à chaque fois que Kasparov joue, Deep Blue essaie de jouer au plus près comme les joueurs humains qui ont battu Kasparov. Lorsque les pièces commencent à mourir, le nombre de possibilités diminue et au bout d’un moment, il devient plus facile à Deep Blue de faire du bruteforcing : calculer toutes les possibilités et gagner à partir de ça.

Et donc AlphaGo il fait quoi ?

AlphaGo n’a pas appris à battre Fan Hui meilleur joueur de go européen, il a appris à jouer au go mieux que lui. AlphaGo ne bruteforce pas le go, son but n’est pas de résoudre le go mais d’être le meilleur joueur.

AlphaGo, vidéo promotionnelle de DeepMind

La différence n’est peut-être pas évidente de prime abord mais la nature de cette différence écrira l’avenir de l’humanité :

·         dans un cas, l’ordinateur est une calculette idiote mais très puissante qui essaie tous les coups possibles sans distinction,

·         dans l’autre, l’ordinateur s’approche de la façon dont les humains pensent.

Dans le premier cas, celui de Deep Blue, vous mettez un robot dans une pièce avec 10 portes fermées et une ouverte et il s’envoie la tête la première dans toutes les portes jusqu’à trouver celle qui est ouverte. On pourra certes admirer sa persistance, sa puissance et sa résistance supérieures en tous points à celles d’un humain qui lui se serait fait mal, mais un vrai humain aurait juste en 10 secondes passé la porte ouverte plutôt que de se cogner le crâne aux autres.

AlphaGo, pour filer la métaphore, regarde autour de lui, se cogne dans une porte fermée puis décide de passer la porte ouverte.


Exemple de robot « pas fut fut » comme dirait ma grand-mère

Eh bien AlphaGo a passé la porte : il a défait Fan Hui par 5 à 0. Et pas comme Deep Blue avec des égalités et des bugs… Non, AlphaGo, rencontrant le champion européen pour la première fois, l’a mis à terre et ce sans avoir appris comme l’avait fait Deep Blue à se battre exclusivement contre Fan Hui. Non, il a juste été meilleur au go.

Et ça n’est pas simple comme prouesse d’ingénierie car cela fait maintenant 50 ans que les informaticiens essaient d’abattre les joueurs de go. Mais jusqu’à présent, avec des méthodes classiques de résolution et de force brute, en raison de la complexité du go, les ordinateurs n’avaient jamais réussi à atteindre un niveau professionnel car encore aujourd’hui nous n’avons pas la capacité de calcul nécessaire pour bruteforcer le go.

Au mieux les intelligences artificielles pouvaient-elles parfois prendre une partie ou deux à des bons joueurs dans les années 90, puis en 2013 quelques avancées ont été faites. Mais AlphaGo vient de renverser la table dans la course que se mènent tous les géants du Web à l’intelligence artificielle.

Comment apprendre le go à un ordinateur ?

A la manière du joueur d’échecs de Stefan Zweig, le programme est enfermé dans une geôle de processeurs informatiques formant un réseau de neurones artificiels [PDF] – inspiré de loin de nos structures cérébrales – et a analysé 30 millions de coups d’humains professionnels, essayant de comprendre pour chacun la logique derrière le mouvement et lesquels ont mené à la victoire ou à la défaite. Il essaie ensuite de comprendre comment s’enchaînent ces mouvements entre eux et quels motifs se répètent et à nouveau cherche parmi ceux-là lesquels sont gagnants dans quelles conditions.

Enfin, AlphaGo créé plusieurs versions de lui-même un peu différentes et joue contre lui-même des millions de parties en essayant de respecter un équilibre de tactique (court terme) et de stratégie (long terme).

Puis comme nous l’avons dit, d’autres sociétés, les Facebook, les Apple et compagnie s’essaient au go, on fait des petits tournois amicaux entre intelligences artificielles. AlphaGo en a remporté 499… sur 500.

Le go comme pierre angulaire de la culture

En mars de cette année, AlphaGo va aller en Corée se frotter en 5 matches à Lee Sedol, légende moderne du go, 9e dan (le plus haut rang) considéré comme l’un des meilleurs joueurs au monde.

joueurs du Xe siècle


Des joueurs de go du Xe siècle. Voilà ce qu’AlphaGo essaie de battre - Tableau de Zhou Wenju/Wikimedia Commons

Pourquoi ? Parce quand moi je joue au go, je joue au même jeu que d’autres humains il y a 2 500 ans. Alors qu’il est évident que notre vision de l’art, des tableaux, des sculptures a changé, l’assemblage de sentiments, de hauts, de bas, de victoires fracassantes et de défaites écrasantes qui constituent le go me connectent du bout des doigts à des siècles d’histoire. La façon dont on mange, dont on marche et dont on parle a changé, mais nous jouons encore au go comme il y a 1 000 ans.

D’une certaine façon, le go comme les échecs avant lui représente une victoire de la machine non pas sur l’intelligence, mais sur la culture humaine : les scientifiques commencent à montrer que la machine peut prendre part à nos jeux et à notre Histoire et abattant le go, symbole de raffinement chez la noblesse et l’aristocratie de certaines de nos cultures humaines, pinacle de la subtilité et de l’intelligence tactique, AlphaGo battant Lee Sedol n’est pas du tout une menace pour nous humains mais bien un pied dans la porte dont nous ne nous déferons pas.

Peut-être (sûrement) seront-elles trop vite trop intelligentes pour nous, pas forcément conscientes d’elles-mêmes (pour peu qu’on comprenne un jour ce qu’est la conscience) mais trop forte à tout ce que nous faisons pour que nous les maîtrisions, ces intelligences artificielles…

Mais pourquoi sommes-nous allés sur la lune déjà ? Parce qu’on en était incapable, parce que c’était impossible et que des imbéciles voulaient accomplir l’impossible.

C’est la raison pour laquelle l’IA se frotte au go mais dans quelques années elle écrira des romans, parlera naturellement, comprendra nos lois et sera peut être capable de nous en proposer des meilleures… Parce qu’aujourd’hui c’est impossible et que des gens ont décidé de rêver grand.

Et si au-delà du tour de force culturel, cette première victoire au go est aussi un exercice pratique pour la machine, tentant d’appliquer ses méthodes d’apprentissage à des règles codifiées, d’apprendre notre monde et de faire avancer les méthodes de calcul moderne, il n’en reste pas moins que ça n’est plus juste une grosse calculette qui va plus vite que nous, mais un pas marquant vers le début de la révolution des intelligences artificielles.

 Dernière mise à jour 02/07/2023

    Retour Go