2048 and algebra (Part 10)

In this series of posts, I used algebra to show that 114,795 moves were needed to produce the following final board. This board represents the event horizon of 2048 that cannot be surpassed.

I reached after about four weeks of intermittent doodling. It should be noted that the above game board was accomplished in practice mode, and I needed perhaps a couple thousand undos to offset the bad luck of a tile randomly appearing in an unneeded place.

For what it’s worth, my personal best in game mode was reaching the 8192-tile. I’m convinced that, even with the random placements of the new 2-tiles and 4-tiles, the skilled player can reach the 2048-tile nearly every time and should reach the 4096-tile most of the time. However, reaching the 8192-tile requires more luck than skill, and reaching the 16384-tile requires an extraordinary amount of luck.

So what are the odds of a skilled player reaching the event horizon in game mode, without the benefit of undoing the previous move? I will employ Fermi estimation to approach this question. Of the approximately 100,000 moves, I estimate that about 5% of the moves require a certain 2-tile or 4-tile to appear at a certain location on the board. For example, in the initial stages of the game, the board is wide open and really doesn’t matter a whole lot where the new tiles appear. However, when the board gets quite crowded, it’s essential that new tiles appear in certain places, or else even a highly skilled player will get stuck.

What is the probability of getting the right tile on each of these occasions? Usually it’s quite high (over 90%). But sometimes it’s necessary to get a 4-tile in exactly the right place when there are four blank spaces (estimated probability of 3%). So let’s estimate 10% to be the probability for getting the right tile for all of these occasions. Let’s also assume that the random number generator is indeed random, so that the tiles appear independently of all other tiles.

With these estimates, I can estimate the probability of reaching the event horizon in game as $\displaystyle \left( \frac{1}{10} \right)^{5000} = \displaystyle \frac{1}{10^{5000}}$ . While this analysis isn’t foolproof, it sure beats playing the game about $10^{10,000}$ times and then dividing by the number of times the event horizon is reached by the total number of attempts!

How small is $\displaystyle \frac{1}{10^{5000}}$ ? Since $2^3 \approx 10$ , this is approximately equal to $\displaystyle \frac{1}{2^{15,000}}$ , and that’s a probability so small that it was reached (and surpassed) when the Heart of Gold spaceship activated the Infinite Improbability Drive in The Hitchhiker’s Guide to the Galaxy. By way of comparison:

$\displaystyle \frac{1}{2^{276,709}}$ is the probability that someone stranded in the vacuum of space will be picked up by a starship within 30 seconds.
$\displaystyle \frac{1}{2^{100,000}}$ is the probability of skidding down a beam of light… or having a million-gallon vat of custard appearing in the sky and dumping its contents on you without warning.
$\displaystyle \frac{1}{2^{75,000}}$ is the probability of a person turning into a penguin.
$\displaystyle \frac{1}{2^{50,000}}$ is the probability of having one of your arms suddenly elongate.
$\displaystyle \frac{1}{2^{20,000}}$ is the probability of an infinite number of monkeys randomly typing out Hamlet.

These are the events to which the probability of reaching the event horizon in 2048 without any undos should be compared.

2048 and algebra (Part 9)

In this series of posts, I consider how algebra can be used to answer a question about the 2048 game: From looking at a screenshot of the final board, can I figure out how many moves were needed to reach the final board? Can I calculate how many new 2-tiles and 4-tiles were introduced to the board throughout the course of this game? In this post, we consider the event horizon of 2048, which I reached after about four weeks of intermittent doodling:

In yesterday’s post, we developed a system of two equations in two unknowns to solve for $t$ and $f$ , the number of 2-tiles and 4-tiles (respectively) that appeared throughout the course of the game:

$2t + 4f = \displaystyle \sum_{n=2}^{17} 2^n$ .

$2t + \displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 3,867,072$

In this post and tomorrow’s post, I consider how the two sums in the above equations can be obtained without directly adding the terms.

In yesterday’s post, we used the formula for the sum of a finite geometric series to calculate the second sum:

$\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 14 \times 2^{18} + 2^3 = 3,670,024$

In this post, I perform this calculation again, except symbolically and more compactly. The key initial steps are writing the series as a double sum and then interchanging the order of summation (much like reversing the order of integration in a double integral). This is a trick that I’ve used again and again in my own research efforts, but it seems that the students that I teach have never learned this trick. Here we go:

