Counting multidimensional structures (Chomp game states)
The game Chomp is described as follows on Wikipedia:
Chomp is a 2-player game of strategy played on a rectangular "chocolate bar" made up of smaller square blocks (rectangular cells). The players take it in turns to choose one block and "eat it" (remove from the board), together with those that are below it and to its right. The top left block is "poisoned" and the player who eats this loses.
I am interested in counting the number of possible game states, including the initial game state where all the chocolate is left, and the end-game state where all the chocolate is gone.
$2$-dimensions
In the 2-dimensional case, this is possible using the following observation:
We will visualise a game board as follows:
$$ \begin{array}{|c|c|c|c|}\hline x & x & x & x\\ \hline x & x & x & x\\ \hline x & x & x & -\\ \hline -& - & - & -\\ \hline \end{array} $$
where $x$ denote the remaining blocks, and the $-$ corresponds to removed blocks. Any 2-dimensional game state, is characterised by the cells on the boundary of the remaining cells (the cells which are adjacent - either directly or diagonally - to a removed cell or the bottom or right side of the board). Here are some examples of game states, with boundary cells highlighted
$$ \begin{array}{|c|c|c|c|}\hline x & x & x & {\bf x}\\ \hline x & x & {\bf x} & {\bf x}\\ \hline {\bf x} & {\bf x} & {\bf x} & -\\ \hline -& - & - & -\\ \hline \end{array} \quad \begin{array}{|c|c|c|c|}\hline x & x & x & {\bf x}\\ \hline x & x & x & {\bf x}\\ \hline x & x & x & {\bf x}\\ \hline {\bf x} & {\bf x} & {\bf x} & {\bf x}\\ \hline \end{array} \quad \begin{array}{|c|c|c|c|}\hline - & - & - & -\\ \hline - & - & - & -\\ \hline - & - & - & -\\ \hline - & - & - & -\\ \hline \end{array} \quad \begin{array}{|c|c|c|c|}\hline x & {\bf x} & {\bf x} & -\\ \hline x & {\bf x} & - & -\\ \hline {\bf x} & {\bf x} & - & -\\ \hline {\bf x} & - & - & -\\ \hline \end{array} $$
In turn, such a boundary corresponds to a special walk on the grid graph constructed by letting each cell be a vertex, and by joining vertices corresponding to adjacent cells (note that the end-state corresponds to the empty walk). These walks start in the left-most column of the grid graph, and end in the top row of the grid graph. Using this bijection from game states to such walks, we compute the number of game states as follows: The number of game states in a 2-dimensional chomp-game with $n_1$ rows and $n_2$ columns is given by
$$ 1 + \sum_{d_1 = 1}^{n_1} \sum_{d_2 = 1}^{n_2} \binom{d_1 + d_2 - 2}{d_1-1}. $$
which is based on the number of staircase walks.
The plus one takes care of the end-game state. For example, plugging in $n_1=n_2=2$ gives us $$ 1 + \sum_{d_1 = 1}^{2} \sum_{d_2 = 1}^{2} \binom{d_1 + d_2 - 2}{d_1-1} = 1 + \binom{0}{0} + \binom{1}{0} + \binom{1}{1} + \binom{2}{1} + = 6 $$
which corresponds to the game states $$ \begin{array}{|c|c|}\hline x & x\\ \hline x & x\\ \hline \end{array} \quad \begin{array}{|c|c|}\hline x & x\\ \hline x & -\\ \hline \end{array} \quad \begin{array}{|c|c|}\hline x & -\\ \hline x & -\\ \hline \end{array} \quad \begin{array}{|c|c|}\hline x & x\\ \hline - & -\\ \hline \end{array} \quad \begin{array}{|c|c|}\hline x & -\\ \hline - & -\\ \hline \end{array} \quad \begin{array}{|c|c|}\hline - & -\\ \hline - & -\\ \hline \end{array} $$
$\geq 2$-dimensions
Now my question is, how do we count the number of game states for chomp games with dimension $\geq 2$? Does the idea of shortest paths on the multidimensional lattice graph generalise? Is there a simple closed formule for the number of Chomp game-positions in a $k$-dimensional game of size $n_1 \times \ldots \times n_k$? What about the simple case of a $k$-dimensional game of size $2 \times 2 \times \ldots \times 2$?
combinatorics combinatorial-game-theory combinatorial-geometry
davidlowryduda♦
76k77 gold badges124124 silver badges264264 bronze badges
utdiscantutdiscant
$\begingroup$ Have you tried calculating some small examples and looking up the results in the Online Encyclopedia of Integer Sequences? Or just type "chomp" into the site - it comes up with 25 sequences. I haven't checked to see if they include what you want. $\endgroup$ – Gerry Myerson Sep 28 '12 at 5:52
$\begingroup$ I have not been able to find anything on oeis. I have found the number of $2 \times 2 \times 2$ games, to be equal to 20. $\endgroup$ – utdiscant Sep 28 '12 at 6:12
$\begingroup$ In the two-dimensional case, I think you're counting Young diagrams, see en.wikipedia.org/wiki/Young_tableau I would not be surprised to find that work has been done on generalizing Young diagrams to higher dimensions. $\endgroup$ – Gerry Myerson Sep 28 '12 at 6:25
$\begingroup$ Isn't you some for the two-dimensional case equal to $\binom{n_1 + n_2}{n_1}$? I think, you can see it if you add a leftmost column and a top row and count the staircase walks from left bottom to right top corner. $\endgroup$ – martini Sep 28 '12 at 7:27
$\begingroup$ @martini Nicely spotted, you are absolutely correct. This makes me believe in a simple formula for the $d$-dimensional case even more. $\endgroup$ – utdiscant Sep 28 '12 at 7:50
If $C_n$ is a linear order with $n$ elements, each state in the $n_1\times n_2\times\ldots\times n_m$ game is uniquely determined by an antichain in the product partial order $C_{n_1}\times C_{n_2}\times\ldots\times C_{n_m}$. The number of antichains in $C_2^m$ is the $m$-th Dedekind number, which is known explicitly only for $0\le m\le 8$:
$$2,3,6,20,168,7581,7828354,2414682040998,56130437228687557907788$$
The Wikipedia article gives a (fairly useless!) exact formula that is a summation of $2^{2^m}$ products and some asymptotic results. This is OEIS A000372, where more references can be found. The generalized Chomp problem seems likely to be at least as intractable, despite the nice result for $m=2$.
Brian M. ScottBrian M. Scott
Not the answer you're looking for? Browse other questions tagged combinatorics combinatorial-game-theory combinatorial-geometry or ask your own question.
Counting board states in a game?
Counting multidimensional lattice paths
Exceptional values in a combinatorial game
Computation of a 3-dimensional game matrix
How to prove this formula for counting sub-sequences?
Variation to Chomp game
Ways to place n distinguishable objects in k non-distinguishable sets.
Cyclic Partisan Nim Variant
Drawing balls from an urn or counting certain posets
Classifying and counting multidimensional arrays