🤖 AI

Strongly Solving 2048 4x3

This paper presents the strong solution of the 4x3 variant of the stochastic game 2048, determining an optimal expected score of approximately 50,724.26 by utilizing an age-based partitioning technique to manage its vast state space of over 1.15 trillion reachable states.

Original authors: Tomoyuki Kaneko, Shuhei Yamashita

Published 2026-05-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tomoyuki Kaneko, Shuhei Yamashita

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine the popular puzzle game 2048 as a giant, chaotic kitchen where you are trying to combine ingredients (tiles) to make bigger and bigger dishes. In the standard version, you have a 4x4 grid (16 spots). In this paper, the authors decided to shrink the kitchen down to a 4x3 grid (12 spots), making it a tighter, more crowded challenge.

Here is the simple breakdown of what they did, how they did it, and what they found, using everyday analogies.

1. The Big Challenge: A Library Too Huge to Read

The authors wanted to "strongly solve" this smaller version of the game. In game terms, this means they didn't just want to know the best move for the start; they wanted to know the perfect move for every single possible situation the game could ever reach.

Think of the game's possible situations as a library.

The original 3x3 version (Mini2048) was like a small bookshelf with about 48,000 books. Easy to read.
This new 4x3 version is a massive library with over 1.15 trillion books (states) and nearly 740 billion "intermediate" books (afterstates).

Trying to read every book in this library one by one would take forever and require a computer with more memory than exists in the world. The authors needed a magic trick to organize this library so they could solve it in just a few days on a regular personal computer.

2. The Magic Trick: The "Age" of the Game

The key to their success was a concept they call "Age."

Imagine every time you play the game, you are adding weight to a scale.

