2048 - Scoring (Part 1)

As everyone probably knows, the game $2048$ has become extremely popular (Even my mother plays it!). The game is simple; smash tiles of the same number together to make the next power of two with the goal of reaching the $2048$ tile.

This will be one of many posts I make about this game because I am fascinated with some of the math behind it. One of the first questions I want to answer is: How is the game scored? Well, anyone watching the score as they play can see that when you make the $4$ tile, you get $4$ points. When you make the $1024$ tile, you get $1024$ points. Pretty straight forward. But, in order to make the $1024$ tile (and get your $1024$ points) you need to first make two of the $512$ tiles and get $512 + 512 = 1024$ more points. And to make pair of $512$ tiles, you need to make a total of four 256 tiles.

So, the next question is: What is the actual value for a tile? Basically, how many points have you actually gotten from any given tile? I will first make the assumption that only $2$'s will spawn and will address the incorrectness at a later point. This means that every $4$ tile in play was created by crashing two $2$ tiles and has given us $4$ points. With $s_a$ representing the score of the tile with a face value $a$, we have the recurrence relation $$s_a=a+2s_{a/2}$$ because we get the value of the tile we create ($a$) and the score of two of the previous tiles ($a/2$). With this relation and the fact that $s_2 = 0$ (because it spawned giving no points) we can tabulate our relation: $$\begin{array}{|c|c|c|} \hline \mathrm{\mathbf{a}} & \mathrm{\mathbf{Relation}} & \mathrm{\mathbf{s_a}}\\ \hline 2 & 0 & 0\\ 4 & 4+2(0) & 4\\ 8 & 8 + 2(4) & 16\\ 16 & 16 + 2(16) & 48\\ 32 & 32 + 2(48) & 128\\ 64 & 64 + 2(128) & 320\\ 128 & 128 + 2(320) & 768\\ \hline \end{array}$$ We can keep going, but I wanted a better way. Is there a closed form solution for $s_a$? Can we find $s_a$ without finding the score of every tile before it? I was looking for a pattern and came across this: $$\begin{array}{|c|c|c|} \hline \mathrm{\mathbf{a}} & \mathrm{\mathbf{s_a}} & \mathrm{\mathbf{Pattern}} \\ \hline 2 & 0 & 2(0)\\ 4 & 4 & 4(1)\\ 8 & 16 & 8(2)\\ 16 & 48 & 16(3)\\ 32 & 128 & 32(4)\\ 64 & 320 & 64(5)\\ 128 & 768 & 128(6)\\ \hline \end{array}$$ where $s_a = a\left[\log_2(a)-1\right]$. But is this true in general? Turns out it is true and we can prove it with induction rather quickly. For simpler algebra, we'll define $n$ such that $2^n = a$, or rather, the $n$^th tile has a face value of $2^n$. Further, we define $t_n$ to be equal to $s_{2^n}$ and see that our closed form guess is $t_n = (n-1)2^n$ and our recurrence relation is $t_n = 2^n + 2t_{n-1}$.

The base case of $n=1$ is trivially true. We want to show that if $t_n = (n-1)2^n$ then $t_{n+1} = n2^{n+1}$. Consider $t_{n+1}$: $$t_{n+1} = 2^{n+1} + 2t_n = 2^{n+1} + 2(n-1)2^n = 2^{n+1} + (n-1)2^{n+1} = n2^{n+1}$$ Pretty straight forward! So, at the end of your games you don't have to waste your time and look at the top corner of the screen for your score. You can simply find $s_a$ for all 16 tiles on the screen and add them together! We will denote $S_e$ as the total estimate score for the game: $$S_e = \sum_{16\;Tiles}s_a$$ But, you'll notice that your estimated scores are always higher than the score the game shows (but only by around $2\%$ to $6\%$ based on how high your score is). This is because we assumed we get the points for the $4$ tiles. So how can we correct for the fact that sometimes a $4$ spawns? The answer is in Part 2.