52
$\begingroup$

I can get to 4096 max. There are videos on youtube of guys making it to 8192. What is the theoretical maximum limit on this?

PS: if you haven't played this, here is the link to addiction.

$\endgroup$
  • $\begingroup$ This is a bit of a plug, but I would really like to see an answer to this as well, to see how the tile is actually achieved. $\endgroup$ – Kendall Frey May 14 '14 at 22:29
  • $\begingroup$ In this answer, the algo made it to 32768 but their limitation was that 2 will appear at a predetermined position, not at a position chosen by algo. I'll see if I can design such algo and actually make it to 65536! $\endgroup$ – kBisla May 14 '14 at 22:43
  • $\begingroup$ I've done it till 131072 in practice mode, and I will post the screenshot as an answer. $\endgroup$ – Rohinb97 Oct 9 '14 at 19:51
52
$\begingroup$

In the original game, sometimes the new tile that pops up is a 4. Let's ignore that possibility for the sake of simplicity.

We've 16 squares in total and considering the new tile popped up at the position we chose, to make it to 4096, we need minimum these tiles:

2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 2

These can be combined from right to left to get to 4096. That's a total of 12 tiles. Since that's less than 16 (max number of tiles that can fit), 4096 is possible. Following along:

  • 8192: 4096, 2048, 1024, ..., 4, 2, 2 Total 13
  • 16384: 8192, 4096, 2048, ..., 4, 2, 2 Total 14
  • 32768: 16384, 8192, 4096, ..., 4, 2, 2 Total 15
  • 65536: 32768, 16384, 8192, 4096, ..., 4, 2, 2 Total 16

Next is 131072 which will require at least 17 tiles which can't fit on the board.

So, the largest possible tile is 65536.

EDIT: Since the game pops up some 4's at times, 131072 is still theoretically possible if the last tile that pops up is a 4 making the board look like this:

131072: 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 4

that's 16 tiles in total.

$\endgroup$
  • 1
    $\begingroup$ Is there an algorithm that can provably get this far, or is this just an upper bound? $\endgroup$ – Kendall Frey May 14 '14 at 22:27
  • 5
    $\begingroup$ @KendallFrey - I don't think it's possible to generate such an algorithm, since the spawning of 2 vs. 4 is random. $\endgroup$ – Xynariz May 14 '14 at 22:48
  • 2
    $\begingroup$ @Xynariz I was thinking more of an algorithm that would allow you to get this far in an optimal situation. I'm not 100% sure that it's actually possible to get a 131072 tile, even when you're lucky enough to get a 4 in the right place every time. $\endgroup$ – Kendall Frey May 14 '14 at 22:51
  • 3
    $\begingroup$ @KendallFrey It's certainly possible - if the 4 always appears in the upper-left corner, using a zig-zag strategy (i.e., fill a row with numbers arranged high to low, and if that row is full, use the next row in reverse direction) would work. The likelihood of such a solution working is obviously very low, though. $\endgroup$ – Xynariz May 14 '14 at 22:56
  • 3
    $\begingroup$ FWIW, Another way to state the same proof: $131072$ is just $2^{17}$, which means you'd need 17 tiles to hold every step. Thus $2^{16}=65536$ is the largest without 4's, and $2^{(16+1)}=131072$ is the largest with 4's. $\endgroup$ – Bobson Jun 23 '14 at 13:16
18
$\begingroup$

BlueFlame gives an essentially correct answer, but I wanted to add a rigorous proof (for anyone looking for it). [EDIT: user2357112's comment points out an annoying hole in the proof, under the "proof that 65536 is theoretically possible" section. While I believe the hole can be filled, I don't have time to do it right now.]

I will prove that 65536 is the maximum when 2 is the only tile which appears newly on the board. It is easy to adapt the proof to show that 131072 is the maximum when 4 may also appear.

1. Proof that 65536 is an upper bound.

At every step of the game, the total value among all tiles goes up by 2, or stays the same.

Suppose towards contradiction that at some point in time the 131072 tile is attained. That at this time the sum of all the tiles is at least 131072. Thus at some point in time, the sum of all the tiles was exactly 131070 (= 131072 - 2). Then at this time there was a set S of at most 16 powers of two adding to get 131070. Recursively adding together pairs of equal elements of S until all the elements are distinct (i.e., adding them as if they had combined in the game), we obtain a set R with at most 16 distinct powers of two adding to get 131070. But 131070 = 2^16 + 2^15 + 2^14 + ... + 2^1 cannot be written as a sum of anything less than exactly 16 distinct powers of two (using unique representation in binary). Therefore the set S must have initially consisted of one each of the numbers 2, 4, 8, ..., 2^15, 2^16, and the entire 4x4 grid must have been filled. But then the position would have been a losing position, i.e. no two tiles could have combined and there was no space left on the board. Contradiction.

