4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The first player has an winning strategy iff the first player eats the last non-poisoned cookie, so that the second player has to eat the poisoned cookie. $\endgroup$ – Newb Nov 4 '14 at 5:11
  • $\begingroup$ Yup I realize that, how do I prove it though? $\endgroup$ – user3362196 Nov 4 '14 at 5:15
  • $\begingroup$ I think you mean the "square" (not rectangle)--although this is a trivial distinction...but what's not trivial is the fact that it's a 1X1 square with the chosen cookie at the top-left. I would normally say that includes the right, bottom, and bottom-right (or diagonal) cookie. And it's not "and/or", it's "and" (of course unless those cookies don't exist via by not being on the board). $\endgroup$ – Jared Nov 4 '14 at 5:15
  • $\begingroup$ You cannot use a strategy stealing argument to prove this because the game is not "symmetric" (i.e., the set of available moves is not the same for each player). Draw a bunch of pictures and come up with a specific strategy. The strategy I came up with works for rectangles too. $\endgroup$ – D Wiggles Nov 4 '14 at 5:25
  • $\begingroup$ Okay, assuming the board is square and not 1 by one, how can I prove this? $\endgroup$ – user3362196 Nov 4 '14 at 5:28
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The above says, "On square boards, taking just one cookie wins for the first player." But this is not true for a 3x3 board. Better stated: Winning strategy on square boards: eat the cookie in the 2nd row, 2nd column. Winning strategy for rectangular boards: Eat just one cookie, then make sure the other player eats the cookie in the 2nd row, 2nd column. Keep in mind that a square board may become a rectangle, and vice versa, so use the appropriate rule on your move. $\endgroup$ – JLee Jan 20 '15 at 16:58
  • $\begingroup$ Addition to the above: "not true for a 3x3 (or larger) square board" $\endgroup$ – JLee Jan 20 '15 at 17:24
  • $\begingroup$ On square boards, the first player should take the maximum square subset of cookies not covering the poisoned one in the first move, which makes $(n-1)^2$ of them. Apart from winning, that would give him also the most possible number of cookies eaten, equal $n(n-1)$. $\endgroup$ – CiaPan Jan 19 '18 at 17:55
2
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ You say that the strategy stealing argument doesn't work here, but what you posted here is essentially the strategy stealing argument. $\endgroup$ – Gregory J. Puleo Nov 4 '14 at 14:54
  • $\begingroup$ That's a very fair point. I still don't think this is quite technically a strategy-stealing argument, because P1's first move could theoretically be a disadvantage. Really, it's this first move that sets up the symmetry to make the strategy-stealing argument. Or am I wrong? Perhaps that is universally the case in strategy stealing arguments? Anyway, I added a note to the solution, but thanks for pointing that out! $\endgroup$ – Shane Nov 4 '14 at 15:02
  • 1
    $\begingroup$ On reflection, you're right that there's a slight different between this argument and, say, the strategy-stealing argument for tic-tac-toe, where the first player can make absolutely any move with no disadvantage. However, every time I've seen this argument before, it's been called the "strategy stealing" argument -- I think that as far as the terminology is concerned, it's good enough that the first player has some move that's functionally a pass. $\endgroup$ – Gregory J. Puleo Nov 4 '14 at 15:53
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.