Eppstein, David
Making Change in 2048
Abstract
The 2048 game involves tiles labeled with powers of two that can be merged to form bigger powers of two; variants of the same puzzle involve similar merges of other tile values. We analyze the maximum score achievable in these games by proving a minmax theorem equating this maximum score (in an abstract generalized variation of 2048 that allows all the moves of the original game) with the minimum value that causes a greedy changemaking algorithm to use a given number of coins. A widelyfollowed strategy in 2048 maintains tiles that represent the move number in binary notation, and a similar strategy in the Fibonacci number variant of the game (987) maintains the Zeckendorf representation of the move number as a sum of the fewest possible Fibonacci numbers; our analysis shows that the ability to follow these strategies is intimately connected with the fact that greedy changemaking is optimal for binary and Fibonacci coinage. For variants of 2048 using tile values for which greedy changemaking is suboptimal, it is the greedy strategy, not the optimal representation as sums of tile values, that controls the length of the game. In particular, the game will always terminate whenever the sequence of allowable tile values has arbitrarily large gaps between consecutive values.
BibTeX  Entry
@InProceedings{eppstein:LIPIcs:2018:8812,
author = {David Eppstein},
title = {{Making Change in 2048}},
booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)},
pages = {21:121:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770675},
ISSN = {18688969},
year = {2018},
volume = {100},
editor = {Hiro Ito and Stefano Leonardi and Linda Pagli and Giuseppe Prencipe},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8812},
URN = {urn:nbn:de:0030drops88124},
doi = {10.4230/LIPIcs.FUN.2018.21},
annote = {Keywords: 2048, changemaking problem, greedy algorithm, integer sequences, halting problem}
}
2018
Keywords: 

2048, changemaking problem, greedy algorithm, integer sequences, halting problem 
Seminar: 

9th International Conference on Fun with Algorithms (FUN 2018)

Issue date: 

2018 
Date of publication: 

2018 