2. Proof that 65536 is theoretically possible.

The idea is to use a strategy like this: enter image description here

Label the 4 x 4 grid with the numbers 1 through 16, with the numbers in the following pattern:

13 14 15 16
12 11 10  9
 5  6  7  8
 4  3  2  1

Call a board state "ideal" if it has the following properties: (1) the tiles that are filled are exactly 16, 15, 14, ..., k for some k, and (2) if two tiles a and b are on the board, with a located on a bigger label than b, then the value of tile a is greater than the value of tile b. This matches the general pattern of the picture above.

Then, suppose we are in an ideal state with all the tiles less than 65536 = 2^16. Since there are only 15 distinct tile values less than 2^16, there must be an open space. Then we can choose to spawn the 2 in the open space with the highest label. After this, we can recursively combine the lowest two tiles if they have equal value, by sliding left, right, or up, depending on the board state. But due to the nature of our "ideal state" strategy, the left, right, and up slides will never modify any tiles but the two lowest ones which are combining. Thus after the entire process we are left in another ideal state. [EDIT: This paragraph has a hole: it forgets to consider that a new 2 tile must spawn after each slide. One should probably be fine if the new 2 tile always spawns, as the first 2 tile, in the open space with the highest label. But the reasoning gets a bit more complicated.]

We will be able to follow this strategy continually as long as there is no 65536 tile on the board. Moreover, the total value of all values on the board will do nothing but increase. Therefore, at some point we will either reach a 65536 tile, in which case we will be done, or we will reach an ideal state with the total value of all tiles equaling at least 65536. Since no set of unique tiles less than 65536 can add to 65536 or more, and since an ideal state contains unique tiles, this is a contradiction and we will necessarily reach the 65536 tile at some point.

$\endgroup$
  • $\begingroup$ Won't tiles spawn while you're merging pieces to preserve the ideality invariant? It takes 5 moves to merge 2+2+4+8+16+32 into 64, and those moves aren't going to do the right thing with the tiles that are spawning in the meantime. $\endgroup$ – user2357112 Oct 28 '15 at 21:44
  • $\begingroup$ @user2357112 Thanks for your comment--I didn't notice it before. You're correct, and I don't see an easy fix :( So I indicated that in the answer. Maybe a better way to prove it's theoretically possible would be to write a computer program to find a sequence of moves that works. I suspect since the program gets to choose where the 2 is placed, it would not have too much trouble reaching 65536 if it follows this general strategy. $\endgroup$ – 6005 Jan 24 '16 at 15:55
10
$\begingroup$

Okay, so I actually made it this far (no photoshop or anything, just a secret trick and play endlessly without any hassle. It works for long time also on normal mode, until you make a mistake).

enter image description here

No more possibilities...

EDIT: So someone did ask me for the "trick", so here it is:

First, always corner your highest tile. This is very important, as this gives you the maximum space to play the game. Since all the middle tiles are surrounded by 4 tiles, the corner tiles are the ones which have minimum contact with the other tiles. If your highest tile is somewhere in the middle, it only acts like an obstruction, so keeping it aside is the best move. Like in the above screenshot, 131072 is in the top left corner.

Ordering your tiles is also a good strategy. Like see how I have ordered my tiles in descending order. It creates minimum wastage of big tiles and less blockage for small tiles.

Secondly, "stick" to a wall. This is the trickiest part. Like seriously, stick to the side of a chosen wall. I had chosen the top wall. Try not to disturb the tiles along the wall. For example for sticking to the top wall, do not swipe down. It works since once your tiles are made, and as you progress, not only the biggest tile will obstruct, but also the tiles just before it also do it's job. Also sticking to a wall makes way for smaller tiles and they could be merged and made off into bigger tiles more easily. This ensures uniformity and a clean game.

The above, although a logically great option, does not work pretty well in normal mode. I was only able to get 8192 by it. Just ensure the chances of getting stuck in a case where the only option is to swipe down is minimum. Play accordingly in normal mode. Practice mode has no such hassle, so it's all good :)

Another thing to ensure is blocking. Never block a tile and make it useless. Remember, unusable spaces are the steps to defeat. Moves will always be available if none of your tiles are blocked. For example, if a 2 gets cornered, on the top right and you stick to the upper boundary, do not make your 2 just sit there. Merge it first and ensure this with other tiles. No tile should block your flow.

I personally prefer to use minimum number of undos, but sometimes when the only move is to go down, or when things go tight and in order to go further and create a tile, you do have to undo. That is the luck part which gets eliminated in practice mode. In normal mode just try to play perfectly and follow your strategy. Your score in normal mode is literally pot luck.

