Proof that there is a winning strategy for player 1 in Chomp.

Question

This question is regarding the game "Chomp" which can be found here:

https://en.wikipedia.org/wiki/Chomp

My quesiton is regarding the proof that there is a winning strategy, the proof can be found here:

https://en.wikipedia.org/wiki/Chomp#Winning_the_game

Here is a copy/paste of the proof from Wikipedia:

For any rectangular starting position, other than 1×1, the first player can win. This can be shown using a strategy-stealing argument: assume that the second player has a winning strategy against any initial first-player move. Suppose then, that the first player takes only the bottom right hand square. By our assumption, the second player has a response to this which will force victory. But if such a winning response exists, the first player could have played it as their first move and thus forced victory. The second player therefore cannot have a winning strategy.

My question:

In the proof they prove that player 2 can not have a winning strategy, this part of the proof I agree with and understand. But what I do not understand is why this imples that player 1 can win? Does player 1 have a winning strategy? My book has a similar proof to the one on Wikipedia and says that there is a winning stragegy for player 1.

Even though player 2 does not have a winning strategy, it does not mean that player 1 has one? If if does, why?, why is it enough to prove that player 2 does not have a winning strategy?

Answer 1

In Chomp, we can classify all positions as

• P-positions: the Previous player, the one who just moved, has a winning strategy.
• N-positions: the Next player, whose turn it is, has a winning strategy.

To prove that all positions must be one or the other, induct on the number of remaining squares. As a base case, the position with only the poisoned square left is a P-position, because the next player must eat the poisoned square and lose. From here, assume that all positions with fewer than $k$ squares are classified, and take any $k$-square position. Then:

• If a move is possible which leads to a P-position, then (by definition) it is a winning strategy for the player whose turn it is to make that move. Therefore the current position is an N-position.
• If all possible moves lead to N-positions, then no matter what the player whose turn it is does, the other player will have a winning strategy. Therefore the current position is a P-position. The previous player's winning strategy is "wait for the player whose turn it is to move, and then follow the winning strategy for the resulting position".

By induction, all positions must be of one type or the other. Some player must have a winning strategy in every situation!

By the strategy-stealing argument, rectangular starting positions are not P-positions, so they must be N-positions: the first player must have a winning strategy. (Note that the proof does not tell us what the strategy is!)

This argument applies more generally.