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 have recently played the game 2048, created by Gabriele Cirulli, which is fun. I suggest trying if you have not. But my brother posed this question to me about the game:

If he were to write a script that made random moves in the game 2048, what is the probability that it would win the game?

Combinatorics is not my area, so I did not even attempt to answer this, knowing this seems like a difficult question to answer. But I thought someone here might have a good idea.

Also, since we are not concerned with time, just with winning, we can assume that every random move actually results in a tile moving.

Addendum

While the answers below shed light on the problem, only BoZenKhaa came close to providing a probability, even if it was an upper bound. So I would like to modify the question to:

Can we find decent upper and lower bounds for this probability?

share|improve this question
    
Just for the fun of it, when I played it first I used really random moves and got surprisingly good results. I think I got a number of 512 tiles by random keying. [Although I couldnt win.] –  Sawarnik Mar 26 at 8:09

6 Answers 6

I implemented a simulation of 2048, because I wanted to analyze different strategies.

Unsurprisingly, the result is that moving at random is a really bad strategy. enter image description here Above you can see the scores of $1000000$ random games (edit: updated after bugfix, thanks to misof). The score is defined as the sum of all numbers generated by merge. It can be viewed as a measure of how far you make it in the game. For a win you need a score of at least $16384$. You can see that most games end in a region below $2000$, that is they generate at most a 128-tile and loose subsequently. The heap on the right at $2500$ represents those games that manage to generate a 256 tile - those games are rather rare. No game made it to the 1024-tile.

Upon request, here is the plot for highest number on a tile: enter image description here When it comes to "dumb strategies", you get better results cycling moves deterministically: move up, right, up, left and repeat. This improves the expected highest number by one tile.

You can do your own experiments using the code here and here.

share|improve this answer
2  
What do the axes denote? –  ShreevatsaR Mar 26 at 11:53
1  
It's a histogram showing how many games (y-axis) end with a specific score (x-axis) which is defined in the game as the sum of all merged numbers. Plotted in bins of 30. –  benh Mar 26 at 14:30
1  
This answer would be super-awsome if the x-axis were highest tile number achieved, but probably the relevant data does not exists at this point? (I know that one can re-run, since you given the code, but if someone already did at least half of the work, maybe there is a chance.) –  luk32 Mar 26 at 16:10
1  
Moving "down" is generally disastrous; what if you change your simulator so that it will move randomly up, left, or right if any of those moves is legal, and only move down if no other move is permissible? I would expect that would improve things quite a bit, though I don't know by how much. –  supercat Mar 27 at 5:56
1  
@AlvinWong PRNG is actually very good for modelling distributions. It's not always so good for other things because you need some source of entropy(actual randomness) as a seed(as if the seed is guessable, so are all the values it will produce). But for modelling distributions, bad entropy like milliseconds since 1970 is sufficient. –  Cruncher Mar 27 at 14:26

I have been running random simulations on my computer, and it won't reach 1024, let alone 2048, as benh showed. So I eliminated one of the keys, and it reached 1024 in ~5-6 million games. I am now trying to see how many moves it takes for it to reach different numbers in different sized grids. Turns out even 5x5 isn't much better, as it doesn't reach even 2048 easily.

share|improve this answer

