Chomp

Chomp

Chomp is a 2-player game of strategy played on a rectangular "chocolate bar" made up of smaller square blocks (rectangular cells). The players take it in turns to choose one block and "eat it" (remove from the board), together with those that are below it and to its right. The top left block is "poisoned" and the player who eats this loses.

The chocolate-bar formulation of Chomp is due to David Gale, but an equivalent game expressed in terms of choosing divisors of a fixed integer was published earlier by Frederik "Fred" Schuh.

Chomp is a special case of a Poset Game where the Poset is a Lattice (chocolate-bar) with the minimal element (poisonous block) removed.

Contents

Example game

Below shows the sequence of moves in a typical game starting with a 3 × 5 bar:

Initially Player A Player B Player A Player B
xoooo xoooo xoooo x     x        
ooooo oooo  oooo o     
ooooo oooo  o    o  

Player A must eat the last block and so loses. Note that since it is provable that player A can win, at least one of A's moves is a mistake.

Who wins?

Chomp belongs to the category of impartial 2-player perfect information games.

It turns out that for any rectangular starting position bigger than 1 × 1 the 1st player can win. This can be shown using a strategy-stealing argument: assume that the 2nd player has a winning strategy against any initial 1st player move. Suppose then, that the 1st player takes only the bottom right hand square. By our assumption, the 2nd player has a response to this which will force victory. But if such a winning response exists, the 1st player could have played it as his first move and thus forced victory. The 2nd player therefore cannot have a winning strategy.

Computers can easily calculate winning moves for this game on two-dimensional boards of reasonable size.

Generalisations of Chomp

3-dimensional Chomp has an initial chocolate bar of a cuboid of blocks indexed as (i,j,k). A move is to take a block together with any block all of whose indices are greater or equal to the corresponding index of the chosen block. In the same way Chomp can be generalised to any number of dimensions.

Chomp is sometimes described numerically. An initial natural number is given, and players alternate choosing positive proper divisors of the initial number, but may not choose 1 or a multiple of a previously chosen divisor. This game models n-dimensional Chomp, where the initial natural number has n prime factors and the dimensions of the Chomp board are given by the exponents of the primes in its prime factorization.

Ordinal Chomp is played on an infinite board with some of its dimensions ordinal numbers: for example a 2 × (ω + 4) bar. A move is to pick any block and remove all blocks with both indices greater than or equal the corresponding indices of the chosen block. The case of ω × ω × ω Chomp is a notable[citation needed] open problem; a $100 reward has been offered[1] for finding a winning first move.

More generally, Chomp can be played on any partially ordered set with a least element. A move is to remove any element along with all larger elements. A player loses by taking the least element.

All varieties of Chomp can also be played without resorting to poison by using the misère play convention: The player who eats the final chocolate block is not poisoned, but simply loses by virtue of being the last player. This is identical to the ordinary rule when playing Chomp on its own, but differs when playing the disjunctive sum of Chomp games, where only the last final chocolate block loses.

See also

References

  1. ^ p. 482 in: Games of No Chance (R. J. Nowakowski, ed.), Cambridge University Press, 1998.

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Chomp — ist ein 2 Personen Spiel, das mit Papier und Bleistift gespielt werden kann. Inhaltsverzeichnis 1 Name und Regel 2 Geschichte 3 Beispiel 4 Theorie des Spiels …   Deutsch Wikipedia

  • chomp — [tʃɔmp US tʃa:mp, tʃo:mp] v [i]informal [Date: 1600 1700; Origin: CHAMP1] to eat something chomp on ▪ She was chomping on a bread roll. chomp away ▪ a boy chomping away on a banana ▪ British people chomp their way through more than a billion bars …   Dictionary of contemporary English

  • chomp — [chämp] vt., vi. [dial. var. of CHAMP1] 1. to chew hard and noisily 2. to bite down (on), repeatedly and restlessly [to chomp on a cigar] n. the act or sound of chomping chomp at the bit CHAMP AT THE BIT (see phrase under …   English World dictionary

  • Chomp — Chomp, v. i. To chew loudly and greedily; to champ. [Prov. Eng. & Colloq. U. S.] Halliwell. [1913 Webster] …   The Collaborative International Dictionary of English

  • chomp — [ tʃamp ] verb intransitive or transitive INFORMAL to bite something several times in a noisy way: chomp on: He was chomping on a roll …   Usage of the words and phrases in modern English

  • chomp — /chomp/, v.t., v.i., n. champ1. * * * …   Universalium

  • chomp — 1640s, U.S. and dialectal variant of CHAMP (Cf. champ). Related: Chomped; chomping …   Etymology dictionary

  • chomp — ► VERB ▪ munch or chew noisily or vigorously. ORIGIN imitative …   English terms dictionary

  • chomp — UK [tʃɒmp] / US [tʃɑmp] verb [intransitive/transitive] Word forms chomp : present tense I/you/we/they chomp he/she/it chomps present participle chomping past tense chomped past participle chomped informal to bite something several times in a… …   English dictionary

  • Chomp — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Chomp peut faire référence à : jeu de Chomp, un jeu mathématique inventé par David Gale un des ennemis de Mario, dans les jeux vidéo Mario Catégorie  …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”