Jeu de la dame : quelles cases font perdre si l’autre joue bien ?

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente. Aujourd'hui, on va imaginer un truc. Une partie d'échec un peu, ben, un peu cauchemardesque.

Intervenant 20:11

Oh carrément cauchemardesque,

Intervenant 10:13

ouais. Genre une partie où peu importe l'intelligence qu'on y met, peu importe la stratégie, chaque mouvement sur le plateau nous fait qu'accélérer notre propre chute.

Intervenant 20:21

C'est un peu le pitch d'un film d'horreur.

Intervenant 10:24

C'est l'essence même de notre exploration d'aujourd'hui en fait. On plonge dans un article fascinant qui s'appelle « Une stratégie pour bouger la dame ». Et l'objectif c'est vraiment de partir d'un tout petit jeu de plateau avec des règles qui ont l'air hyper enfantines pour s'enfoncer direct dans le rouage super complexe de la théorie des jeux.

Intervenant 20:42

Et le plus beau là-dedans, c'est qu'on va pas juste effleurer le sujet. L'idée de cette plongée, c'est vraiment de décortiquer la mécanique interne. On part d'une simple grille pour atterrir, contre toute attente, sur un des nombres les plus mythiques de toute l'histoire des maths.

Intervenant 10:59

Ouais, on promet des « aha moments » en cascade. Le but, c'est de comprendre pourquoi les choses fonctionnent sans jamais se noyer dans le jargon.

Intervenant 21:07

Exactement. Zéro jargon, juste de la logique pure.

Intervenant 11:10

Du coup, plantons le décor. Le matériel qu'il faut, c'est basique. On prend un grand damier ou un échiquier qu'on oriente de façon très classique. Un haut, un bas, une gauche, une brette. Et sur ce grand damier, on ne pose qu'une seule et unique pièce. Une dame.

Intervenant 21:26

Une seule dame, oui.

Intervenant 11:27

Voilà. Deux adversaires s'affrontent et c'est tout. Un plateau, une pièce et une tension qui monte,

Intervenant 21:33

mais alors très très vite. Et cette tension, il faut bien comprendre qu'elle vient direct des règles de déplacement. Parce qu'elles sont hyper contraignantes. À tour de rôle, on a le droit de bouger cette dame du nombre de cases qu'on veut. Ce qui ressemble aux échecs classiques pour le coup. Oui, jusque-là ça va. Sauf qu'il y a une restriction monumentale. La dame, elle peut glisser que dans trois directions. C'est soit vers la gauche, soit vers le bas, soit en diagonale vers le bas gauche. C'est tout. C'est la seule liberté.

Intervenant 12:04

Donc aucun retour en arrière ?

Intervenant 22:05

Aucun. Tu ne peux pas monter, tu ne peux pas aller à droite. C'est interdit.

Intervenant 12:09

C'est vraiment ça qui crée cette ambiance hyper oppressante. Moi, ça me fait penser à une dystopie urbaine. Tu sais, imaginons une ville où absolument toutes les rues seraient des sens uniques.

Intervenant 22:18

Ah ouais ? L'enfer des automobilistes ?

Intervenant 12:20

C'est ça. Et toutes ces rues, sans aucune exception, finiraient par converger vers une seule et même impasse, tout au sud-ouest de la ville. Du coup, au volant, chaque carrefour te rapproche du mur.

Intervenant 22:32

Tu peux pas faire demi-tour ?

Intervenant 12:33

Impossible de fuir. Tu peux juste choisir par quelle rue tu vas précipiter l'autre personne dans le cul de sac.

Intervenant 22:39

C'est une super métaphore. Et ce cul de sac, sur notre échiquier, c'est le coin tout en bas à gauche. Celui ou celle qui se retrouve obligé de jouer, mais qui ne peut plus bouger parce que la dame est coincée dans ce fameux coin, a perdu. Fin de la partie.

Intervenant 12:51

C'est radical.

Intervenant 22:52

