Chomp

Last updated December 12, 2023

Chomp is a two-player strategy game played on a rectangular grid made up of smaller square cells, which can be thought of as the blocks of a chocolate bar. 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.

Example game

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

Player A eats two blocks from the bottom right corner; Player B eats three from the bottom row; Player A picks the block to the right of the poisoned block and eats eleven blocks; Player B eats three blocks from the remaining column, leaving only the poisoned block. Player A must eat the last block and so loses.

Note that since it is provable that player A can win when starting from a 5 × 4 bar, at least one of A's moves is a mistake.

Positions of the game

The intermediate positions in an m × n Chomp are integer-partitions (non-increasing sequences of positive integers) λ₁ ≥ λ₂ ≥···≥ λ_r, with λ₁ ≤ n and r ≤ m. Their number is the binomial coefficient ${\binom {m+n}{n}}$ , which grows exponentially with m and n.^[1]

Winning the game

Chomp belongs to the category of impartial two-player perfect information games, making it also analyzable by Nim because of the Sprague–Grundy theorem.

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

Computers can easily calculate winning moves for this game on two-dimensional boards of reasonable size. However, as the number of positions grows exponentially, this is infeasible for larger boards.

For a square starting position (i.e., n × n for any n ≥ 2), the winning strategy can easily be given explicitly. The first player should present the second with an L shape of one row and one column only, of the same length, connected at the poisonous square. Then, whatever the second player does on one arm of the L, the first player replies with the same move on the second arm, always presenting the second player again with a symmetric L shape. Finally, this L will degenerate into the single poisonous square, and the second player would lose.

Generalisations of Chomp

Three-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 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 open problem; a $100 reward has been offered^[2] 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.

Related Research Articles

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements . It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.

In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers a and b, usually denoted by lcm(a, b), is the smallest positive integer that is divisible by both a and b. Since division of integers by zero is undefined, this definition has meaning only if a and b are both different from zero. However, some authors define lcm(a, 0) as 0 for all a, since 0 is the only common multiple of a and 0.

<span class="mw-page-title-main">Nim</span> Game of strategy

Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps or piles. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap or pile. Depending on the version being played, the goal of the game is either to avoid taking the last object or to take the last object.

<span class="mw-page-title-main">Roulette</span> Casino game of chance

Roulette is a casino game which was likely developed from the Italian game Biribi. In the game, a player may choose to place a bet on a single number, various groupings of numbers, the color red or black, whether the number is odd or even, or if the numbers are high (19–36) or low (1–18).

In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as $or$

In mathematics, the surreal number system is a totally ordered proper class containing not only the real numbers but also infinite and infinitesimal numbers, respectively larger or smaller in absolute value than any positive real number. Research on the Go endgame by John Horton Conway led to the original definition and construction of surreal numbers. Conway's construction was introduced in Donald Knuth's 1974 book Surreal Numbers: How Two Ex-Students Turned On to Pure Mathematics and Found Total Happiness.

A solved game is a game whose outcome can be correctly predicted from any position, assuming that both players play perfectly. This concept is usually applied to abstract strategy games, and especially to games with full information and no element of chance; solving such a game may use combinatorial game theory and/or computer assistance.

In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically checking all possible candidates for whether or not each candidate satisfies the problem's statement.

In mathematics, the nimbers, also called Grundy numbers, are introduced in combinatorial game theory, where they are defined as the values of heaps in the game Nim. The nimbers are the ordinal numbers endowed with nimber addition and nimber multiplication, which are distinct from ordinal addition and ordinal multiplication.

<i>On Numbers and Games</i> 1976 mathematics book by John Conway

On Numbers and Games is a mathematics book by John Horton Conway first published in 1976. The book is written by a pre-eminent mathematician, and is directed at other mathematicians. The material is, however, developed in a playful and unpretentious manner and many chapters are accessible to non-mathematicians. Martin Gardner discussed the book at length, particularly Conway's construction of surreal numbers, in his Mathematical Games column in Scientific American in September 1976.

In mathematics, a multiplicative inverse or reciprocal for a number x, denoted by 1/x or x⁻¹, is a number which when multiplied by x yields the multiplicative identity, 1. The multiplicative inverse of a fraction a/b is b/a. For the multiplicative inverse of a real number, divide 1 by the number. For example, the reciprocal of 5 is one fifth (1/5 or 0.2), and the reciprocal of 0.25 is 1 divided by 0.25, or 4. The reciprocal function, the function f(x) that maps x to 1/x, is one of the simplest examples of a function which is its own inverse (an involution).