$\endgroup$
  • $\begingroup$ What's the secret trick? $\endgroup$ – PopularIsn'tRight Nov 6 '14 at 18:52
  • 1
    $\begingroup$ First, ensure you biggest tile is in the corner. This will ensure maximum no. Of playable moves and you won't get blocked easily. Secondly, ensure you "stick" to a wall. Like to stick to the upper wall, don't swipe down, at all costs. And last and foremost, never let a tile of lower number be blocked by some high numbers, like never block it and make the space unusable. Preferably, try to make the tiles in descending order, like the one I showed. It's all logical. $\endgroup$ – Rohinb97 Nov 7 '14 at 17:18
  • $\begingroup$ Let me put all this in this answer. $\endgroup$ – Rohinb97 Nov 7 '14 at 17:19
  • $\begingroup$ @Bachrach44 see it here. $\endgroup$ – Rohinb97 Nov 7 '14 at 17:50
  • 2
    $\begingroup$ You should really make it clear at the top that you aren't actually playing normal 2048. Practice mode with undos is cheating. $\endgroup$ – 6005 Oct 28 '15 at 20:54
3
$\begingroup$

My brother used to play this game for a long time. He also used to play in practice mode (so he could undo his last move). When I saw this question, I asked him if he could send me a screenshot of his best result. This is what he sent me (no cheating or photoshop):

result 1

$\endgroup$
  • 2
    $\begingroup$ Although interesting, this doesn't prove anything. I don't doubt this board, personally (the scores look reasonable, as it's expected to be around 17*2^17), although being able to undo means you basically can sort of force any tile to appear at your desired position, by repeating it many times. =) $\endgroup$ – justhalf Oct 2 '14 at 13:44
  • $\begingroup$ There's video's around aswell. youtube.com/watch?v=8H0nDr9B2uQ $\endgroup$ – Tim Couwelier Oct 2 '14 at 13:58
  • $\begingroup$ @justhalf ...It proves that the statement (maximum is 65536) in other answers is false. $\endgroup$ – Memet Olsen Oct 2 '14 at 14:16
  • $\begingroup$ Hmm, fair enough. +1 for you =). This requires sheer luck, if played in the original game, though, since as @BlueFlame mentioned in his answer, you need to get 4 as the last tiles (not to mention the difficulty to get there). $\endgroup$ – justhalf Oct 2 '14 at 18:37
  • 2
    $\begingroup$ @MemetOlsen The answers that gives 65536 explicitly states that they assume that only 2's enter the board. I think all of them notes that if you figure in the possibility of a 4 at the right time then the answer is 131072 $\endgroup$ – Taemyr Nov 6 '14 at 15:24
3
$\begingroup$

We can simplify 2048 by discarding the layout and focusing on a multiset (or bag) of tiles. We can do this, if we assume that a new tile will always appear in a position that is most advantageous to us.
We can then define two rules to make a new bag out of the current one (we also ignore the possibility of getting 4s for simplicity's sake):

  1. Combine one or more pairs of tiles of equal value into tiles of double that value.
  2. Add a 2-tile if there's an empty slot.

Rule 1 is optional, rule 2 is mandatory. If rule 2 fails, we stop.

With this, we can see that for a bag of maximum size 3, we have the following states:

{} → {2} → {2,2} → {2,2,2}
             ↓        ↓
           {2,4} → {2,2,4}
                      ↓
                   {2,4,4}
                      ↓
                   {2,2,8}
                      ↓
                   {2,4,8}

For a bag of maximum size 4, we build from this:

{} → {2} → {2,2} → {2,2,2} → {2,2,2,2}
             ↓        ↓          ↓
           {2,4} → {2,2,4} → {2,2,2,4}
                      ↓          ↓
                   {2,4,4} → {2,2,4,4}
                      ↓          ↓    ↘
                   {2,2,8} → {2,2,2,8}  {2,4,4,4}
                      ↓          ↓    ↙
                   {2,4,8} → {2,2,4,8}
                                 ↓
                             {2,2,8,8}
                                 ↓     ↘
                             {2,2,2,16}  {2,4,8,8}
                                 ↓     ↙
                  {2,4,16} → {2,2,4,16}
                                 ↓
                             {2,4,4,16}
                                 ↓
                             {2,2,8,16}
                                 ↓
                             {2,4,8,16}

To allow for more than one pair of tiles combining, imagine a couple of diagonal arrows from {2,2,2,2} to {2,4,4}, from {2,2,4,4} to {2,4,8}, and from {2,2,8,8} to {2,4,16}.

From this, we can infer that for a table of size $n$, the maximum value attainable is $2^n$. For a standard 2048 game, assuming only 2-tiles appear, this means the maximum tile value is 65536. If we allow 4-tiles, 131072.

†: Drawing those arrows isn't easy and would've made for a less clear diagram.

$\endgroup$
  • 1
    $\begingroup$ Maybe you are just making it harder than you need to with your diagram :P $\endgroup$ – martijnn2008 May 17 '14 at 8:50

protected by Aza Mar 13 '16 at 4:29

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

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.