Très radical. Et sur le plan mathématique, ton histoire de ville à sens unique, ça illustre parfaitement ce qu'on appelle un jeu fini sans partie nulle.

Intervenant 13:00

Fini parce qu'on ne peut pas tourner en rond, c'est ça ?

Intervenant 23:02

Vu qu'il y a un nombre limité de cases avant le mur, la fin va forcément arriver. Tout à fait. Et sans partie nulle. Parce qu'on ne peut pas bloquer la partie indéfiniment. Il n'y a pas de match nul possible ici.

Intervenant 13:12

À chaque mouvement, l'espace se rétrécit, les options fondent. C'est une certitude géométrique en fait.

Intervenant 23:18

Voilà. Et curieusement, c'est justement cette impossibilité totale de reculer qui rend l'analyse possible. Quand tu peux aller que dans une seule direction générale, la stratégie c'est plus de l'esquive ou du bluff tu vois, c'est du calcul pur.

Intervenant 13:31

Ce qui veut dire, si je suis bien la logique, qu'il doit forcément exister une méthode infaillible pour gagner. Puisqu'on ne peut pas bluffer, la victoire est écrite quelque part sur le plateau, non ?

Intervenant 23:39

Elle est littéralement gravée dessus. Et pour la lire, il faut adopter la posture classique des maths face à ce genre de problème fini. On part de la fin, du moment où c'est terminé, et on rembobine.

Intervenant 13:49

Ok, on fait le chemin à l'envers.

Intervenant 23:50

C'est ça. Essayons de visualiser. Le fameux coin en bas à gauche, c'est l'abîme. C'est la case fatale. Mentalement, on peut y peindre une énorme croix rouge. Bam ! Défaite garantie.

Intervenant 14:03

D'accord. Donc logiquement, si c'est à moi de jouer et que la dame est posée n'importe où sur la ligne tout en bas, j'ai juste à la faire glisser tout droit vers la gauche jusqu'au coin. Et boum, l'autre a perdu.

Intervenant 24:14

Exact. Même chose si elle est sur la colonne tout à gauche. Tu la descends d'un coup.

Intervenant 14:18

Et pareil pour la grande diagonale alors ?

Intervenant 24:20

C'est vraiment comme un faisceau laser, un cône de danger qui partirait du coin.

Intervenant 14:24

Tu as tout compris. Toutes les cases qui sont sur cette ligne du bas, sur cette colonne de gauche et sur cette grande diagonale directe, on va y dessiner des ronds verts. Ce sont des zones de tir dégagées.

Intervenant 24:35

Des pistes d'atterrissage vers la victoire. Voilà. Depuis n'importe quel rond vert, en un seul petit glissement, tu expédies la dame sur la croix rouge et tu gagnes instantanément.

Intervenant 14:46

Ok, donc un rond vert, c'est une case où je veux être juste avant de jouer. Mais attends, une seconde.

Intervenant 24:53

Quoi ? Un problème ?

Intervenant 14:54

Si c'est à moi de jouer et que je décide de placer la dame sur un rond vert, ça veut dire que pour le tour suivant, c'est à l'autre personne de jouer depuis ce rond vert.

Intervenant 25:03

Ah, très juste. Le piège se referme.

Intervenant 15:06

Bah oui, c'est le piège mental. Si je pose la dame sur un rond vert, c'est mon adversaire qui a la voie libre, vers le coin en bas à gauche. Donc ma stratégie, ça ne doit surtout pas être de m'arrêter sur un rond vert. Ma stratégie, c'est d'obliger l'autre à commencer son tour sur une case toxique.

Intervenant 25:22

C'est la bascule conceptuelle qu'il fallait faire. Bravo. En fait, on cherche les positions perdantes pour la personne qui débute son tour. Notre coin inférieur gauche, c'est notre croix rouge ultime, notre point zéro.

Intervenant 15:35

Ok.

Intervenant 25:36

