1 Search Results for "Acharya, Aditya"


Document
2048 Without New Tiles Is Still Hard

Authors: Ahmed Abdelkader, Aditya Acharya, and Philip Dasler

Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)


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.

Cite as

Ahmed Abdelkader, Aditya Acharya, and Philip Dasler. 2048 Without New Tiles Is Still Hard. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{abdelkader_et_al:LIPIcs.FUN.2016.1,
  author =	{Abdelkader, Ahmed and Acharya, Aditya and Dasler, Philip},
  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 =	{Demaine, Erik D. and Grandoni, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.1},
  URN =		{urn:nbn:de:0030-drops-58858},
  doi =		{10.4230/LIPIcs.FUN.2016.1},
  annote =	{Keywords: Complexity of Games, 2048}
}
  • Refine by Author
  • 1 Abdelkader, Ahmed
  • 1 Acharya, Aditya
  • 1 Dasler, Philip

  • Refine by Classification

  • Refine by Keyword
  • 1 2048
  • 1 Complexity of Games

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail