Probability that random moves in the game 2048 will win

Solution 1:

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

Solution 2:

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: https://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.

Solution 3:

(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

Solution 4:

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)