$\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = \displaystyle \sum_{n=1}^{15} \sum_{k=1}^n 2^{n+2} = \displaystyle \sum_{k=1}^{15} \sum_{n=k}^{15} 2^{n+2}$

The inner sum is a finite geometric series with $15-k+1$ terms, common ratio of 2, and initial term $2^{k+2}$ . Therefore,

$\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = \displaystyle \sum_{k=1}^{15} \frac{ 2^{k+2} \left(1 - 2^{15-k+1} \right) }{1 - 2}$

$= \displaystyle \sum_{k=1}^{15} \left(2^{18} - 2^{k+2} \right)$

$= \displaystyle \sum_{k=1}^{15} 2^{18} -\sum_{k=1}^{15} 2^{k+2}$

The first sum is merely the sum of a constant. The second sum is another finite geometric series with 15 terms, common ratio of 2, and initial term $2^3$ . So

$\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 15 \times 2^{18} - \displaystyle \frac{ 2^3 \left(1 - 2^{15} \right) }{1 - 2}$

$\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 15 \times 2^{18} - \left( 2^{18} - 2^3 \right)$

$\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 14 \times 2^{18} + 2^3$

$\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 3,670,024$

2048 and algebra (Part 8)

$2t + 4f = \displaystyle \sum_{n=2}^{17} 2^n$ .

$2t + \displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 3,867,072$

In this post and tomorrow’s post, I consider how the two sums in the above equations can be obtained without directly adding the terms.

In yesterday’s post, we showed that the formula for the sum of a finite geometric series can be used to calculate the first sum:

$\displaystyle \sum_{n=2}^{17} 2^n = \displaystyle \frac{4(1-2^{16})}{1-2} = 4(2^{15} - 1) = 262,140$

Let’s now consider the second (and more complicated) sum, which can be written as

$2^3 + 2 \cdot 2^4 + 3 \cdot 2^5 + \cdot + 15 \cdot 2^{17}$

For reasons that will become clear shortly, this sum can be written in expanded form as

$2^3$

$+ 2^4 + 2^4$

$+ 2^5 + 2^5 + 2^5$

$\vdots$

$+ 2^{17} + 2^{17} + 2^{17} + \dots + 2^{17}$

Let’s now rearrange the terms of this sum. We will do this by adding along the diagonals instead of along the rows. In this way, the above sum can be rearranged as

$2^3 + 2^4 + 2^5 + \dots + 2^{17}$

$+ 2^4 + 2^5 + \dots + 2^{17}$

$+ 2^5 + \dots + 2^{17}$

$\vdots$

$+ 2^{17}$

Each of these new rows (or the original diagonals) is a geometric series and can be calculated using the formula:

$2^3 + 2^4 + 2^5 + \dots + 2^{17} = \displaystyle \frac{2^3 (1-2^{15})}{1-2} = 2^{18} - 2^3$

$2^4 + 2^5 + \dots + 2^{17} = \displaystyle \frac{2^4 (1-2^{14})}{1-2} = 2^{18} - 2^4$

$2^5 + \dots + 2^{17} = \displaystyle \frac{2^5 (1-2^{13})}{1-2} = 2^{18} - 2^5$

$\vdots$

$2^{17} = (2-1) \cdot 2^{17} = 2^{18} - 2^{17}$

So, thus far in the calculation, we have established that

$\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = \displaystyle \sum_{n=3}^{17} \left( 2^{18} - 2^n \right)$ .

Simplifying,

$\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2}=\displaystyle \sum_{n=3}^{17} 2^{18} - \sum_{n=3}^{17} 2^n$

The first sum on the right is the sum of a constant being added to itself 15 times:

$\displaystyle \sum_{n=3}^{17} 2^{18} = 15 \times 2^{18}$

The second sum on the right is yet another geometric series. Indeed, it’s the same geometric series from the first diagonal above:

$\sum_{n=3}^{17} 2^n = \displaystyle \frac{2^3 (1-2^{15})}{1-2} = 2^{18} - 2^3$

Therefore,

$\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 15 \times 2^{18} - \left(2^{18} - 2^3 \right)$

$\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 14 \times 2^{18} + 2^3$

$\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 3,670,024$

Not surprisingly, this matches the sum that was found via direct addition.

2048 and algebra (Part 7)

$2t + 4f = \displaystyle \sum_{n=2}^{17} 2^n$ .

$2t + \displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 3,867,072$

In this post and tomorrow’s post, I consider how the two sums in the above equations can be obtained without directly adding the terms.

The first sum is certainly the easiest to handle, as it requires the sum of a finite geometric series:

