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$?