Strongly Solving 2048 4 × 3

Abstract

2048 is a stochastic single-player game involving 16 cells on a 4 $\times$ 4 grid, where a player chooses a direction among up, down, left, and right to obtain a score by merging two tiles with the same number located in neighboring cells along the chosen direction. This paper presents that a variant 2048 ${}_{4\times 3}$ with 12 cells on a 4 $\times$ 3 board, one row smaller than the original, has been strongly solved. In this variant, the expected score achieved by an optimal strategy is about $50,724.26$ for the most common initial states: ones with two tiles of number 2. The number of reachable states and afterstates are identified to be $1,152,817,492,752$ and $739,648,886,170$ , respectively. The key technique is to partition the state space by the sum of tile numbers on a board, which we call the age of a state. An age is invariant between a state and its successive afterstate after any valid action and is increased by two or four by a stochastic response from the environment. Therefore, we can partition the state space by ages and enumerate all (after)states of an age depending only on states with the recent ages. Similarly, we can identify (after)state values by going along with ages in decreasing order.