Chomp

In 2008, I attended a conference in Athens, the 4th Conference on Computability in Europe (CiE), where my student Craig Wilson and I presented a paper that was fun to write, as it examined the algorithmic complexity of a strategy game called Chomp.

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.

This fun paper, turned out to be one of my most cited works, and how the Wikipedia page dedicated to chomp cites it in its references: Chomp – Wikipedia

The paper itself was first published in the conference proceedings, and then in the journal Theory of Computing Systems, 48(3):680-692, 2011:

Leave a Reply

Your email address will not be published.