Chomp (jeu)

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.

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.

Le jeu de Chomp peut se généraliser à trois dimensions. 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 ${\displaystyle i\geq i_{0}}$, ${\displaystyle j\geq j_{0}}$ et ${\displaystyle k\geq k_{0}}$.

On peut généraliser de la même manière à n dimensions.

Le jeu de Chomp peut s'étendre à des tablettes de chocolat de dimensions infinies. On parle alors de Chomp tranfini[3]. Les deux dimensions de la tablette sont représentées par ${\displaystyle (\alpha ,\beta )}$ où et ${\displaystyle \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 ${\displaystyle (2,\omega )}$ où ${\displaystyle \omega }$ représente le premier ordinal infini.

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

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