| Jeu de go
Un programme d' ordinateur construit des programmes qui jouent au go.
La victoire de l'ordinateur Deeper Blue sur le champion d'échecs Gary Kasparov inciterait à croire que les ordinateurs surpassent désormais les humains dans les jeux de l'esprit. Il n'en est rien: le jeu de go résiste encore à l'intelligence artificielle. La construction de programmes qui élaborent eux-mêmes des programmes de jeu de go est une voie prometteuse.
Depuis plus de dix ans, chercheurs et programmeurs améliorent des programmes de go sans dépasser le niveau d'un amateur moyen. Ce n'est pas faute de
motivation : un riche Taiwanais, M. Ing, a offert un prix de huit millions de francs au premier programme de go qui battrait le professionnel de son choix.
Le jeu de go paraît plus simple que les échecs: le damier est un quadrillage de 18 cases de côté, et les joueurs posent alternativement une pierre (blanche pour un joueur, noire pour l'autre) sur une intersection vide du quadrillage. Au début d'une partie entre joueurs de forces égales, le damier est vide, et c'est Noir qui a le trait. Un joueur capture une chaîne de pierres adverses s'il les entoure complètement de ses propres pierres. Le but du jeu est d'entourer le plus de territoire possible sans se faire entourer. À la fin de la partie, chaque intersection vide entourée compte pour un point, ainsi que chaque pierre capturée; le joueur qui a le plus de points a gagné.
Aux échecs, un joueur a le choix, en moyenne, entre 35 coups possibles. Les meilleurs programmes, tel
Deeper Blue, essaient ces coups, envisagent les réactions possibles de l'adversaire, puis les réactions aux réactions, et ainsi de suite. Le nombre de positions à évaluer croît exponentiellement avec la profondeur d'analyse, mesurée en nombre de coups. Les programmes d'échecs les plus rapides examinent jusqu'à 14 coups à l'avance, soit environ 80 milliards de positions.
Au go, le problème est pire, car, en moyenne, chaque joueur a le choix entre 250 coups possibles. Si l'on utilisait la puissance de
Deeper Blue pour exécuter un programme de go, celui-ci ne pourrait envisager que cinq coups à l'avance. De surcroît, au contraire des échecs, un programme de go ne peut recourir à des fonctions d'évaluation simples permettant de mesurer l'intérêt d'une position.
Aussi l'approche par la force brute est inadaptée au go : l'ordinateur doit reconnaître des formes complexes de territoires, faire de longs raisonnements, et utiliser parfois des connaissances floues et difficilement formalisables.
|
Les meilleurs programmes de go actuels sont le fruit de sept à vingt ans de travail. Chen
Zhixing, professeur de chimie chinois à la retraite et excellent joueur de go, s'est fait aider d'une
joueuse professionnelle pour réaliser le meilleur, nommé Handtalk, et tenter de maîtriser ce qu'il considère comme «un des plus grands des jeux de l'esprit" .Pour ce spécialiste lyrique, «La pensée est séduite par la beauté des formes qui se développent sur le damier, et les séquences
de coups sont comparables à des morceaux de musique. La difficulté vient de faire comprendre et de faire composer à un ordinateur cette musique visuelle» .
Plus prosaïquement, les bons joueurs de go évaluent une position en fonction de la forme et des positions respectives des groupes de pierres, et leurs raisonnements sont souvent plus intuitifs que rationalisés. Comment programmer ces capacités intellectuelles ? Les meilleurs programmes de go actuels exécutent des milliers de règles identifiées empiriquement par des experts du jeu, mais les joueurs ne savent pas décrire comment ils évaluent les positions et choisissent leur coup. D'où la difficulté de programmation.
Au Laboratoire d'informatique de Paris VI, l'équipe Métaconnaissance de Jacques Pitrat étudie des méthodes
générales pour faire découvrir par l'ordinateur lui-même des connaissances d'experts. J'ai appliqué ces méthodes au jeu de go : le programme nommé
Introspect s'améliore par observation et analyse de son propre fonctionnement, puis il donne ses connaissances au programme qui joue véritablement, le programme Gogol. Fondé sur l'autoobservation, l'apprentissage d'
Introspect s'effectue de la façon suivante: ayant en mémoire la configuration du damier, il cherche les conséquences de chaque coup joué et analyse les raisons tactiques de ce coup. Quand il trouve des idées tactiques qu'il n'aurait pas su mettre en oeuvre, il s'enrichit d'une connaissance nouvelle.
Une fois apprises et traduites en langage d'exécution rapide, les règles sont données au programme Gogol.
Celui-ci n'envisage que quelques coups parmi les quelque 250 coups envisageables à chaque branche de l'arbre de recherche; exécuté par un microprocesseur Pentium 133, il joue un coup en dix secondes sur un damier 19 x 19. Il envisage à chaque coup des centaines d'arbres de recherche qui comprennent chacun entre 2 et 500
nœuds, et il prévoit des séquences jusqu'à 60 coups à l'avance. À chaque
nœud de chaque arbre, le programme applique les règles qu'il a apprises et qui conseillent les coups à utiliser. Ces règles, écrites par le programme, sont au nombre de 10 000.
Ainsi mon «métaprogramme» bat la plupart des autres programmes de go qui ont été écrits par des humains (il s'est classé sixième sur 40, lors de la dernière coupe Fost, qui a eu lieu en août 1997) et son potentiel de progression est supérieur à celui des autres programmes: une petite amélioration du métaprogramme peut conduire à de grandes améliorations des programmes finaux.
|
