Chinook : l'IA qui a résolu le jeu de Dames
En 2007, une équipe de l'université d'Alberta, au Canada, a annoncé avoir résolu le jeu de dames anglaises (les checkers, sur damier 8×8) : quand aucun des deux camps ne commet d'erreur, la partie se termine par une nulle. Le programme au cœur de ce travail s'appelle Chinook, et son histoire commence dix-huit ans plus tôt, par une série de matchs contre le meilleur joueur que ce jeu ait connu.
Une précision avant d'aller plus loin : la preuve porte sur les dames anglaises, pas sur les dames internationales jouées en France sur damier 10×10, qui ne sont pas résolues à ce jour. Les deux jeux n'ont pas les mêmes règles, comme le détaille notre comparatif des dames internationales et anglaises. Et elle ne dit rien des Chinese checkers, nos dames chinoises, un jeu de course sans aucune prise qui n'a du jeu de dames que le nom (voir d'où vient cette confusion).
Chinook en bref
- Qui ? Une équipe du département d'informatique de l'université d'Alberta, à Edmonton, dirigée par Jonathan Schaeffer.
- Quel jeu ? Les dames anglaises (checkers) : damier 8×8, 12 pions par camp, environ 5×1020 positions possibles.
- 1989 : début du projet.
- 1992 : défaite à Londres contre Marion Tinsley, 4 victoires à 2 et 33 nulles.
- 1994 : Chinook devient champion du monde homme-machine à Boston, après le retrait de Tinsley, malade.
- 2007 : la preuve est publiée dans la revue Science. Résultat du jeu parfait : la nulle.
Jonathan Schaeffer : l'homme derrière Chinook
Jonathan Schaeffer, professeur d'informatique à l'université d'Alberta, lance le projet Chinook en 1989. L'objectif de départ, tel que l'équipe le formule elle-même, est de construire un programme capable de défier le champion du monde de checkers. L'idée de résoudre le jeu, c'est-à-dire de remplacer un très bon joueur par un joueur parfait, viendra ensuite.
Le travail est collectif. L'article de 2007 est signé par huit chercheurs : Jonathan Schaeffer, Neil Burch, Yngvi Björnsson, Akihiro Kishimoto, Martin Müller, Robert Lake, Paul Lu et Steve Sutphen. Il a aussi demandé des moyens de calcul considérables pour l'époque : des dizaines d'ordinateurs ont tourné presque sans interruption depuis 1989, avec un pic de plus de 200 processeurs en 1992.
Marion Tinsley : le plus grand joueur de tous les temps
Pour mesurer la force de Chinook, il fallait l'opposer au meilleur. Marion Tinsley (1927-1995), mathématicien de formation et professeur de mathématiques en Floride, a été champion du monde de 1955 à 1958 puis de 1975 à 1991. Dans leur article de Science, Schaeffer et ses coauteurs le décrivent simplement comme le plus grand joueur de checkers qui ait jamais vécu.
Son palmarès tient en quelques lignes :
- Champion du monde de 1955 à 1958, puis de 1975 à 1991, après un long retrait volontaire de la compétition.
- Presque jamais battu : d'après le récit de Schaeffer, les deux victoires de Chinook en 1992 n'étaient que les sixième et septième défaites de Tinsley en 42 ans.
- Un mathématicien : docteur de l'université d'État de l'Ohio, spécialiste d'analyse combinatoire, il a enseigné à l'université d'État de Floride puis à l'université A&M de Floride.
Tinsley ne jouait pas seulement bien : il ne se trompait presque jamais. Battre un tel adversaire représentait un défi colossal, même pour une machine.
1990-1992 : le droit de défier le champion
En 1990, Chinook termine deuxième du championnat national américain, derrière Tinsley. Ce résultat lui donne le droit de disputer le titre mondial : c'est la première fois qu'un programme gagne ce droit face à des humains, tous jeux confondus. Les fédérations américaine et anglaise refusent pourtant qu'une machine joue pour le titre. Tinsley, qui veut ce match, renonce alors à sa couronne en 1991, et un titre distinct est créé : le championnat du monde homme-machine.
Le match a lieu à Londres du 17 au 29 août 1992. Il se joue sur 39 parties : Tinsley en gagne quatre, Chinook deux, et 33 se terminent par la nulle. Tinsley remporte le titre, mais de peu, et les deux défaites qu'il concède sont un événement en soi pour un joueur qui ne perdait pratiquement jamais.
Le match de 1994 : un drame humain
La revanche s'ouvre le 15 août 1994 au Computer Museum de Boston. Chinook a beaucoup progressé en deux ans. Les six premières parties sont nulles. Puis Tinsley se retire pour raisons de santé : un cancer du pancréas lui est diagnostiqué dans les jours qui suivent. Il meurt le 3 avril 1995, à 68 ans.
Conformément au règlement, Chinook est déclaré champion du monde homme-machine. L'équipe n'a jamais caché que cette façon d'obtenir le titre ne la satisfaisait pas : Chinook n'a jamais battu Tinsley dans un match mené à son terme. Le programme défend ensuite son titre contre Don Lafferty, que l'équipe tenait pour le deuxième meilleur joueur du monde : un premier match disputé à Boston dans la foulée se termine à égalité (une victoire chacun et 18 nulles), puis Chinook gagne la revanche en janvier 1995 par une victoire et 31 nulles. En 1996, jugé nettement plus fort que tous les joueurs humains, il est retiré de la compétition.
Schaeffer a raconté toute cette période dans son livre One Jump Ahead. Comme l'illustrent les finales célèbres aux Dames, les confrontations au sommet produisent des histoires inoubliables.
La résolution du jeu : 2007
Le match inachevé laissait une question ouverte : qui était le meilleur ? L'équipe a choisi d'y répondre autrement. Si les checkers sont une nulle avec le jeu parfait, un Chinook parfait ne perdra jamais, contre personne. Il restait à le prouver.
Résoudre un jeu peut vouloir dire trois choses différentes. On peut connaître seulement le résultat du jeu parfait, sans savoir comment l'obtenir. On peut connaître le résultat et une stratégie qui le garantit depuis la position de départ : c'est la résolution dite « faible ». On peut enfin connaître le résultat de toutes les positions possibles : c'est la résolution « forte ». Les checkers ont été résolus au sens faible : Chinook dispose d'une stratégie qui ne perd jamais, avec les Noirs comme avec les Blancs.
Le jeu compte environ 500 milliards de milliards de positions (5×1020). Il n'était ni possible ni nécessaire de les examiner toutes. La preuve combine deux recherches qui se rejoignent :
- En partant de la fin : des bases de finales, construites par analyse rétrograde. On calcule le résultat de toutes les positions à une pièce, puis à deux, à trois, et ainsi de suite. L'équipe est allée jusqu'à 10 pièces, soit 39 billions de positions (3,9×1013), compressées dans 237 gigaoctets. Ce calcul s'est achevé en 2005.
- En partant du début : une recherche vers l'avant depuis la position de départ. Un programme tient à jour l'arbre de la preuve et choisit les positions à examiner ; d'autres les analysent, d'abord avec la recherche alpha-bêta de Chinook, puis avec un algorithme conçu pour prouver un résultat plutôt que pour l'estimer. Dès qu'une ligne de jeu atteint une position à 10 pièces ou moins, la base de finales donne la réponse.
La prise obligatoire aide beaucoup : elle fait disparaître les pièces rapidement et ramène vite le jeu vers les finales connues. Au total, la recherche vers l'avant a porté sur environ 1014 positions, une infime partie du jeu. L'effort n'a pas été continu : le problème étant encore trop difficile, les calculs se sont arrêtés après 1996, puis ont repris en 2001 avec des machines plus puissantes.
L'article, intitulé Checkers Is Solved, paraît en ligne le 19 juillet 2007 puis dans le numéro de Science du 14 septembre. Le verdict : avec un jeu parfait des deux côtés, la partie est nulle, ce que les grands maîtres supposaient depuis des décennies. Les auteurs présentent les checkers comme le jeu populaire le plus difficile résolu à cette date, environ un million de fois plus complexe que le Puissance 4.
Ce que la preuve ne dit pas
Une résolution faible a ses limites. Elle garantit qu'on ne perd pas depuis la position de départ, mais elle ne donne pas le meilleur coup dans n'importe quelle position : si un joueur commet une erreur, l'arbre de la preuve ne montre pas forcément comment la punir. Les auteurs jugent d'ailleurs peu probable une résolution forte à court terme, faute de place pour stocker le résultat de toutes les positions.
Surtout, la preuve ne dit rien des autres jeux de dames. Les dames internationales se jouent sur 50 cases au lieu de 32, avec 20 pions par camp, des pions qui prennent en arrière et des dames qui traversent le damier : le jeu est beaucoup plus vaste, et personne ne l'a résolu. Quant aux échecs, les auteurs estiment qu'ils resteront non résolus longtemps, sauf rupture technologique.
L'impact sur l'intelligence artificielle
Chinook a joué à un niveau surhumain plusieurs années avant la victoire de Deep Blue sur Garry Kasparov aux échecs, en 1997. Mais gagner et résoudre sont deux choses différentes : Deep Blue, comme plus tard AlphaGo face à Lee Sedol au go (2016), s'appuie sur des évaluations approchées de la position. Résoudre un jeu, c'est remplacer ces estimations par une certitude.
Pour ses auteurs, le résultat montre surtout jusqu'où peut aller une approche fondée sur la recherche intensive, avec très peu de connaissances propres au jeu. Les techniques mises au point pour interroger en temps réel d'énormes bases de données ont d'ailleurs servi ailleurs, notamment en bio-informatique.
Le jeu de Dames est-il mort ?
On pourrait penser que résoudre un jeu le tue. Si l'issue est connue d'avance, pourquoi jouer ? En réalité, la preuve ne change rien pour les joueurs, pour une raison simple : aucun humain ne peut jouer de manière parfaite.
Personne ne peut mémoriser la stratégie de Chinook. Même Tinsley, qui s'en est approché plus que quiconque, a perdu quelques parties dans sa carrière. Savoir qu'un jeu parfait mène à la nulle ne dit rien sur la manière de punir les erreurs de l'adversaire, et c'est là que se joue une partie entre humains, comme le détaille notre guide de stratégie aux dames.
Jouer aux dames anglaises aujourd'hui
Le jeu que Chinook a résolu se joue sur ce site : les dames anglaises font partie des variantes proposées, avec leurs règles officielles (les Noirs commencent, les pions ne prennent que vers l'avant, la dame avance d'une seule case). Notre ordinateur n'est pas Chinook et il n'est pas parfait : à vous de trouver ses erreurs. Vous pouvez jouer une partie de dames en ligne, en choisissant la variante au moment de lancer la partie.
Sources
- J. Schaeffer et al., « Checkers Is Solved », Science, vol. 317, 14 septembre 2007, p. 1518-1522 (doi:10.1126/science.1144079).
- J. Schaeffer et al., « Chinook: The World Man-Machine Checkers Champion », AI Magazine, vol. 17, n° 1, 1996.
- Site du projet Chinook, université d'Alberta : historique et parties des matchs de 1992 et 1994.
- J. Schaeffer, One Jump Ahead, Springer, 1997.