Le jeu de dames est-il résolu ? Comment dix-huit ans de calcul ont prouvé la nulle et ce que cela signifie

Depuis l’époque des salons littéraires et des premiers cercles d’échecs et de dames, une énigme théorique a toujours intrigué les passionnés : l’issue d’une partie est-elle scellée dès le premier coup ? Si deux maîtres s’affrontent sur un plateau de soixante-quatre cases sans commettre la moindre faute, les Blancs disposent-ils d’un avantage décisif ? Les Noirs peuvent-ils résister indéfiniment ? Ou bien le destin de la rencontre est-il une égalité mathématique absolue ?

En juillet 2007, une annonce scientifique majeure publiée dans la prestigieuse revue Science a mis fin aux spéculations^[1]. Conduite par l’informaticien canadien Jonathan Schaeffer de l’Université d’Alberta, une équipe de chercheurs a prouvé que les dames anglaises (connues sous le nom de checkers en Amérique du Nord) sont officiellement résolues. Après un travail titanesque qui a duré 18 ans et mobilisé des grappes entières de processeurs depuis 1989, leur programme, baptisé Chinook, a apporté la démonstration définitive : un jeu parfait de la part des deux adversaires conduit inéluctablement à une partie nulle.

Cette avancée historique n’a pourtant pas sonné le glas du plaisir de disputer une partie de jeu de dames en famille ou en ligne. Bien au contraire, elle a mis en lumière la richesse géométrique d’un classique universel.

Qu’est-ce qu’un jeu résolu en théorie des jeux ?

Dans le langage courant, résoudre une énigme signifie découvrir l’astuce qui rend le problème évident. En mathématiques combinatoires et en intelligence artificielle, la notion repose sur un cadre rigoureux formulé en 1994 par le chercheur Victor Allis^[2]. Allis a défini 3 niveaux de résolution distincts pour les jeux à information parfaite :

1. La résolution ultra-faible. Une démonstration prouve le résultat théorique de la position de départ (gain du premier joueur, gain du second ou partie nulle), sans pour autant fournir un algorithme ou une liste explicite de coups pour parvenir à ce résultat. C’est le cas emblématique du jeu de Hex, pour lequel la théorie des jeux démontre que le premier joueur gagne forcément par vol de stratégie, sans que l’on sache jouer parfaitement sur grand tablier.
2. La résolution faible. Un algorithme ou un arbre de preuve offre une stratégie complète et calculable garantissant au moins la nulle ou le gain depuis la position de départ, quelle que soit la réplique choisie par l’opposant. Le système ne connaît pas nécessairement l’évaluation de positions fantaisistes nées d’une suite d’erreurs absurdes, mais depuis la case départ, il est rigoureusement invincible. C’est précisément à ce niveau que se situent les dames^[1].
3. La résolution forte. Un algorithme détermine en temps réel l’évaluation exacte ainsi que le coup optimal pour chaque configuration légale possible, peu importe les maladresses antérieures. Le jeu Puissance 4 est fortement résolu depuis 1988 : le premier joueur gagne obligatoirement en jouant dans la colonne centrale^[2].

Les dames anglaises n’ont pas été fortement résolues, car mémoriser chaque position aberrante aurait exigé un espace de stockage astronomique. L’équipe de Schaeffer s’est concentrée sur la résolution faible à partir de la disposition réglementaire. La partie débute avec 12 pions foncés face à 12 pions clairs sur les 32 cases sombres du damier, soit 24 pièces au total^[3].

L’exploit scientifique de Chinook : dix-huit ans de calculs

L’univers combinatoire des dames dépasse de très loin ce que suggère la simplicité apparente des règles. Sur un damier 8x8, le nombre de positions légales envisageables avoisine 5 x 10^20 configurations^[1]. Ce nombre vertigineux correspond à environ cinq cents milliards de milliards d’états. Si un ordinateur individuel avait tenté de vérifier ces positions l’une après l’autre, la tâche aurait demandé des milliers d’années.

Pour vaincre cet océan de possibilités, l’équipe canadienne a articulé sa stratégie autour de deux piliers complémentaires : calculer à rebours depuis les finales, et forer en avant depuis l’ouverture.

L’exploration rétrograde et les 39 billions de positions

La clé de voûte de la preuve réside dans l’analyse rétrograde. Au lieu de partir du premier coup et de se perdre dans l’arbre des variantes, les chercheurs ont débuté par la fin absolue de la partie, avec un nombre infime de pièces sur le damier. Une position avec une dame contre une dame seule est immédiatement reconnue comme nulle. Deux dames encerclant un pion isolé dans un angle constituent un gain élémentaire forcé.

En injectant progressivement des pièces sur le damier vide, Chinook a déterminé la valeur exacte de chaque configuration. Lorsqu’un coup permet de basculer dans une position gagnante déjà cataloguée, la position examinée est étiquetée comme gagnante. Si tous les coups autorisés mènent à une situation perdante, elle est marquée comme perdue. Si le jeu optimal préserve l’équilibre, elle est enregistrée comme nulle.

