Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
$\sum_{i=1}^{n} 2^i = 2^{n+1} - 2$ fyi –  Flowers Mar 18 at 6:03
1  
Yes, I am aware of this. –  Isaac Mar 18 at 22:10
    
How is the score computed from the move sequence? –  Peter Taylor Mar 22 at 20:10
    
If you're asking about my game and not 2048: Score is equivalent to 2x the number of put moves, since only these moves change the board total. –  Isaac Mar 22 at 22:42
    
How do you define score? The sum of the values on the board? –  DanielV Apr 5 at 3:11

9 Answers 9

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.

share|improve this answer
    
How do we know that is the optimal board? For instance, why couldn't we have a bunch of $65536$s in the right-hand column? (Dumb question, but I'm just not seeing right now...) –  anorton May 2 at 21:14
1  
@anorton I believe this might clear things up: how would you go about getting to the board you are describing in the first place? ;) –  Just_a_fool May 2 at 21:30
2  
@anorton In order to create the number $2^n$, you must have all the numbers from $4$ to $2^{n-1}$ present on the board simultaneously, plus another $4$ to set them off. So if you are to make $2^16$, that means that 14 squares must take up the space $2^2$ to $2^15$ plus the extra $4$ tile. So you can have at most 2 $2^16$ tiles on the board. –  DanielV May 2 at 23:38
    
@DanielV I'm having the same trouble as Just_a_fool. You could, say, form a 4096 from 2 2048s already on the board. –  YatharthROCK Aug 14 at 13:37
    
@YatharthROCK But you could not create the second 2048 without first having two 1024, but you could not create the second 1024 without first having two 512, but... and so to create 4096, at some point you have to have a board that contains every $2^i < 4096$ –  DanielV Aug 19 at 13:14

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

share|improve this answer
2  
The key assumption you make (but do not prove) is about the optimal strategy to produce a block of size $2^k$. I believe you, but the purpose of my question was to come up with a proof. Paragraphs 2-6 seem to be about calculating the "score" in 2048. I didn't ask about this because I don't think it is relevant to the core topic. –  Isaac Mar 18 at 22:09
    
Also, since you are talking about the original game, you have not proven that your strategy is achievable to fill the entire board, even if the user controls both sides of the game. –  Isaac Mar 18 at 22:11
    
For now, think of what I said as an upper bound, and I will prove/disprove whether this situation is actually achievable later on since it's a bit technical. To prove the upper bound, define $a_n$ to be the # of blocks needed for a size n block. You have a recursive definition of $a_n = 1 + a_{n-1}$ or $a_n = 2 + a_{n-1}$. The first option is if you make one n-1 block first and then the other, and the second is if you create them both at the same time. The first option is clearly optimal for every n, so $a_n = 1 + a_{n-1}$. And $a_2 = 1$. Solving the recurrence gives you the upper bound. –  Flowers Mar 19 at 5:03
    
..you asked for the score in bold in you question. –  Flowers Mar 19 at 5:06
    
Yes, the score of the new game which is defined to be the sum. –  Isaac Mar 19 at 5:32

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.

share|improve this answer
    
Thanks. The main difference in my alternate game is that the proof didn't have to focus on layout of the board, it can assume that there is a layout to achieve a merge strategy. –  Isaac May 2 at 21:37

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.

share|improve this answer
    
That's a good upper bound, but can you prove that that's attainable? (Also, it actually has to be 262140, because you can have 4 8 16 32 48 64 128 ... up to 131072 on the board.) –  Joe Z. Mar 24 at 16:46

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...

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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$

share|improve this answer
    
David, your argument goes in the right direction (of course! :-). However, when your maximal tile is attained then by this time some other tiles are already advanced. Thus they may exceed the given so-to-speak previous maximal tile. A few extra words would take care of this objection. (See my post on OM :-). –  Włodzimierz Holsztyński Aug 19 at 19:04

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

share|improve this answer
    
That does not answer the core of the question. –  NasuSama Apr 4 at 23:35

protected by Alex Becker May 2 at 23:26

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.