ECCC-Report TR14-116https://eccc.weizmann.ac.il/report/2014/116Comments and Revisions published for TR14-116en-usSat, 06 Sep 2014 15:27:17 +0300
Paper TR14-116
| 2048 is (PSPACE) Hard, but Sometimes Easy |
Rahul Mehta
https://eccc.weizmann.ac.il/report/2014/116We 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.Sat, 06 Sep 2014 15:27:17 +0300https://eccc.weizmann.ac.il/report/2014/116