There are 2 code files: “main.cpp” and “chomp.cpp”. The
“main2.cpp” is extra code file that checks correctness of
some table enties
“PA1 Problem 1” (one PDF file): This is the solution to
“chomp.cpp” (one code file): This is the solution to
Problem 2. It should be one code file as described in
Problem 2. Name of the file should be chomp.cpp
This assignment is to design a dynamic programming recurrence for the game
of Chomp and then write code to solve the 5 x n version of the game. The
description of Chomp below is taken from Anna R. Karlin and Yuval Peres.
Game theory, Alive. American Mathematical Society Press , 2017. Figure (1)
illustrates the rules and concepts described below.
Chomp is played on a bar of chocolate divided into m x n squares. The
bottom left corner of the bar has been removed and replaced with a poisoned
Two players take turns biting off a chunk of the bar. More specifically,
each player, in his turn, chooses an uneaten chocolate square and removes
it along with all of the squares that lie above and to the right of it.
The person who bites the last piece of chocolate wins and the loser has to
eat the poisoned square.
Note. There is a lot of information about Chomp available on the internet.
Some sources, such as the Wikipedia page on the game, present a slightly different
version that has the upper left square poisoned. Don’t get confused by this.