In Part 1 we talk about how to estimate the score of your game based on a single snapshot. However, we hadn't yet corrected for the fact that $4$'s sometimes spawn. So, to compensate for the number of $4$'s that spawn, we need to know how often they spawn! The online, open-source version has a $10\%$ chance of spawning a $4$, but based on nearly $38,000$ (No, I didn't count them all, I'll show you how I came about this in a little bit.) spawns on my iPhone app version, there is about a $15.3\%$ chance that a $4$ will spawn (leading me to believe that it's supposed to be a $15\%$ chance).
With that in mind, we need to have an estimate for the total number of tiles spawned. And under our old assumption (that only $2$'s spawn), we can compute that very easily. Consider the following. Every $2$ tile that spawns counts as a spawn. Therefore, every $4$ tile that we have is really two total tiles that spawned (the two $2$ tiles). The $8$'s are 4 spawns (two $4$ tiles each with two $2$ tiles spawning). It doesn't take long to figure out that each tiles has
$$c_a = a/2$$
where $a$ is the face value of the tile. Thus we just sum this for each of the $16$ tiles on the board and we have a good estimate for the number of total tiles that spawned, $C_e$
$$C_e = \sum_{16\;Tiles}c_a$$
Well, we just assumed that all the spawns were number $2$ tiles. To compensate for the fact that $4$ tiles can spawn at a probability of $p_4$ we know the following two relationships:
$$p_4 = \frac{C_4}{C_a}$$
$$C_a = C_e - C_4$$
where $C_4, C_a, $ and $C_e$ are the number of $4$ tiles spawned, the actual number of total tiles spawned, and the estimated total tiles spawned, respectively. The first relationship is fairly straight forward; it's how the probability of a four-spawn is defined. However, the second relationship involves a little more thought. We guessed, based on only $2$ tiles spawning that there are $C_e$ total spawns. If we actually know that there are $C_4$ four-spawns, then we have to account for the number of two-spawns that would've smashed into these $4$'s. So, since there are two $2$'s that make a $4$ we have $C_2 = C_e - 2C_4$ two-spawns. To get the actual number of spawns we add the two-spawns to the four-spawns
$$C_a = C_2 + C_4 = (C_e - 2C_4) + C_4 = C_e - C_4$$
Plugging the second equation into the first and solving for $C_4$ we find out that
$$C_4 = \frac{p_4C_e}{1+p_4}$$
Lastly, since each of these $4$'s that spawned does not give us 4 points (we assumed we got the points for all $4$ tiles), our expected score ($S_x$) is the estimate score ($S_e$) minus four times the number of $4$'s that spawned:
$$S_x = S_e - 4C_4 = S_e - 4\frac{p_4C_e}{1+p_4}$$
Since we know $p_4$ and we know how to find $S_e$ (See Part 1) and $C_e$, we can compute our expected score. I played approximately 30 games with this and the average relative error for these guesses is about $0.2\%$. The results were even better once you scored above $10,000$. Only averaging the games with scores higher than $10,000$ (which was all but four of them), the average relative error was about $0.1\%$. Pretty cool results!
I said I would tell you how I came about the probability of a four-spawn of $15.3\%$. So I played a bunch of games and compared the actual score of the game to what I estimated it would be if there were only $2$ tiles that spawned. The difference between these two divided by four is the actual number of $4$ tiles that spawned. With that I used the two equations above and calculated what $p_4$ was!
There are a few more questions about 2048 that I still have. What is the highest score one can get? What is the lowest score? These questions (and others if I think of more) will be discussed in Part 3.
Showing posts with label 2048. Show all posts
Showing posts with label 2048. Show all posts
Monday, June 9, 2014
Friday, May 30, 2014
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.
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.
Subscribe to:
Posts (Atom)