Jeu de Cram : pourquoi une somme nulle fait-elle perdre ?

Intervenant 10:00

Bienvenue à l'écoute de cette nouvelle exploration sur le podcast du magazine Tangente. Bonjour

Intervenant 20:04

tout le monde.

Intervenant 10:06

Aujourd'hui, on va parler d'un truc un peu fou. Imaginons un instant que, sous le chaos apparent d'un jeu de stratégie, sous les millions de combinaisons possibles, il y a en fait un code source unique, un moteur invisible complètement implacable qui décide de la victoire ou de la défaite. Et ça, avant même qu'on ait joué le premier coup.

Intervenant 20:27

C'est exactement ça et c'est ce que révèle le document mathématique qu'on va décortiquer aujourd'hui.

Intervenant 10:32

Notre mission du jour, pour ceux qui aiment creuser, c'est de plonger dans une démonstration pure et dure. Une preuve qui relie deux univers qui, sur nos papiers, n'ont rien à voir. Le jeu de Cram et le célèbre jeu de Marianne Bade.

Intervenant 20:44

Et l'objectif ici, c'est vraiment de relever un gros défi. Vulgariser cette preuve mathématique, en extraire toutes les sens, mais sans rien sacrifier à la rigueur de l'auteur.

Intervenant 10:55

Donc on ne va pas se simplifier à outrance.

Intervenant 20:57

Non, surtout pas. Le texte montre comment les maths plient la stratégie à leur volonté. On va parler de concepts géniaux comme les NIMS, les sommes binaires ou la fonction du minimum exclu.

Intervenant 11:09

Rien que les noms, ça donne envie.

Intervenant 21:10

N'est-ce pas ? Et surtout, on va voir comment tous ces outils prouvent qu'à un niveau très profond, certains jeux ne sont que des illusions d'optique.

Intervenant 11:19

Avant de plonger dans les équations et les symboles bizarres, il faut quand même poser le décor, histoire de bien comprendre ce que l'auteur veut prouver.

Intervenant 21:26

C'est indispensable, ouais.

Intervenant 11:27

Donc, d'un côté, on a le jeu de Crom. Pour faire simple, c'est un jeu sur une grille, genre un damier.

Intervenant 21:33

D'accord.

Intervenant 11:34

Deux joueurs posent tour à tour des dominos, qui recouvrent deux cases adjacentes. Et dès qu'un joueur ne peut plus poser de domino, hop, il a perdu.

Intervenant 21:42

C'est la règle classique des jeux impartiaux.

Intervenant 11:45

Exactement. Et de l'autre côté, il y a Mariannebad, qu'on appelle aussi le jeu de Nîmes. Là, on a des tas d'allumettes ou des rangées. Chaque joueur peut retirer autant d'allumettes qu'il veut, mais sur une seule rangée à la fois.

Intervenant 21:57

Et le dernier qui peut jouer gagne, là aussi.

Intervenant 11:59

Voilà. Visuellement, ça n'a aucun rapport. Et pourtant, l'énoncé de base de notre document dit qu'un état spécifique du cram, un état qu'on appelle Q, il est strictement équivalent à un état de Mariannebad.

Intervenant 22:11

Oui, c'est ce qu'on appelle un isomorphisme. Et le texte ne fait pas juste une analogie poétique. Il affirme qu'un plateau de crâme, avec ses espaces vides, se traduit littéralement par des lignes d'allumettes virtuelles.

Intervenant 12:23

C'est fou ! Les composantes connexes du plateau de crâme, donc les petits îlots de cases vides, ça deviennent les rangées de Marianne Badd.

Intervenant 22:32

Exactement. On appelle ça Q1-10i dans la démonstration.

Intervenant 12:36

Si on fait une analogie avec les jeux vidéo, c'est comme si on découvrait que deux jeux hyper différents, disons un simulateur de vol 3D et un jeu de réflexion en 2D, tournent sur le même moteur physique.

Intervenant 22:47

C'est une très bonne façon de le voir.

Intervenant 12:49

Les pixels changent, la manette est différente, mais l'algorithme des collisions derrière, c'est exactement le même.

Intervenant 22:55

Et la magie du texte, c'est qu'il donne la formule de ce moteur. L'auteur explique que l'équivalence est régie par une somme globale des valeurs de chaque kilo.

Intervenant 13:04

Et la condition de défaite, c'est ça qui est dingue, c'est que l'état Q est perdant si, et seulement si, cette fameuse somme est égale à zéro.

Intervenant 23:12

Toute la démonstration repose là-dessus. Prouver que ce zéro est inviolable. Mais attention, l'auteur n'utilise pas une addition classique.

Intervenant 13:20

Oui, c'est là qu'on rentre dans le dur. Dans la formule, il y a ce symbole étrange, un plus, entouré d'un cercle.

Intervenant 23:27

Voilà, c'est la somme binaire sans retenue, le fameux symbole de la formule NIM de Q1, plus encerclé, jusqu'à NIM de Qp.

Intervenant 13:36

C'est le, ou exclusif, le XOR que les informaticiens connaissent bien.

Intervenant 23:40

Tout à fait.