Regard sur le match AlphaGo – Fan Hui [3/5] : Alphago et le computer-go

Dans le précédent billet, nous avons regardé pourquoi le jeu de go constituait un problème intéressant pour l’intelligence artificielle … en plus d’être un jeu passionnant.

Pour ce troisième billet de regard sur le match AlphaGo – Fan Hui, nous allons nous intéresser aux principales avancées qui ont eu lieu dans le domaines de l’informatique du jeu de go (computer-go) pour aboutir à AlphaGo.

Il complète la « petite histoire de l’informagologie » parue dans la RFG 138.

 

 

Les pionniers

 

Le 28 mai 1936, Alan Turing publie un article parlant d’une machine qui (en résumant l’Histoire) donnera naissance à ce que l’on nomme aujourd’hui ordinateur. Outre le fait d’inventer une science (l’informatique) dont la plus haute distinction porte aujourd’hui son nom (prix Turing), il en sera l’un des principaux architectes en mettant au point la bombe électromécanique qui déchiffrera Enigma (contribuant fortement à l’issue de la seconde guerre mondiale).

L’un de ses collaborateurs à Betchley Park sera le mathématicien Irving John Good (« Jack »). De son vrai nom Isidore Jacob Gudak, il posera en 1965 la problématique de l’informatique du jeu de go :

Le jeu de go sur ordinateur ? – en plus de programmer un ordinateur pour jouer une partie raisonnable, et pas seulement une partie légale – il est nécessaire de formaliser les principes d’une bonne stratégie, ou de concevoir un programme apprenant. Les principes sont plus qualitatifs et mystérieux qu’aux échecs et dépendent plus du jugement. Je pense qu’il sera beaucoup plus difficile de programmer un ordinateur pour jouer une partie raisonnable au Go qu’aux échecs.

Lorsque l’on sait que l’une des choses surprenantes avec AlphaGo est que « L’ordinateur joue comme un humain » on peut dire que « Jack » avait vu juste. Il sera également l’un des conseillers de 2001 : l’Odyssée de l’espace dont HAL 9000 est l’un des premiers ordinateurs médiatisés. Quand on sait que ce dernier pourrait signifier « ce qui vient après IBM » (chaque lettre de « HAL » venant après celles d’IBM), on pourrait presque croire qu’Arthur C. Clarke et Stanley Kubrick avaient annoncé AlphaGo ! Malheureusement, tout ceci pourrait n’être que coïncidence …

Ce qui semble en revanche établi est que le premier programme jouant au go est celui de D.Lefkovitz en 1960 et le premier article scientifique celui d’Horst Remus, en 1962 : Simulations of a Learning Machine for playing Go.

 

Le computer-go

 

Dans leur article de 1964 (A partial Analysis of Go) Edward Thorp et William Walden inventent le computer go ! Ou plus exactement, ils introduisent le terme pour définir des règles rigoureuses … donc différentes des règles japonaise 🙂

Cependant, l’article le plus emblématique est celui écrit en 1969 par Albert Zobrist dans le cadre de sa thèse : A model of visual organization in the game of Go. La seconde thèse du domaine sera celle de Ryder en 1971 et l’un des premiers (vrai) logiciel Interim.2 (1974). Il y a aura également des travaux en psychologie cognitive (1976) et le go inspirera John Conway pour inventer les nombres surréels. Pour creuser la question nous vous invitons à lire l’Etat actuel de la programmation du jeu de go de Bruno Bouzy (représentant français au championnat du monde 1993 et l’un des premiers thésards français).

Cependant, s »il faut associer une date au terme « computer go » ce serait plutôt 1986-1987 : c’est le moment où la revue Computer go (1986-1991) verra le jour. En France, la FFG organise à l’ENS un séminaire « go et informatique » pour faire le point sur les avancées du domaine.

 

Bernd Brugmann, l’alea et Monte-Carlo

 

En 1993, les logiciels de go ont un niveau comparable à celui de l’auteur de ce billet (10±5kyu), ce qui est bien mais pas top. C’est Bernd Brugmann, un physicien, qui va permettre aux logiciels de faire des progrès … en jouant au hasard ! Son programme, Gobble, va immédiatement faire sensation : bien que plus simple, il va battre tous ses concurrents !

Gobble est en effet programmé avec une idée géniale : le Monte Carlo Go. Comme on ne dispose pas de fonction d’évaluation (cf. billet précédent), que la stratégie est difficile à formaliser mais que la fin de partie est « simple » à déterminer … l’idée est de faire jouer un nombre de parties aléatoires à l’ordinateur et de regarder le coup qui fonctionne le mieux.

C’est notamment ce type de méthode qui a permis au logiciel MoGo de l’INRIA d’être le meilleur pendant longtemps. Un point intéressant dans ces recherches est que les développements réalisés sur ces logiciels de go ont trouvé des applications dans d’autres domaines.

 

AlphaGo et les réseaux de neurone

 

Le truc en plus d’AlphaGo est d’associer à ces techniques un réseau de neuronne. Voici quelques vidéos de vulgarisation sur le sujet :

passescience

Passe science #14 + Bonus

scienceetonnante deeplearning

Science étonnante #27

Et pour ceux qui voudraient aller plus loin, nous ne pouvons que vous recommander le cours de Yann Lecun au Collège de France L’apprentissage profond : une révolution en intelligence artificielle.

Une autre manière de creuser la question est de s’intéresser aux conséquences de ces avancées. Dans la vidéo du premier billet, Fan Hui aborde les conséquences sur le jeu de go. Mais les conséquences sont également sociétales et éthiques (ces algorithmes pouvant servir à bien d’autres choses). Pour aborder ces questions, nous vous proposons les vidéos suivantes :

science4all alphago
science4all | Actu 1

 

bibliotheque medicis
Bibliothèque Médicis du 04/03/16