Les échecs ont une réponse, mais personne ne la connaît

Théorie des jeux, partie 2 sur 9

Le 24 novembre, à Cologny, aux portes de Genève, Gukesh et Javokhir Sindarov joueront la première partie de leur match pour le titre mondial. Tous deux se préparent depuis des mois, avec des équipes de secondants et les logiciels d’échecs les plus puissants. Et pourtant, aucun des deux ne connaît la réponse à la question la plus simple sur les échecs : qui gagne si les deux camps jouent parfaitement ?

Le plus étrange, c’est que des mathématiciens ont montré il y a plus d’un siècle que cette réponse existe. Elle est aussi fixée que le résultat de 2 + 2. Simplement, personne ne l’a jamais vue.

Ce qu’a montré Zermelo

Dans le premier volet de la série, nous avons résolu le jeu des allumettes en raisonnant de la fin vers le début. Dans un article de 1913, le mathématicien allemand Ernst Zermelo — surtout connu aujourd’hui pour ses travaux en théorie des ensembles — a appliqué un raisonnement semblable aux échecs.

Les échecs sont un jeu à deux joueurs, à information parfaite, sans aucun hasard. Le nombre de positions est fini, et les règles empêchent une partie de durer éternellement. Pour de tels jeux, une seule de ces trois affirmations est vraie :

1. Les Blancs peuvent forcer le gain, quelle que soit la défense des Noirs.
2. Les Noirs peuvent forcer le gain, quel que soit le jeu des Blancs.
3. Chaque camp peut s’assurer au moins la nulle.

Voilà « la réponse des échecs ». Laquelle des trois est la bonne, personne ne le sait.

Une petite note historique. Zermelo s’est en réalité posé une question plus étroite que celle qu’on lui prête d’habitude : un joueur en position gagnante peut-il forcer le gain, et en combien de coups ? L’énoncé familier des trois possibilités, ainsi que l’induction à rebours formulée explicitement, sont venus plus tard, dans les travaux des mathématiciens hongrois Dénes Kőnig (1927) et László Kalmár (1928). Les historiens de la théorie des jeux Ulrich Schwalbe et Paul Walker ont démêlé cette confusion en détail. Le « théorème de Zermelo » est donc plutôt l’œuvre de plusieurs personnes, baptisée du nom de la première.

Trois niveaux de « résolu »

Quand on dit qu’un jeu est « résolu », on peut vouloir dire trois choses :

• résolu ultra-faiblement : on sait comment la partie se termine avec un jeu parfait, mais pas comment y parvenir ;
• résolu faiblement : on connaît le résultat et une stratégie qui l’assure depuis la position initiale ;
• résolu fortement : on connaît le bon coup dans toute position qui peut se présenter.

Le jeu des allumettes du premier volet est résolu fortement : nous avons une règle pour n’importe quel nombre d’allumettes. Voici où en sont quelques vrais jeux :

Attention à la formulation pour les dames. Le résultat porte sur une variante précise : les pions n’avancent que vers l’avant, la dame se déplace d’une seule case dans n’importe quelle diagonale, et la prise est obligatoire. Il ne s’applique pas aux dames internationales sur 10×10 — celles que l’on joue en France, en Belgique ou aux Pays-Bas. Celles-là ne sont pas résolues.

Les dames : dix-huit ans de calcul

L’équipe de Jonathan Schaeffer, à l’université de l’Alberta (Canada), a commencé le calcul en 1989. Au plus fort, en 1992, plus de 200 processeurs y travaillaient. La seule base de finales — toutes les positions à dix pièces ou moins — compte environ 39 000 milliards de positions. Au total, les dames 8×8 comptent à peu près 5 × 10²⁰ positions possibles.

En septembre 2007, la revue Science a publié le résultat : avec un jeu parfait des deux côtés, les dames se terminent par la nulle. Fait intéressant, la preuve n’a pas exigé d’examiner toutes les positions. Il a suffi de montrer qu’aucun camp ne peut s’écarter avec profit des lignes menant à la nulle.

Pourquoi on ne peut pas calculer les échecs de la même façon

En 1950, Claude Shannon, fondateur de la théorie de l’information, a estimé le nombre de positions possibles aux échecs à environ 10⁴³, et celui des parties possibles à environ 10¹²⁰. Il a calculé qu’une machine examinant une variante par microseconde aurait besoin de plus de 10⁹⁰ ans pour choisir son premier coup.

Une estimation plus récente de John Tromp est encore plus élevée : environ 4,8 × 10⁴⁴ positions légales. Les dames, en comparaison, en comptent environ 5 × 10²⁰. Les échecs ne sont donc pas « deux fois plus difficiles » que les dames : l’écart est de l’ordre d’un million de milliards de milliards.

Les mathématiciens ne disent pas que résoudre les échecs est impossible. Comme pour les dames, prouver un gain ou une nulle n’exigerait pas d’examiner chaque position. Mais Jonathan Schaeffer, qui a dirigé la preuve pour les dames, a lui-même estimé qu’il faudrait une rupture technologique, comme l’informatique quantique, avant même de pouvoir s’attaquer aux échecs.

Là où la réponse est déjà connue

Il existe une partie des échecs où la réponse a été trouvée entièrement : les finales. Les ordinateurs ont calculé toutes les positions comptant jusqu’à sept pièces sur l’échiquier, rois compris. Ces tables — on parle de tablebases — connaissent le résultat exact de chaque position et le chemin le plus court pour y parvenir. Certains de ces gains durent plus de cinq cents coups, et aucun humain ne saurait en expliquer la logique.