Les ronds verts, ce sont les tremplins directs vers cette croix rouge. Donc, l'étape logique d'après, c'est de trouver les cases qui ne mènent nulle part ailleurs qu'un rond vert.

Intervenant 15:46

Attends, comment on évite le paradoxe de l'œuf et de la poule ? Parce que j'entends la définition. Une croix rouge, c'est une case dont toutes les issues mènent à un rond vert. Mais un rond vert, c'est une case qui a au moins un accès vers une croix rouge. La logique, elle se mord carrément la queue, non ?

Intervenant 26:03

Ça en a tout l'air, je te l'accorde. Mais c'est là qu'intervient la magie de la récurrence. L'onde de choc, elle progresse étape par étape depuis un point d'ancrage absolu.

Intervenant 16:12

Le point zéro,

Intervenant 26:13

le coin en bas à gauche. Exactement. On part de notre première croix rouge. On a coloré la ligne, la colonne et la diagonale qui en partent en vert. Notre plateau, il est déjà partiellement rempli. Maintenant, cherchons la toute première case, la plus proche du coin, qui n'est pas encore coloriée.

Intervenant 16:29

Ok, laisse-moi visualiser le truc. La ligne du bas est verte, la colonne de gauche est verte, la diagonale est verte. Donc la première case vierge, elle serait située juste un cran au-dessus de la ligne du bas et un cran à droite de la colonne de gauche.

Intervenant 26:45

Soit la case de coordonnées de 2 si on compte à partir du coin. Regarde ces options de mouvement. Si la dame est là et que tu la bouges vers la gauche, tu tombes sur la colonne

Intervenant 16:54

verte.

Intervenant 26:55

Si je la bouge vers le bas, je tombe sur la ligne verte.

Intervenant 16:58

Et si tu la bouges en diagonale vers le bas gauche, j'atterris direct sur la diagonale verte. Quoi que je fasse, je glisse sur du vert.

Intervenant 27:05

Et voilà, c'est une nouvelle croix rouge, un nouveau piège mortel. Celui ou celle qui commence son tour sur cette case est littéralement condamné à offrir un rond vert à son adversaire.

Intervenant 17:16

C'est comme une espèce de pierre de guet isolée au milieu d'une rizière hyper dangereuse.

Intervenant 27:21

C'est très poétique et c'est tout à fait ça. Et l'onde de choc continue. À partir de cette deuxième croix rouge, on trace à nouveau un faisceau de rond vert. Sur sa gauche, vers son bas et sur sa diagonale.

Intervenant 17:34

On vient de verrouiller de nouvelles lignes de tir en fait. C'est ça. Et on

Intervenant 27:36

recommence. On cherche la prochaine case vierge la plus proche. Elle devient notre troisième croix rouge. Et ainsi de

Intervenant 17:44

suite. En construisant le maillage comme ça, on se rend compte d'un truc géométrique assez fou quand même. Puisqu'à chaque fois qu'on pose une croix rouge, on colorie en vert tout ce qui se trouve sur sa ligne, sa colonne et sa diagonale.

Intervenant 27:56

Oui.

Intervenant 17:56

Ça veut dire qu'il est physiquement impossible de trouver deux croix rouges sur la même ligne horizontale ou sur la même colonne verticale.

Intervenant 28:03

C'est d'une pureté absolue, oui. Le motif des croix-rouilles, ces zones de défaite inévitables, ils se dispersent sur le plateau de manière très spécifique, sans jamais, au grand jamais, se chevaucher sur les axes de mouvement.

Intervenant 18:15

C'est fascinant, donc si on arrive à placer la dame sur l'une de ces croix rouges, à la fin de notre tour, la victoire est assurée.

Intervenant 28:21

Garantie à 100%. L'adversaire va s'arracher les cheveux parce que n'importe lequel de ses dépassements l'éjectera forcément de la croix rouge et le fera atterrir sur une case verte.

Intervenant 18:30

Et à notre tour, on n'a plus qu'à replacer la dame sur la croix rouge suivante, un peu plus près du coin.

Intervenant 28:35