(Would post this as a comment, not a separate answer, but, alas, as a new user I don't have the reputation. Blame the spambots :) Also, note that the content of this answer is partially a repost of my post on Quora a few days ago.)

The answer to the question being asked: As already suggested in other answers, the probability of winning the game by making random moves is essentially zero.

Some more details:

The stats in the answer by @benh are incorrect. There is at least one bug I know of in his code, and it causes the stats he posted to be lower than they should. The bug I see is in how he detects the end of the game. In his simulations he ended the game as soon as the board becomes full. However, in 2048 the game is only over once that happens and no two adjacent tiles share the same number.

Below are the results of my simulations with a proper terminating condition.

Largest tile stats for 5,000,000 games, each move chosen uniformly at random:

  8:      78
 16:   13300
 32:  338969
 64: 1872573
128: 2382743
256:  391386
512:     951

Expected value of the largest tile at the end of the game: ~107.32

link to my code

share|improve this answer
    
Thank you for spotting the bug, you are right! I updated my code. Sorry that I haven't seen your post until now, I would have updated it before. –  benh Apr 8 at 17:17

Instead of trying to get an exact answer, let me give you a very rough intuition based estimate based on few observations about the game and a related question on SO:

  • Before you make it to the 2048 tile, you will need to have at least 10 tiles of different values on the board: $2,4,8,16,32,64,128,256,512$ and $1024$.
  • You will have to make at least $520$ moves to get to the 2048 tile (each time you make a move, the sum of tiles on the board increases by at most 4).
  • This is the awesome post on SO concerning the same game: http://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048 . It is noteworthy that the best algorithm mentioned in one of the answers has claimed success rate of around 90%, i.e. it does not get to win every time.
  • In the abovementioned post, it is suggested that a good winning strategy is to select one side, say the top one, and then try not to ever move your highest number away from that side. It is also suggested that if you have to move the high numbers away from this side of choice, it can be hard to save the day and still win.

Now for the sake of giving a pseudo-rudimentary estimate, let us entertain the idea that the last bullet point is right about the winning strategy and that this strategy covers most of the winning strategies.

Next, imagine, that our Random AlgoriThm (RAT) made it to the stage where half the board is covered with different numbers, meaning there are 8 different numbers on board $2,4,8,16,32,64,128, 256$. This means we are on the move number at most around $256 = \frac{1}{2}{\sum_1^{8} 2^k}$.

Also, our RAT miraculously made it this far and managed to keep it's high numbers by the top side of the board, as by the last bullet point. For the final assumption, assume that if the RAT presses the bottom arrow, it will always loose the game (because it is so random, it will not be able to salvage the situation.)

Now, the chance of our RAT winning after the move 256 is for sure smaller than the chance of RAT not pressing the bottom arrow. There is $3/4$ chance of the RAT not pressing the down arrow on every move, and there are at least 256 moves to be made before the RAT can get the 2048 tile. Thus the chance of the RAT winning in our simplified scenario is smaller $\frac{3}{4}^{256} \leq \frac{1}{2^{32}}$.

$P=\frac{1}{2^{32}}$ makes for a rather rare occurencce. As by N.Owad's comment, this chance is MUCH smaller than picking one specific second since the beginning of the universe. This should give you some intuition as to how unlikely a random win in this game actually is.

Disclaimer: I do not pretend that P is a bound of any sorts for the actual probability of random win due to the nature of simplifications made. It just tries to illustrates a number which which is likely larger than a chance of randomly winning.

share|improve this answer
    
+1 for RAT .. :D –  Silviu Burcea Mar 26 at 7:48
1  
I think your number of moves is wrong. ie its 1024 moves to get to 2048. Each move spawns a two or a four, if you assume its a two every time then the total on the board increases by two each move which means that 1024 moves gives a total of 2048 on the board. –  Chris Mar 26 at 9:42
    
My, I have not realized 4 can spawn as well, thanks for bringing that to my attention. 2048 moves is only required if you spawn two on each move. Each move that spawns 4 will reduce the number of required moves by one. On the other hand, having a sum of 2048 and and having a 2048 tile on the board are two different situations as you will have a sum of 2048 on the board by the time you have ten tiles with different values. –  BoZenKhaa Mar 26 at 13:06
    
Chris is right. You have overestimated the number of moves needed by roughly a factor of two. It would take 1024 optimal moves to get to the board 2,2,4,8,16,32,64,128,256,512,1024 but from there it is just to combine them using ten moves to get to the 2048 tile. –  user1884905 Mar 26 at 13:27
    
Oh yeah, that is right, I edited the answer to address this. For some reason I kept thinking of a winning situation being all the possible different digits on the board (which, I imagine, would be as much a feat as actually winning :-) ). –  BoZenKhaa Mar 26 at 14:45

Unfortunately I don't have the time to do this right now, but I still want to through this idea of how to tackel this (very hard) problem out there.

This method somewhat resembles what is often used in statistical physics. Cf as well to ergodic theory and the likes (we would have to prove ergodicity.... but well...).