Voyons ce que disent les tables d’une des études les plus célèbres de l’histoire des échecs.

La position de Saavedra

Blancs : roi b6, pion c6. Noirs : roi a1, tour d5. Les Blancs jouent.

FEN : 8/8/1KP5/3r4/8/8/8/k7 w - - 0 1

L’histoire commence en 1895, dans la rubrique d’échecs du Glasgow Weekly Citizen. Son responsable, Barbier, publie une position proche de celle-ci et pense qu’avec un bon jeu des Noirs, elle est nulle. La solution qui a rendu l’étude célèbre a été trouvée par un lecteur : Fernando Saavedra, un prêtre espagnol qui vivait à Glasgow.

Ce que presque tout le monde voit. Le pion est à un pas de la promotion. La tour noire donne des échecs, et le roi blanc les fuit. Le plan naturel : échapper aux échecs et faire une dame.

1.c7 Td6+ 2.Rb5 Td5+ 3.Rb4 Td4+ 4.Rb3 Td3+ 5.Rc2 Td4 !

Les Noirs ne peuvent plus donner échec, mais ils jouent avec ruse. 6.c8=D semble maintenant gagner facilement. Pourtant, après 6...Tc4+ ! 7.Dxc4, le roi noir n’a plus aucun coup légal. C’est le pat : partie nulle. Les Blancs ne peuvent pas non plus refuser la prise : après n’importe quelle retraite du roi, les Noirs prennent la dame par ...Txc8, et ce sont eux qui jouent alors pour le gain.

Ce qu’on rate. 6.c8=T !! Une tour ne pate pas, car elle ne contrôle pas la diagonale dont le roi noir a besoin. Les Blancs menacent un échec depuis a8, après lequel plus rien ne sauve les Noirs. La défense la plus tenace est 6...Ta4 (seul 6...Td2+ tient aussi longtemps), et alors 7.Rb3 ! Les Blancs menacent à la fois de prendre la tour a4 et de mater par Tc1. Les Noirs ne peuvent pas parer les deux.

Ce que les tables ont ajouté. La tablebase confirme l’essentiel : 1.c7 est le seul premier coup gagnant, et 6.c8=D ne fait vraiment que nulle. Mais elle montre aussi quelque chose que l’analyse classique ne fait pas voir. Au sixième coup, 6.c8=T n’est pas le seul à gagner : 6.Rb3 et 6.Rc3 gagnent aussi. Le chemin vers le mat y est environ trois fois plus long, et bien moins élégant. La sous-promotion est le gain le plus court, pas le seul.

Ce que cela signifie pour le joueur

Une tablebase ne pense pas en coups « beaux » ou « mauvais ». Elle pense en trois catégories : gain, nulle, perte. Tout coup qui conserve la catégorie est, en un sens, correct. 6.Rb3 est correct. 6.c8=D est une erreur, même si c’est le coup le plus naturel sur l’échiquier : il transforme un gain en nulle.

D’où un principe pratique. Avant un coup qui paraît évident, mieux vaut se demander non pas « est-ce le meilleur coup ? », mais « est-ce qu’il change le résultat ? ». Pat, échec perpétuel, pion perdu : c’est ainsi que des positions gagnées deviennent nulles.

Ce principe a pourtant une limite. En milieu de partie, personne ne sait dans quelle catégorie se trouve la position : il n’existe pas de tables pour 32 pièces, et il n’y en aura pas dans un avenir prévisible. Là, joueurs et logiciels doivent évaluer la position de façon approchée et chercher le coup le meilleur face à la réponse la plus forte de l’adversaire. Cette idée — le minimax — fera l’objet du prochain volet de la série.

Et le match de Genève est intéressant justement parce que Gukesh et Sindarov ne jouent pas parfaitement. Ils jouent à un jeu dont personne ne connaît la réponse.

Exercice

1. Dans la position après 6.c8=T Ta4, trouvez le coup gagnant des Blancs et expliquez pourquoi il gagne.
2. Pourquoi, après 6.c8=D Tc4+, les Blancs sont-ils obligés de prendre la tour, alors que c’est pat ?
3. À quel niveau de « résolu » appartient pierre-feuille-ciseaux, vu dans le premier volet ? Peut-on même dire qui gagne avec un jeu parfait ?

Réponses à la fin de l’article.

Questions pour la discussion

• Si l’on annonçait demain que les échecs sont nuls avec un jeu parfait, cela changerait-il quelque chose à votre rapport au jeu ?
• Qu’est-ce qui est le plus utile pour apprendre : connaître le coup parfait grâce à une table, ou comprendre pourquoi un coup fonctionne, même s’il existe des coups plus rapides ?
• Saavedra a trouvé un coup que l’auteur de l’étude avait manqué. Vous est-il arrivé de voir une solution qui avait échappé à des personnes plus expérimentées ?

Prochainement dans la série : « Le minimax : comment pense un adversaire qui vous veut le pire », sur le théorème de von Neumann et la façon dont « pensent » les logiciels d’échecs.

Réponses. 1) 7.Rb3 ! — selon la tablebase, le seul coup gagnant. Les Blancs attaquent la tour a4 et menacent en même temps de mater par Tc1. 2) Après n’importe quelle retraite du roi, les Noirs prennent la dame par ...Txc8 et se retrouvent avec une tour contre un roi seul. 3) Les coups sont simultanés, il n’y a donc pas un seul « bon coup ». La stratégie parfaite consiste à choisir chaque option au hasard avec une probabilité de 1/3. Ainsi, en moyenne, personne ne gagne, quel que soit le jeu de l’adversaire. Ces stratégies mixtes auront leur propre article dans la série.