Gagner aux dames à tous les coups : prouvé impossible sur 64 cases depuis 2007, mystère sur 100

Récit

18 ans de chantier, et un verdict publié le 19 juillet 2007 dans la revue Science : aux dames anglaises sur 64 cases, deux joueurs parfaits font toujours match nul.

Gagner à tous les coups y est donc impossible face à un adversaire sans faille. L’équipe de Jonathan Schaeffer, à l’Université de l’Alberta (Canada), l’a démontré avec son programme Chinook. Pour les dames internationales, le jeu de 100 cases pratiqué en France, personne ne connaît encore la réponse.

Comment gagner au jeu de dames à tous les coups ?

On ne peut pas, du moins sur 64 cases. L’article de Science établit qu’en partant de la position initiale, chaque camp dispose d’une défense qui lui garantit au moins la nulle. Une victoire n’arrive que sur une faute d’en face.

Comment une machine a-t-elle pu le prouver ?

Sans tout regarder. Les dames anglaises comptent environ 5 × 10²⁰ positions possibles, soit 500 milliards de milliards, selon IEEE Spectrum. Le calcul n’en a évalué que 10¹⁴ : une position sur cinq millions.

L’astuce tient en deux bouts : côté fin de partie, des bases recensent 39 000 milliards de positions dont l’issue est connue, compressées dans environ 237 gigaoctets. Côté ouverture, la recherche descend depuis la position de départ jusqu’à rejoindre ces bases. Les chercheurs parlent de résolution « faible » : la preuve vaut pour une partie qui commence au début, pas pour n’importe quelle position en cours de jeu.

Marion Tinsley, l’adversaire que Chinook n’a jamais battu en match

Chinook naît en 1989. En 1990, il termine deuxième de l’Open national américain, derrière Marion Tinsley. Ce joueur né dans l’Ohio en 1927 passe pour le plus grand de l’histoire, et la deuxième place donne à la machine le droit de le défier.

Le premier match se joue à l’hôtel Park Lane de Londres, du 17 au 29 août 1992. Selon les archives du match de 1992, c’est la première fois qu’une machine dispute un titre officiel à un humain dans un vrai jeu de réflexion. Tinsley gagne 4 parties, en perd 2 et fait 33 nulles.

La revanche s’ouvre le 15 août 1994 au Computer Museum de Boston. Six parties, six nulles. Le 18 août, Tinsley abandonne le match et son titre pour raisons de santé. Le mardi suivant, un cancer lui est diagnostiqué, selon le récit de la revanche. Les organisateurs sacrent Chinook champion du monde homme-machine, sans une victoire.

Tinsley meurt le 3 avril 1995, selon sa fiche sur le site de Chinook. Faute de pouvoir battre l’homme, Schaeffer s’attaque au jeu lui-même. Ses bases de fins de partie, lancées en 1989, avancent jusqu’en 1996. Le projet s’arrête en 1997, faute de puissance de calcul, puis repart en 2001.

Et chez nous ?

Pourquoi les dames internationales résistent-elles encore ?

Parce qu’elles sont des milliards de fois plus vastes. Les règles de la Fédération française fixent un damier de 100 cases et 20 pions par camp. La prise y est obligatoire, et celle du plus grand nombre de pièces passe avant toute autre.

Victor Allis, dans sa thèse de 1994, estimait leur nombre de positions à environ 10³⁰, selon le tableau de complexité des jeux. La méthode de 2007 a déjà réclamé 18 ans sur le petit damier. Aucune preuve n’a été publiée pour le grand.

Un autre grand jeu de 64 cases a rendu son verdict depuis. Hiroki Takizawa a annoncé le 30 octobre 2023, dans une prépublication sur arXiv, que le jeu parfait à Othello mène lui aussi à la nulle. Les échecs, avec 10⁴⁰ à 10⁵⁰ positions selon IEEE Spectrum, restent ouverts.

Alors, à quoi bon jouer encore aux dames anglaises ?

Parce que personne ne joue parfaitement : la nulle garantie suppose deux joueurs qui ne se trompent jamais.

« La seule chose que j’ai apprise dans tout cela, c’est de ne jamais sous-estimer les progrès de la technologie », confiait Schaeffer à IEEE Spectrum en 2007.

Face à Chinook, depuis la position de départ, la meilleure issue possible reste la nulle.

Article créé en collaboration avec l’IA.