Chomp (jeu)

Chomp est un jeu mathématique à deux joueurs, joué sur un rectangle composé de blocs carrés, souvent représenté comme une tablette de chocolat. Chaque joueur choisit un carré à tour de rôle, et le mange, ainsi que tous les carrés situés à sa droite ou plus bas. Le carré en haut à gauche est empoisonné et celui qui le mange perd la partie. C'est un jeu impartial, c'est-à-dire que les coups possibles ne dépendent que de position courante, mais pas du joueur dont c'est le tour.

Dans Chomp, le joueur choisit de manger un carré de chocolat, et du même coup tous les carrés en bas à droite. Attention, il ne faut pas manger le carré en haut à gauche qui est empoisonné.

Le jeu a été inventé en 1952 par Frederik "Fred" Schuh, en termes de choix de diviseurs à partir d'un entier donné, puis ré-inventé indépendamment en 1974 par David Gale sous sa formulation actuelle.

Exemple de partie

Voici un exemple de partie à partir d'une tablette de taille 4x5

Exemple de partie sur une tablette de taille 4x5.

Le joueur A commence. On notera les coordonnées (ligne, colonne) en prenant (1,1) pour le carré empoisonné. Il choisit le carré en (3, 5) et mange les deux carrés en bas à droite, en (3, 5) et (4, 5). Le joueur B choisit le carré en (4, 2) et mange alors 3 carrés. Puis le joueur A choisit le carré en (1, 2) et mange 11 carrés. Le joueur B choisit le carré en (2, 1) et mange trois carrés de la seule colonne restante. Enfin le joueur A est obligé de manger le seul carré restant, celui en (1, 1) qui est empoisonné. Le joueur A perd donc la partie.

Stratégie gagnante

Sur la tablette de taille 1x1, le premier joueur perd la partie puisqu'il doit manger le seul carré empoisonné. Pour toutes les tablettes d'une taille supérieure à 1x1, on peut montrer que le premier joueur a une stratégie gagnante. On peut le montrer par vol de stratégie (strategy-stealing argument en anglais), comme pour le jeu de Hex.

Supposons que le 2^e joueur possède une stratégie gagnante. Cette stratégie contre tous les premiers coups possibles du 1^er joueur. Supposons que le 1^er joueur mange le carré en bas à droite. Le 2^e joueur répond avec sa stratégie gagnante en mangeant un certain carré (n, m). Mais dans ce cas, le 1^er joueur aurait pu lui-même jouer le coup (n, m) dès le début, et appliquer ensuite lui-même la stratégie gagnante. Ceci prouve que le deuxième joueur ne peut pas posséder de stratégie gagnante. On parle de preuve par vol de stratégie parce que le deuxième joueur se fait voler toute stratégie potentielle possible par le premier.

Par contre, le vol de stratégie est un argument non-constructif : il permet de savoir que le premier joueur dispose d'un coup gagnant, mais n'indique pas lequel.

Chomp tridimensionnel

Le jeu de Chomp peut se généraliser à trois dimensions^{[réf. nécessaire]}. La tablette de chocolat devient alors un pavé droit. Le pavé de chocolat est découpé en cubes de chocolat, indexés par (i, j, k), et le cube (1, 1, 1) est bien sûr empoisonné. Un coup consiste à manger un cube de chocolat (i₀, j₀, k₀), ainsi que les cubes (i, j, k) dont tous les indices sont supérieurs ou égaux, c'est-à-dire $i\geq i_{0}$, $j\geq j_{0}$ et $k\geq k_{0}$.

On peut généraliser de la même manière à n dimensions^{[réf. nécessaire]}.

Chomp transfini

Le jeu de Chomp peut s'étendre à des tablettes de chocolat de dimensions infinies. On parle alors de Chomp transfini. Les deux dimensions de la tablette sont représentées par $(\alpha ,\beta )$ où et $\alpha ,\beta$ sont des ordinaux. Contrairement au Chomp classique, dans certaines configurations de Chomp transfini, la preuve par vol de stratégie ne peut pas s'appliquer. Cela conduit à des situations où le deuxième joueur possède une stratégie gagnante, comme c'est le case avec une tablette de dimensions $(2,\omega )$ où $\omega$ représente le premier ordinal infini.

On peut également généraliser Chomp à des tablettes de dimensions $\Omega _{1}\times \Omega _{2}\times ...\times \Omega _{d}$ où $d$ est un entier naturel et $\Omega _{1},\Omega _{2},...,\Omega _{d}$ sont des ordinaux.

Liens externes

• The game of Chomp, une page en anglais détaillant l'historique et la théorie mathématique du jeu.