MathB.in - Share Mathematics with LaTeX and Markdown

A quick upper bound estimates on number of states of the 2048 game.

1. We can divide all numbers by $2$ to get the 1024 game instead.
3. An upper bound of at most 8094 moves before the game ends or you win. This number can be improved but it's not that important. The mass concentrates before 3000 moves.
4. There are 8 symmetries. I assume for most board, it is counted 8 times if we ignore symmetry. (really no mood for burnside's lemma)

The idea is we will count the number of boards where the sum of the value of elements on the board is $i$. Let $a(i)$ be the number board with value $i$.

\[ \sum_{i=2}^{8094} a(i) \]

We can consider how many ways $i$ can be expressed as 16 powers of $2$., and then try to count how many boards can there exist with such expression.

Say, $i=\sum_{j=0}^9 s_j 2^{j}$ where $\sum_{j=0}^t s_j \leq 16$. It induces a vector $(s_{-1},s_0,\ldots,s_9)$, where $s_{-1}=16-\sum_{j=0}^9 s_j$. It is called a solution. The set of all solution for a particular $i$ is $S(i)$. We let $p( (s_{-1},\ldots,s_9))$ to be $\prod_{j=-1}^9 s_j!$. An obvious number of boards that uses the values in a solution $s$ is just $16!/p(s)$. Thus

\[ \sum_{i=2}^{8094} a(i) \leq \sum_{i=2}^{8094} \sum_{s\in S(i)}16!/p(s) = 45949729863572160\sim 4.5\times 10^{16}\]

Due to some symmetries, we assume we count most elements $8$ times. So I have an upper bound of the number of states to be around $6\times 10^{15}$. I feel the real number of reachable board position might be smaller than $10^{15}$. Many of the board we counted are not valid. For example, we never considered...

1. No 2 elements can just floating around. 
2. There will always be either a 2 or a 4 on the board.

The calculation is done by mathematica. I'm still not pro with mathematica.

A[i_] := Map[Last, Map[Tally, IntegerPartitions[i,16, 2^Range[0, 9]]], {2}];
    F[t_] := 16!/((16 - Total[t])! * Apply[Times, Map[Factorial, t]]);
    X = Table[Total[Map[F, A[i]]], {i, 1, 8192}];
    Total[X]

Wed, 12 Mar 2014 17:18 GMT