Maximum board position in 2048 game

Question

A game called 2048 is making rounds on social media. I am trying to determine the maximum score attainable for this game. Let's assume WLOG that only 2s are returned (if 4s are possible the max score is doubled).

First, I'll relax some of the rules to create a game, $\mathcal{G}$, that can achieve a score at least as high as the original, 2048 game. A run $R$ of $\mathcal{G}_n$ consists of a sequence of moves $m_1,\ldots,m_k$ which manipulate a multiset, $\mathcal{S}$ of maximum size n. Each $m_i$ is either:

• a put $p$, which inserts a 2 into $\mathcal{S}$, or
• a merge, $\alpha_i$, which replaces two $2^i$ elements from $\mathcal{S}$ with a single $2^{i+1}$ elt.

I allow sequential moves of the same type because 2048 allows multiple merges or no-merge turns. The score of a position is the sum of $\mathcal{S}$.

What is the maximum score possible on a game of order n?

Note: The final position must have only unique values, else a merge and put would be possible in increase score.

I claim it is $\sum_{i=1}^{n} 2^i$, but couldn't come up with any good induction arguments. It's pretty easy to prove that an element $2^k$ is producible in a game $\mathcal{G}_k$, but proving an upper bound for production got a bit hairy, and also doesn't cover the full space.

Answer 1

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

Answer 2

I think you can build Flowers' maximal-score board by induction pretty easily (given that we control placement in this game). First, just to set this up, let's agree that:

1. (WLOG regarding which side/corner is used) a maxed out board will have its highest value in the top/left corner, sequentially decreasing values going right across the top row, then the next step down in the sequence underneath the rightmost entry of the second row, sequentially decreasing values to the left along the second, etc (let's call this a snaking pattern)

2. $2^{n^2}$, the highest value on a square ($n\times n$), can be obtained from an initially empty grid (this is obvious since moving only left/right within a single column will get you up to $2^n$, then move them all to the right and then stack them).

Once we agree on point 2, then all we really need is the induction hypothesis: - $2^{(n-1)^2}$ can be obtained on an initially empty $(n-1)\times(n-1)$ subgrid.

So when you put the $2^{n^2}$ in the top left there's plenty of room left to start building the next component of the snake (namely, $2^{(n-1)^2}$) since a full $(n-1)\times(n-1)$ subgrid remains, plus an additional $(n-1)$ squares across the top and left edges.

Oh yeah, and for the base case (a $2\times2$ grid) it isn't hard to figure out on your own (I did it on paper to be sure, there's just no convenient format for me to write out the procedure).

EDIT: I forgot to mention this, but under your rules it seems that we are not forced to alternate between a left/right/up/down move versus a tile placement, correct? This means that, for example, I can start by filling a row with 2's and then just shifting them all together with several moves to the right in sequence.

Answer 3

Isn't it theoretically possible to get 131072? 16 squares on the board. 2^16 = 65536 Add one power to 2 because the highest possible starting piece is 2^2 instead of 2^1.

Answer 4

I'm not sure, but I think there may be a difference in meaning of "score" in the above discussion. "Score" to most people means the points earned by merging blocks, whereas Isaac appears to be using the word to mean the maximum value shown on a single block. I will use the majority definition. And I apologize for not having quick and handy access to all the symbols and superscripts; please bear with me.

To answer Saryu first, yes, for the standard game (Isaac's game uses only 2's, so 2^16 is the maximum block value for his game). 2^17 is reachable if and only if a 4-block appears instead of a 2-block when the board reaches its maximum state for the 2^16 pattern, thus allowing another series of merges to occur.

Unfortunately, I can't offer a rigorous proof, but I can offer my numbers and let you folks make of them what you will. I will primarily discuss the standard game, of which Isaac's variant could be considered a subset as it does not include 4-blocks.

The block values on a maximum board (m = n^2 = 16) are established as 2^(m+1), 2^m, 2^(m-1)...2^3, b (either a 2 or 4).

The maximum score value of a given block valued 2^k, according to my reasoning, is (2^k)(k-1). Since either I'm misreading Flowers's formula or I've reached a different conclusion, I reason as follows: since score is gained each time blocks are merged, the maximum number of merges to create a block of 2^k would be done with blocks of size 2, and would be 2k-1. To derive score, imagine a line of 2-blocks long enough to add up to the desired 2^k value, and then take them through successive pair-merges (merging each pair of adjacent blocks throughout the line in a single operation) until you end up with the single block of 2^k. Each of these pair-merges would score 2^k points. The number of pair-merges required would be (k-1).

A brief example to illustrate k=3: a line of 2222 is pair-merged to 44 (each 4 scoring 4 points, total 8), and then pair-merged again to 8 (scoring 8 points). Each pair-merge was worth 2^k points, and k-1 of them occurred, thus (2^k)(k-1) for the total score value of 16.