C'est implacable.

Intervenant 18:35

C'est littéralement une mise à mort mathématique. Tu le fais sauter de pierre en pierre jusqu'à la noyade finale. Faut

Intervenant 28:40

pas jouer avec toi,

Intervenant 18:42

t'es impitoyable. Mais ouais. Mais dis-moi, cette histoire de cases vertes et rouges, cette matrice de décision, est-ce que c'est une particularité propre à ce jeu de la dame précisément ?

Intervenant 28:51

Alors là, c'est là que l'horizon s'élargit drastiquement. Cette logique de cartographie, elle s'applique pas du tout qu'à notre petite dame sur son damier. C'est en fait l'illustration d'un monument de la théorie des jeux.

Intervenant 19:01

Oh,

Intervenant 29:02

carrément un monument ! Ah oui, le théorème de Sprague-Grundy. Il a été formulé indépendamment dans les années 30 par l'allemand Roland Percival Sprague et le britannique Patrick Michael Grundy. Et ce truc, ça fournit une méthode universelle pour décortiquer toute une galaxie de jeux.

Intervenant 19:15

Attends, quand on dit toute une galaxie, ça veut dire qu'on pourrait appliquer ça aux échecs classiques, par exemple ? Pour calculer la victoire à tous les coups ? Genre on met des millions de croix rouges sur un super ordinateur et on résout les échecs ?

Intervenant 29:29

Ah, ce serait trop beau, non ? Le théorème de Sprague Grundy, il a une frontière très stricte. Il s'applique uniquement aux jeux qu'on appelle impartiaux.

Intervenant 19:38

Si on reprend notre jeu de la dame, il y a une différence majeure avec les échecs. Aux échecs, je contrôle les pièces blanches et l'autre personne contrôle les noires. Nos options sont totalement asymétriques. Alors que dans notre jeu d'aujourd'hui, c'est la même dame pour tout le monde. Peu importe qui est en train de jouer, les options de mouvement vers le bas ou la gauche sont exactement les mêmes. Le jeu est aveugle à l'identité de la personne qui joue. C'est ça l'impartialité.

Intervenant 210:04

C'est parfaitement résumé. Un jeu impartial, c'est un jeu où l'éventail des choix ne dépend que de l'état actuel du plateau et absolument pas de la personne dont c'est le tour. Dès qu'un jeu a cette caractéristique qu'il est fini sans hasard et sans partie nulle, hop, le théorème de Sprague-Grenu entre en scène.

Intervenant 110:21

Le dossier mentionne d'autres jeux de ce type d'ailleurs. Comme le jeu de Nîmes, tu sais, avec les fameuses allumettes qu'on retire une par une. Ou alors un autre jeu mathématique super intéressant appelé Retire un carré.

Intervenant 210:32

Ah, le Retire un carré, c'est un exemple fantastique. Le principe est simple, on commence avec un nombre entier, disons 37. Et à tour d'œuvre rôle, on doit soustraire de ce nombre le carré d'un entier.

Intervenant 110:43

Le premier qui

Intervenant 210:44

tombe à zéro a perdu, c'est ça ? C'est ça.

Intervenant 110:46

Donc, à partir de 37, on pourrait soustraire 1 au carré, ce qui laisse 36, ou 2 au carré, donc on enlève 4, il reste 33. On pourrait même carrément enlever 25, vu que c'est 5 au carré, ce qui nous ferait tomber direct à 12.

Intervenant 211:01

Et face au nombre 12, la personne suivante aurait exactement les mêmes options de soustraction. C'est totalement impartial.

Intervenant 111:09

D'accord, je vois bien le lien.

Intervenant 211:10

Et ce que Sprague et Grundy ont prouvé, et c'est là que c'est brillant, c'est qu'en réalité tous ces jeux impartials, même s'ils ont l'air super différents, une dame sur un plateau, des tas d'allumettes, des soustractions, ils partagent le même ADN mathématique.

Intervenant 111:24

C'est-à-dire ?

