License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2016.1
URN: urn:nbn:de:0030-drops-58858
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5885/
Abdelkader, Ahmed ;
Acharya, Aditya ;
Dasler, Philip
2048 Without New Tiles Is Still Hard
Abstract
We study the computational complexity of a variant of the popular 2048 game in which no new tiles are generated after each move. As usual, instances are defined on rectangular boards of arbitrary size. We consider the natural decision problems of achieving a given constant tile value, score or number of moves. We also consider approximating the maximum achievable value for these three objectives. We prove all these problems are NP-hard by a reduction from 3SAT.
Furthermore, we consider potential extensions of these results to a similar variant of the Threes! game. To this end, we report on a peculiar motion pattern, that is not possible in 2048, which we found much harder to control by similar board designs.
BibTeX - Entry
@InProceedings{abdelkader_et_al:LIPIcs:2016:5885,
author = {Ahmed Abdelkader and Aditya Acharya and Philip Dasler},
title = {{2048 Without New Tiles Is Still Hard}},
booktitle = {8th International Conference on Fun with Algorithms (FUN 2016)},
pages = {1:1--1:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-005-7},
ISSN = {1868-8969},
year = {2016},
volume = {49},
editor = {Erik D. Demaine and Fabrizio Grandoni},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5885},
URN = {urn:nbn:de:0030-drops-58858},
doi = {10.4230/LIPIcs.FUN.2016.1},
annote = {Keywords: Complexity of Games, 2048}
}
|
Keywords: |
|
Complexity of Games, 2048 |
|
Collection: |
|
8th International Conference on Fun with Algorithms (FUN 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
02.06.2016 |
