TLDR: Researchers Tomoyuki Kaneko and Shuhei Yamashita have strongly solved the 2048 4×3 variant, a stochastic single-player game. They achieved this by introducing the concept of “age” (the sum of tile numbers on the board) to partition the game’s massive state space, enabling the enumeration of over a trillion states and afterstates. Their method identified an optimal strategy with an expected score of approximately 50724.26 for common initial states and revealed insights into game dynamics and optimal play, including the importance of optimal actions at critical junctures and the slight disadvantage of starting with a ‘4’ tile.
The popular single-player puzzle game 2048, known for its simple rules but deep strategic complexity, has long been a challenging environment for artificial intelligence research. While the original game is played on a 4×4 grid, researchers often explore smaller variants to test new algorithms and computational methods. A significant breakthrough has recently been announced: the 4×3 variant of 2048 has been “strongly solved.”
Strongly solving a game means identifying the optimal move for every possible state, effectively mapping out the entire game space to guarantee the best possible outcome from any given point. This is a monumental task, especially for games with a vast number of potential configurations.
The Challenge of 2048 4×3
The 2048 4×3 variant, with its 12 cells, might seem only slightly smaller than the original 4×4 (16 cells), but the number of possible game states is still astronomically large. Previous work had strongly solved the even smaller 3×3 variant, which had a manageable 48 million states. However, the 4×3 variant presented a much greater hurdle, with researchers identifying an astounding 1,152,817,492,752 reachable states and 739,648,886,170 afterstates. This scale is more than 10,000 times larger than the 3×3 version, making straightforward enumeration impossible.
The ‘Age’ of a State: A Game-Changing Concept
The key to conquering this immense state space lies in a novel concept introduced by Tomoyuki Kaneko and Shuhei Yamashita: the “age” of a state. The age is simply defined as the sum of all tile numbers on the board. This seemingly simple metric proved to be incredibly powerful because of two crucial properties:
- When a player makes a move (up, down, left, or right), the age of the board remains invariant between the state and its successive afterstate. Any merging of tiles (e.g., two ‘2’s becoming a ‘4’) maintains the total sum.
- When the environment responds by spawning a new tile (either a ‘2’ or a ‘4’), the age of the state increases predictably by two or four.
This “age” property allowed the researchers to partition the entire state space into smaller, more manageable subsets. By processing states in increasing order of age (a “forward” pass) and then calculating optimal values in decreasing order of age (a “backward” pass), they could systematically enumerate and evaluate all reachable states without needing to hold the entire game tree in memory simultaneously. This approach meant that at any given time, only a few consecutive “ages” needed to be in memory, making the computation feasible on a personal computer.
Also Read:
- Unlocking Wordle’s Secrets: How Constraint Satisfaction Improves Guessing Strategies
- Learning Abstract Models for Strategic AI in Hidden-Information Games
Computational Feats and Optimal Play
The computational effort was significant, taking several days on a modern CPU. To store the vast amount of data (over a trillion afterstate IDs), the team employed a compact representation technique based on Elias-Fano codes. This method dramatically reduced the storage requirement from an estimated 4.4 terabytes (TiB) to about 1.4 TiB, while still allowing efficient lookup of state information.
The results of this strong solve are fascinating. For the most common initial states (those starting with two ‘2’ tiles), the optimal strategy yields an expected score of approximately 50724.26. The research also revealed several insights into the game’s dynamics:
- “Valleys” in the number of states and “jumps” in optimal values were observed at ages that are multiples of 2048. This indicates the inherent difficulty of creating larger tiles like 2048, which requires careful tile arrangement.
- Starting with a ‘4’ tile in an initial state was found to be a slight disadvantage compared to starting with two ‘2’ tiles, resulting in a few points lower in the expected optimal score.
- The average number of empty cells on the board remains surprisingly stable, around 1.5, for most of the game, highlighting the constant pressure of limited space.
- The difference between optimal and suboptimal actions was particularly pronounced near ages that are multiples of 2048, emphasizing the critical importance of making the best move during these pivotal moments.
This achievement not only adds 2048 4×3 to the growing list of strongly solved games but also provides a rich dataset for future research in reinforcement learning and game AI. The methodology, particularly the use of “age” partitioning and compact data structures, offers a valuable blueprint for tackling other complex stochastic games. For more details, you can read the full paper here.