When you start, you have two tiles (say, two 2s). The "Age" is the sum of all numbers on the board (2 + 2 = 4).
When you slide tiles and merge them, the numbers double, but the Age stays exactly the same. (Merging two 2s into a 4 doesn't change the total sum).
The only time the Age changes is when the computer randomly drops a new tile (a 2 or a 4). This adds 2 or 4 to the Age.

The Analogy:
Think of the game not as a maze, but as a multi-story building.

Each "floor" of the building represents a specific Age (e.g., Floor 4, Floor 6, Floor 8...).
You can move around freely on the same floor (sliding and merging tiles) without going up or down.
You only move to the next floor when the computer drops a new tile.

Because the game always moves forward in Age (you never go back to a lower sum), the authors could treat the library floor by floor. They didn't need to hold the whole library in their head at once. They just needed to keep the current floor, the next floor, and the one after that in their memory. Once they finished calculating the best moves for Floor 100, they could throw away the data for Floor 98 to make room for Floor 102.

3. The Compression: Fitting a Whale in a Backpack

Even with this floor-by-floor trick, the data was still huge. If they tried to write down every single game state on paper, it would take up about 4.4 Terabytes of hard drive space (roughly the size of a massive data center).

To fix this, they used a clever data compression technique called Elias-Fano coding.

The Analogy: Imagine you have a list of 1 billion people, but they are all wearing red shirts. Instead of writing "Red Shirt" next to every single name (which wastes space), you write a special code that says, "Everyone in this list is wearing red."
They found a way to compress the "ID cards" of every possible game state down to about 1.4 Terabytes. If they only cared about the best moves (ignoring the raw data), they could shrink it even further to about 300 Gigabytes (the size of a high-end laptop's hard drive).

4. The Results: What Did They Learn?

By solving the game, they calculated the perfect expected score for a player who never makes a mistake.

The Score: If you start with the most common setup (two 2s) and play perfectly, you can expect to score about 50,724 points.
The "Bad Luck" Factor: They found that starting with a 4 tile instead of two 2s actually puts you at a slight disadvantage (about 4 points lower). It's like starting a race with a heavy backpack; you have to work harder to catch up.
The "2048" Hump: The graph of their results showed "valleys" (dips in performance) whenever the Age reached multiples of 2048. This confirms a feeling many players have: it gets incredibly hard to make the 2048 tile because you are running out of space on your small 12-square board. You need perfect arrangement to fit all the smaller numbers (2, 4, 8... up to 1024) before you can combine them.

Summary

The authors took a game that seemed too complex to solve completely because of its massive number of possibilities. They realized that the game naturally organizes itself by the "sum of numbers" (Age). By treating the game as a series of floors rather than a giant tangled web, and by using a super-efficient filing system (compression), they mapped out the perfect strategy for every possible move.

They proved that with a standard computer and a few days of work, you can mathematically master a game that usually relies on luck and intuition.

Technical Summary: Strongly Solving 2048 on a 4×3 Board

Problem Definition

This paper addresses the "strong solution" of a stochastic, single-player game variant: 2048 on a 4×3 board (denoted as 2048 $^{4\times3}$ ). Unlike the standard 4×4 version, this variant utilizes a grid of 12 cells. The game is modeled as a Markov Decision Process (MDP) where an agent selects actions (up, down, left, right) to merge adjacent tiles of equal value. Following a valid action, the board state deterministically transitions to an "afterstate" (sliding and merging tiles). Subsequently, the environment stochastically spawns a new tile (2 with 90% probability, 4 with 10%) in a random empty cell, transitioning to the next state.

The objective is to compute the optimal policy $\pi^*$ and the optimal value function $v^*(s)$ , representing the expected cumulative reward from any reachable state $s$ . The primary challenge lies in the state space size: the 4×3 variant contains approximately $1.15 \times 10^9$ reachable states and $7.4 \times 10^8$ afterstates. This scale is roughly $10^4$ times larger than the previously solved 3×3 variant (Mini2048), rendering straightforward enumeration and storage infeasible on standard hardware.

Methodology

The authors propose a solution based on state space partitioning by "age" and compact data representation.

1. Age-Based Partitioning

The core innovation is defining the age of a state as the sum of all tile numbers on the board ( $age(s) = \sum c_i$ ).

Invariance: The age remains constant between a state and its immediate afterstate following a valid action (since merging tiles preserves the sum of values, and sliding does not change values).
Progression: The age increases by 2 or 4 during the stochastic transition (spawning a new tile).
Algorithmic Implication: This property allows the state space to be partitioned into disjoint subsets based on age.
- Forward Pass (Enumeration): Valid states of age $n$ can be generated solely from afterstates of ages $n-2$ and $n-4$ . The algorithm iterates through increasing ages, maintaining only three sets in memory (current age, age+2, age+4) to enumerate all reachable states and afterstates.
- Backward Pass (Value Computation): Optimal values are computed by iterating backward from the maximum age to the initial age. The value of a state is the maximum value of its reachable afterstates; the value of an afterstate is the expected value of its reachable next states (weighted by spawn probabilities).

2. Compact Representation

To handle the storage requirements (estimated at ~4.4 TiB for raw 48-bit IDs), the authors employ Elias-Fano codes for storing sets of unique state IDs.

Structure: Sorted unique IDs are split into high-order bits ( $h_i$ ) and low-order bits ( $l_i$ ). The low bits are stored in a contiguous bit-vector, while the high bits are encoded in a sparse bit-vector $H$ using rank operations.
Optimizations:
- Symmetry Reduction: IDs are normalized to the minimum value among horizontal, vertical, and 180-degree rotational symmetries.
- Base Adaptation: The encoding base is adjusted based on the maximum tile value for a specific age.
- Cell Dropping: One cell's information is dropped during encoding because the sum (age) constrains the total, allowing full reconstruction later.
Efficiency: This reduces the storage for all afterstate IDs from ~4.4 TiB to approximately 1.4 TiB while maintaining efficient lookup capabilities. For optimal play specifically, a specialized representation (using the BuRR algorithm) reduces the requirement to under 300 GiB.

Key Results

State Space Statistics: The total number of reachable states is 1,152,817,492,752, and the number of afterstates is 739,648,886,170.
Optimal Expected Score: For the most common initial states (two tiles of value 2), the expected score under an optimal strategy is approximately 50,724.26.
- Initial states with a 4 tile (age 6) yield a slightly lower expected score (~50,720.62).
- Initial states with two 4 tiles (age 8) yield the lowest (~50,708.99), indicating a small disadvantage to starting with higher-value tiles.
State Distribution: The number of states per age is generally manageable (less than $3 \times 10^6$ per age), allowing the algorithm to keep several age layers in memory.
Terminal States: "Valleys" in the state count distribution occur at ages that are multiples of 2048, reflecting the difficulty of forming large tiles with limited board space. Certain ages (e.g., 8190, 12286) have zero valid afterstates because forming those sums would require more tiles than the 12 available cells allow.
Action Sensitivity: The difference in value between optimal and suboptimal actions peaks near ages 2048 and 4096, suggesting that early decisions immediately after forming large tiles are critical.

Significance and Claims

The paper claims to have strongly solved the 2048 $^{4\times3}$ variant, a task previously considered intractable due to the state space size. The significance of this work lies in:

Scalability: Demonstrating that a game with over $10^9$ states can be solved on a personal computer within a few days by leveraging game-specific structural properties (age) rather than brute-force methods.
Methodological Contribution: The introduction of the "age" partitioning technique allows for the enumeration and value computation of stochastic MDPs where state values depend on expectations, effectively bypassing the need for $\alpha\beta$ pruning (which is ineffective in stochastic environments).
Data Availability: The authors provide the optimal value function and a compact representation of the state space, serving as a baseline for future reinforcement learning research and game analysis.
Storage Efficiency: The successful application of Elias-Fano codes to compress a massive set of game states to ~1.4 TiB makes the dataset accessible for researchers with moderate computational resources (e.g., 4 TiB SSDs).

The authors note that while the primary goal was solving the game, the resulting dataset and the "age" concept may serve as a foundation for further studies in stochastic games and reinforcement learning evaluation.