Maximum board position in 2048 game

Solution 1:

An optimum board just before the last number is played on 4x4:

$$\begin{array} {|c|c|c|c|} \hline & 256 & 512 & 65536 \\ \hline 4 & 128 & 1024 & 32768 \\ \hline 8 & 64 & 2048 & 16384 \\ \hline 16 & 32 & 4096 & 8192 \\ \hline \end{array}$$

... and then a 4 luckily falls into the empty square giving the largest number that can be created is $2^{17} = 131072$ . The fact is, in order to make a number $2^n$, then you have to have all the numbers $[4 \dots 2^{n-1}]$ already present on the board.

The largest number that can be made is then $2^{\left(n^2 + 1\right)}$, or if you assume that no 4s will fall, then it is $2^{\left(n^2\right)}$.

Such a board position can be easily constructed by always having an increasing sequence in the nonempty squares of the path starting at the top left:

$$\begin{array} {|c|c|c|c|} \hline \downarrow & \rightarrow & \downarrow & \circ \\ \hline \downarrow & \uparrow & \downarrow & \uparrow \\ \hline \downarrow & \uparrow & \downarrow & \uparrow \\ \hline \rightarrow & \uparrow & \rightarrow & \uparrow \\ \hline \end{array}$$

and then having the next number fall on the last empty square of the path.

Aside, this turns out to be a very effectively strategy for playing the game with non-optimal drops as well.

Edit: James Grime to the rescue again. He made a fairly entertaining youtube video to address this question.

Solution 2:

To start, let's find the largest possible number that can enter the game. And to make life easier, let's work with the log of the numbers.

For a number $n$ to be reachable, the smallest group of blocks to have to exist at at least one time frame must be $n-1, n-2, n-3,...2,2,$ where 2 is a 4 in the game (Since 4's are the largest number that can be generated). That means that to make an n block there must be n-1 free cells.

Therefore, for an $m\times m$ board the largest number can be $m^2 + 1$. With the same reasoning, the maximum board will be filled with $m^2 + 1, m^2, m^2 - 1,...,3,2.$

Each block on the board is made by adding two other blocks. Skipping the calculation, for a block of worth $2^k$, the maximum points made for the block is $(k-1)2^k - 4$. If you observe how the points are being made, this is easily reachable.

Therefore the maximum score that can be made is $-4m^2+\sum_{i=1}^{m^2} i\cdot2^{i+1}$.

To simplify, $\sum_{i=1}^{n} i\cdot 2^{i+1} = (n-1) 2^{n+2} + 4$. This can be proved by induction.

With that, the maximum score is $-4m^2 + (m^2-1)2^{m^2+2}+4 = (m^2-1)2^{m^2+2} - 4(m^2-1) = 4(m^2-1)(2^{m^2}-1)$