2048 is (PSPACE) Hard, but Sometimes Easy

Abstract

We prove that a variant of 2048, a popular online puzzle game, is PSPACE-Complete. Our hardness result holds for a version of the problem where the player has oracle access to the computer player's moves. Specifically, we show that for an $n\times n$ game board $\mathcal{G}$, computing a sequence of moves to reach a particular configuration $\mathbb{C}$ from an initial configuration ${\mathbb{C}}_0$ is PSPACE-Complete. Our reduction is from Nondeterministic Constraint Logic (NCL). We also show that determining whether or not there exists a fixed sequence of moves $\mathcal{S}\in \{\Uparrow ,\Downarrow ,\Leftarrow ,\Rightarrow {\}}^k$ of length $k$ that results in a winning configuration for an $n\times n$ game board is fixed-parameter tractable (FPT). We describe an algorithm to solve this problem in $O(4^k{n}^2)$ time.

13 pages, 11 figures

Cited by in corpus (1)

• Threes!, Fives, 1024!, and 2048 are Hard