A number of us at the office have been playing 2048, a simple yet challenging puzzle game. (I credit xkcd for getting me started.) It also has some fun math for us programmers, and not just because it uses powers of two. As you’ll see, predicting the level of game play from a player’s score leads to a Lambert W function, used in quantum mechanics, granular fluid flow, diode modeling, and in my own life, holography.
The goal of 2048 is to combine like-numbered tiles to build up to a 2048-valued tile. You can slide all of the tiles on a game board in the same direction at each move, and a tile with either a 2 or a 4 is randomly placed in an open space after your move. Two neighboring tiles with the same number that slide into each other will clobber during the slide move, so that two eights will combine to form a 16-valued tile, two 16’s combine to form a 32, and so on. You are awarded the same number of points as the tiles you clobber together.
The version of 2048 that I downloaded allows you to continue playing after reaching the 2048 tile and includes a public scoreboard. When I started playing, there was someone who had scored 79,000 points. As of mid-April, someone had reached an astounding 271,192 points. But what does that actually mean? What tile combination where they able to reach? How long did that take? That’s where the math starts!
Three successive boards of 2048, left to right. The tiles were slid upwards in each move. After each move, a random tile was added to the board.
It is easier to understand the sequence of moves required to reach the 2048 tile by redrawing the moves required to reach a particular tile as a graph. For example, here’s a simple graph of which tiles need to be combined to reach 8:
Three merges are required to get to an 8-tile starting from 2-tiles.
Computer scientists will recognize this as a binary tree. Counting up the number of merges is the same as counting the number of nodes on everything but the first level of the graph. Making a simple table shows the pattern clearly:
In the worst case, the game randomly populates open spaces with 2-tiles, and you need 2^(n-1)-1 merges to reach the 2^n tile. In the best case, 4-tiles are placed in all the open spaces by the game, and you need 2^(n-2)-1 merges.
On average, let’s assume that you merge one set of tiles per second*. Some moves don’t merge tiles, some moves merge several sets of tiles, some moves are faster than one second, some moves take some thinking… so on average, one second per merge is probably ball-park for someone who’s been playing 2048 for long enough. Reaching 2048 (= 2^11) requires, at minimum, 511 merges and about 9 minutes (if all 4’s are randomly placed on the board) or up to 1023 merges (if all 2’s are placed on the board) and about 17 minutes. (It took me 13.5 minutes just now, for example.)
*If you’re starting out, one second per move may seem ludicrous. Talking to my coworkers who have been playing 2048 for long enough, they’ve all come up with heuristics for which moves and merges to make, so that a one-second-per-merge average is possible.
The next question relates to the score: given that someone scored S on a game, what tile level did they likely reach? You score points based on the tiles which clobber together, so that clobbering two 2-tiles gets you 4 points, and clobbering two 16-tiles nets you 32 points for that move. If you graph the points out, the total score accumulated by the time you reach a certain tile becomes more obvious:
Each merge scores the same number of points as the tiles that were combined. The top number in each box is the score for that merge, while the bottom number is the total number of points accumulated by the time you reach that level. For example, by the time you reach an 8-tile, you will have accumulated 4+4+8 = 16 points.
Ha! In order to reach the 2^n tile, you will have scored (n-1)*2^n points (at most — and that would be the score just to build that tile). It’s worth noting that this equation assumes that all the auto-generated tiles are 2-tiles, and thus provides a maximum limit to the score.
Here’s where the math gets interesting: try going backward and finding the tile level n corresponding to a specific score, S. If you work through the math and put in a few judicious moves (which will become useful in a moment),
you can reach a stage where you have an equation of the form
with
This is where a function known as the Lambert W comes to the rescue: it is the inverse solution to this exact problem. In other words, the value of W(y) is defined so that setting x = W(y) makes the left and right sides of the equation match,
Using the Lambert W, the tile-level-vs-score equation can be factored further to get n directly:
This equation lets us know, to within a fairly good degree, what tile level a player reached when achieving a particular score. For example, say I got a score of S = 20492. Putting this into the equation gives n = 11.0007, which corresponds to the 2048 tile (plus a few more tiles beyond 2048). I found a score on youtube of 71,684, which gives n = 12.6, which is a 4096 tile and a 2048 tile. Another youtube video has a score of 151,796, which gives n = 13.6, an 8192 tile and a 4096 tile both. The high score on my game’s leaderboard of S =271,152 means that a Mr. Alexius Timothy managed to get a 16384 tile.
Plots of the tile level versus score
How long does it take to reach 151,796? If n = 13.6, that’s around 6000 merges, or 100 minutes at one merge per second at worst-case. The player in that video gets to their high score after 76 minutes. Not too bad of an estimate.
If you don’t have Matlab handy but want to estimate how well your coworkers did, it may also help to note that the score is approximately linear with tile value as S gets very large. (This is because the expansion of the Lambert W for large arguments is given by natural logs, and taking 2^ln(…) gives an approximately linear result.) Around 20,000 points (close to the 2048 tile), the slope is about 0.1, and drops slowly to about 0.083 by 100,000 points. So if your coworker announces that he scored 55,000 points in a game, you could estimate that 55,000 * 0.09 = 4950, and he probably reached the 4096 tile.
One of the recurring caveats is that the equations I’ve presented here are based on the assumption that the game generates all 2-tiles or 4-tiles in the blank spaces. In the actual game, there is a distribution of 2’s and 4’s. The popular version from Gabriele Cirulli has a 90% chance of generating a 2-tile and a 10% chance of generating a 4-tile, which you can see in his code:
This means that out of every 20 tiles which are auto-generated, you can expect 18 to be 2-tiles and two to be 4-tiles. The result is that, out of every eleven 4-tiles, two are randomly generated and the rest are built through merging, as described by the equations thus far:
Intuitively, you’d expect very similar results from Mr Cirulli’s 90-10 probability distribution as if the game had generated all 2-tiles.
The precise answer is only a step away from the intuitive. The only difference occurs at the very top of the graph (as I’ve drawn it), where the 2-tiles merge into 4-tiles. Let’s call f_m the fractional number of merges you have in the real game (in other words, using a non-zero probability of generating 4-tiles) compared to the case where the game generates all 2-tiles. In the example above, where 18 2-tiles and two 4-tiles are generated, you “lose” two of the 11 merges you could have had if all 2-tiles had been created, and f_m is 9/11. In general, if P_2 is the probability of getting a 2-tile, then f_m is easy to find:
It’s interesting to note that if if you used a value for P_2 that is related to a power of 2, like 1-2^-3 = 1-1/8 = 0.8750, f_m is not a power of 2; f_m = 7/9. I’d also suggest that Mr Cirulli’s choice of using 0.9 was interesting in that it destroys some of the power-of-2 symmetry.
We can use f_m to modify the equations and find the expected number of merges or points. Again noting that f_m affects the number of merges or points in only the top-most rows of the graph, we can divide the graphs into two sections: the top row and the bottom pyramid. Looking first to the score, each row of the tree contributes 2^n points to the overall total when trying to reach the 2^nth tile, so that you have 2^n(n-2) points from everything except the top-most row of 2-tiles merging into 4-tiles. The number of points you would expect from the 2-tiles merging if then f_m*2^n, and the expected point total is
The number of merges from the 4-tiles on down to the 2^nth tile is 2^(n-2)-1. If all the auto-generated tiles were 2-tiles, you would need an additional 2^(n-2) merges to convert all of the 2-tiles into 4’s. The expected number of merges is then
If the game randomly generates almost all 2-tiles, then f_m is almost 1, and the equations reduce back down. You can also see that the score, S, is almost constant as f_m changes, since it is dominated by the (n-2) term as n becomes large. Given the number of different ports of 2048, that’s a good thing: even if my port uses a different P_2 (and thus a different f_m), I can still compare my scores against my coworkers’ scores and expect them to compare well. It doesn’t matter that CV and I might be playing different versions, he’s still got a higher score.
Before closing out, I did want to talk a bit about the Lambert W function — or at a minimum, point you, dear reader, to more reading if you’re curious. It has a number of unique properties, especially relating to e, pi, 0, and interesting integrals; check the Wikipedia article for a listing. The function comes up in quantum mechanics as the energy of an electron in a conductor sandwiched between two other conductors which almost touch. The Lambert W gives the values for digit-shifting using powers. (If you have ideas of how digit-shifting could be used, I’d like to hear them.) The function generates the so-called Omega constant. The current in a diode has the Lambert W as part of its solution. It’s also worth noting that, since W is related to exponentials, it can also be used with complex numbers.
Finally, I wanted to pass on a link to an interesting port of 2048, Fe[26], where you fuse elements together to create higher “valued” isotopes — starting from hydrogen and working up to iron. Just beware the half-lives of the unstable isotopes and stable atoms which can’t be used…
Jens Kubieziel
All Jonkman Microblog content and data are available under the