Have you ever heard of 2048? If you memorize the powers of 2, then you would know this is simply 2 to the power of 11. However, that’s not how most people react. My first impression was “What’s with this random number? A satisfying number with even digits?” Soon, I learned it’s a game. Not long later, I got addicted to beating it.
About 2048
2048 was released back in 2014. It is a single-player sliding tile puzzle video game written by Italian web developer Gabriele Cirulli over the weekends (Wikipedia). 2048 has an easy concept with great animation and a goal where players can beat, and even surpass. It soon became a global hit! The first time I heard about the game was a decade ago when I was in Vietnam. I fell in love with it. Thanks to that, I actually memorized the powers of 2 before I actually learned about the concept of exponents in school! 2048 is a great educational game by all means.
In an interview with Hey.gg, 19-year old Gabriele revealed that 2048 was influenced by Saming’s 1024. The gameplay is similar except that 2048 has initial tiles of 2 and 4, while 1024 only has 2s. If we dig in further, the 1024 game was influenced by Threes, a game with the goal of sums or multiples of 3, starting with 1 and 2 tiles. Threes was also influenced by Drop7, which in turn was influenced by… (Wikipedia) Let’s stop here since it could go forever. It’s amazing how game development can be about creativity and improving your childhood games.
2048 Gameplay
The game has a simple and clean design with 4 x 4 tile board. Initially, the player is given two randomly placed tiles. There is a 90% chance of a 2 and a 10% of a 4. In total there are 3 combinations; (2, 2), (2, 4), or (4, 4). Players can use the four arrow keys to slide the tiles in the corresponding direction. When a tile collides with an identical tile, they merge and become a new tile with a higher power of 2. One single move can merge many tiles, but tiles can only merge once in a move. This can be confusing, so let’s look at an example.
If there are 4 tiles of number 2 at the bottom, and the player presses <-, then there are 2 tiles of 4 on the bottom rows to the left, and an additional new tile can be anywhere. In order to get a new tile of 8, another move needs to be made. The goal is to reach 2048, but players can continue if they want to beat the game. The maximal tile is 2^17 = 131072 if the last new tile is 4 (Goel, 2017). I actually had the honor to see someone achieve this a decade ago! Now it’s time for the math behind the game!
Mathematical Induction
Mathematical induction is a method to prove a statement or formula is true for all natural numbers or integers. It first proves this is true for the lower bound, i.e the base case number. Then it proves that if it is true for arbitrary numbers k where k >= base case, then it also is true for any k + 1. The latter is called an inductive step. According to Hoang Le, a Vietnamese Mathematics enthusiast, we can use mathematical induction to prove why 2048 always and only has tiles of power of 2.
| Problem: In 2048, the new tiles are either 2 or 4, and two identical tiles can sum and merge into one new tile. Using mathematical induction, prove that 2048 can only have tiles of power of 2. Tiles are either randomly generated or merged. The randomly generated tiles are the base cases. Base case 1: the new tile 2 = 2^1. Base case 2: the new tile 4 = 2^2. The base cases hold true. Induction: Assume that at any moment there are tiles in the form of 2^k, where integer k >= 1 (because smallest tile is 2), then after the next move the new tiles are still power of 2. There are 2 cases. 1. There is no merge, then the board still has the existing tiles with power k and the new tile 2 = 2^1 or 4 = 2^1. The new board state still only has power of 2 tiles. 2. There are merges, then for each tile 2^k that could merge, 2^k + 2^k = 2 * (2^k) = 2^(k+1). Some of the existing tiles merge into a new tile with a higher power of 2, and the newly generated tiles of 2 or 4 are also powers of 2. By mathematical induction, when 2048’s randomly generated tiles are 2 and/or 4, and tiles can only merge if they are identical as a sum, then the board can only contain tiles that are powers of 2. |
Markov Chain and Markov Decision Processes
Overleaf is a London-based startup that builds collaborative authoring tools for scientists, including support for the LaTeX language that allow users to present mathematical symbols. Today we are not talking about Overlead, but rather John Lees-Miller, a Cofounder and CTO at Overleaf. John studied 2048 and published an article series about how Markov Chain and Markov Decision Processes can be used to understand the game.
Based on the concepts of Markov Chain, through complex mathematical samplings and calculation, John concludes that the average number of moves to win the game is 939. This aligns with Bhargavi Goel’s, a student from Delhi Public School Vasant Kunj, India, conclusion about the move range to win the game [519, 1032]. The bounds are for extreme lucky cases with all tiles of 4 or extreme unlucky with just tiles of 2 (Goel, 2017). However, since the game also involves human’s decisions when facing the probabilities and random location of the tiles, Markov Chain is a better approximation. In addition, John works with Markov Decision Processes to find the optimal way to play 2048.
He divided the game into three dynamic concepts: states, actions, and transition probabilities (Lees-Miller, 2018). States refer to the current tiles and their positions. Actions are named after the 4 choices of directions. There are different probabilities of getting 2 or 4 at different positions, hence transition probabilities.
Another three concepts are rewards, values, and policies which are used to understand a player’s goal and how to achieve that goal (Lees-Miller, 2018). Rewards refer to the goal of achieving the state that has a 2048 tile. At each state, there is a value assigned to represent how close the current tile board is to reaching 2048. In addition, to win the game, the player needs to play optimally, in which John called the set of optimal states the optimal policy.
Below is the image of John’s formula and the states the computer generated to get to the losing or winning state.
After various chains of states with 2×2 and 3×3 boards, John figures that in order to arrive at the winning state, the optimal way is to minimize the direction choices to 3, so that the tiles are ordered and do not go all over the place. This will end up looking like a snake filling the tile board.
Topology for optimal strategy
Not only John, other 2048 enthusiasts also agree to some degree. In order to merge tiles as soon as they are identical, the tiles need to be adjacent before the merge move. If there is a sequence of merging continuously, like 64, 32, 16, 4, 2, followed by a new tile of 2, the biggest tiles after merging (multiple turns) would be 128. In order to minimize the moves, they need to be adjacent in order from largest to smallest. Hoang says that there are alternative paths where the head can be anywhere as long as the tiles are ordered (Le, 2014). Bhargavi concludes the optimal path is a snake line through the tiles with the largest tile at the corner and the next largest adjacent to it, continuing to all tiles (Goel, 2017). Hence, the optimal strategy is to have the largest at the corner and order from largest to smallest tiles in the snake-like line. This can only be done by playing with three directional moves (unless you are very unlucky). This is actually the only way to achieve 131072!
AI attempts at 2048
In 2019, Stanford University’s students Yun Nie, Wenqi Hou, and Yicheng An attempted Machine Learning with 2048. They program an AI to play 2048 using different advanced approaches, and record the scores of 100 trials for each approach. The difference between average and highest scores was significiant. They conclude at the end that the randomness of 2 and 4 make it hard for AI to beat the game.
Afterword
At first 2048 looks like a simple game, but once you get to know it from an academic perspective, it’s pretty complicated. Do not feel bad if you find the game hard to win. You see, even AI could not beat the game easily. If you’ve never played the game — give it a try — I promise you will like it (and become addicted to it). What are the chances that you come across this article? Here is your chance to apply what you learned and show off to your friends how to reach 131072!
References
- Cirulli, G. (2014). 2048. http://gabrielecirulli.github.io/2048/
- Goel, B. (2017). Mathematical Analysis of 2048, The Game. Advances in Applied Mathematical Analysis, 12(1). 1-7. https://www.ripublication.com/aama17/aamav12n1_01.pdf
- Hey.gg (2024, November 5). From viral sensation to full-time passion: The 2048 story. Hey.gg. https://www.hey.gg/blog/2048
- Le, H. N. (2014, June 4). The addictive mathematics of the 2048 tile game. Science4All. https://www.science4all.org/article/2048-game/
- Lees-Miller, J. (2018, March 18). The mathematics of 2048: Optimal play with markov decision processes. jdlm.info. https://jdlm.info/articles/2018/03/18/markov-decision-process-2048.html
- Nie, Y., Hou, W., & An, Y. (2016). AI plays 2048. CS229: Machine Learning Projects, Stanford University. https://cs229.stanford.edu/proj2016/report/NieHouAn-AIPlays2048-report.pdf
- Tu, R. (n.d.). 131072 tile? Is it possible?. YouTube. https://www.youtube.com/watch?v=MDkZkweB5lM&list=LL&index=1
- Wikipedia Contributors. Wikimedia Foundation. (2025, April 5). Threes. Wikipedia. https://en.wikipedia.org/wiki/Threes
- Wikipedia Contributors. Wikimedia Foundation. (2025, March 18). 2048 (video game). Wikipedia. https://en.wikipedia.org/wiki/2048_(video_game)
