Cram, jeu de dominos : comment les nimbers révèlent l’issue

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente. Imaginez un instant, juste un instant, que poser des dominos sur une table de manière totalement chaotique, ça soit exactement la même chose, mathématiquement parlant en tout cas, que de retirer une simple petite allumette d'un tas.

Intervenant 20:17

Ouais, et ça paraît complètement absurde dit comme ça.

Intervenant 10:20

C'est clair. Mais aujourd'hui, on plonge dans une analyse vraiment fascinante qui démontre très exactement cela. L'objectif, il est vertigineux. On va explorer le monde impitoyable des jeux de stratégie pure et on va le faire en les regardant à travers le prisme de la rigueur mathématique.

Intervenant 20:36

Tout à fait. Et pour ceux qui nous écoutent, on a des sources solides pour ça.

Intervenant 10:40

Oui, absolument. Nos sources pour cette exploration, c'est une analyse ultra détaillée des mathématiques derrière le célèbre jeu des allumettes, couplée à une étude approfondie d'un jeu de placement de dominos qu'on appelle le jeu de cram.

Intervenant 20:54

Et c'est un terrain de jeu intellectuel absolument extraordinaire, parce que derrière ce qui ressemble à de simples petits passe-temps du dimanche, se cachent en réalité des structures logiques d'une pureté absolue. C'est

Intervenant 11:04

ça, on est loin du

Intervenant 21:06

Monopoly là. Ah oui, très loin. Dans les jeux que nous analysons aujourd'hui, il n'y a pas la moindre place pour le hasard. Aucun dé à lancer, pas de carte à piocher, aucune information cachée quoi. Ouais,

Intervenant 11:16

donc tout est sur la table.

Intervenant 21:17

C'est ça, juste de la stratégie pure. C'est ce qu'on appelle en mathématiques des jeux à information parfaite.

Intervenant 11:23

C'est vraiment ce qui rend la chose si captivante, l'idée que sous le désordre apparent d'un plateau de jeu super complexe se cache une équation implacable. Mais bon, pour comprendre comment on peut réduire un placement de dominos en deux dimensions à une simple ligne d'allumettes, il faut d'abord poser des bases solides.

Intervenant 21:41

Bien sûr, il faut comprendre la mécanique de base, le moteur de tout ça.

Intervenant 11:44

Exactement, d'où la nécessité de se pencher sur un classique intemporel de la théorie des jeux, le jeu de Nîmes. Et plus spécifiquement, sa variante la plus célèbre, le jeu de Mariambad.

Intervenant 21:55

Absolument, le jeu de Nîmes puise ses racines dans une histoire super ancienne. Mais cette variante précise, le Mariambad, a connu une popularité fulgurante. C'était en 1961, grâce aux films d'Alain Resney et Alain Robrier.

Intervenant 12:08

Ah oui, le fameux « l'année dernière » à Marianne Badd.

Intervenant 22:11

C'est ça ! Et les règles de ce jeu, elles sont d'une simplicité trompeuse. En gros, on dispose plusieurs lignes d'allumettes sur une table. Et à tour de rôle, un joueur choisit une seule de ces lignes et il retire le nombre d'allumettes qu'il veut.

Intervenant 12:26

Il y a une limite ou pas ?

Intervenant 22:28

La seule contrainte, c'est d'en retirer au moins une. Mais sinon, on peut même vider la ligne entière si on a envie.

Intervenant 12:34

D'accord. Et comment on gagne ?

Intervenant 22:36

Le but ultime, c'est d'être la dernière personne à pouvoir jouer.

Intervenant 12:39

Donc, le dernier joueur qui ramasse la ou les dernières allumettes remporte la partie. C'est tout bête.

Intervenant 22:45

En apparence, oui.

Intervenant 12:46

Mais quand on observe des joueurs autour d'une table avec ce jeu, on ressent un truc, une tension psychologique palpable, genre des bluffs, des regards assassins. Mais j'imagine que l'approche mathématique, elle balaye tout ça d'un revers de la main, non ?

Intervenant 22:59

Ah mais totalement ! L'aspect psychologique, ça n'aide prise que sur les novices en fait. En théorie des jeux combinatoires, on s'appuie sur un principe fondamental. Chaque état du jeu, c'est-à-dire chaque configuration précise d'allumettes restantes sur la table à un instant T, cet état y possède une nature intrinsèque.

Intervenant 13:17

C'est-à-dire ?

Intervenant 23:18

C'est-à-dire qu'un état est mathématiquement soit gagnant, soit perdant pour la personne dont c'est le tour de jouer.

Intervenant 13:24

D'accord, décortiquons un peu tout ça parce que c'est fort comme concept. Ça veut dire que si je m'assois à la table, peu importe ce que je ressens ou ce que je pense faire, la configuration des allumettes devant moi, elle a déjà scellé mon destin.

Intervenant 23:36

Ouais, c'est exactement ça.

Intervenant 13:38

Genre, si c'est un état perdant et que mon adversaire joue de manière optimale, je ne peux absolument rien faire pour échapper à la défaite.

Intervenant 23:45

Rien du tout. C'est inéluctable. C'est l'idée, oui. Mais la question centrale, la vraie question, c'est de savoir comment on identifie cette nature.

Intervenant 13:54

Ouais, comment on sait si on a la victoire entre les mains, quoi.

Intervenant 23:57

