- Chomp (jeu)
-
Chomp est un jeu mathématique, impartial, à deux joueurs, joué avec une "tablette de chocolat", c'est-à-dire un rectangle composé de blocs carrés. Les joueurs choisissent 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.
Le jeu a été inventé en 1952 par Frederik "Fred" Schuh, en termes de choix de diviseurs à partir d'un entier donné[1], puis ré-inventé indépendamment en 1974 par David Gale sous sa formulation actuelle[2].
Sommaire
Exemple de partie
Voici un exemple de partie à partir d'une tablette de taille 3x5 :
Initialement Joueur A Joueur B Joueur A Joueur B 
Le joueur A commence. Chaque joueur choisit un carré, et le mange, ainsi que les carrés situés à droite ou plus bas. Les carrés mangés sont indiqués en pointillés. La dernière figure montre le dernier coup du joueur B. C'est alors au joueur A de jouer, et comme il ne reste que le carré empoisonné, il est obligé de le manger et perd la partie.
Stratégie gagnante
Les coups disponibles ne dépendent que de la position et pas du joueur dont c'est le tour, ce qui fait de Chomp un jeu impartial.
Sur la tablette de taille 1x1, il est évident que le joueur qui joue en premier perd la partie.
Pour toutes les tablettes d'une taille supérieure à 1x1, le joueur qui joue en premier peut au contraire gagner. On peut le montrer par vol de stratégie (strategy-stealing argument en anglais), comme pour le jeu de Hex : supposons que le 2nd joueur possède une stratégie gagnante contre tous les premiers coups possibles du 1er joueur. Supposons ensuite que le 1er joueur effectue son premier coup en mangeant le carré en bas à droite. Le 2nd joueur répond avec sa stratégie gagnante en mangeant un certain carré (n, m). Mais dans ce cas, le 1er 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. 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 (i0, j0, k0), ainsi que les cubes (i, j, k) dont tous les indices sont supérieurs ou égaux, c'est-à-dire
, 
et 
.On peut généraliser de la même manière à n dimensions.
Références
- Fred Schuh. Spel van delers, Nieuw Tijdschrift voor Wiskunde 39 (1952) 299-304
- D. Gale, A curious Nim-type game, Amer. Math. Monthly 81 (1974) 876-879.
Liens externes
- The game of Chomp, une page en anglais détaillant l'historique et la théorie mathématique du jeu.
Wikimedia Foundation. 2010.
