Un ordinateur médaille Fields ?

Il y a quelques mois, un programme de go nommé MoGo ¹Mogo est développé par des chercheurs français ! https://www.espace-sciences.org/rennes/evenements/rennes-capitale-du-jeu-de-go a battu un joueur professionnel coréen, à neuf pierres de handicap.

Je ne vais pas expliquer ici les règles du jeu de go ²Voir ce site porté par la fédération française de go., disons simplement que le principe est que deux joueurs posent alternativement des pions noirs et blancs sur un quadrillage de 19 lignes par 19 colonnes, en s’efforçant de clôturer des espaces d’aires les plus grandes possibles. Entre deux joueurs de forces différentes, il est d’usage de jouer des parties pédagogiques en donnant des coups d’avance (handicap) au joueur le plus faible, qui joue avec les noirs. Donner neuf pierres d’avance est habituellement le handicap maximal accordé. Ceci dit, un honnête joueur de club français tel que moi ³Je suis plus ou moins 2ième kyu. aurait très certainement les plus grandes difficultés à battre un professionnel coréen même avec cet avantage de 9 coups d’avance, ce qui situe le niveau atteint par le programme MoGo.

Le jeu de go est par nature beaucoup plus difficile à programmer que le jeu d’échec (et programmer ce dernier n’est déjà pas une trivialité ! ⁴En mathématiques, le caractère « trivial » s’entend au sens d’ « évident ».Une difficulté est qu’il est très difficile d’évaluer une position, car pour cela il est essentiel de tenir compte du contexte global. Une analogie séduisante est le problème de la traduction automatique d’une langue à l’autre, où la traduction d’un même mot se fera de façon différente en fonction du contexte, notion qu’il est difficile d’implémenter dans un ordinateur. Avec ce parallèle en tête j’avais depuis longtemps l’idée que d’excellents programmes de go devraient voir le jour à peu près au même moment que d’excellents programmes de traduction automatisée.

La réalisation d’un programme informatique peut parfois être l’occasion de mieux comprendre un problème donné. Je suis moi-même depuis quelques semaines plongé dans la conception d’un programme pour réaliser de façon automatisée, et sur un grand nombre d’exemples, un algorithme complexe issu du monde de la géométrie algébrique : peu importe le problème précis, mais en tous cas, le fait de devoir écrire ce programme m’a obligé à réfléchir à comment on menait en pratique les calculs à chaque étape du processus (alors qu’avant comme mathématicien je m’étais plutôt focalisé sur la preuve du fait que l’algorithme aboutit bien toujours à la réponse au problème posé). C’est un peu analogue à l’expérience qu’a éprouvé tout enseignant : on ne comprend vraiment bien un sujet qu’après l’avoir enseigné. Et faire comprendre quelque chose à un ordinateur est plutôt plus difficile à mon avis que de le faire comprendre à des étudiants…

Or, le programme qui a réalisé l’exploit mentionné ci-dessus est basé sur une approche complètement non-intuitive, du moins pour moi, et qui n’a pas dû permettre à ses concepteurs de beaucoup progresser dans leur pratique du go ! L’idée centrale du programme est en gros la suivante ⁵En tous cas, c’est ce que j’en ai compris, j’espère ne pas faire de contre-sens. Si un spécialiste passe par là, ne pas hésiter à rectifier, avec indulgence…. Pour donner une note à un coup dans une situation donnée, le programme joue ce coup puis termine la partie en faisant jouer blanc et noir de façon complètement aléatoire, et note l’écart de points qui en résulte. Le programme répète ceci un grand nombre de fois (disons un million de parties aléatoires avec ce même premier coup), et la note du coup testé sera la moyenne des scores observés. Basiquement le programme joue ensuite le coup qui a obtenu la meilleure note. A première vue il me parait absolument ahurissant qu’un tel algorithme (même amendé à l’aide de quelques règles heuristiques pour présélectionner une liste de coups « plausibles ») puisse être performant. Et pourtant, ça marche !

Dans les articles que j’ai pu parcourir, les spécialistes du sujet appellent la démarche ci-dessus : méthode de Monte Carlo. Il me semble qu’on pourrait la qualifier de méthode Darwiniste, car on y retrouve l’idée de mutations aléatoires et de sélection des meilleures mutations. En effet, si la nature devait jouer au go, elle jouerait des millions de parties (des millions d’individus) où chaque coup serait le fruit du hasard (mutations aléatoires), mais ne survivraient (individus les mieux adaptés) que les parties où ces coups au hasard s’avéreraient être en fait des « bons » coups (mutations entrainant un avantage adaptatif). Je ne sais pas ce que vaut cette analogie, mais au moins elle m’a permis de me réconcilier avec l’idée que cette façon de programmer était peut-être raisonnable ⁶Et puis, c’est le bicentenaire de la naissance de Darwin, qui a produit l’une des théories scientifiques les plus impressionnantes à mes yeux : facile à énoncer, et pleine de pièges retors dès que l’on cherche à l’appliquer à n’importe quel cas particulier (je tire cette opinion de la lecture des merveilleux essais de S. J. Gould)..

En ce début de 21ième siècle, quelles sont les activités humaines qui pourraient se prêter à l’automatisation et où les ordinateurs font encore piètre figure face aux (meilleurs spécialistes) humains ? Aux deux exemples déjà mentionnés dans ce billet, j’en ajoute un troisième, pour obtenir la liste : 1) La pratique du jeu de go, 2) La traduction littéraire, 3) La production de théorèmes mathématiques. Pour chacun de ces exemples, j’ai essayé d’imaginer un test qui certifierait que les programmes ont dépassé les programmeurs. Pour le go, c’est assez facile : « battre un joueur professionnel de top niveau dans les conditions habituelles d’une partie de championnat ». Au vu des progrès récents des programmes, on peut s’attendre à ce que ceci se réalise d’ici une décennie ou deux. Pour la traduction, c’est un peu moins clair. Que pensez vous de « traduire un roman d’une manière qui pourrait convaincre un éditeur de le publier tel quel » ? Je ne sais pas si on peut imaginer un meilleur test, mais en tous cas une telle performance me paraît être du domaine de l’avenir lointain. Il est aussi intéressant de se demander si une approche « Darwiniste » de ce problème pourrait être développée. A première vue, cela ne semble pas le cas, ce qui tendrait à montrer que contrairement à mon idée initiale ces deux problèmes ne sont pas dans le même registre de difficulté. Enfin, les mathématiques ! Là je suis incapable de trouver un test qui me satisfasse ; je m’en tire donc avec une pirouette : « résoudre l’un des problèmes à un million de dollars répertorié par le Clay Mathematics Institute » ⁷Si vous voulez tenter votre chance., et (tant qu’à faire !), se voir attribuer la médaille Fields. Ce genre de perspective fait bien sûr sourire tous les mathématiciens professionnels (dont je suis).

Nous rirons moins si cela se produit au cours de notre carrière…