enter image description here

There are two players 1 and 2, and the game begins with player 1 selecting one of the boxes marked 1 to 16. Following such a selection, the selected box, as well as all boxes in the square of which the selected box constitutes the leftmost and lowest corner, will be deleted. For example, if he selects box 7, then all the boxes, 3, 4, 7 and 8 are deleted. Similarly, if he selects box 9, then all boxes 1 to 12 are deleted. Next it is player 2’s turn to select a box from the remaining boxes. The same deletion rule applies in this case. It is then player 1’s turn again, and so on. Whoever deletes the last box loses the game? What is a winning strategy for player 1 in this game?

I can't even begin to form a payoff matrix or anything for this question, do we have to consider ALL the possible alternatives?

  • $\begingroup$ You have to use dynamic programming. $\endgroup$ – Jamie Lannister Apr 29 '15 at 2:18
  • $\begingroup$ forming sequential subgames? $\endgroup$ – dexter Apr 29 '15 at 2:19
  • $\begingroup$ Yes. start with the case when there's one left, then when there's four, etc... and look for an invariant strategy. $\endgroup$ – Jamie Lannister Apr 29 '15 at 2:23
  • 1
    $\begingroup$ It sounds like you might be getting confused by mixing concepts from combinatorial game theory with those from economic game theory. A payoff matrix suggests that players 1 and 2 make their choices simultaneously and are rewarded or penalized according to the entry in the matrix; this is an economic concept that doesn't apply to turn-based games. $\endgroup$ – Théophile Apr 29 '15 at 2:30
  • $\begingroup$ There's no payoff matrix. Your strategy is a best response function that is recursive based on the instance at hand. You find this function via dynamic programming. It's analogous to the continuous case where you find an equilibrium best response function of quantity in the Cournet model. In short, you're not looking for a fixed point in a finite dimensional space but an invariant strategy in a function space. Hope that makes sense. Took me a while to get that the first time I saw it. $\endgroup$ – Jamie Lannister Apr 29 '15 at 2:46

This is the game of Chomp. It is a first player win for any board size, but the strategy is not known in general. The proof is "stategy-stealing". Assume player 2 can win. Then player 1 can take box 4. Any move that the second player can play now, the first player could have played on the first turn, so the first player plays the second player strategy and can win. We have a contradiction, so we know the first player can win. We don't know whether player 1 should take 4 or something else. It varies with board size.

For a square board like yours, the first player has an easy win by taking the square diagonally next to the poison square, in this case $10$. The first player can then maintain equal lengths on the vertical and horizontal legs, which forces the second player to take $13$.


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.