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.22
URN: urn:nbn:de:0030-drops-58661
URL: https://drops.dagstuhl.de/opus/volltexte/2016/5866/
Langerman, Stefan ; Uno, Yushi
Threes!, Fives, 1024!, and 2048 are Hard
| pdf-format: |
|
Abstract
We analyze the computational complexity of the popular computer games Threes!, 1024!, 2048 and many of their variants. For most known versions expanded to an m*n board, we show that it is NP-hard to decide whether a given starting position can be played to reach a specific (constant) tile value.
BibTeX - Entry
@InProceedings{langerman_et_al:LIPIcs:2016:5866,
author = {Stefan Langerman and Yushi Uno},
title = {{Threes!, Fives, 1024!, and 2048 are Hard}},
booktitle = {8th International Conference on Fun with Algorithms (FUN 2016)},
pages = {22:1--22: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/5866},
URN = {urn:nbn:de:0030-drops-58661},
doi = {10.4230/LIPIcs.FUN.2016.22},
annote = {Keywords: algorithmic combinatorial game theory}
}
| Keywords: | algorithmic combinatorial game theory | |
| Seminar: | 8th International Conference on Fun with Algorithms (FUN 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 02.06.2016 |