For every field store an array of probabilities that this particular field is in the state 0 (unoccupied), 1 (has the number $2^1$), 2 (number $2^2$), ..., 11 (winning field $2^{11} = 2048$).

Let $P(i,j,x)$ denote the chance that the field with coordinates $(i,j)$ is in state $0\le x \le 11$.

Each move (up, left, right, down) has a clearly defined effect that can be expressed as a set of rules for example $$P'(i,j,x) = \underbrace{P(i,j,x)}_{\text{already was in this state}} - \underbrace{P(i,j,x) * (P(i+1,j,x)+P(i+1,j,x))}_{\text{leaves this state due to a join or move to the right}} + \underbrace{P(i,j,x-1)*P(i-1,j,x-1)}_{\text{joines this state due to join from the left}} + \dots $$ where $\dots$ stands for the more lengthy terms due to moving tiles (eg. somewhere to the right is an empty tile and left of me was the value $x$ in the last step).

The insertion of random numbers will simply decrease the likelihood that each field is unoccupied and respectively increase the state's $x=1$ and $x=2$ chances $$ P'(i,j,1) =P(i,j,1) + P(i,j,0)/16 \\ P'(i,j,2)=P(i,j,2) + P(i,j,0)/16 \\ P'(i,j,0)=P(i,j,0)*\frac{14}{16}\,. $$

Any move and the random insertion step are alternated on our current state (the vectors of probabilities). The likelihood of loosing in the current step is equal to the likelihood of all fields being occupied before the random insertions step. The likelihood of winning is the likelihood of any field being in state $x=11$ after the chosen move.*

Clearly the probabilities should be correlated. Assuming that they are not is somewhat equal to the "molecular" chaos that is assumed in statistical physics / ergodic theory. But, assuming that we are indeed ergodic with this description of the model, we can get the chance of winning the game after $n$ predefined steps (and not loosing it before) by iterating this $n$ times. This way one could compare different strategies easily, but would still have to test several random chains of moves to get a decent average. (We only implicitly averaged over all possible positions of the inserted $2$ and $4$ fields)


(*) Note that we have to remove any winning states from our vector of possibilities before each random insertion. Clearly we did not win yet if we are still playing. (Also this is necessary to have any chance at being ergodic)

share|improve this answer
    
I would love to implement and test this. Too bad I don't have as much time right now. What I assume you would see, is that the likelihood of each field being occupied (and thus you loosing in the given step) will only increase and thus the total chance of you already having lost will increase super-exponentially. Maybe this could even be shown (under the given assumptions) analytically... –  example Mar 26 at 20:34

The mere fact that the game is difficult to win regardless suggests that it's highly unlikely to win using random moves. I'm still not totally clear on how the game is played, but the chances of winning through random moves is likely extremely low (as in, so low you would never expect to observe it within a reasonable time--like the age of the universe).

share|improve this answer
2  
While you may be correct that it is extremely unlikely, we can still right down a probability that is accurate for something that small. $\frac{1}{4.3\times 10^{17}}$ is approximately the probability of picking one of the seconds since the beginning of the universe. –  N. Owad Mar 26 at 2:46
    
You are correct, but so what? What is the point of calculating an "exact" probability of something so unlikely. Once it becomes exponentially unlikely, the exact value is not important. It takes an absolute minimum of $\frac{2048}{2} = 1028 \approx 10^3$ moves (to introduce the necessary $1028$ 2-tiles). Once you figure in all possible values of the other tiles (other than the 2048 tile), it essentially becomes an exponential problem--so the only important answer is that a random script likely will never solve the problem (i.e. through brute force). –  Jared Mar 26 at 3:14
14  
What's the point? fun! –  chubakueno Mar 26 at 3:47
6  
This is math stack exchange... it should not be surprising that users here consider the difference between 0 and a somewhat small number to be a fundamental one. –  PeterT Mar 26 at 17:10
1  
"I'm still not totally clear on how the game is played" -- It seriously takes under 5 minutes to learn the game's rules. The game itself isn't complicated (which is part of how it's gained popularity). –  Brian S Mar 26 at 19:07

protected by Community Apr 8 at 11: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.