$a + ar + ar^2 + \dots + a r^{n-1} = \displaystyle \sum_{i=1}^n a r^{i-1} = \displaystyle \frac{a(1-r^n)}{1-r}$

For the geometric series

$\displaystyle \sum_{n=2}^{17} 2^n$ ,

there are 16 terms (after all, there are 16 tiles on the board). The first term is 4, and the common ratio is 2. Therefore,

$\displaystyle \sum_{n=2}^{17} 2^n = \displaystyle \frac{4(1-2^{16})}{1-2}$

$\displaystyle \sum_{n=2}^{17} 2^n = 4(2^{15} - 1)$

$\displaystyle \sum_{n=2}^{17} 2^n = 262,140$

We’ll consider the more complicated sum in tomorrow’s post.

2048 and algebra (Part 6)

In the previous posts, we have developed a system of two equations in two unknowns to solve for $t$ and $f$ , the number of 2-tiles and 4-tiles (respectively) that appeared throughout the course of the game.

The first equation,

$2t + 4f = \sum T_i$ ,

says that the sum of the tiles that were introduced has to be equal to the sum of the tiles $T_i$ that appear on the final board. Directly adding the sixteen tiles above yields

$2t + 4f = 262,140$ .

This sum can also be calculated using a trick to be discussed in tomorrow’s post.

The second equation,

$2(t - t_0) + \displaystyle \sum_{T_i \ge 8} (\log_2 T_i -2) T_i = P$ ,

says that the total number of points $P$ may be divided into the contributions provided by the tiles on the final board. For example, the 16-tile was formed by joining two 8-tiles for 16 points. Each of those 8-tiles were formed by joining two 4-tiles for another $2 \times 8 = 16$ points. Added together, the 16-tiles results in $2 \times 16 = (\log_2 16 - 2) \times 16 = 32$ points. This analysis does not account for any 4-tiles that were created by adding two 2-tiles. The number of such 2-tiles is $t - t_0$ , where $t_0$ is the number of 2-tiles that appear on the final board (in this case, $t_0 = 0$ ). These additions result in $(t - t_0)/2$ 2-tiles worth $4 \times (t-t_0)/2 = 2(t-t_0)$ points.

For the board above, this equation becomes

$2t + \displaystyle \sum_{T_i \ge 8} (\log_2 T_i - 2) T_i = 3,867,072$

and (for this particular board) the sum can be written more simply as

$2t + \displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 3,867,072$

Directly adding the sum $1 \cdot 8 + 2 \cdot 16 + 3 \cdot 32 + \dots + 15 \cdot 131,072$ — and being very careful to double-check the arithmetic — yields the second equation

$2t + 3,670,024 = 3,867,072$

This sum can also be calculated using a trick to be discussed in a future post.

Solving, we find

$2t = 197,048$

$t = 98,524$

Substituting into the first equation:

$2 \times 98,524 + 4f = 262,140$

$197,048 + 4f = 262,140$

$4f = 65,092$

$f = 16,273$

So we conclude that 98,524 2-tiles and 16,273 4-tiles were introduced to the board. Stated another way, about 85.8% of the new tiles were 2-tiles, while about 14.2% of the new tiles were 4-tiles. Also, since two tiles were on the board before any moves were made, a total of $98,524 + 16,273 - 2 = 114,795$ moves were needed to reach the above board.

2048 and algebra (Part 5)

(The above board is the only picture I currently have of reaching 4096 without using an undo — the version of the game that I had at the time permitted two undos per game. I have also reached 8192 in game mode — I was really lucky that day — but I sadly don’t have a screenshot to memorialize the occasion.)

In the previous post, I used two insights to develop of a system of two equations in two unknowns. Let $t$ and $f$ denote the number of 2-tiles and 4-tiles, respectively, that were introduced by the game. The sum of the tiles on the final board must also be the sum of the 2-tiles and 4-tiles that were introduced during the course of the game. Therefore,

$2t + 4f = 3 \times 2 + 3 \times 4 + 2 \times 8 + 16 + 4096$

$2t + 4f = 4146$

Next, we consider how the total of 44,148 points was reached by looking at the final tiles.

Each 8-tile was formed by joining two 4-tiles (for 8 points). Some of those 4-tiles were added by the computer; others were formed by joining two 2-tiles (for 4 points each). So each 8-tile is worth $1 \times 8$ points, plus 4 times some undetermined number.
Each 16-tile was formed by joining two 8-tiles (for 16 points). Each of those two 8-tiles was formed by joining two 4-tiles (for 8 points for each 8-tile, or $2 \times 8 = 16$ more points). Again, some of those 4-tiles were added by the computer; others were formed by joining two 2-tiles (for 4 points each). So each 16-tile is worth $16 + 16 = 2 \times 16 = 32$ points, plus 4 times some undetermined number.
There are no 32-tiles on this board. However, to continue the pattern, any 32-tiles are formed by joining two 16-tiles (for 32 points). Each of those two 16-tiles was formed by joining two 8-tiles (for 16 points for each 16-tile, or $2 \times 16 = 32$ more points). Each of those four 8-tiles was formed by joining two 4-tiles (for 8 points for each 8-tile, or $4 \times 8 = 32$ more points). Again, some of those 4-tiles were added by the computer; others were formed by joining two 2-tiles (for 4 points each). So each 16-tile is worth $32 + 32 + 32 = 3 \times 32 = 96$ points, plus 4 times some undetermined number.
By now, the pattern should be clear. Any 64-tile on the board would contribute $4 \times 64 = 256$ points, plus 4 times some undetermined number (as a reminder, the number of 4-tiles formed by adding in the course of making the 64-tile).
Any 128-tile on the board would contribute $5 \times 128 = 640$ points, plus 4 times some undetermined number.
And, in general, a $2^n$ -tile would contribute $(n-2) \times 2^n$ points, plus 4 times some undetermined number.
In particular, when $n = 12$ , a 4096-tile would contribute $10 \times 2^{12} = 40,960$ points, plus 4 times some undetermined number.

In summary, for the above board, there are:

Three 4-tiles (for 4 times some undetermined number),
Two 8-tiles (for $2 \times 8 = 16$ points plus 4 times some undetermined number),
One 16-tile (for $32$ points plus 4 times some undetermined number), and
One 4096-tile (for $40,960$ points plus 4 times some undetermined number).

Adding, this board will have $16 + 32 + 40,960 = 41,008$ , plus 4 times some undetermined number.

What is this undetermined number? It is the number of 4-tiles that are formed by combined two 2-tiles throughout the course of the game thus far. Since $t$ is the number of 2-tiles that have appeared and there are three 2-tiles on the board above, we conclude that $t-3$ 2-tiles have been combined into $(t-3)/2$ 4-tiles throughout the course of the game, resulting in $4 \times (t-3)/2 = 2(t-3)$ points. Therefore, we have the second equation

$41,008 + 2(t-3) = 44,148$

Let’s start solving:

$2(t-3) = 3,140$

$t -3 = 1570$

$t = 1573$

Substituting into the first equation:

$2 \times 1573 + 4f = 4146$

$3146 + 4f = 4146$

$4f = 1000$

$f = 250$

So we conclude that 1573 2-tiles and 250 4-tiles were introduced to the board. Stated another way, about 86.3% of the new tiles were 2-tiles, while about 13.7% of the new tiles were 4-tiles. Also, since two tiles were on the board before any moves were made, a total of $1573 + 250 - 2 = 1821$ moves were needed to reach the above board.

2048 and algebra (Part 4)

In the previous two posts, we developed two key insights (which will be used to develop of system of two equations in two unknowns):

1. Likewise, the 16-tile on the board was formed by adding two 8-tiles (16 points). Each of those 8-tiles was formed by adding two 4-tiles ( $2 \times 8$ , or another 16 points). And those 4-tiles, as well as the final 4-tile on the board, could have been (a) newly introduced by the game or else (b) formed by adding to 2-tiles (thus adding 4 points to the score for each of those 4-tiles).

Let $t$ and $f$ denote the number of 2-tiles and 4-tiles, respectively, that were introduced by the game. Since there are three 2-tiles on this final board, we conclude that $t-3$ 2-tiles were combined to make $(t-3)/2$ 4-tiles. Since each of these 4-tiles adds 4 points, we conclude that the final score of 44 points was obtained as follows:

$16 + 2 \times 8 + 4 \left( \displaystyle \frac{t-3}{2} \right) = 44$

$2(16) + 2(t-3) = 44$

$32 + 2(t-3) = 44$

2. The sum of the tiles on the final board is $2 \times 3 + 4 + 16 = 26$ . This also must be the sum of the 2-tiles and 4-tiles that were introduced during the course of the game. This gives us a second equation:

$2t + 4f = 26$ .

