Mathematical Analysis of the 2048 Game
This article investigates three questions related to the computer game 2048: 1. What is the minimum number of turns required to win? 2. What is the maximum number that can be created in accordance with the rules? 3. Is it always possible to win?
Written by Claus Volko
Vienna, Austria, Europe
Contact: cdvolko (at) gmail (dot) com
The 2048 game, which was developed by Gabriele Cirulli, is based on a board sized 4*4 fields. In each turn one of the two numbers 2 or 4 appears on a random empty field at the border of the board. The player has to press one of the four cursor keys, which makes all numbers located on the board move into the respective direction as far as possible. Whenever two identical numbers bump into eachother, one of them is removed and the other is replaced by the sum of the two numbers. Since only 2 and 4 may appear as new numbers, all numbers that may appear in the game are powers of 2. The game is won as soon as the number 2048 is created. The game is lost as soon as there is no empty field any more.
What is the minimum number of turns required to win the game?
We can get 2 or 4 as new numbers. If we always get 4, we can create 8 in 2 turns, 16 in 5 turns, 32 in 11 turns and so on. The number of turns required to create 2^n, hence, follows the pattern:
f(3) = 2
f(n + 1) = 2f(n) + 1 for n > 3
This results in the general formula:
f(n) = 2^(n-1) - 2^(n-3) - 1 for n >= 3
For 2048, n = 11, so f(n) = 767. We need at least 767 turns to win the game. This requires that we get only 4 as a new number.
If we consider a variant of the game where we get only 2 as a new number, we get a similar formula:
g(2) = 2
g(n + 1) = 2f(n) + 1 for n > 2
g(n) = 2^n - 2^(n-2) - 1 for n >= 2
g(11) = 1535
In this variant, we need at least 1535 turns to win the game.
What is the maximum number that can be created in accordance with the rules of this game?
The number 8 can be created from two 4s. This means we need 2 fields to create 8. As soon as 8 is created, we can create another 8 with two 4s. In total 3 fields have been occupied. As soon as the number 16 has been created, we can again create 8 using 2 fields. As soon as we have 16 and 8, we need 2 fields to create another 8 so that we can merge the two 8s to 16. This means we need 4 fields to create 32. Obviously we need n - 1 fields to create number 2^n. Since we have 4*4 = 16 fields on the game board, the maximum number we can create is 2^17 = 131072.
In a variant of the game in which we get only 2 as a new number, the maximum number would be 2^16 = 65536.
Is it always possible to win the game?
Obviously the game would be rather trivial if the board was linear and always the same number, either 2 or 4, appeared. If the board was sized 16*1 and we always got a 2, we could not do anything wrong! No matter what cursor key we pressed, we would always win the game.
If the numbers 2 and 4 always appeared in alternating order, we could still win the game by moving all numbers alternately to the left or to the right.
The question is what is with stochastic behaviour. We can easily see that in a linear board, it is always possible that the computer selects just the wrong number and the player cannot win the game, no matter what strategy he pursues.
Does this apply to the original game as well?
In the original game, we can also move the numbers on the board upwards or downwards. This indeed gives the player opportunities to tackle less favorable moves of the computer.
The question whether it is always possible to win the game is therefore still open. The easiest way to solve it would be to write a computer program that enumerates all possible courses of the game and checks if there are any courses that will inevitably lead to failure.
This essay was first published at my personal homepage, in 2014.