Intervenant 211:25

Le théorème démontre que n'importe quelle position dans n'importe quel jeu impartial est rigoureusement équivalente à un tas d'allumettes dans le jeu de Nîmes.

Intervenant 111:33

Équivalente à des allumettes, ça veut dire que le théorème ne fait pas juste mettre des croix rouges et donne une sorte de valeur de danger à chaque case.

Intervenant 211:42

Mais c'est la clé de voûte du truc. On appelle ça des valeurs de Grundy, ou des Nimburs en anglais. Au lieu de juste dire gagnant ou perdant, on donne un nombre à chaque état du jeu. Notre croix rouge, la case de défaite absolue, elle a une valeur de zéro. C'est l'équivalent d'un tas d'allumettes vides.

Intervenant 111:56

Ok, c'est le vide total.

Intervenant 211:58

Voilà. Le théorème permet de calculer cette valeur pour n'importe quelle case. Et la stratégie universelle pour absolument tous ces jeux, ça se résume à une seule règle. Jouer de manière à laisser à son adversaire une configuration dont la valeur globale est zéro.

Intervenant 112:12

C'est vertigineux de penser qu'un nombre abstrait et une case de damier puisse être traduit dans la même langue mathématique, celle des allumettes quoi.

Intervenant 212:20

C'est l'unification des maths, c'est magnifique !

Intervenant 112:23

Mais du coup, si le théorème permet de résoudre notre jeu de la dame étape par étape, pourquoi notre dossier mentionne un raccourci ? Enfin, si on a la méthode des Nimburs, on a la méthode, non ? On n'a pas besoin de raccourci ?

Intervenant 212:36

On a la méthode, c'est sûr. Mais la construction récursive, tu sais, cette fameuse onde de choc pour placer nos croix rouges case après case, c'est super laborieux. Si tu veux connaître la position de la millième croix rouge, il faut avoir calculé les 999 précédentes. Ah ouais, l'enfer. Et c'est là qu'entre en scène le mathématicien néerlandais Willem Abraham Wythoff, en 1907. Bien avant que Sprague et Grundy ne généralisent tout ça, Wythoff, lui, il a étudié précisément ce jeu de la dame. Et il a cherché, et surtout il a trouvé, une équation directe de ces croix rouges. Et pour formuler les coordonnées de ces cases fatales, Wythoff a fait appel à un paramètre hyper inattendu. La formule utilise bien sûr un entier pour le numéro de la croix rouge, mais elle le multiplie par une constante.

Intervenant 113:24

Ne me dis pas que c'est...

Intervenant 213:26

Qui n'est autre que le nombre d'or.

Intervenant 113:28

Le nombre d'or, phi, 1 plus racine de 5, le tout divisé par 2, environ 1,618. Mais qu'est-ce que ce nombre vient fabriquer là-dedans ?

Intervenant 213:37

Dingue, non ?

Intervenant 113:38

Mais grave ! Je veux dire, on associe le nombre d'or à la géométrie grecque, à l'architecture du Parthénon ou à la croissance des plantes. C'est la proportion continue par excellence. Qu'est-ce qu'il fiche dans les coordonnées super rigides d'un damier en carton ?

Intervenant 213:51

C'est ce qui rend cette découverte si bouleversante en fait. Pour comprendre pourquoi le nombre d'or surgit ici de nulle part, il faut se pencher sur la mécanique de nos croix rouges. Rappelle-toi la règle fondamentale qu'on avait déduite. Pour que la stratégie marche, il ne doit jamais

Intervenant 114:06

Jamais y avoir deux croix rouges sur la même ligne ou la même colonne. Sinon les zones vertes se chevauchent et tout le système s'effondre.

Intervenant 214:12

Exactement. Donc sur un quadrillage discret fait de nombres entiers, on a besoin de générer deux séries de coordonnées, les abscisses et les ordonnées de nos croix, qui s'imbriquent avec une perfection totale. Elles doivent se répartir tous les nombres entiers, sans jamais en oublier un seul, et surtout sans jamais utiliser le même deux fois. En maths, on appelle ça des suites de Betty.

