Chomp
Encyclopedia
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.
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.
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.
al 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-dimension
al Chomp, where the initial natural number has n prime factor
s 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 open problem; a $100 reward has been offered 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.
Square (geometry)
In geometry, a square is a regular quadrilateral. This means that it has four equal sides and four equal angles...
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
David Gale
David Gale was a distinguished American mathematician and economist. He was a Professor Emeritus at University of California, Berkeley, affiliated with departments of Mathematics, Economics, and Industrial Engineering and Operations Research...
, 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
Poset game
Poset games are mathematical games of strategy where, given a poset P, two players alternate on choosing one point in P, removing it and and all points that are greater...
where the Poset is a Lattice
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
(chocolate-bar) with the minimal element (poisonous block) removed.
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 |
|---|---|---|---|---|---|---|---|---|
  |
|
|
 |
 |
||||
| |
|
|
|
|
||||
| |
|
|
|
|
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 impartialImpartial game
In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric...
2-player perfect information
Perfect information
In game theory, perfect information describes the situation when a player has available the same information to determine all of the possible games as would be available at the end of the game....
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
Strategy-stealing argument
In combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many games, that the second player cannot have a winning strategy .The strategy-stealing argument applies to any symmetric game In combinatorial game theory, the strategy-stealing argument is a...
: 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-dimensionDimension
In physics and mathematics, the dimension of a space or object is informally defined as the minimum number of coordinates needed to specify any point within it. Thus a line has a dimension of one because only one coordinate is needed to specify a point on it...
al Chomp has an initial chocolate bar of a cuboid
Cuboid
In geometry, a cuboid is a solid figure bounded by six faces, forming a convex polyhedron. There are two competing definitions of a cuboid in mathematical literature...
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
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
is given, and players alternate choosing positive proper divisors of the initial number, but may not choose 1 or a multiple
Divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
of a previously chosen divisor. This game models n-dimension
Dimension
In physics and mathematics, the dimension of a space or object is informally defined as the minimum number of coordinates needed to specify any point within it. Thus a line has a dimension of one because only one coordinate is needed to specify a point on it...
al Chomp, where the initial natural number has n prime factor
Prime factor
In number theory, the prime factors of a positive integer are the prime numbers that divide that integer exactly, without leaving a remainder. The process of finding these numbers is called integer factorization, or prime factorization. A prime factor can be visualized by understanding Euclid's...
s and the dimensions
Dimensions
Dimensions is a French project that makes educational movies about mathematics, focusing on spatial geometry. It uses POV-Ray to render some of the animations, and the films are release under a Creative Commons licence....
of the Chomp board are given by the exponents
Exponentiation
Exponentiation is a mathematical operation, written as an, involving two numbers, the base a and the exponent n...
of the primes in its prime factorization
Fundamental theorem of arithmetic
In number theory, the fundamental theorem of arithmetic states that any integer greater than 1 can be written as a unique product of prime numbers...
.
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 open problem; a $100 reward has been offered for finding a winning first move.
More generally, Chomp can be played on any partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
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
Disjunctive sum
The disjunctive sum of two games is a game in which the two games are played in parallel, with each player being allowed to move in just one of the games per turn...
of Chomp games, where only the last final chocolate block loses.