2014/08/27 by Rahul Mehta, Mehta, Rahul
Computer Science · #Advanced Graph Theory Research #Artificial Intelligence in Games #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #F.1 #F.2.2 #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1408.6315
openalex publication_date 2014/08/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 × n game board G, computing a sequence of moves to reach a particular configuration ℂ from an initial configuration ℂ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 S ∈ \\Uparrow, \Downarrow, ⇐, ⇒\k of length k that results in a winning configuration for an n × n game board is fixed-parameter tractable (FPT). We describe an algorithm to solve this problem in O(4k n2) time.