Un ordinateur médaille Fields ?

Le 8 août 2009  - Ecrit par  Stéphane Lamy Voir les commentaires (7)

Il y a quelques mois, un programme de go nommé MoGo [1] a battu un joueur professionnel coréen, à neuf pierres de handicap.

Je ne vais pas expliquer ici les règles du jeu de go [2], 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 [3] 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é ! [4]). 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 [5]. 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 [6].

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 » [7], 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...

Notes

[1Mogo est développé par des chercheurs français ! voir ici pour cette nouvelle et pour le site du projet MoGo (INRIA-CNRS-Paris 11).

[2Voir ce site porté par la fédération française de go.

[3Je suis plus ou moins 2ième kyu.

[4En mathématiques, le caractère « trivial » s’entend au sens d’ « évident ».

[5En 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...

[6Et 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).

[7Si vous voulez tenter votre chance.

Partager cet article

Pour citer cet article :

Stéphane Lamy — «Un ordinateur médaille Fields ?» — Images des Mathématiques, CNRS, 2009

Commentaire sur l'article

  • Un ordinateur médaille Fields ?

    le 10 mars 2009 à 13:11, par Vincent Beffara

    Super billet !

    Mais je ne suis pas du tout d’accord avec ta remarque finale que ce genre de perspective fait bien sûr sourire tous les mathématiciens professionnels ! Enfin, la perspective me fait en effet sourire, mais plus par anticipation que par sentiment qu’il s’agit d’une idée ridicule ...

    Et la perspective qu’un ordinateur puisse prouver un théorème dont on lui donne l’énoncé (s’il est vrai, et si il en existe disons une preuve de moins de 50 pages en passant — ou pas — par une liste finie de lemmes intermédiaires qu’on lui fournirait), d’une part me semble tout à fait réaliste avant la fin de ma carrière, d’autant plus si des méthodes du genre Monte-Carlo s’appliquent ; mais de plus n’enlève rien à l’intérêt du métier de mathématicien : faut-il encore trouver l’énoncé en question, et qu’il soit intéressant. Et c’est ça le vrai métier du mathématicien.

    Comme disait Picasso (il me semble), les ordinateurs n’ont pas d’intérêt pratique, ils ne savent que donner des réponses ...

    PS : un test un peu plus réaliste que de prouver l’hypothèse de Riemann, quand un ordinateur pourra-t-il être admissible à l’agrégation ?

    Répondre à ce message
    • Un ordinateur médaille Fields ?

      le 10 mars 2009 à 22:37, par François Sauvageot

      L’agrégation ? Encore faut-il que les questions ne soient pas ouvertes. Car si on en vient à se munir de tels ordinateurs pour l’agrégation, les questions s’adapteront. L’homme aussi a quelques possibilités d’évolution ! ;-)

      Enfin ... est-ce la bonne question ?

      Pourquoi faire des mathématiques ?

      Répondre à ce message
    • Un ordinateur médaille Fields ?

      le 13 mars 2009 à 23:41, par Sébastien Martineau

      Je suis tout à fait d’accord sur la nature du métier de mathématicien : il doit se poser les bonnes questions, introduire les bonnes notions mais aussi (trouver et) comprendre les preuves (où comprendre n’est pas à prendre comme « vérifier la validité de » !). Et c’est ça qui pourrait être difficile : créer un programme qui prouve de manière jugée moralement satisfaisante (je ne dis pas que c’est impossible, mais je rejoins l’avis de Picasso !).

      Répondre à ce message
  • Darwin

    le 10 mars 2009 à 20:06, par Rémi Peyre

    Bonjour,

    Je ne vois pas trop le lien entre le darwinisme et la méthode utilisée ici. La méthode darwinienne consiste à changer aléatoirement les règles qui définissent la stratégie de l’ordinateur et à sélectionner les meilleures stratégies en fonction des résultats obtenus (généralement dans une confrontation contre d’autres ordinateurs, car sinon cela prendrait trop de temps). Rien de tel ici : l’idée de base est plutôt que si vous jouez contre un grand maître, le meilleur coup possible est le même que si après avoir joué ce coup vous et votre adversaire quittez la table pour laisser vos petits neveux de quatre ans finir la partie. L’idée d’une comparaison avec le darwinisme (par ailleurs utilisée dans d’autres branches de l’intelligence artificielle) était séduisante, mais, si je ne m’abuse, elle n’est pas pertinente ici.

    Répondre à ce message
  • Un ordinateur médaille Fields ?

    le 18 mars 2009 à 23:06, par Arnaud Lionnet

    Je ne saurais me prononcer sur la validité de la comparaison évolutionniste (il est un peu tard que je m’y risque). Par contre après avoir lu les réponses aux 2 billets suivants, je me demande : serait-ce ce billet qui nous a attiré un troll sur Images des Mathématiques ? (Et sachant que répondre à un troll c’est perdre (même pour dire « c’est un troll »), ai-je perdu ?)

    A part ça, super billet oui. Je comprend comment marche le programme, et le probabiliste que je suis n’est pas mécontent d’apprendre qu’on peut gagner au go simplement en tirant (plein de fois) à pile ou face.
    Question : il y a d’autres jeu du même type (dames, échecs) où l’on a des programmes de jeu qui utilisent des probas ? D’ailleurs si quelqu’un est à jour, n’y en a t’il pas qui sont résolus (au sens : on a montré qu’il y avait une stratégie gagnante, qu’on a explicité) ?

    Répondre à ce message
    • Un ordinateur médaille Fields ?

      le 30 mars 2009 à 23:25, par Pierre Colmez

      J’ai cru comprendre que les checkers (dames anglaises sur 8x8)
      ont été résolues. La méthode de Monte-Carlo ne semble pas très performante pour les échecs (peu de bon coups au milieu d’une masse de coups plus ou moins catastrophiques), et les progrès des programmes de go ne sont pas uniquement dus à cette méthode, mais reposent aussi sur de la théorie sous la forme de reconnaissance de formes à partir de parties de forts joueurs amateurs (l’honneur de l’esprit humain est donc encore sauf...). Au cours des deux ou trois dernières années l’ordinateur a progressé presque aussi vite qu’un être humain, ce qui est assez impressionnant quand on compare à la situation d’il y a 5 ans, mais son niveau actuel est atteint par un humain doué en à peu près un an ; on est loin d’un niveau professionel (sur 19x19 tout au moins ; sur 9x9 les progrès sont assez incroyables). Le point le plus faible du programme semble être sa piètre gestion des combats (la phase du jeu se rapprochant le plus des échecs : une petite imprécision peut coûter très cher...).

      Répondre à ce message
      • Un ordinateur médaille Fields ?

        le 8 avril 2009 à 13:25, par Adrien Sicart

        En revanche, les programmes d’échecs sont eux très satisfaisants depuis bien plus de 5 ans, non ? Il me semble que depuis 10 ans les matchs « champion du monde d’échecs VS ordinateur » se terminent généralement par des matchs nuls, ce qui paraît être un bon test pour les juger efficaces. Et on ne peut pas dire que n’importe quel humain doué arriverait à ce niveau même en 10 ans...

        Il doit donc y avoir une différence fondamentale de conception et d’efficacité des algorithmes, puisque la puissance des supercalculateurs d’il y a 10 ans était vraiment inférieure, et pourtant aux échecs l’ordinateur était déjà excellent.

        Enfin un dernier mot, si un ordinateur devait démontrer un théorème à 1M$, ou encore gagner la médaille Fields, je serai pour en attribuer tout le mérite à son/ses programmeurs.
        En effet, en l’absence de réelle « intelligence artificielle » capable de se programmer elle-même, les ordinateurs ne restent que des grosses calculatrices qui appliquent un algorithme créé, lui, par un/des humains.

        Le véritable « fossé » entre la grosse calculatrice dont tout le mérite revient au programmeur et la véritable intelligence artificielle, je crains de ne pas le voir arriver de mon vivant.

        Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM