La fin des Dames anglaises ?

Joueurs de dames anglaises.
De la collection de Jack et Beverly Wilgus.

Le jeu de Dames dans sa version anglaise, nommé aussi Checkers ou Draugths, se joue sur un tableau 8×8 et non pas 10×10 comme le jeu de Dames françaises, avec lequel il a de grandes similarités. C’est un jeu très pratiqué dans le monde anglo-saxon, aussi populaire que les Échecs, le Go ou Othello. Parmi ces quatre jeux, il était le plus susceptible de conduire à une victoire définitive de la machine. Espoir confirmé : il y a quelques mois, une équipe de chercheurs de l’Université canadienne d’Alberta a dévoilé une stratégie optimale pour ce jeu de Dames anglaises.

Le travail, coordonné par Jonathan Schaeffer depuis 1989, est un exploit historique qui a nécessité toutes sortes de compétences et un ensemble de calculs d’une incroyable complexité. Cette recherche a fait progresser le domaine de l’algorithmique des jeux et a permis la mise au point de techniques qui servent déjà dans d’autres disciplines. Contrairement à ce que l’on prétend, ce n’est pas une victoire de la machine sur l’homme, mais une victoire de l’intelligence humaine et de l’opiniâtreté de brillants chercheurs qui ont tiré des systèmes informatiques d’aujourd’hui un résultat étonnant, à l’extrême limite du possible !

Il y a trois façons pour une machine de battre les joueurs humains à des jeux de tableau. La première méthode consiste pour l’ordinateur à jouer suffisamment bien pour que le joueur humain perde, ou fasse partie nulle, à chaque fois qu’il s’oppose à la machine. Le jeu de Dames anglaises se trouve dans cette situation depuis 1994. Le jeu d’Échecs est similairement maîtrisé depuis le fameux combat entre Garry Kasparov et la machine Deeper Blue en mai 1997. La supériorité de la machine sur l’homme aux Échecs a été confirmée en décembre 2006 par la victoire du programme Deep Fritz contre le champion du monde en titre Vladimir Kramnik.

Trois types de victoires

Cependant, une telle méthode n’interdit pas, en théorie, qu’un joueur humain particulièrement perspicace élabore une stratégie de jeu exploitant les points faibles du programme et réussisse ainsi à le battre. Les algorithmes utilisés pour écrire ces programmes de premier niveau sont fondés sur des « heuristiques », des procédés qui fonctionnent bien en général, mais dont rien n’assure qu’ils fonctionnent à tous les coups. Un bon jeu n’est pas un jeu parfait.

Pour obtenir des programmes qui gagnent infailliblement, un travail d’analyse plus fin est indispensable. Il faut en quelque sorte prévoir tous les coups possibles lors d’une partie. La machine n’a ainsi battu irrémédiablement le joueur humain que dans quelques jeux simples, dont le morpion sur échiquier 15×15 (nommé aussi Go-Moku) en 1996.

L’équipe de J. Schaeffer, déjà conceptrice du meilleur programme de jeu de Dames en 1994 (ce programme utilisait la méthode des heuristiques), vient de découvrir une stratégie de jeu infaillible. L’article publié électroniquement en juillet 2007 dans la revue Science s’intitule Checkers is solved, car la stratégie obtenue au final fonctionne parfaitement. Que le programme joue en premier (c’est-à-dire Noir) ou qu’il joue en second, jamais il ne perdra ; si l’adversaire du programme joue correctement, la partie sera nulle. Deux joueurs parfaits, par exemple l’ordinateur face à lui-même, feront partie nulle. Rien ne pourra modifier cette situation décevante, mais les spécialistes de ce jeu avaient pressenti depuis longtemps que l’opposition de deux joueurs parfaits donnerait un match nul.

La troisième façon pour une machine de bien jouer contre un adversaire consisterait à pratiquer une stratégie optimale de jeu quelle que soit la configuration initiale des pièces sur le damier, même s’il s’agit d’une configuration artificielle (plutôt que celle obtenue en suivant les règles du jeu). Ce troisième niveau de jeu, atteint pour le jeu africain Awari (ou Awele) en 2002, n’est pas à portée de main pour le jeu de Dames anglaises : quelques années supplémentaires seront nécessaires pour y parvenir.

Le nombre de configurations possibles des pions sur un damier anglais 8×8 est évalué à 5×10²⁰, soit 100 millions de fois plus que le nombre de configurations possibles pour le jeu Awari. C’est la première fois qu’un jeu de cette difficulté est résolu complètement. On remarquera que c’est encore le nombre 10²⁰ qui marque la limite des capacités technologiques actuelles. Ce nombre est celui de la mémoire artificielle : la mémoire cumulée des disques durs d’aujourd’hui sur Terre avoisine 10²⁰ octets, et dans le domaine de la puissance de calcul, la puissance cumulée des microprocesseurs sur Terre est aujourd’hui évaluée à environ 10²⁰ instructions par seconde. Ces capacités cumulées suivent la loi de Moore : elles sont doublées, au moins, tous les 18 mois, ce qui est équivalent à une multiplication par 10, au moins, tous les cinq ans. Peut-être en est-il de même pour la taille de l’arbre des jeux dont on peut déterminer les stratégies optimales.

Pour réaliser son exploit, l’équipe canadienne a décomposé le problème en plusieurs étapes, certaines ayant exigé des années de travail et des milliers d’heures de calculs. Précisons que la méthode utilisée ne consiste pas à représenter dans les mémoires d’un ou de plusieurs ordinateurs l’ensemble des 5×10²⁰ configurations possibles, puis, après avoir analysé cet ensemble, à en déduire la stratégie optimale. Cette méthode d’exploration exhaustive du jeu par analyse rétrograde (mathématiquement bien définie et parfaite en théorie) exigerait un espace de stockage supérieur à l’ensemble de la mémoire numérique disponible aujourd’hui sur Terre ! Il a fallu être plus subtil…

La longue histoire de Chinook

Le projet a débuté en 1989. Au début, l’objectif était de développer un programme capable de battre le champion du monde en titre, Marion Tinsley, qui dominait le jeu depuis 1950. Entre 1950 et sa mort en 1995, Tinsley gagna tous les tournois auxquels il participa et ne perdit jamais aucune partie contre des humains en tournoi. C’est dire à quel point il dominait la discipline !

L’objectif de le battre ne fut pas atteint en 1992, année où le programme Chinook de l’Université d’Alberta perdit un tournoi officiel contre Tinsley (le Chinook est un vent chaud qui descend des montagnes et qui se réchauffe par la compression résultant de la diminution d’altitude). Lors de ce tournoi, Tinsley s’inclina cependant deux fois devant la machine ; c’était donc ses premières parties perdues dans un tournoi depuis 1950. En 1994, un second tournoi entre Chinook (amélioré entre-temps) et Tinsley fut organisé. Ce tournoi fut interrompu à cause de l’état de santé de Tinsley ; il était atteint d’un cancer du pancréas qui l’emporta huit mois plus tard. Depuis, le programme Chinook est reconnu comme le meilleur joueur, et tous les humains qui s’y sont confrontés ont perdu contre lui. Cette situation peu satisfaisante – Marion Tinsley aurait-il battu Chinook ? – a incité l’équipe de J. Schaeffer à aller plus loin. Cette fois, le but fixé était l’élaboration d’une stratégie optimale de jeu qui assurerait mathématiquement que jamais aucun humain, pas même Tinsley, ou aucune autre machine ne remettrait en cause la domination des nouvelles versions, parfaites, de Chinook.

Pour un jeu simple, on trouve les stratégies optimales en utilisant la méthode d’analyse rétrograde. Les configurations finales correspondant à des parties terminées sont marquées gagnante (pour celui dont c’est le tour de jouer) perdante ou nulle selon les cas. Ce marquage permet de connaître la nature perdantes, gagnantes ou nulles des configurations qui précèdent un coup. Puis, pas à pas, en remontant, on marque des configurations de plus en plus complexes et proches du début de la partie. Dans le cas des jeux élémentaires, on peut remonter jusqu’à la position initiale dont on sait alors si elle est gagnante, perdante ou nulle.

Schéma général de l’exploration.
Recherche d’un marquage de la position initiale du jeu de Dames anglaises par l’équipe de chercheurs de l’Université d’Alberta. Le nombre de pièces présentes sur le damier est représenté sur l’axe vertical, le nombre total de positions est donné en échelle logarithmique sur l’axe horizontal. La zone rosée représente l’ensemble des fins de parties (toutes les configurations de 10 pièces ou moins) dont la liste complète a été calculée, marquée (gagnante, perdante ou nulle) et stockée. La zone ovale bleue représente la partie de l’espace réellement utile pour déterminer le marquage de la position de départ. De nombreuses configurations ne servent à rien, soit parce qu’elles ne peuvent pas être atteintes à partir de la configuration initiale du jeu, soit parce que la stratégie optimale trouvée les évitera. Les petits ronds représentent les positions utilisant plus de 10 pièces dont le marquage a été calculé et mémorisé pour arriver au marquage de la position initiale.

Pour contrôler que la stratégie est optimale, il suffit de s’assurer que (a) de toute position marquée gagnante pour le joueur A, on peut atteindre une position marquée perdante pour le joueur B et que (b) tous les coups permis par les règles à partir d’une position marquée perdante pour le joueur B conduisent à des positions marquées gagnantes pour le joueur A. La possibilité de parties nulles complique un peu l’idée, mais le principe reste le même.

Dans le cas du jeu de Dames anglaises, l’analyse rétrograde n’est pas praticable sur la totalité des configurations, car leur nombre, 5×10²⁰, est trop grand. Cependant, même partiel, ce marquage par l’analyse rétrograde est utile. Dès les premières versions de Chinook, de tels marquages étaient faits à l’avance et utilisés par le programme qui, grâce à cela, ne commettait aucune erreur en fin de partie ; cette méthode de calcul préalable par analyse rétrograde est classique dans la programmation de tous les jeux de tableau (Échecs, Othello, etc.), où elle règle à l’avance les fins de parties, calculées une fois pour toutes.

En 1989, toutes les configurations ayant moins de quatre pièces du jeu de Dames anglaises étaient ainsi marquées et stockées. En 1994, pour le second tournoi contre Tinsley, une proportion importante des configurations à huit pièces ou moins avait été marquée. En 1996, la base de données des marquages de toutes les configurations à huit pièces ou moins était achevée et utilisée par le programme Chinook. C’était malheureusement encore insuffisant pour obtenir une stratégie parfaite. Aussi, en 2001, l’équipe entreprit de calculer le marquage par analyse rétrograde de toutes les configurations ayant dix pièces ou moins. Le travail ne fut achevé qu’en 2005, après des milliers d’heures de calculs opérées simultanément sur plusieurs dizaines de machines. Ce travail nécessita la mise au point de programmes massivement parallèles, domaine de recherche auquel l’équipe canadienne apporta des contributions intéressantes.

La base de données obtenue contient 39 000 milliards de configurations. La manipulation de cette base exige des techniques spécifiques de compression de données qui réduisent sa taille à 237 gigaoctets. Pour utiliser la base, des opérations de décompression sont donc nécessaires et ont été conçues et optimisées par les chercheurs canadiens. C’est une technologie adaptée et extrêmement délicate qui a ainsi été élaborée et appliquée pour le calcul, le contrôle et l’exploitation du marquage des configurations finales.

Après le bas, le haut

L’impossibilité d’utiliser la méthode rétrograde jusqu’à la position de départ pour obtenir une stratégie optimale de jeu a alors contraint les chercheurs à attaquer le problème par l’autre bout : le début de la partie.

À la méthode rétrograde et aux bases de données qu’elle produit, on a donc adjoint une méthode nouvelle « en avant », qui oriente le marquage vers des parties de l’espace des configurations et évite au calcul de s’égarer dans des recherches désespérées. Le but est toujours de découvrir une partie de l’arbre de toutes les configurations ne comportant que des positions dont le marquage a été calculé, le tout définissant une stratégie optimale.

Le haut de l’arbre.
Pour déterminer le marquage de la position initiale du jeu de Dames anglaises, une partie de l’arbre des configurations a été marquée. Voici le haut de cet arbre.
Le marquage utilisé est légèrement différent de celui décrit dans l’encart 3 (analyse rétrograde), car un marquage un peu moins précis est suffisant (ce qui économise du calcul). On suppose que les deux joueurs jouent parfaitement. La lettre N indique (comme précédemment) que la partie sera nulle. Le marquage <– N signifie que la partie sera nulle ou perdue pour les Noirs, le marquage –> N que la partie sera nulle ou gagnée pour les Noirs et le marquage P que la partie sera perdue pour les Noirs. Les déplacements des pions suivent la numérotation des cases de la figure b dans l’encart 1 (règles).
Les branches non explorées représentent des coups possibles qu’il n’est pas nécessaire d’explorer pour conclure sur la nature de la position de départ (comme expliqué dans l’exemple avec la pile de pions de l’encart 1).

Notons que pour prouver qu’une configuration donnée est perdante, gagnante ou nulle, il est inutile de marquer toutes les configurations ; seules celles susceptibles d’être atteintes selon les règles du jeu importent. Dans la méthode « en avant », on ne cherche pas à marquer toutes les configurations, mais uniquement celles d’une partie de l’arbre du jeu, que la stratégie optimale exploitera en forçant l’adversaire à ne pas la quitter. Précisément, dans le cas du jeu de Dames anglaises, l’arbre partiel finalement marqué et stocké par l’équipe canadienne comporte 10⁷ configurations, nombre 10 000 milliards de fois plus petit que le nombre de configurations total.