Entre 1989 et 2007, Chinook a ainsi composé des tables de finales intégrales pour toutes les positions comptant 10 pièces ou moins^[1]. Cette base de données gigantesque recense 39 billions de positions distinctes. Dès qu’une partie descend sous le seuil de 10 pièces, Chinook ne cherche plus : il consulte la vérité absolue en mémoire.

La jonction entre l’ouverture et la table de finales

Une fois la base de 10 pièces achevée, il restait à tracer une passerelle infaillible reliant la position initiale de 24 pions à cette frontière de 10 pièces^[1].

Les chercheurs ont combiné des algorithmes d’élagage alpha-bêta avec la recherche par numéro de preuve (proof-number search). L’algorithme a exploré les lignes principales, privilégiant les échanges obligatoires et les simplifications vers la base de données, tout en écartant les branches où un mauvais coup était immédiatement puni.

Ce travail a nécessité des années de calcul parallèle sur des centaines de serveurs. Des milliards de variantes superflues ont été éliminées pour bâtir un arbre de preuve vérifié de dizaines de millions de positions clés. Chaque embranchement partant de la position initiale menait soit à une forteresse infranchissable, soit directement à une position de nulle de la base de données de 39 billions d’états. En 2007, la preuve était complète : les dames sont mathématiquement un match nul^[1].

Marion Tinsley : l’intuition humaine face à l’algorithme

Bien avant que la force brute des microprocesseurs ne résolve le jeu, un joueur d’exception a approché la perfection par la seule puissance de sa réflexion. Le Dr Marion Tinsley, professeur de mathématiques en Floride, est unanimement reconnu comme le plus grand joueur de dames de tous les temps.

Le palmarès de Tinsley défie l’imagination. Tout au long d’une carrière en tournoi longue de 45 ans, Tinsley n’a concédé que 9 défaites sur plusieurs milliers de parties officielles^[1]. Champion du monde incontesté pendant des décennies, il ne laissait échapper sa couronne que lorsqu’il décidait volontairement de s’éloigner de la compétition. Pour confronter Chinook au sommet de l’esprit humain, Jonathan Schaeffer organisa un match pour le titre mondial en 1992.

Cette confrontation de 1992 marqua un tournant historique entre l’intuition humaine et la machine. Au terme de 39 parties passionnantes, Tinsley fit preuve d’une profondeur stratégique remarquable et s’imposa face à Chinook sur le score de 4 victoires, 2 défaites et 33 nulles^[1]. C’était la première fois qu’un programme disputait un championnat du monde officiel contre un souverain humain régnant dans un jeu de plateau traditionnel.

En 1994, une revanche très attendue eut lieu. Après 6 parties nulles consécutives, Tinsley dut abandonner le match en raison d’un cancer foudroyant, avant de s’éteindre en 1995^[1]. Chinook fut alors sacré champion du monde homme-machine. L’analyse des parties de Tinsley par les concepteurs de Chinook a révélé un fait extraordinaire : les choix de Tinsley correspondaient quasiment coup pour coup aux préconisations optimales des bases de données.

L’échelle de complexité combinatoire : des dames aux échecs

Pour apprécier à sa juste valeur la résolution des dames, il est éclairant de positionner ce jeu sur l’échelle générale des jeux combinatoires.

En 1950, le mathématicien Claude Shannon a posé les jalons de l’analyse moderne de la complexité des échecs^[4]. Shannon évaluait le nombre de positions légales aux échecs à environ 10^44, et le nombre de parties possibles à au moins 10^120, une valeur colossale désormais célèbre sous le nom de nombre de Shannon^[4].

Voyons comment se comparent ces différents univers :

• Puissance 4 : Fortement résolu en 1988^[2]. Comptant des milliers de milliards d’états, ce jeu se résout en une poignée de secondes sur un simple ordinateur portable moderne.
• Dames anglaises 8x8 : Faiblement résolues en 2007 avec près de 5 x 10^20 positions^[1]. Il a fallu 18 ans de calcul distribué et une table de 39 billions de positions pour en venir à bout.
• Échecs : Totalement non résolus. Avec 10^44 positions et 10^120 chemins possibles^[4], les échecs dépassent de loin nos moyens de calcul actuels. Aujourd’hui, les tables de finales d’échecs ne couvrent que les positions jusqu’à 7 pièces. Passer à 8 pièces nécessiterait des pétaoctets de mémoire, tandis que le jeu complet à 32 pièces reste inaccessible aux ordinateurs classiques.
• Dames internationales 10x10 : Non résolues. Disputée sur cent cases avec vingt pions par camp, cette variante présente un espace d’états estimé à 10^30 positions. Les dames volantes et la prise majoritaire obligatoire démultiplient l’arbre de calcul.

Pourquoi le jeu de dames reste passionnant pour les humains

Lorsque la publication de 2007 a fait la une des journaux, quelques voix ont affirmé que le jeu de dames était mort. À quoi bon déplacer des pièces si la machine a prouvé que la partie débouche sur un partage des points ?

Une telle vision oublie la nature humaine de la compétition. Une solution mathématique décrit le comportement de deux intelligences parfaites effectuant cinquante coups impeccables. Or, aucun être humain ne possède en tête 39 billions de finales ni un arbre de recherche arborescent de dizaines de millions de branches.

Sur l’échiquier des dames, chaque partie reste un affrontement tactique intense. La règle de la prise obligatoire constitue le moteur de cette tension : dès qu’un saut est possible, vous devez le jouer. Cette contrainte engendre des combinaisons spectaculaires où un joueur sacrifie volontairement plusieurs pions pour forcer son adversaire à sauter sur une diagonale piégée avant de tout rafler.

Trois domaines fondamentaux font la différence entre les pratiquants :

1. La justesse de l’ouverture. Même si la meilleure ligne égalise, de nombreuses déviations précoces constituent des pièges mortels. Une imprécision commise au quatrième ou cinquième coup mène souvent à la catastrophe en quelques tours.
2. La conduite positionnelle. Occuper le centre, préserver sa ligne de fond et contrôler les cases clés exigent une solide vision du jeu. Les pratiquants qui étudient la stratégie aux dames prennent régulièrement le dessus sur les adeptes du calcul immédiat.
3. La maîtrise des finales. Lorsque le matériel est égal, la notion d’opposition s’avère souvent décisive. Un faux pas peut ruiner un gain net ou permettre à l’adversaire d’établir une forteresse imprenable, comme nous l’analysons dans notre guide des finales aux dames.

Dans les compétitions de haut niveau, le tirage au sort des premiers coups (système des ouvertures imposées) évite les sentiers battus et plonge immédiatement les maîtres dans des territoires inexplorés. Loin d’avoir tué le jeu, la démonstration mathématique a révélé toute la profondeur et l’équilibre de son architecture.

La dimension psychologique du combat sur le damier

L’égalité théorique ne signifie jamais une partie sans étincelle. Au contraire, lorsque la pendule tourne, la tension nerveuse pousse même les joueurs chevronnés à la faute. Anticiper les pièges, peser chaque liquidation et maintenir l’harmonie des diagonales requièrent une concentration sans faille. C’est dans cette confrontation vivante des esprits que réside toute la magie des dames.

L’équilibre entre patience et contre-attaque

Face à une offensive directe, la défense exige une précision chirurgicale pour préserver les diagonales maîtresses. Savoir temporiser et attendre l’affaiblissement adverse constitue souvent la clé d’une contre-attaque victorieuse.

Que vous consultiez les règles du jeu de dames pour parfaire vos bases, que vous exploriez les différentes variantes du jeu de dames ou que vous souhaitiez tout simplement jouer aux dames en ligne contre d’autres passionnés, le damier reste un formidable théâtre d’expression tactique. La science a révélé le verdict ultime, mais la beauté du combat appartient tout entière aux joueurs.

Foire aux questions sur la résolution des dames

Les dames sont-elles résolues pour n’importe quelle faute commise ?

Non. Les dames anglaises sont faiblement résolues, et non fortement résolues. La preuve garantit une stratégie optimale depuis la position de départ avec 24 pions sur 32 cases sombres pour assurer la nulle^[1]. De plus, toutes les configurations de 10 pièces ou moins sont parfaitement résolues par la base de données de 39 billions d’états. En revanche, des positions bizarres comptant une douzaine de pièces après des gaffes mutuelles ne sont pas toutes répertoriées.

Un humain peut-il battre Chinook de nos jours ?

Face à une version complète de Chinook dotée de son livre d’ouvertures et de sa base de finales à 10 pièces, aucun humain ne peut s’imposer. Puisque le jeu est une nulle théorique démontrée, la machine ne perdra jamais. Si l’opposant joue avec une perfection absolue, la partie s’achève par une nulle ; à la moindre inexactitude humaine, le programme prend l’ascendant et convertit son avantage en gain forcé.

Les Noirs ont-ils l’avantage aux dames anglaises ?

Aux dames anglaises, les Noirs effectuent le premier coup. Cette initiative initiale permet de contester immédiatement les cases centrales, mais la preuve de Schaeffer a établi que cet avantage ne suffit pas à forcer la victoire face à une défense rigoureuse^[1]. Avec un jeu parfait de part et d’autre, l’initiative s’épuise et la partie se conclut par la nulle.

Sources

1. Schaeffer, J., Burch, N., Björnsson, Y., Kishimoto, A., Müller, M., Lake, R., Lu, P., & Sutphen, S. (2007). Checkers Is Solved. Science, 317(5844), 1518–1522.
2. Allis, L. V. (1994). Searching for Solutions in Games and Artificial Intelligence. Ph.D. thesis, University of Limburg, Maastricht.
3. Boardgammon. “Checkers Rules: How to Play, Movement, and Captures.”
4. Shannon, C. E. (1950). Programming a Computer for Playing Chess. Philosophical Magazine, Ser. 7, 41(314), 256–275.
5. Boardgammon. “Checkers Crown: Play Online Checkers and Regional Draughts Variants.”
6. Boardgammon. “Play Checkers Online: Free Browser and Mobile Draughts.”
7. Boardgammon. “Checkers Variants: The Kinds of Draughts Played Around the World.”

Vous avez repéré une erreur ou une tournure bizarre ? Écrivez-nous