Chomp (The Esthetics of Not Knowing)

Mathematics has a few peculiarities (inherited by their owners, the mathematicians) that irritate the uninitiated. One of them is the non-constructive aspect of many of its statements. A delicious example is the game Chomp, played with a chocolate bar. Traditionally, the top left piece is poisoned. Two players take turns selecting a piece, breaking it off together with the rectangular chunk of the pieces that are to the right or below of that piece, and instantly eating all of it. Here is an example sequence of turns. The lighter brown indicates which pieces the player is about to eat. We see that here Two has the last bite. Let’s not talk about it.Chomp 1 01

As with each move the number of uneaten chocolate pieces decreases, the game necessarily ends, and there is no draw. Mathematicians conclude from this that either One or Two has a winning strategy, i.e. a way of choosing chocolate pieces so that they win (survive), no matter what the other is doing. In Chomp, the situation is more surprising: One can always win, no matter how large the chocolate bar, but we are generally clueless how One can accomplish this. This is done by an argument that is called strategy stealing, and uses a perplexing indirect proof. So let’s assume, by contradiction, that Two has a winning strategy.

Chomp 2 01

One steals this strategy as follows: One takes the bottom right piece, and sees what Two is doing. Two will make a winning move, removing another piece and everything below and to the right. But One could have done the exact same thing, reaching the same position in the first place (as the bottom right piece will disappear with that move as well). But the nagging question remains unanswered: How does One win? What is the winning move? This happens to be a very difficult question. We not only have to consider the whole, intact chocolate bar, but also the ones that arise while chomping, and we can (very plausibly) even allow bars where some of the chocolate pieces have already been eaten (by someone) before the game even starts. For instance, below are all 132 fragmentary chocolate bars that fit in a 2×6 box where the moving player will lose, assuming the other player has their wits together.

2x6

Out of decency I have removed the poisoned piece in the top left corner, the game now simply ends when one player has no move left, meaning they lose, but keep at least their life. Below are the 182 losing positions that fit in a 3×4 box.

3x4

This is incomprehensible determinism made visible. There are patterns, though. If one encodes all possible positions that fit in a 2×10 box by a pair of binary numbers and plots the losing positions as dots in a 1024×1024 square, one gets the following:

Losers10b

Some of the patterns (like the emerging periodicity) have been partially understood, and I’ll write about that later, time and comprehension permitting.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s