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.
A move in the game of Chomp, removing two blocks: a player has chosen a block to "eat", and must also eat the block below it. The top-left block is "poisoned" and whoever eats it loses the game.
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 Schuh.
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) λ1 ≥ λ2 ≥···≥ λr, with λ1 ≤ n and r ≤ n. Their number is the binomial coefficient, which grows exponentially with m and n.[1]
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 nprime 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.
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
More information about the game
Play Chomp online
All the winning bites for size up to 14
March 04, 2023
chomp, other, uses, disambiguation, this, article, needs, additional, citations, verification, please, help, improve, this, article, adding, citations, reliable, sources, unsourced, material, challenged, removed, find, sources, news, newspapers, books, scholar. For other uses see Chomp disambiguation This article needs additional citations for verification Please help improve this article by adding citations to reliable sources Unsourced material may be challenged and removed Find sources Chomp news newspapers books scholar JSTOR July 2021 Learn how and when to remove this template message 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 A move in the game of Chomp removing two blocks a player has chosen a block to eat and must also eat the block below it The top left block is poisoned and whoever eats it loses the game 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 Schuh Chomp is a special case of a poset game where the partially ordered set on which the game is played is a product of total orders with the minimal element poisonous block removed Contents 1 Example game 2 Positions of the game 3 Winning the game 4 Generalisations of Chomp 5 See also 6 References 7 External linksExample game EditBelow 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 EditThe intermediate positions in an m n Chomp are integer partitions non increasing sequences of positive integers l1 l2 lr with l1 n and r n Their number is the binomial coefficient m n n displaystyle binom m n n which grows exponentially with m and n 1 Winning the game EditChomp belongs to the category of impartial two player perfect information games 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 EditThree 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 w 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 w w w 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 misere 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 EditNim HackenbushReferences Edit 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 EditMore information about the game A freeware version for windows Play Chomp online All the winning bites for size up to 14 Retrieved from https en wikipedia org w index php title Chomp amp oldid 1130539549, wikipedia, wiki, book, books, library,
