Chocolate Chomp Essay
About The Game
Chocolate Chomp is an implementation of the game Chomp, as described by mathematician David Gale in 1974.
Chomp is a simple two-player strategy game which takes place on a rectangular grid of squares. This grid represents a chocolate bar which has one “poisoned” piece in the upper-left hand corner. Players alternately choose squares on the chocolate bar to take bites. When you take a bite, all of the squares below and to the right of your chosen piece are “chomped.” The player who is forced to eat the poisoned piece loses, ending the game.
This version of Chomp can be played against a friend, solo against the computer, or you can watch the computer play both sides of the game. By selecting different board dimensions you can explore the different properties and winning conditions of the game.
Combinatorial Games
Chomp is an example of a combinatorial game. Chess, Checkers and Tic-Tac-Toe are all combinatorial games.
Combinatorial games have these characteristics in common:
- Two player.
- Perfect information.There is no information hidden from either player.
- No chance moves.There are no dice,spinners or other randomizing elements.
- Positions.The game is made up of a series of positions, which can be considered games themselves.
- Options.At each position, the two players have zero or more moves, or options, available to them.
- Finite.The game must eventually end (one or both players have no options remaining.) This does not mean the game must always have a winner. Tic-tac-toe can end in a draw, for instance.
Chomp has the additional property of being an impartial game, in which the same moves are available to both players. In contrast, a game where each player has different potential moves available, such as Chess or Tic-Tac-Toe, is a partisan game.
The two players in a game are usually called Left and Right, or L and R. Typically, a combinatorial game
conforms to the Normal Play Convention, in which a player is declared the “loser” when that player has no valid options available. Chomp is unusual in this respect as it uses the Misère Play Convention. Under this convention, the last player to move loses. Clearly, Chomp would be no game at all under normal play – a wise player would immediately “chomp” the entire board. Chomp is a good way to explore the basics of combinatorial game theory because there is only one set of positions available to the players – Chomp never breaks down into a set of independent games (each requiring independent analysis), as the game of Go does, for instance.
Strategy
It can be proven that there is a winning strategy for Chomp: player 1 can always win with a perfect strategy.
Because Chomp is symmetric (both players have the same set of available moves), the first player can always win by playing the winning strategy first. Any move that player 2 could use to set a winning strategy in motion is available to player 1 beforehand. The argument, called the strategy-stealing argument, was first applied to games by John Nash, made famous by the Hollywood film A Beautiful Mind. This approach proves that there is a winning strategy for the first player in all games of Chomp, but it does not help us to identify any specific winning strategy.
Although most of the winning strategies for Chomp remain mysterious, David Gale described winning strategies for some simple cases: ”Square Chomp,” in which the grid is the same size in both directions, and “Thin Chomp,” in which the grid is two squares high or wide. These configurations are important to understand if you want to be a good Chomp player because they are found in the endgame of nearly every game of Chomp. Warning: reading further will reveal some of the secrets of Chomp. It is much more fun to discover them for yourself by playing the game!
For the purpose of this discussion, consider the Chomp board as a grid whose upper-left square (the poison piece) is position (0,0).
The square to the right of the poison piece is (1,0), and the square below the poison piece is (0,1).
Square Chomp
Any square Chomp board has the same winning strategy: select square (1,1) first.
This will leave a single row of squares to the right of the poison piece, and a column of equal size below the poison piece. To complete the win, follow up your opponent’s move (whether on the column or the row) by chomping enough squares to make the row and column have the same number of squares. Eventually, your opponent will have to chomp (1,0) or (0,1). When this happens, chomp the other piece in this pair leaving only the poison piece for your opponent. Most Chomp games will end up with a 2×2 square as the endgame.
Thin Chomp
Any Chomp board that is 2 squares high or two squares wide can be won by giving your opponent a position in which the top row has one more square than the bottom row. Eventually, your opponent will be forced to give you a 2×2 square, which you can defeat using the strategy for Square Chomp.
Further Reading
The resources listed below were used in researching Chocolate Chomp. Links will open in the Safari browser.
- On Numbers and Games, by John Conway
- Tracking the Automatic Ant, by David Gale
- Games of No Chance, Richard Nowakowski, Ed.
- Combinatorial Game Theory, Wikipedia
- Mathematical Mysteries: Chomp, by Helen Joyce, Plus Magazine March 2001
Credits
Program and Text: Doug Sartori
Art and Design: Amanda Sinasac
Toolbar Icons: Joseph Wain / glyphish.com