## Winning strategy at chomp (a chocolate bar game)?

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

The game of chomp is an example of a game with very simple rules, but no known winning strategy in general.

I copy the rules from Ivars Peterson's page http://www.maa.org/mathland/mathtrek_03_24_03.html

"Chomp starts with a rectangular array of counters arranged neatly in rows and columns. A move consists of selecting any counter, then removing that counter along with all the counters above and to the right of it. In effect, the player takes a rectangular or square "bite" out of the array—just as if the array were a rectangular, segmented chocolate bar. Two players take turns removing counters. The loser is the one forced to take the last "poisoned" counter in the lower left corner."

A nice non-constructive argument shows that the first player has a winning strategy. The winning strategy can be made explicit in very specific cases. As far as I know, the more general setting for which the winning strategy is known is when we have 3 rows and any number of columns, see http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/chomp.html

My question is

Are there any recent advances on chomp?

-

3
I don't think this is "recent", but in case you're not aware, it's an interesting exercise to see who has the winning strategy in $n\times \infty$ chomp ($2\leq n\leq \infty$). The usual argument doesn't work, but one can construct an explicit winning strategy. I heard this from Shmuel Zamir at BWGT $2010$. – Noah Stein Jan 5 2011 at 14:03

2
A closely related question is mathoverflow.net/questions/41913/…. – Richard Stanley Jan 5 2011 at 17:08
I don't understand the question. Can't you just calculate nimbers for all possible chocolate bars inductively? See en.wikipedia.org/wiki/Nimber – Theo Johnson-Freyd Jan 5 2011 at 18:00

1
A small point, but technically the array can't be 1x1. – Henry Towsner Jan 5 2011 at 19:00
@Theo: More easily, for any size of the bar, you can inductively determine winning and losing positions. But this task is very long and probably untractable for more than 10 rows and 10 columns, say. – Pierre Dehornoy Jan 6 2011 at 10:12

## 2 Answers

Here are two papers, from 2002 and 2007; not sure if they are new to you.

Jan Draisma and Sander van Rijnswou show in their paper, "How to chomp forests, and some other graphs" (2002), that Chomp can be completely solved when the underlying graph $G$ is a forest. From the Abstract:

Interesting consequences are: ﬁrst, that the starting player has a winning strategy for any non-empty tree; and second, that he has a winning strategy for the complete graph on $n$ vertices if and only if $n$ is not a multiple of 3.

A second relatively recent paper is, "Scaling, Renormalization, and Universality in Combinatorial Games: The Geometry of Chomp," by Eric J. Friedman and Adam Scott Landsberg (Combinatorial Optimization and Applications, Lecture Notes in Computer Science, 2007, Volume 4616/2007, 200-207). Their results resist succinct summary, but, for example, they are able to compute "the expected number of winning moves" under certain circumstances.

-

Thanks, I did not know the second paper. I will have a look. – Pierre Dehornoy Jan 6 2011 at 10:12

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

The non-constructive proof you refer to is proving a $\Pi_2$ statement, and therefore can be unwound to give an explicit proof. (This was pointed out to me by Mints, in the context of the game Hex, for which the same situation occurs.)

If the argument is what I expect it to be The strategy is to simply produce the tree of all possible moves and then label them as winning or losing (for player 1) by induction: and end-state is winning if player 2 takes the poison, a node where player 1 moves is winning if any of its children are winning, and a node where player 2 moves is winning if all of its children are winning. Roughly the same argument as in the non-constructive proof shows that the root node is winning, and so player 1's strategy is just to always move so they end up on a winning node.

(Of course, this isn't an elegant strategy, so there's still a reasonable open question there, but it is a known winning strategy in any formal sense of the term.)

-
I'd call it a known winning strategy for a fixed size of rectangle... – Cam McLeman Jan 5 2011 at 18:58
Technically, this gives a computable algorithm which transforms the parameters of the rectangle (assuming they're not 1x1) to a strategy for the game on that rectangle. Most of the strategies we consider explicit seem like they're more uniform in the parameters, in some sense, but I think you'd run into difficulty making that formal. – Henry Towsner Jan 5 2011 at 19:04

1
@Henry: This gives a (long) algorithm to determine the strategy, but you will agree that it is not very satisfying: it does not make me understand this game better or give any structure to the set of positions. Thanks nevertheless – Pierre Dehornoy Jan 6 2011 at 10:16
Here's a question that may help clarify the issue: Consider the problem of determining whether an arbitrary Ferrers shape is a first-player win. Is this problem PSPACE-complete? As far as I know, this is an open problem. (I believe that the analogous question for Hex, which also admits a similar strategy-stealing argument, is known to be yes.) If the answer is yes then that means that for general (finite) Chomp positions, there is no winning strategy in the sense of something polynomial in length that can be used to find a winning move in polynomial time, unless NP = PSPACE. – Timothy Chow Nov 22 2011 at 21:27
Note, however, that it would still be technically possible for there to be a satisfactory winning strategy for rectangular shapes, if the Ferrers shapes arising from perfect play from a rectangular starting position happened to be particularly tractable for some reason. – Timothy Chow Nov 22 2011 at 21:31
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 7, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9386307001113892, "perplexity_flag": "middle"}