Voici l’idée utilisée pour cette recherche « en avant » d’une stratégie optimale. Un programme nommé contrôleur tente, à partir de la situation de départ, d’engendrer progressivement l’arbre prouvant que cette situation initiale du jeu est gagnante, perdante ou nulle. Le contrôleur détermine à chaque étape quelles sont les positions qui méritent d’être évaluées (c’est-à-dire dont il peut être intéressant de trouver le marquage exact), et il lance sur ces configurations soigneusement sélectionnées des programmes nommés résolveurs, qui tentent de découvrir le marquage.

Les algorithmes écrits pour le fonctionnement du contrôleur s’appuient sur des méthodes heuristiques, c’est-à-dire sur des méthodes qui évaluent sans certitude absolue qu’il est utile de s’attaquer à telle configuration ou à telle autre, et qui organisent les traitements prioritaires. Toutefois, l’usage de ces méthodes heuristiques n’a pas d’effet sur la certitude du résultat final. Les méthodes heuristiques guident le calcul de la recherche d’un arbre prouvant le marquage de la position de départ et, une fois trouvé, ce marquage est vérifiable sans avoir à utiliser d’heuristiques. Si les heuristiques sont bonnes, une stratégie optimale est trouvée plus rapidement que si elles sont mauvaises, mais ce qui est éventuellement trouvé au bout du compte est un arbre définissant, sans aucun risque d’erreurs, une stratégie optimale.

Les résolveurs utilisés dans cette recherche ont été de deux types, et là encore leur agencement réciproque est subtil. Le premier type de résolveur est construit sur une ancienne version du programme Chinook. Normalement, Chinook exploite des méthodes heuristiques ne permettant pas le marquage sans erreur des configurations qu’on lui soumet. Cependant, dans certains cas, le résultat proposé est rendu sûr et donne donc un marquage garanti. Lorsque ce n’est pas le cas, les informations calculées par l’ancien Chinook sont quand même utiles et transmises au programme contrôleur qui les exploite pour reconsidérer l’ensemble des configurations à traiter et leur ordre. Lorsque le premier résolveur ne donne pas d’informations assez précises, un second résolveur, fondé sur des travaux de recherche de Ayumu Nagai, de l’Université de Tokyo, est mis au travail. L’ensemble des sous-problèmes à résoudre évolue ainsi petit à petit, géré globalement par le contrôleur qui coordonne les tâches confiées aux résolveurs et récupère auprès d’eux des informations pour la construction de la stratégie optimale.

Pour que le calcul aboutisse plus vite, une méthode d’approximations successives a aussi été mise en œuvre dans l’organisation générale du calcul. Dans un premier temps, on ne recherche pas un arbre dont chaque marquage est certain, on se contente de marquages approchés : la stratégie optimale trouvée ainsi n’est pas absolument garantie, même si c’est sans doute une assez bonne méthode de jeu. Elle sert de guide pour organiser une seconde étape de calcul qui produit de nouveaux marquages plus sûrs. De proche en proche, l’erreur due aux marquages approchés est réduite, et, au bout du calcul, le contrôleur dispose de marquages parfaits et donc d’une stratégie optimale valide.

Le calcul qui a abouti en avril 2007 s’est déroulé pendant plusieurs mois ; il était distribué entre une cinquantaine de machines calculant simultanément les explorations nécessaires. L’arbre trouvé permet un jeu parfait et peut être consulté sur le site.

La méthode ressemble à celle utilisée lorsque l’on résout un Sudoku. Beaucoup de travail et de raisonnements utilisant toutes sortes d’astuces, voire d’intuitions et même de prises de risques, sont nécessaires pour trouver la solution. Cependant, une fois celle-ci obtenue, la vérification qu’elle est exacte consiste simplement en un contrôle mécanique du tableau, ce qui ne demande plus aucun raisonnement et ne repose donc plus sur les méthodes peut-être imparfaites utilisées dans la phase de découverte.

La méthode est finalement un mélange entre :

• d’une part, un calcul fait à l’avance, le marquage de toutes les configurations ayant dix pièces ou moins, dont les résultats sont stockés en utilisant de grandes quantités de mémoire et des techniques de compressions de données ;
• et d’autre part, un autre calcul prolongé « en avant » monopolisant des dizaines d’ordinateurs pendant des mois, coordonnés par un contrôleur et qui, pour aboutir rapidement, n’hésite pas à utiliser toutes sortes d’approximations et de raisonnements heuristiques.

