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.

I'm trying to figure out the fewest number of moves one could make to win the game 2048. In another thread, someone placed the figure at 520, but I'm wondering if anyone knows how to mathematically approach this problem given the game's statistical/probabilistic complexities.

share|improve this question
    
Can we assume that the new $2$'s or $4$'s are dropped where and when we need them to be? –  ABC Mar 26 at 18:34
    
I'd assume since you are looking for a lower bound of moves you get perfect luck. –  ruler501 Mar 26 at 18:36
    
Sure, assuming a perfect game. –  user138217 Mar 26 at 18:36
    
Then is just a matter of counting: $4$, $4$, $4$, $4$,... –  ABC Mar 26 at 18:38
    
Can you also privide/link to the rules? How does the game begin etc. –  ABC Mar 26 at 18:38

6 Answers 6

Informal idea: Only 4's arrive, so $2048/4=512$ and since you start with a block out, its actually $512-1=511$ have to arrive and the last one needs to be combined $\log_22048/4$ (9) times to make the final 2048 block so a minimum of 520 moves are required, if a perfect game comes up and its perfectly set up when that last 4 comes out, so yes, $520$ is the validated absolute minimum.

share|improve this answer
    
But it's not strictly linear counting, is it? I mean, if you spawn a four, then it combines with another four to make eight, then you spawn a four and another four and it combines to make another eight, then the eight and eight make sixteen. This can be done, I think, in three moves? –  user138217 Mar 26 at 19:17
    
@user138217 no because 4 fours have to be spawned. The only thing he got wrong is that you start with 1 tile so its $521-1=520$ moves minimum. –  ruler501 Mar 26 at 19:19
    
I believe this is overstating the minimum, because multiple blocks can be combined in one move –  qwr Mar 26 at 21:36
    
@qwr yes you can join more than one at once, but if you join them together quickly, the new blocks appear no more often, so how quickly you match them has no impact. To get the 511 needed blocks to appear, you need to make 511 moves. Simple as that –  Asimov Mar 26 at 21:40
    
@JohnJPershing How are you counting moves? You are given a block before your move starts so wouldn't it take $n-1$ moves to get $n$ blocks? –  ruler501 Mar 27 at 5:29

Informal idea: In a completely perfect game, only $4$s appear, and they appear in a way in which every step you can combine greedily and add $4$, so I'd say $2048 / 4 = 512$.

share|improve this answer
    
I think this might be too low of a boundary. I'd be interested in seeing someone draw out the procession this would form. –  ruler501 Mar 26 at 18:56

has anyone taken into account the geometric constraint of the box? we have a 4x4 box, if 4's continually come, you can collapse them obviously into 8's into 16's into 32's, but the box geometry isn't infinite, if you have a 256 in the corner, then say a 128 next to it 64 next to that, if a 4 is produced that won't collapse into 64. Now, there is still probability that a new block will be created so that it collapses the 4--> 8, but then another will appear.

It seems that this thread has only taken into consideration as if the block had no bounds, and then it seems that 510 is the correct answer (although I've never seen proof that it is the absolute shortest algorithm to get to 2048

share|improve this answer

Now we will have to assume that all numbers are spawned as '4' to create as few moves as possible.

Let's start with small numbers first.

Creating an '8' will require 1 move (2^0).

Creating a '16, 2^4' will require 3 moves (2^0+2^1)

Creating a '32, 2^5' will require 7 moves (2^2+2^1+2^0)

And so on.

Creating a '2^n' will require (2^(n-3)+...) moves.

You will then realize that the number of moves required is a summation of a geometric sequence.

sigma (2^k). The lower limit will be 0, the upper limit being the 7.

Using a summation calculator you will receive the answer 255.

share|improve this answer

The lowest possible number of moves to win is 519, assuming a perfect game with all 4s appearing:

2048/ 4 = 512 // all fours appear

512 - 2 = 510 // two tiles start before the first move

510 + 9 = 519 // the final endgame summation after the final 4 is placed, to add all tiles together and get the 2048. Two fours become an 8 (move 1), two eights become a 16 (move 2), two sixteens become a 32 (move 3), two thirty-twos become a 64 (move 4), two sixty-fours become a 128 (move 5), two 128s become a 256 (move 6), two 256s become a 512 (move 7), two 512s become a 1024 (move 8) two 1024s become a 2048 (move 9).

I had also calculated the lowest probable and average number of moves, which I'm actually going to recalculate today because I had assumed a 50/50 distribution of 2's and 4's appearing, which it isn't. On the original game it's a 90/10 distribution, which changes my lowest probable and lowest average scores. I should have a video up with all of the numbers and they were derived within the next week on my YouTube Channel.

share|improve this answer

I did some math here that determines the number of combinations required given a spawn ratio of 2- to 4-tiles. It doesn't address the number of moves required, but given the number of available tiles for movement, I'm sure it could be adapted for your purposes here.

share|improve this answer

protected by Asaf Karagila May 24 at 17:06

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.