Chomp

<h2 id="example-game">Example game</h2>
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.

<h2 id="positions-of-the-game">Positions of the game</h2>
The intermediate positions in an m × n Chomp are integer-partitions (non-increasing sequences of positive integers) λ1 ≥ λ2 ≥···≥ λr, with λ1 ≤ n
and r ≤ m. Their number is the <a href="/facts/Binomial_coefficient/Tsx7eY5h">binomial coefficient</a> 
 
 
 
 
 
 
 (
 
 
 
 m
 +
 n
 
 n
 
 
 )
 
 
 
 
 
 {\displaystyle {\binom {m+n}{n}}}
 
, which grows exponentially with m and n.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>

<h2 id="winning-the-game">Winning the game</h2>
Chomp belongs to the category of <a href="/facts/Impartial_game/kQWPKPGv">impartial</a> two-player <a href="/facts/Perfect_information/bouFdU4l">perfect information</a> games, making it also analyzable by <a href="/facts/Nim/JfDdzxyc">Nim</a> because of the <a href="/facts/Sprague%25E2%2580%2593Grundy_theorem/0ED4gBMY">Sprague–Grundy theorem</a>.
For any rectangular starting position, other than 1×1, the first player can win. This can be shown using a <a href="/facts/Strategy-stealing_argument/L9v2HBDE">strategy-stealing argument</a>: 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.
Similarly, any 2 × n (for any n ≥ 2) is also trivial. The winning starting move is always the bottom right square. The board after this move can be thought of as two vertical chains of squares (ignoring the poisoned square), and to win, simply mimic player 2's moves on the other chain. Other paths to victory are often more complicated however.

<h2 id="generalisations-of-chomp">Generalisations of Chomp</h2>
Three-<a href="/facts/Dimension/0ktmUyac">dimensional</a> Chomp has an initial chocolate bar of a <a href="/facts/Cuboid/eLLKX4rh">cuboid</a> 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 <a href="/facts/Natural_number/u65og8JE">natural number</a> is given, and players alternate choosing positive <a href="/facts/Divisor/DKNa2GvC">divisors</a> of the initial number, but may not choose 1 or a <a href="/facts/Multiple_(mathematics)/tkte6NXa">multiple</a> of a previously chosen divisor. This game models n-<a href="/facts/Dimension/0ktmUyac">dimensional</a> Chomp, where the initial natural number has n <a href="/facts/Prime_factor/L20FLkgn">prime factors</a> and the <a href="/facts/Dimensions/0ktmUyac">dimensions</a> of the Chomp board are given by the <a href="/facts/Exponentiation/pac6QY2g">exponents</a> of the primes in its <a href="/facts/Fundamental_theorem_of_arithmetic/EzHUwlXX">prime factorization</a>.
Ordinal Chomp is played on an infinite board with some of its dimensions <a href="/facts/Ordinal_numbers/GelFLjJt">ordinal numbers</a>: 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<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> for finding a winning first move.
More generally, Chomp can be played on any <a href="/facts/Partially_ordered_set/qb4a3FAX">partially ordered set</a> with a <a href="/facts/Least_element/JVn2B3mo">least element</a>. 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 <a href="/facts/Mis%25C3%25A8re_play_convention/q0hwTI2G">misère play convention</a>: 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 <a href="/facts/Disjunctive_sum/qS2BARP9">disjunctive sum</a> of Chomp games, where only the last final chocolate block loses.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Nim/JfDdzxyc">Nim</a></li>
<li><a href="/facts/Hackenbush/RQoAuvkI">Hackenbush</a></li></ul>

<ul><li>Zeilberger, Doron (2004). "Chomp, recurrences and chaos(?)". J. Diff. Eq. Applic. 10 (13–15): 1281–1293. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1080%2F10236190410001652720">10.1080/10236190410001652720</a>.</li>
<li>Brouwer, A. E.; Horvath, Gabor; Molna-Saska, Ildiko; Szabo, Csaba (2005). <a href="https://research.tue.nl/nl/publications/05fb55ee-a2aa-404f-a41f-4de630028623">"On three-rowed Chomp"</a>. Integers. 5: #G07.</li>
<li>Friedman, Eirc J. (2007). <a href="https://scholarship.claremont.edu/cgi/viewcontent.cgi?article=1024&context=wmkeckscience">"Nonlinear dynamics in combinatorial games: renormalizing Chomp"</a>. Chaos. 17 (2): 023117. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/2007Chaos..17b3117F">2007Chaos..17b3117F</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1063%2F1.2725717">10.1063/1.2725717</a>. <a href="/facts/PMID_(identifier)/JlHAvMHt">PMID</a> <a href="https://pubmed.ncbi.nlm.nih.gov/17614671">17614671</a>.</li>
<li>Khandhawit, Tirasan; Ye, Lynnelle (2011). "Chomp on graphs and subsets". <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1101.2718">1101.2718</a> [<a href="https://arxiv.org/archive/math.CO">math.CO</a>].</li>
<li>Soltys, Michael; Wilson, Craig (2011). "On the complexity of computing winning strategies for finite Poset games". Theory Comput. Syst. 48 (3): 680–692. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs00224-010-9254-y">10.1007/s00224-010-9254-y</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:2720334">2720334</a>.</li>
<li>Brouwer, A. E. (2017). <a href="https://www.win.tue.nl/~aeb/games/chomp.html">"The game of chomp"</a>.</li>
<li>Cho, In-Sung (2018). "Winning strategies for the game of Chomp: A practical approach". J. History Math. 31 (3): 151–166. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.14477%2Fjhm.2018.31.3.151">10.14477/jhm.2018.31.3.151</a>.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="http://www.win.tue.nl/~aeb/games/chomp.html">More information about the game</a></li>
<li><a href="https://web.archive.org/web/20200116070016/http://www.ossiemanners.co.uk/">A freeware version for windows</a></li>
<li><a href="https://www.math.ucla.edu/~tom/Games/chomp.html">Play Chomp online</a></li>
<li><a href="http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/chompc.html">All the winning bites for size up to 14</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Zeilberger, Doron (2001). "Three-Rowed CHOMP". Advances in Applied Mathematics. 26 (2): 168–179. doi:10.1006/aama.2000.0714. <a href="https://doi.org/10.1006%2Faama.2000.0714" target="_blank">https://doi.org/10.1006%2Faama.2000.0714</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">p. 482 in: Games of No Chance (R. J. Nowakowski, ed.), Cambridge University Press, 1998. <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
</ol>

Chomp open-in-new

Chomp