Math and Play 2048

For the first time the game 2048 presented on Habrahabr here . Less than five days, as revealed the secret of a simple strategy for its passage. It is really simple - you need to build a snake from the tiles (as in the picture).

However, a clear goal does not always mean its easy achievement. Mrrl and I shared our successes in turn: blocks 8, 16, 32, and 65 thousand blind . Now I managed what I didn’t expect - collect the maximum possible tile in the game - 131 072 or 2 ¹⁷ , accumulating over 2 million points.

This inspired me to refine and formalize the post- started reflections on the game 2048. This is not about the strategy and tactics of passing, but about such issues as:
- Is 2 ¹⁷ really the highest possible block?
- How many points can you basically dial on the way to the inevitable end of the game?
- how many moves does the puzzle make?
')
It takes a bit of math to figure it out ...

Maximum possible tile

Looking at the picture with the snake leading to the creation of block 2 ¹⁷ , it is obvious that it would not be possible to assemble the first tile with this particular strategy. However, is it true that 131,072 is really the maximum? Intuition gives us the answer “yes”, but I would like more convincing arguments. And this part of the study was for me the most difficult. Several approaches were brought to a standstill, until finally I came to the following construction.

The main idea is to abstract away from how the tiles are located on the playing field, focusing only on their values. From this point of view, the state of the game can be described in an ordered ascending set of 16 numbers currently displayed on the screen (a blank cell corresponds to zero).

In the case as in the picture, the state will be set (4, 4, 8, 16, ..., 65536). And at the very beginning of the game, it can be, for example, a vector (0, 0, ..., 0, 2, 2). Each move (both human and machine) leads to a new state, which, however, cannot be arbitrary. So, the rules of the game do not allow to jump at once with (0, ..., 0, 2, 2, 8) to (0, ..., 0, 4, 16).

We describe all possible transitions from one state to another:
- in the course of a person - either nothing changes, or one or several pairs of identical numbers are replaced by the sum of the elements in the pair, then the required number of zeros is added and the vector is ordered;
- in the course of the machine - either one deuce or one four is added to the set (so as not to disturb the order), and one zero is removed, or (if there are no zeros) the player is declared a loss.
The initial state (that is, the state at the start of the puzzle) can be (0, ..., 0, 2, 2), (0, ..., 0, 2, 4) or (0, ..., 0, 4, 4). The man and the car take turns, the player starts first.

These rules can be viewed as an axiom of the 2048 game model we have constructed. As expected, it is simpler than the object of modeling, but it has important properties:
- if in the original puzzle you can build a tile, for example, 2 ¹⁷ , then in the new one too;
- and vice versa, if in the simplified game it is impossible to go to the state with the number 2 ¹⁸ , then in the original creation of such a block is impossible.

Thus, to answer the question “Is 131 072 exactly the maximum possible tile?”, It remains to prove that it is never possible to switch to the state with the number 2 ¹⁸ in the model.

Proof: suppose the contrary and consider a chain of states from one of the initial states to the time when the number 2 ¹⁸ first appeared. Based on the model axioms, the last vector could appear only after a person’s progress in a situation of the species (..., 2 ¹⁷ , 2 ¹⁷ ).

Consider the first such condition that occurs in the chain. It was preceded by (again, according to the accepted axioms) either (..., 2 ¹⁶ , 2 ¹⁶ , 2 ¹⁷ ), or (..., 2 ¹⁶ , 2 ¹⁶ , 2 ¹⁶ , 2 ¹⁶ ), with the turn behind man.

This in turn means that the player had to be in one of the situations earlier: (..., 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁶ , 2 ¹⁷ ), (..., 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁷ ), (..., 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁶ , 2 ¹⁶ , 2 ¹⁶ ), (..., 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁶ , 2 ¹⁶ ), (..., 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁶ ) or (..., 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ ).

Remark: some states and transitions are possible only in the model we are considering; they have no analogues in the 2048 game, which does not affect the course of the proof.