En théorie, une méthode uniquement fondée sur la mémoire est possible : la méthode rétrograde de marquage des 5×10²⁰ configurations du jeu. En théorie aussi, une méthode « en avant » uniquement fondée sur des calculs prolongés d’un algorithme classique (nommé minimax sans limitation de profondeur) aurait aussi conduit à une stratégie parfaite. Cependant, l’état des technologies disponibles rend inutilisables les deux méthodes « pures » utilisées seules. C’est finalement une très délicate et complexe association des deux qu’il a fallu inventer et faire fonctionner.

Un théorème démontré par la machine

La découverte d’une stratégie optimale établissant que la position de départ du jeu de Dames anglaises conduit à une partie nulle en présence de deux joueurs parfaits est un travail de démonstration automatique. En effet, au bout du compte, on dispose d’un théorème nouveau « la position de départ du jeu de Dames anglaises est de type nulle » et d’une démonstration de ce résultat, car l’arbre marqué trouvé par le contrôleur contient tous les éléments nécessaires à une preuve du théorème – preuve qui peut donc être vérifiée indépendamment (ce qui a d’ailleurs été entrepris). Par rapport aux grandes démonstrations utilisant des ordinateurs – par exemple, pour le théorème des quatre couleurs ou la conjecture de Kepler –, il faut noter une double nouveauté :

• jamais la recherche d’une démonstration n’a nécessité un aussi long et complexe calcul s’étalant sur de nombreuses années et s’appuyant sur des technologies informatiques aussi variées ;
• jamais l’utilisation d’heuristiques n’a été aussi essentielle dans la recherche d’une preuve. Ces heuristiques, qui doivent être vues comme des conseils intelligents donnés par l’homme pour guider le calcul de la machine, sont le plus souvent absentes des méthodes de démonstration automatique (ou y jouent un rôle secondaire) ; ici, sans elles, rien n’aurait été possible.

L’intelligence du jeu, acquise par les joueurs du jeu de Dames anglaises et traduite dans les heuristiques utilisées à plusieurs niveaux dans les programmes des chercheurs canadiens, et l’intelligence humaine travaillant des années à l’élaboration de nouvelles méthodes et coordonnant une multitude de techniques informatiques ont permis un calcul qui, grâce au niveau actuel de notre technologie (aussi bien concernant le stockage des données, que le calcul rapide), a produit la démonstration d’un résultat mathématique d’énoncé simple. Le résultat de l’équipe canadienne n’est pas une victoire de la machine sur l’homme, mais une victoire de l’homme lui-même : celui-ci, par la maîtrise d’outils de calculs et de stockage qu’il a construits, obtient ce qu’aucun humain seul n’obtiendrait seul, et ce qu’aucune machine programmée naïvement ne pourra jamais obtenir non plus. Tinsley était sans doute un génie du jeu de Dames, le nouveau Chinook, grâce au travail de l’équipe de J. Schaeffer, égale et dépasse l’imbattable maître, et cette affirmation est un théorème mathématique.

L’avenir et les autres jeux

Quel est l’avenir des jeux de cette catégorie ? D’abord le problème du jeu de Dames anglaises n’est pas totalement réglé : une stratégie optimale n’est pas connue pour toutes les positions possibles des pièces (alors que c’est le cas pour le jeu Awari), mais seulement pour la position standard de début de partie. Cette nuance n’est pas sans importance, car dans de nombreux tournois entre joueurs humains, les parties ne commencent pas de la position de départ standard, mais d’une position tirée au hasard en faisant faire trois mouvements licites aux pièces. Pour devenir invincible lors de ces compétitions, il faudrait déterminer les stratégies optimales d’environ 200 positions, ce qui, d’après J. Schaeffer, pourrait exiger une autre décennie de travail !

Le jeu de Dames français (aussi nommé jeu de Dames international), qui se joue sur un damier 10×10, est nettement plus difficile que la version anglaise et il ne semble pas concevable que, dans un avenir immédiat, un résultat équivalent à celui des Canadiens soit atteint.

Le nombre de configurations possibles au jeu d’échecs est environ le carré du nombre de configurations possibles au jeu de Dames anglaises. Cela permet d’affirmer que la mise au point d’une stratégie optimale pour les échecs restera impossible durant de nombreuses décennies encore. Pour ce jeu, même si l’ordinateur gagne aujourd’hui, l’espoir qu’un humain puisse renverser les choses persistera longtemps. Quant au jeu de Go, malgré de récents progrès dans sa programmation, il n’est même pas question d’amener les ordinateurs à jouer au niveau des champions.

Une première version de ce document est parue dans la rubrique « Logique et calcul » de la revue Pour la Science, n°363, en janvier 2008.