Chinook : l’IA qui a résolu le jeu de Dames
En 2007, une équipe de chercheurs de l’université d’Alberta, au Canada, a accompli ce que beaucoup croyaient impossible : résoudre complètement le jeu de Dames anglaises (8×8). Après dix-huit ans de calculs, leur programme Chinook a démontré que le jeu de Dames, joué parfaitement par les deux camps, aboutit nécessairement à un match nul. Cette prouesse scientifique constitue l’un des plus grands accomplissements de l’intelligence artificielle appliquée aux jeux. Pour mieux comprendre la richesse de ce jeu millénaire, découvrez notre article sur l’histoire du jeu de Dames.
Jonathan Schaeffer : l’homme derrière Chinook
Jonathan Schaeffer, professeur d’informatique à l’université d’Alberta, a commencé à travailler sur Chinook en 1989. Son objectif initial était modeste : créer un programme capable de rivaliser avec les meilleurs joueurs humains. Mais au fil des années, l’ambition a grandi. Schaeffer ne voulait plus seulement gagner - il voulait prouver mathématiquement que son programme jouait de manière parfaite.
Le projet a mobilisé une équipe de chercheurs dévoués, des dizaines d’ordinateurs et une détermination sans faille. Schaeffer a souvent décrit cette quête comme une obsession qui a dévoré deux décennies de sa carrière académique.
Marion Tinsley : le plus grand joueur de tous les temps
Pour mesurer la force de Chinook, il fallait l’opposer au meilleur joueur humain de l’histoire. Marion Tinsley (1927-1995) est unanimement considéré comme le plus grand joueur de Dames de tous les temps. Mathématicien de formation et pasteur de profession, Tinsley a dominé les Dames pendant près de quarante ans.
Ses chiffres sont vertigineux :
- Champion du monde de 1955 à 1991 (avec une pause volontaire dans les années 1960).
- Seulement sept défaites en plus de quarante ans de compétition.
- Une capacité d’analyse que ses adversaires comparaient à celle d’un ordinateur : Tinsley voyait des dizaines de coups à l’avance.
Tinsley ne jouait pas seulement bien : il jouait de manière quasi parfaite. Battre un tel adversaire représentait un défi colossal, même pour une machine.
Le match de 1992 : l’homme contre la machine
Le premier affrontement officiel entre Chinook et Tinsley a eu lieu en 1992, lors du championnat du monde homme-machine organisé à Londres. L’événement a captivé le monde de l’intelligence artificielle et des jeux de réflexion.
Le match s’est déroulé sur 39 parties. Tinsley a remporté quatre parties, Chinook en a gagné deux, et 33 se sont terminées par un match nul. Le verdict : Tinsley conservait son titre. Mais le score serré a démontré que Chinook pouvait rivaliser avec le meilleur joueur humain de l’histoire.
Schaeffer a noté avec admiration que Tinsley semblait deviner les failles de son programme. Lors d’une partie mémorable, Tinsley a sacrifié un pion dans une position que Chinook évaluait comme égale. Soixante-sept coups plus tard, la supériorité du sacrifice devenait évidente. L’intuition humaine venait de triompher du calcul brut.
Le match de 1994 : un drame humain
Un deuxième match a été organisé en 1994 à Boston. Chinook avait été considérablement amélioré depuis 1992. Les six premières parties se sont soldées par des matchs nuls. Puis, au début de la septième partie, Tinsley s’est retiré.
À 67 ans, Tinsley souffrait d’un cancer du pancréas, diagnosticé quelques semaines plus tard. Il est décédé en avril 1995. Chinook a été déclaré champion du monde par forfait - un titre que Schaeffer a toujours considéré comme incomplet, car il n’avait jamais battu Tinsley dans un match terminé.
Cet épisode tragique a profondément marqué Schaeffer. Dans son livre One Jump Ahead, il rend hommage à Tinsley comme à un adversaire extraordinaire et un être humain remarquable. Comme l’illustrent les finales célèbres aux Dames, les confrontations au sommet produisent des histoires inoubliables.
La résolution complète : 2007
Après le décès de Tinsley, Schaeffer a réorienté son objectif. Plutôt que de battre les humains, il a décidé de résoudre le jeu lui-même. Résoudre un jeu signifie déterminer, pour chaque position possible, le résultat avec un jeu parfait des deux côtés.
Le jeu de Dames anglaises (8×8) compte environ 500 milliards de milliards (5×10⁶⁰) de positions possibles. Pour les analyser toutes, Chinook a utilisé :
- Des bases de finales : toutes les positions avec 10 pièces ou moins ont été calculées exhaustivement (39 billions de positions).
- La recherche rétrograde : à partir des positions finales connues, l’algorithme remonte coup par coup vers la position initiale.
- L’élagage alpha-bêta : une technique qui permet d’éliminer les branches de calcul inutiles.
Le 29 avril 2007, l’équipe a publié ses résultats dans la revue Science. Le verdict : le jeu de Dames, joué parfaitement par les deux joueurs, se termine toujours par un match nul. Le jeu de Dames anglaises devenait le plus complexe jeu jamais résolu complètement.
L’impact sur l’intelligence artificielle
La résolution du jeu de Dames par Chinook a eu des répercussions bien au-delà du monde des jeux de société. Elle a démontré que les techniques d’intelligence artificielle pouvaient résoudre des problèmes d’une complexité astronomique, pourvu qu’on leur accorde suffisamment de temps et de puissance de calcul.
Les méthodes développées pour Chinook ont trouvé des applications dans :
- La planification logistique : optimiser les itinéraires, les stocks, les horaires.
- La bioinformatique : explorer les repliements possibles des protéines.
- La vérification de logiciels : prouver l’absence de bugs dans les systèmes critiques.
Chinook a aussi ouvert la voie à d’autres exploits de l’IA dans les jeux : la victoire de Deep Blue sur Kasparov aux échecs (1997), celle d’AlphaGo sur Lee Sedol au Go (2016), et les performances surhumaines de l’IA dans le poker, le Starcraft et bien d’autres jeux.
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é, c’est tout le contraire. La résolution de Chinook n’a pas diminué l’intérêt du jeu de Dames, pour une raison simple : aucun humain ne peut jouer de manière parfaite.
Le jeu de Dames reste un défi fascinant parce que la profondeur stratégique dépasse de loin les capacités de calcul du cerveau humain. Même Tinsley, le plus grand joueur de l’histoire, a perdu sept parties en carrière. Savoir qu’un jeu parfait mène au nul ne dit rien sur la manière de punir les erreurs de l’adversaire - et c’est là que réside tout l’art du jeu, comme le détaillent nos stratégies pour débutants aux Dames.
L’héritage de Chinook
L’histoire de Chinook est bien plus qu’une anecdote technologique. C’est le récit d’une obsession intellectuelle portée pendant près de vingt ans, d’une rivalité homme-machine qui a touché à l’universel, et d’un hommage involontaire au génie de Marion Tinsley.
Schaeffer l’a lui-même résumé avec humilité : « Nous avons résolu le jeu de Dames, mais nous n’avons pas résolu Tinsley. » La perfection algorithmique ne remplacera jamais l’intuition humaine. Et c’est peut-être la plus belle leçon que Chinook nous ait apprise : même lorsqu’une machine peut calculer toutes les possibilités, le jeu reste une aventure profondément humaine.