Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-116 | 6th September 2014 15:07

2048 is (PSPACE) Hard, but Sometimes Easy

RSS-Feed




TR14-116
Authors: Rahul Mehta
Publication: 6th September 2014 15:27
Downloads: 4414
Keywords: 


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 G, computing a
sequence of moves to reach a particular configuration C from an initial
configuration 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 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.



ISSN 1433-8092 | Imprint