Voilà. Et la méthode pour résoudre ce jeu de Marianne Badd, elle a été formulée en 1901 par le mathématicien américain Charles Leonard Bouton. Son coup de génie, ça a été d'utiliser la décomposition binaire.

Intervenant 14:10

Du binaire, comme en informatique, etc. ?

Intervenant 24:13

Exactement. Il a utilisé ça avec une opération bien précise, la somme exclusive, qu'il a joliment baptisée la somme sans retenue.

Intervenant 14:20

Et c'est là que l'analyse devient vraiment brillante. Parce qu'au lieu de regarder le jeu comme un sculpteur regarderait du bois, avec les formes et tout, Bouton, il le regarde comme un informaticien regarde des données.

Intervenant 24:32

C'est une super façon de le dire.

Intervenant 14:34

C'est comme s'il mettait des lunettes à rayons X. Prenons un exemple précis de nos sources. Imaginons qu'il reste trois lignes sur la table. Une ligne de 1 allumette, une ligne de 3 allumettes et une ligne de 4 allumettes.

Intervenant 24:48

Ok, on visualise bien.

Intervenant 14:49

Étant donné que le public de Tangente maîtrise parfaitement la base 2, on peut directement convertir ça. Le 1, ça reste 1. Le 3, en binaire, ça s'écrit 11. Et le 4, il s'écrit 100. On a donc nos trois nombres binaires 1, 11 et 100.

Intervenant 25:05

Exactement. Et c'est ici qu'intervient l'opération clé de bouton. L'addition sans retenue. On la note souvent avec le symbole « plus » entouré d'un cercle en mathématiques, le fameux XOR de la logique.

Intervenant 15:16

Et comment on fait cette addition concrètement ?

Intervenant 25:19

On va additionner ces nombres binaires colonne par colonne, comme à l'école. Mais on s'interdit formellement de reporter la moindre retenue sur la colonne suivante. D'accord,

Intervenant 15:26

aucune retenue.

Intervenant 25:28

Voilà. Concrètement, si une colonne contient un nombre pair de 1, le résultat de cette colonne est 0. Et si elle contient un nombre impair de 1, le résultat est 1.

Intervenant 15:38

Ah, c'est presque trop simple. Faisons le calcul de tête, du coup, pour notre état 1, 3, 4.

Intervenant 25:44

Vas-y.

Intervenant 15:44

Donc, on a lignes 1, 11 et 100. Pour la colonne de droite, celle des unités, on a un 1, un autre 1 et un 0. Ça fait deux fois le chiffre 1, c'est pair, donc on pose 0.

Intervenant 25:57

C'est ça.

Intervenant 15:58

Ensuite, pour la colonne du milieu, celle des deux N. On a un 1 dans le nombre 11, et c'est trou. C'est impair, donc on pose 1.

Intervenant 26:06

Toujours bon.

Intervenant 16:06

Et enfin, pour la colonne de gauche, la colonne des quatre N, on a seulement le 1 du nombre 100, on pose 1. Donc, le résultat final de cette somme sans retenue, c'est 110 en binaire.

Intervenant 26:19

Parfait. Ton calcul est nickel. Et puisque ce résultat final, 110, est différent de 0, le théorème de bouton est formel.

Intervenant 16:27

Il dit quoi ?

Intervenant 26:28

Il dit que l'état 1, 3, 4 est un état gagnant. Le joueur qui doit jouer à cet instant précis peut forcer la victoire. C'est garanti.

Intervenant 16:37

Mais alors, quel est le mécanisme sous-jacent derrière ça ? Par quelle magie le fait de ramener cette somme abstraite à zéro permet-il de gagner concrètement sur la table avec de vraies allumettes ?

Intervenant 26:51

Ce n'est pas de la magie en fait. C'est un piège mathématique inéluctable qui est basé sur la notion de clôture.

Intervenant 16:57

De clôture ?

Intervenant 26:58

Oui. Le but de la stratégie optimale, c'est de toujours, toujours donner à l'adversaire un plateau dont la somme sans retenue est nulle.

Intervenant 17:05

Ok, mais pourquoi ça marche si bien ?

Intervenant 27:08

Parce que les mathématiques dictent que toute modification, je dis bien toute modification, apportée à un état dont la somme est zéro, va nécessairement rompre cet

Intervenant 17:17

équilibre.

Intervenant 27:19

Si on enlève que Zélui-Mepa est un état nul, on crée obligatoirement un état dont la somme est non nulle. Du coup, l'adversaire, il est forcé de recevoir un état déséquilibré.

Intervenant 17:27

Ouais, c'est super vicieux. Et à l'inverse, si moi je suis face à un état non nul, comme notre fameux 11-0 de tout à l'heure.

Intervenant 27:37

Eh bien, il existe toujours, toujours au moins un coup possible qui permet de rétablir l'équilibre et donc de ramener la somme exacte à zéro.

Intervenant 17:44

C'est une tenaille en fait.

Intervenant 27:45

C'est exactement le mot. Depuis un état zéro, on ne peut aller que vers un état non zéro. Et depuis un état non zéro, on peut toujours retourner à un état zéro.

Intervenant 17:53

D'accord. Donc si je comprends bien l'analogie, c'est un peu comme maintenir en équilibre une balance extrêmement complexe.

Intervenant 27:59

Ouais, j'aime bien cette image.