Since in the real game merges may only occur of equal blocks, and since each 2^k value must be built up by successive merges, I cannot find any logical reason why this method does not derive the maximum possible score value for a given 2^k block. However, since 4-blocks sometimes appear in the game, the actual score obtained may be lower...in fact, it will be 4 points lower for each 4-block which appears, since no points will be obtained for the creation of that 4-block from a pair of 2-blocks. If my reasoning thus far is correct, the maximum score value for the official game's maximum block size (k=17) is thus 2097152. For Isaac's variant (k=16) it would be 983040.

From that basis for maximum possible score of a single block, and knowing the maximum board position, we can then sum the maximum scores of each block on that board to obtain a maximum possible score for the entire board. I admit that at this point I "cheated" and used Excel to do totals and then deduced the formula therefrom, but I think the conclusions are still valid.

For Isaac's version, the sum for k=2...m of (2^k)(k-1) equals (2^k)(2k-4)+4, or 1835012.

For a standard board, the sum for k=3...m+1 of (2^k)(k-1) equals (2^k)(2k-4). This is 3932160, which I assure you is a far higher score than I've ever obtained. However, this sum neglects the fact that for the k=17 block to occur, a 4-block must (as stated earlier) have appeared at a particular point, and since each 4-block reduces the score by 4 points, the actual value is (2^k)(2k-4)-4, or 3932156. Which is still a lot higher than I'm ever going to score...

Answer 5

Here are my 2 pence if I have correctly understood what Isaac meant by score. I would restate its definition to avoid any unnecessary confusion. Let's denote by $S_{\tau}$ the multiset at stage $\tau$ of the game. Isaac defined score as "The score of a position is the sum of $S$"; so score $s(S_{\tau})$ of the game is the sum of elements of $S_{\tau}$. In my version of the game a 1 s inserted into the system instead of a 2 but this only ends up in reducing the maximum to its half. So Isaac's claim amounts to proving the maximum is $\sum\limits_{i=0}^{n-1}2^i = 2^n - 1$. WLOG assume $S_2$ consists of 2 1's (this might require shifting the index $\tau$ but that doesn't matter). In the same vein I let $\tau$ increase only when a put is inserted. So score $s(S_{\tau})$ is simply $\tau$. Let's now examine $S_{2^n-1}$. If the game reaches a stalemate before this stage then the upper bound is obvious, so suppose instead we reach this stage. In this case $s(S_{2^n-1}) = 2^n - 1$. We just need to prove this position must be a stalemate i.e. all the elements are different and cardinality of $S_{\tau}$ is $n$. For if not you could have a binary representation of $2^n - 1$ with fewer than $n$ 1's!! Next to the point of attaining the bound. Just carry on binary addition by 1 until you reach $11\ldots1$ ($n$ times) i.e. $2^n-1$ in base 2! This works because "carry-forward" in binary addition corresponds to merging two $2^i$'s to one $2^{i+1}$ and the $0$ we would get by the carrying forward corresponds to a slot emptied. Finally notice there will always be at least one $0$ in the $n$ digits binary expansion of $m$ as long as it is less that $2^n -1$.

I am not sure how much this adds to the repertoire :)

Answer 6

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.

Answer 7

For highest score i calculated 3,932,060 , largest tile 131072 & for a game without 4's appearing it would be 1,834,972 largest tile 65536

Answer 8

When you start the game, you have $16$ rooms for moving the new coming numbers.But as you make your max number becomes bigger, the amount of available rooms decreases.To create an $8$, you may need $3$ rooms to get $4$, $8$.And to create a $32$, you may need $5$ rooms to get $4$, $8$, $16$, $32$ in the correct order.

So when the max one reaches $2^{16}$, $16$ rooms are needed. But since all the rooms are dedicated to $2^{17}$, you have no more rooms to get new coming numbers away. It is game over by then.

Answer 9

Maybe I'm missing the answer that did this, but I don't see a clean proof anywhere on this thread that $2^{16}$ is best possible, assuming that only $2$'s drop. So here one is. Forget about the geometry of the board, and just imagine $n$ slots for tiles. On each turn, we pick up two equal tiles of value $2^k$ from two of the slots and replace them by a single tile of value $2^{k+1}$. New tiles enter the board, always with value $2^1$.

Claim This procedure can never create a tile of value more than $2^n$.

Proof: By induction on $n$. In the base case, $n=1$, there is no combination so we just start with the initial $2^1$ tile.

Now suppose that the result is proved for $n-1$, and we are looking at a board of size $n$. We must show that we cannot make $2^{n+1}$. Consider the moment we make our first $2^n$. After this moment, we cannot get rid of that $2^n$ tile until we make another one. So there are only $n-1$ slots on the board which can be used to make the $2^n$ tile. By our inductive claim, we can't make $2^n$ using $n-1$ slots, so we can never make a second $2^n$ tile, and thus we can never make any $2^{n+1}$ tile. This concludes the induction. $\square$