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.
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.
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
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.
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.
protected by Asaf Karagila♦ May 24 '14 at 17:06
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?