| Three-rowed Chomp (2009) | |||||||||||||||
Abstract | |||||||||||||||
| A “meta ” (pseudo-) algorithm is described that, for any fixed k, finds a fast (O�log�a��) algorithm for playing 3-rowed Chomp, starting with the first, second, and third rows of lengths a, b, and c, respectively, where c ≤ k, buta and b are arbitrary. © 2001 Academic Press How to Play CHOMP David Gale’s famous game of Chomp [Ch] starts out with an M by N chocolate bar, in which the leftmost-topmost square is poisonous. Players take turns picking squares. In his or her (or its) turn, a player must pick one of the remaining squares, and eat it along with all the squares that are “to its right and below it. ” Using matrix-notation with the poisonous square being entry (1, 1), and the initial position consisting of the whole bar ��i � j��1 ≤ i ≤ M � 1 ≤ j ≤ N�, then picking the square �i0�j0 � means that one has to eat all the remaining squares �i � j � for which both i ≥ i0 and j ≥ j0 hold. The player that eats the poisonous (leftmost-topmost) square loses. Of course picking (1, 1) kills you, so a non-suicidal player will not play that move unless forced to. For example, if M = 4 and N = 3, then the initial game-position is | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||