Given a chomp game with board size $ m * \infty $.

So I've already understood that this game is final, and has a finite number of states.

However I'm having problems with figuring out whether there is a player who can guarantee win and what's his winning strategy?

Also tried for $ m = 2$ to make the game easier but still couldn't figure out.

  • $\begingroup$ (Two-dimensional) chomp is played on a board of dimensions $\alpha\times\beta$ where $\alpha$ and $\beta$ are (finite or infinite) ordinal numbers. By "$m\times\infty$" I think you mean $m\times\omega$ where $\omega$ is the smallest infinite ordinal number. $\endgroup$ – bof May 18 '18 at 4:38
  • $\begingroup$ I don't know what you mean by "this game is final" but I'm pretty sure it has an infinite number of states. (Of course any play of the game will end in a finite number of moves — I don't suppose that's what you were trying to say?) $\endgroup$ – bof May 18 '18 at 4:40

Well, this is funny.

On any finite board, player 2 cannot have a winning strategy. If player 2 has a winning strategy, he must have a winning response to an opener of 1 block taken. But player 1 could then have used that move in the first place. Therefor player 1 could have done that move to begin with. This proof does not tell you what that winning move is, though. Computers are pretty good at figuring it out on 2 dimensional finite boards.

But this logic does not always apply to infinite boards.

Fortunately, 2 dimensional infinite boards are easy to analyze.

We assume upper left is the poisoned square, and that the infinite dimension extends to the right.

For m=1, the winning first move is trivial. leave the other player the losing square.

The next simplest, m=2, does not have a winning first move. This is in fact a LOSS for player 1. there are effectively three possible opening moves.

0) pick upper left. instant loss.

1) pick any other square on upper row. other player picks square one down and to the left, which is guaranteed to be uncollected. This is devastating reply 1 prime.

2) pick ANY square on lower row. other player picks square up and to the right, which is guaranteed to be uncollected. This is devastating reply 2 prime.

first player then has the same choices, now on a finite board x by 2, with the lower right block missing.

For ALL m > 2, the winning first move is to take the first block in the third row, leaving the other player with the m=2 board, which we already know is a loser.


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.