Prove using a strategy stealing argument that player 1 has a winning strategy in the chomp game

Question

I have no idea what this question is asking or how to prove it mathematically. I realize based on the strategy stealing theory that if player two has a winning stratagy then player one can use the same strategy by going first and since both players can't win, player one wins. How can I show this mathematically?

The game of Chomp is played by two players. In this game, cookies are laid out on a rectangular grid. The cookie in the top left position is poisoned. The two players take turns making moves; at each move, a player is required to eat a remaining cookie, together with all cookies to the right and/or below (that is all the remaining cookies in the rectangle, in which the first cookie eaten is the top left corner). The loser is the player who has no choice but to eat the poisoned cookie. Prove that if the board is square (and bigger than 1 × 1) then the first player has a winning strategy.

Answer 1

The strategy stealing theory does not apply here because the moves available to both players are not the same. It is possible that the first player does not have a winning strategy and no matter what he does on move 1, player 2 has a winning strategy. Of course, it is not very likely because player 1 has a lot of options that affect the rest of the game, but there could be a possible square where player 2's winning strategy guarantees player 1 the poisoned cookie.

Answer 2

As pointed out above, I don't think the strategy-stealing argument technically applies here because P1's first move could in fact be a disadvantage (it's not like he can pass). However, as pointed out below in the comment, the proof does essentially use the strategy-stealing argument.

In terms of proving that P1 has a winning strategy, here's one route (proof by contradiction) for an $m \times n$ board, which is obviously a generalization of a square board.

Suppose to the contrary that P1 does not have a strategy that guarantees victory. Then, player 2 must have such a strategy, since there are no ties. Then, no matter what P1 does with his first move, P2 can guarantee victory from that point onwards. Let $C$ be the set of all possible grid configurations that can result from P1's first move. From every such configuration $c \in C$, the next player moving, P2 here, can guarantee victory for himself.

However, suppose P1 selects $(m,n)$, that is the lower-right cell, with his first move. Then, no matter what P2 chooses with his second choice, the resulting configuration $c^*$ will be in $C$ - that is to say P1 could have taken us directly to $c^*$ with his first move. By assumption above, for all $c \in C$, the next player moving, now P1, can guarantee victory for himself. Since P1 can guarantee victory following whatever move P2 makes, we have found a contradiction - therefore, P1 must have a strategy that guarantees victory.

I'm not sure we actually know what the winning strategy is in a general $m \times n$, just that one exists. In the special case in which $m=n$, the winning strategy involves P1 selecting $(2,2)$ in the first round then exploiting symmetry going forward (just copy your opponent's play basically). See if you can convince yourself why!

Answer 3

The usual game of Chomp (with your orientation) has the player eating all cookies that are at least as far right and at least as low down as the selected cookie, not and/or. We can then use strategy stealing on any rectangular board, square or not. The game is a symmetric perfect information game, so every position is either P (won by the previous player) or N (won by the next player). Assume the second player can win, so the rectangle is a P position. The second player must have a winning response to the first player move of the lower right cookie, taking the board to a P position. The first player can make that move (which will include removing the lower right cookie), achieve the P position, then follow the winning second player strategy. This is a contradiction, so our assumption that the second player can win is wrong.

Note that this shows there is a winning first player strategy, but gives no help at finding it. It turns out that on some boards the first player should just take the one cookie, while on others he should take some other move. On square boards, taking just one cookie wins for the first player. He can then make symmetric moves to the second player and win.