Rester

Chomp est un jeu de stratégie à deux joueurs qui se joue sur une grille rectangulaire composée de cases, souvent représentée sous la forme d’une tablette de chocolat. Les joueurs « mangent » à tour de rôle une case ainsi que toutes celles situées au-dessus et à droite de celle-ci. La case située dans le coin inférieur gauche est « empoisonnée » : le joueur contraint de la manger perd la partie. Malgré ses règles simples, Chomp présente des propriétés mathématiques complexes et est lié à des concepts importants de la théorie combinatoire des jeux.

Règles

1. Le jeu commence avec une grille rectangulaire (par exemple, 5x4), représentée sous la forme d’une tablette de chocolat divisée en carrés.
2. Les joueurs jouent à tour de rôle.
3. À chaque tour, un joueur choisit n'importe quelle case restante. Cette case, ainsi que toutes celles situées au-dessus et à sa droite, sont retirées (« mangées »).
4. La case en bas à gauche est empoisonnée (souvent marquée d'une tête de mort ou d'une couleur différente).
5. Le joueur qui est contraint de manger la case empoisonnée perd.

Stratégies

• Le premier joueur gagne : il a été prouvé mathématiquement (par un argument dit de « vol de stratégie ») que le premier joueur dispose toujours d’une stratégie gagnante sur toute grille rectangulaire supérieure à 1x1. Cependant, la preuve est non constructive : elle démontre qu’une stratégie gagnante existe sans révéler laquelle.
• Ouverture « mordillement du coin » : au premier coup, ne manger que la case du coin supérieur droit constitue souvent une bonne ouverture, car elle préserve un maximum de flexibilité.
• Positions en L : Lorsque les cases restantes forment un L dont les branches sont de longueur égale, la position est souvent perdante pour le joueur dont c'est le tour.
• Stratégie de symétrie : sur les grilles carrées (NxN), le premier joueur peut gagner en prenant la case du coin supérieur droit au premier coup, puis en reproduisant en miroir les coups de son adversaire. Cela ne fonctionne pas sur les grilles rectangulaires.
• Mémorisation des petites grilles : pour les petites grilles (jusqu’à 5x4), les positions gagnantes et perdantes peuvent être mémorisées grâce à une analyse complète de l’arbre de jeu.
• Réduire les options : essayez de placer votre adversaire dans des positions où il ne reste que peu de cases, le forçant ainsi à se diriger vers le coin empoisonné.

Le jeu « Chomp » a été inventé indépendamment par le mathématicien David Gale en 1974 et par Fred Schuh en 1952 (qui lui avait donné un autre nom dans son ouvrage en néerlandais consacré aux jeux mathématiques). Gale a publié ce jeu dans la revue *American Mathematical Monthly*, où il a rapidement attiré l’attention des mathématiciens et des spécialistes de la théorie des jeux.

La propriété mathématique la plus célèbre de ce jeu est sa preuve dite du « vol de stratégie ». L'argument est le suivant : si le premier joueur ne dispose pas d'une stratégie gagnante, alors le second joueur en a une. Mais le premier joueur pourrait toujours ne manger que la case du coin supérieur droit lors de son premier coup — si le deuxième joueur dispose alors d’une réponse gagnante, le premier joueur aurait pu adopter cette même réponse comme premier coup. Cette contradiction prouve que le premier joueur doit disposer d’une stratégie gagnante. Cependant, cette démonstration ne nous apprend rien sur la nature exacte de cette stratégie.

Pour les grilles rectangulaires non carrées, la recherche de la stratégie optimale reste un problème ouvert en mathématiques. Bien que les ordinateurs aient résolu de manière exhaustive les petites grilles, aucune formule générale n’est connue. Cela fait de Chomp l’un des problèmes non résolus les plus simples à énoncer en théorie des jeux combinatoires.

Chomp présente des liens étroits avec d’autres domaines des mathématiques, notamment les ensembles partiellement ordonnés (posets) et les treillis de diviseurs. Une variante appelée « jeu de Schur » ou « Divisor Chomp » remplace la grille rectangulaire par les diviseurs d’un nombre : les joueurs choisissent un diviseur et retirent tous ses multiples. Ce jeu a été utilisé comme outil pédagogique dans les universités pour initier les étudiants à la théorie des jeux, aux techniques de démonstration et à la complexité algorithmique.