Each subsequent stage of such reasoning leads to an increase of at least one unit in the number of strictly specified components of the vector that must be present in the circuit. In this case, the smallest of fixed values ​​is halved.

As a result, in no more than 15 steps, all 16 components will be explicitly specified. Then we come to the statement that there should be a state in the chain of the form (2 ^k , ...), where k ≥ 3, and a person walks.

However, the player could not find himself in such a situation, since after the action of the machine the smallest of the numbers represented in the vector can only be 0, 2 or 4. They arrived at a contradiction that refutes our initial assumption of the contrary, thus proving the required.

As a result, 2 ^{17 is} indeed the maximum possible tile in the 2048 game . It also means that passing a puzzle can be done no more than some fixed number of moves, while gaining a limited number of points. I wonder how many points and actions are at our disposal?

The maximum possible number of points

Scoring was much easier for me. To begin, let us outline the best for what a player can strive for in 2048. The record holder’s cherished goal by points (and by the number of moves, by the way, too) is a situation described by a vector (2, 8, 16, 32, ..., 131 072) or 4, 8, 16, 32, ..., 131 072). In this case, the game ends, while any other state is “dominated” by the indicated ones, that is, it can be improved precisely by gaining additional points (by completing additional actions).

We also note that on the way to the desired final, the car can produce more or fewer fours. The more often a player receives such "gifts", the worse his score will be on points. Therefore, let's assume that the car in all (except for the cases specified below) produces a deuce. To get to the end, you need to get only 15 fours - to collect the block 131 072, the 65,536 tile next to it, and so on up to 8.

So, let us remember the assumption made and consider the function f ( n ), the value of which is defined as the smallest possible number of points earned by the time of the first appearance of a 2 ⁿ tile. Why precisely the least? The fact is that by collecting for the first time, for example, block 4, we can guarantee the presence of the four points obtained for this, but there may be more (if several tiles of 4 are gathered in parallel).

We get f (2) = 4. Next:
f (3) = 16 (4 points we get for each of the two necessary blocks 4, then another 8 - for combining them into the figure eight),
f (4) = 48 (= 16 + 16 + 16),
f (5) = 128 (= 48 + 48 + 32), etc.

The recurrence relation is: f ( n ) = 2 f ( n - 1 ) + 2 ⁿ for all natural n , 3 ≤ n ≤ 16. One of the ways to solve it is to consider the equalities f ( n ) = 2 (2 f ( n - 2 ) + 2 ^{n - 1} ) + 2 ⁿ = 4 f ( n - 2 ) + 2 * 2 ⁿ , f ( n ) = 4 (2 f ( n - 3 ) + 2 ^{n - 2} ) + 2 * 2 ⁿ = 2 ³ f ( n - 3 ) + 3 * 2 ⁿ , ..., f ( n ) = 2 ^{n - 2} f ( 2 ) + ( n - 2) * 2 ⁿ . Taking f (2) = 4 into account, we get f ( n ) = 2 ⁿ ( n - 1), which is true, we recall, for 3 ≤ n ≤ 16.

Collecting tile 2 ¹⁷ we will get 4 points less than the predicted formula predicts, since we will have to use one of the four given to us by the machine. That is, f (17) = 2 ¹⁷ * 16 - 4 or 2 097 148.

It remains only to understand that after creating the maximum block, we again have to “assemble” tile 2 ¹⁶ “for the first time”, rescuing f (16) for this - 4 points (fine again for using the free four), then 2 ¹⁵ , receiving accompanying f (15 ) - 4 points, and so on up to 2 ³ and f (3) - 4 points in the piggy bank.

Calculating the sum f (17) + f (16) - 4 + f (15) - 4 + ... + f (3) - 4, we get 3 932 100, which is the maximum possible number of points in the game 2048 .

A small note: by definition, f ( n ) is the smallest possible number of points earned by the time of the first appearance of a tile on a 2 ⁿ field. However, in the final of the game, the number of points earned is exactly equal to the sum of the values ​​of the functions for n from 3 to 17 (minus the fine). There is no surplus, as they are taken into account in the terms corresponding to smaller blocks.

Maximum possible number of player moves

The task about the number of moves seemed to me the most difficult at the beginning. But the reasoning is simple: we introduce the function g ( n ), somewhat similar to f . We define its value as the minimum number of tiles 2 needed to collect a block 2 ⁿ . In order to maximize the number of moves, we also act on the assumption that the machine each time (with the exception of 15 specially specified cases) gives us twos.

So, g (2) = 2 (to collect four, you need to merge 2 deuces), g (3) = 4 (to collect eight, you need to merge two four, the production of each of which requires 2 deuces), g (4) = 8 ( = 4 + 4) and so on. A simple recurrence relation g ( n ) = 2 g ( n - 1) gives the formula g ( n ) = 2 ^{n - 1} for 3 ≤ n ≤ 16.

When creating block 2 ^17, we need two tiles 2 less than the expression above indicates, since we are given one of the four right away, we don’t need to assemble it. Therefore, g (17) = 2 ¹⁶ - 2 = 65 534. Just as in the case of points, to calculate the total number of twos involved on the way to one of the two final states, add the values ​​of the function g ( n ) for n from 3 to 17 with penalties. We get g (17) + g (16) - 2 + ... + g (3) - 2, equal to 131 038. For the full order, we must add one to this number if we have arrived at the final state (2, 8, 16, ... 131 072).

Now back to our task. Two tiles 2 are given to us from the very beginning. To get the remaining 131,036 (not counting the last in one of the finals), you need to perform an appropriate number of actions (after all, the machine gives us exactly one deuce each turn). Plus, you will need another 15 fours (also not counting the last in one of the finals). And finally, another action will lead to the appearance of the last two or four.

Total, willy-nilly, you have to do 131,036 + 15 + 1 = 131,052 keystrokes (or touching the touch screen) - this is the desired maximum number of user moves in the game 2048 .

Analysis of my current achievements in the 2048 game

In conclusion, let me apply the above results and approaches for analyzing my recent success in the game of 2048. It seemed to me surprising and interesting that it turns out you can determine the exact number of moves required to achieve the situation depicted in the picture. Of course, this does not take into account the actions that I performed, repeatedly replaying individual episodes from the last save (saves can be done, tritely duplicating tabs with the game). And without this, to collect the maximum possible unit is extremely unlikely.

So, following the arguments that were tested earlier, if the whole game had only two and one four fall out of me, then as a result g (16) + g (15) + ... + g (2) + 1 - 2 = 65 533 moves I had to dial integers f (16) + f (15) + f (14) + ... + f (2) = 1,835,012 points. However, as you can see, only 1,811,320 were earned. 23,692 is not enough, that is, the car gave me 5,923 fours, making it impossible to get points, but saving the corresponding number of moves.

Findings:
- by now I have done about 60 thousand correct actions on the way to complete victory in the 2048 game;
- to one of the two inevitable finals, there are still about 71 thousand keystrokes (with a perfect game and luck);
- the total number of points I received (after collecting the maximum tile and the four thousand block next to it) is 2,117,800, that is ~ 54% of the maximum possible. More than a half! Even with the irrecoverable losses in the amount of almost 24 thousand points due to a random number generator.

If suddenly I finish the toy to the end - I will post a picture in this post. Good mood to you all!

UPD:
Appearing immediately after the screen shot, the phrase Game over seems to me not quite appropriate in this case. After all, on the way to one of two possible final states, the victory block 2048 had to be collected 127 times. Total made 119,322 correct moves. The car threw out on the field 11 730 fours (not counting the last in the upper left corner), which accelerated the victory, but deprived of 46 920 points.