In mathematics, the order of a finite group is the number of its elements. If a group is not finite, one says that its order is infinite. The order of an element of a group is the order of the subgroup generated by the element. If the group operation is denoted as a multiplication, the order of an element $a$ of a group, is thus the smallest positive integer $m$ such that $a m = e$ , where $e$ denotes the identity element of the group, and $a m$ denotes the product of $m$ copies of $a$ . If no such $m$ exists, the order of $a$ is infinite.

In combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many two-player games, that the second player cannot have a guaranteed winning strategy. The strategy-stealing argument applies to any symmetric game in which an extra move can never be a disadvantage. A key property of a strategy-stealing argument is that it proves that the first player can win the game without actually constructing such a strategy. So, although it might prove the existence of a winning strategy, the proof gives no information about what that strategy is.

Sylver coinage is a mathematical game for two players, invented by John H. Conway. The two players take turns naming positive integers greater than 1 that are not the sum of nonnegative multiples of previously named integers. The player who cannot name such a number loses. For instance, if player A opens with 2, B can win by naming 3.

In mathematics, the axiom of determinacy is a possible axiom for set theory introduced by Jan Mycielski and Hugo Steinhaus in 1962. It refers to certain two-person topological games of length ω. AD states that every game of a certain type is determined; that is, one of the two players has a winning strategy.

In mathematics, the Eisenstein integers, occasionally also known as Eulerian integers, are the complex numbers of the form

Determinacy is a subfield of set theory, a branch of mathematics, that examines the conditions under which one or the other player of a game has a winning strategy, and the consequences of the existence of such strategies. Alternatively and similarly, "determinacy" is the property of a game whereby such a strategy exists. Determinacy was introduced by Gale and Stewart in 1950, under the name "determinateness".

Wythoff's game is a two-player mathematical subtraction game, played with two piles of counters. Players take turns removing counters from one or both piles; when removing counters from both piles, the numbers of counters removed from each pile must be equal. The game ends when one player removes the last counter or counters, thus winning.

In mathematics, the supernatural numbers, sometimes called generalized natural numbers or Steinitz numbers, are a generalization of the natural numbers. They were used by Ernst Steinitz in 1910 as a part of his work on field theory.

In combinatorial game theory, poset games are mathematical games of strategy, generalizing many well-known games such as Nim and Chomp. In such games, two players start with a poset, and take turns choosing one point in the poset, removing it and all points that are greater. The player who is left with no point to choose, loses.

References

↑ Zeilberger, Doron (2001). "Three-Rowed CHOMP". Advances in Applied Mathematics. 26 (2): 168–179. doi: 10.1006/aama.2000.0714 .
↑ p. 482 in: Games of No Chance (R. J. Nowakowski, ed.), Cambridge University Press, 1998.

Zeilberger, Doron (2004). "Chomp, recurrences and chaos(?)". J. Diff. Eq. Applic. 10 (13–15): 1281–1293. doi:10.1080/10236190410001652720.
Brouwer, A. E.; Horvath, Gabor; Molna-Saska, Ildiko; Szabo, Csaba (2005). "On three-rowed Chomp". Integers. 5: #G07.
Friedman, Eirc J. (2007). "Nonlinear dynamics in combinatorial games: renormalizing Chomp". Chaos. 17 (2): 023117. Bibcode:2007Chaos..17b3117F. doi:10.1063/1.2725717. PMID 17614671.
Khandhawit, Tirasan; Ye, Lynnelle (2011). "Chomp on graphs and subsets". arXiv: 1101.2718 [math.CO].
Soltys, Michael; Wilson, Craig (2011). "On the complexity of computing winning strategies for finite Poset games". Theory Comput. Syst. 48 (3): 680–692. doi:10.1007/s00224-010-9254-y. S2CID 2720334.
Brouwer, A. E. (2017). "The game of chomp".
Cho, In-Sung (2018). "Winning strategies for the game of Chomp: A practical approach". J. History Math. 31 (3): 151–166. doi:10.14477/jhm.2018.31.3.151.

External links

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Zeilberger, Doron (2001). "Three-Rowed CHOMP". Advances in Applied Mathematics. 26 (2): 168–179. doi: 10.1006/aama.2000.0714 .

[2] . 482 in: Games of No Chance (R. J. Nowakowski, ed.), Cambridge University Press, 1998.

[1]

[2]