Chomp: A Proof in Game Theory

Game theory and proofs are two of my favorite areas of mathematics; game theory is practical and fun while proofs are interesting and insightful. So, when I learned about this problem that combines the two, I thought that it was definitely worth a post.

This game is called Chomp. It is normally played with just a table of squares, but I find it easier to understand by thinking of a chocolate bar.

The mouth-watering Chomp playing board

Chomp is played where the first player chooses a square on the board, and then takes away everything above and to the right of it (essentially taking a bite out of the top right corner of the chocolate bar). The second player would do the same thing with another remaining square. This process keeps continuing until all that remains is the bottom left square. Whoever is forced to take that square loses.

To better understand how the game works, click here to practice playing it. You will see how easy it is to play and understand.

At this point, any game theorist would be wondering if there is an optimal strategy for this game. From what we saw a couple weeks ago with Anti Tic-Tac-Toe, you might be wondering if symmetry is involved in this game. And yes, you can win this game by playing symmetrical moves in the end game. However, the board is not square, it is a rectangle. So, there cannot be full symmetry.

I do not know what the actual optimal strategy is. But, I do know that one exists that would enable player one to always force a win. I will demonstrate this by an "existence proof" where you prove it exists without finding the actual thing.

Pretend player one just took the top right corner square. This is either a good position or a bad position. If it is a good position, then by definition, player one can continue to play perfectly and force a win. If it is a bad position, then player two must have a responding move that will force them to win.

But, this responding move must be a square that player one could have hit on their first move. Since the top right square really doesn't have an effect on the rest of the board, this would not be a problem. So, player one could have played this strategy, which would allow them to force a win as well.

In either of these situations, player one wins. So, there is our proof. I find these existence proofs really interesting because you don't always think you can know if a statement is true without being able to see an example, but with mathematics, it can be done.