Intervenant 114:31

Ok, des suites de Betty. Et c'est dur à faire.

Intervenant 214:34

Et c'est là que le piège se referme. Si tu essaies de créer ces suites avec des nombres normaux, des fractions, des motifs réguliers, tu finis inévitablement par créer un cycle. Les nombres vont finir par se croiser sur la grille. Il y aura une collision.

Intervenant 114:48

Ah, et s'il y a collision, il y a deux croix rouges sur la même ligne.

Intervenant 214:52

Voilà. Pour éviter toute collision dans ce monde de nombres entiers, il faut introduire le chaos de l'irrationalité.

Intervenant 114:58

Ah, un nombre irrationnel. Pour ceux qui nous écoutent, c'est un nombre dont les décimales sont infinies et ne forment absolument jamais de motifs répétitifs. Comme pi, par exemple, ou racine de 2.

Intervenant 215:10

C'est tout à fait ça. En multipliant notre numéro de cases par un nombre irrationnel, on garantit que le résultat ne retombera jamais au grand jamais sur un cycle régulier. Et le nombre d'or, Φ, il a une particularité monumentale en théorie des nombres, c'est le nombre considéré comme le plus irrationnel de tous.

Intervenant 115:27

Le plus irrationnel ?

Intervenant 215:28

Ouais.

Intervenant 115:29

Il est le plus éloigné possible de n'importe quelle fraction. Et grâce à cette propriété unique, les séquences générées avec le nombre d'or s'encastrent avec une perfection absolue. Elle trie les nombres entiers en deux listes distinctes qui ne se chevauchent jamais.

Intervenant 215:46

Non mais c'est fou ! Donc, pour résoudre un problème purement discret, un jeu de quadrillage où la dame avance par à coup, la nature a besoin de l'irrationalité la plus pure de la géométrie continue. C'est d'une beauté sidérante. C'est comme si on soulevait le capot d'une petite voiture en plastique pour enfant et qu'on y trouvait un moteur de Formule 1 ultra complexe. C'est la magie de l'abstraction. Des mondes mathématiques qu'on pensait totalement cloisonnés, d'un côté la théorie des jeux discrets sur un damier, de l'autre la géométrie continue, ils entrent soudainement en résonance. Et c'est cette mécanique profonde, cette impossibilité de créer un rythme régulier avec des fractions, qui invite le nombre d'or à la table de jeu.

Intervenant 116:29

Le pari de départ est largement tenu. On est parti d'une simple contrainte de mouvement, d'une dystopie avec des rues à sens unique. On a construit mentalement notre onde de choc avec nos pièges rouges et nos lignes vertes.

Intervenant 216:40

On a découvert avec Sprague et Grundy que tout ça n'était qu'un immense genime déguisé.

Intervenant 116:45

Et on finit par contempler le nombre d'or qui orchestre le chaos des coordonnées random.

Intervenant 216:50

C'est un voyage qui prouve une fois de plus que la simplicité des règles n'empêche jamais la complexité de l'univers de s'y inviter. C'est ça qui est bon.

Intervenant 116:58

C'est clair. C'est une pensée vertigineuse à garder en tête pour tout le monde. Si un petit jeu de stratégie où l'on pousse un bout de bois sur un quadrillage dissimule en son cœur une constante aussi universelle que le nombre d'or, combien d'autres systèmes de notre quotidien, combien d'interactions qui ont l'air banales, sont en réalité dictées par des lois mathématiques titanesques qu'on n'a pas encore pris la peine de calculer ?

Intervenant 217:21

Ça laisse songeur.

Intervenant 117:23

Totalement. En tout cas, le mieux pour visualiser tout ça, c'est encore de dessiner le plateau chez soi et d'essayer de coincer quelqu'un dans le coin en bas à gauche. Merci d'avoir suivi cette plongée et à la prochaine exploration.