So we have a system of two equations in the two unknowns $t$ and $f$ . This is actually a simple system of equations to solve. Starting with the first equation:

$2(t-3) = 12$

$t -3 = 6$

$t = 9$

Substituting into the second equation:

$2 \times 9 + 4f = 26$

$18 + 4f = 26$

$4f = 8$

$f = 2$

This indeed matches what happened: nine 2-tiles and two 4-tiles were introduced to the board. Furthermore, since two of these tiles were on the initial board, we can conclude that it took nine moves to reach the final board.

2048 and algebra (Part 3)

To study this question, here’s a graphic showing the first nine moves in a typical game of 2048. I’ve included black circles to highlight the new 2-tiles and 4-tiles that are placed with each successive move, and I’ve added dark red ovals to indicate when two tiles are about to be combined in the next move.

In yesterday’s post, I raised one key insight about this game: we can calculate how many points were added for making each tile on the final board.

In today’s post, I raise a second insight. The final board has three 2-tiles, one 4-tile, and one 16-tile. So the sum of the tiles is 6 + 4 + 16, or 26. Also, during the course of the game, nine 2-tiles and two 4-tiles were introduced by the game. The sum of these tiles is 18 + 8, which is also 26. In other words, the sum of the tiles on the final board must equal the sum of the tiles that are introduced during the successive moves of the game.

With these two insights, we will (in tomorrow’s post) set up a system of two equations in two unknowns that will allow us to solve for the number of 2-tiles and 4-tiles that were introduced during the game using only the information on the final board.

2048 and algebra (Part 2)

Clearly, for these 9 moves, the computer introduced nine 2-tiles and two 4-tiles (including the two tiles that began the game in the initial position.) So here’s the question: is there a way, from looking only at the final board (with three 2-tiles, one 4-tile, and one 16-tile) and without looking at any of the prior history of the game, to calculate the number of 2-tiles and 4-tiles that were introduced?

In this post, I introduce the first of two insights that will allow us to answer these questions using algebra. (The second insight will be discussed in tomorrow’s post.) To study this question, let’s begin with the final board (with a score of 44 points) and look at how the tiles on the final board were formed.

Clearly, the three 2-tiles do not contribute anything to the final score. Net contribution: 0 points.

The one 4-tile on the final board (marked with a green circle) hypothetically could have either been a new tile that was introduced by the computer or else formed by combining two 2-tiles. In this case, we see that this particular 4-tile was indeed formed by adding two 2-tiles on Move 8. Net contribution: 4 points.

Handling the one 16-tile on the final board is a little more interesting. To begin, this 16-tile was formed from adding two 8-tiles on Move 8. Net contribution: 16 points.

Each of these 8-tiles were formed by adding two 4-tiles (one on Step 4, the other on Step 7). Net contribution: $2 \times 8$ , or another 16 points.

Two of the four tiles were formed by adding two 2-tiles (on steps 3 and 6). The other two four tiles were introduced by the computer (on steps 0 and 3) and were moved around the board prior to combining with another 4-tile. Net contribution: $2 \times 4$ , or 8 points.

So the total score is 4 points from making 4-tile on the final board and 16+16+8 = 40 points from making the 16-tile on the final board, for a total of 44 points.

This way of thinking about the game… how many points were added for making each tile on the final board… is one of two insights necessary to use algebra to solve for the prior history of the game. After discussing the second insight tomorrow, we’ll be ready to discuss the algebra of 2048.

2048 and algebra (Part 1)

In July and early August of this year, I finally defeated the wildly addicting 2048 game. That’s not to say that I reached the 2048-tile. No, I really defeated the game by reaching the event horizon that literally cannot be surpassed. (This is the usual way I overcome video-game addiction… play the game so much that I get sick of it.)

Over the four weeks or so that it took me to reach the event horizon, I thought of some interesting questions: From looking at only the above screenshot, can I figure out how many moves were needed to reach the final board? Can I calculate how many new 2-tiles and 4-tiles were introduced to the board throughout the course of this game?

It turns out that these questions can be solved with simple algebra. Indeed, if posed in the correct fashion, these questions can be answered using only elementary-school arithmetic. I will discuss the answers to these questions in this series of posts.

It should be noted that the above game board was accomplished in practice mode, and I needed perhaps a couple thousand undos to offset the bad luck of a tile randomly appearing in an unneeded place. I estimate the odds of a skilled player reaching the event horizon in game mode to be about $10^{5000}$ to one. Later in this series, I’ll give my rationale for this estimate.