Coincidentally, the same day as my FUN 2018 paper “Making Change in 2048” appeared on the arXiv (arXiv:1804.07396), another paper on 2048 also appeared. It is “Analysis of the Game “2048” and its Generalization in Higher Dimensions” (Madhuparna Das and Goutam Paul, arXiv:1804.07393), and one of the things it looks at is higher dimensional versions of the game. I didn’t know about these before, but you can play two such versions at 2048 4D (16 cells like the usual 2048, but arranged as a hypercube) and 2048 5D (the same thing but with 32 cells in a higher dimension).

16-cell 2048 goes on long enough to be addictive but eventually you get stuck, after a few thousand moves. The total tile value goes up by 2 (or 4) at each step and to represent this number you need at least as many tiles as the number of ones in its binary representation. Eventually you reach numbers whose binary representations have too many ones and you can’t fit all their tiles onto the board. But I think that in 32-cell variants that use the same system of tile values (like the 5D one above) you are likely to get bored before you get stuck, because the numbers that can be represented with 32 tiles are so much bigger. But what about if you use other tile values than the binary numbers (still allowing tiles to combine when their sum is another tile)? A couple of years ago I posted a proof that the game terminates whenever the tile values have arbitrarily large gaps, and the new paper expands on that proof and gives you a way of telling exactly how many steps you can hope to go before getting stuck.

The termination proof for standard 2048 uses the optimal representation of the current total tile value as a sum of powers of two (its binary representation) and observes that the number of terms in this optimal representation controls how many game squares you need to reach that tile value. But for other games, it turns out that it’s not the optimal representation that’s important, but the greedy representation. We pretend that the tiles are really coins (of the value shown on the tile), and use them to make change for the total tile value, using the greedy change-making algorithm (in which we repeatedly use as large a tile as possible to approximate the remaining value). If the greedy algorithm would use a certain number of coins for a given tile value, then the 2048-like game would need at least the same number of squares to reach the same tile value.

To prove this, my paper has to generalize, beyond five-dimensional hypercubes, to a form of 2048 where you can slide any set of two or more tiles into each other (no matter how they are arranged) and combine them to form a larger tile (as long as they add up to exactly the larger tile’s value). For this version of the game, the relation between 2048 and greedy change-making is exact, and there is a min-max theorem: the maximum tile value you can achieve with a given number of squares equals the minimum value that would cause greedy change-making to use the same number of coins!

I think the following example will make the difference between optimal representations and greedy representations clearer. Suppose you have coins whose values form the sequence

\[1, 2, 4, 5, 8, 10, 16, 17, 20, 21, 32, \dots\]

Do you see the pattern in these numbers? It is clearer if we write their binary representations:

\[1, 10, 100, 101, 1000, 1010, 10000, 10001, 10100, 10101, 100000, \dots\]

They are the numbers that have every other bit zero (sequence A126684 in the OEIS). Either all the bits in the even positions of their binary representations are zero, or all the bits in the odd positions are zero. You can represent any positive integer \(x\) as a sum of two numbers in this sequence, by splitting the binary representation of \(x\) into the even and odd bit positions. So if we used these numbers as coin values, we could make change for any amount of money using only two coins! But not with the greedy algorithm.

Coins of value 1, 2, 4, 5, 8. 10, and 16

(From Category:Coins by face value. Anyone know where to find a 17-unit coin?)

If we make change with these coins, let \(g(k)\) denote the smallest value that causes the greedy algorithm to use \(k\) coins, or equivalently the largest value achievable in a 2048-like game with \(k\) squares. Then \(g(k)\) can be found recursively from \(g(k-1)\) by finding the largest gap between two coins that is bigger than \(g(k-1)\) and adding the bottom of the two coin values on either side of the gap to \(g(k-1)\). So, for instance, because \(g(2)=3\) (the smallest value not representable as a single coin), and the first gap bigger than \(3\) is between \(10\) and \(16\), we have \(g(3)=3+10=13\). If you try to make change for \(13\) greedily, you have to use a \(10\)-unit coin (the big gap prevents any bigger coin from being usable) and you are left with \(3\) units taking another two coins. The sequence of largest gaps in A126684 are easy to calculate: they are the ones between \(2^i\) (a power of two) and \(\lfloor 2^{i+1}/3\rfloor\) (the number with alternating ones and zeros in its binary representation closest to that power of two). And based on this, we can calculate the values of \(g(k)\) for A126684: they are the sequence

\[1, 3, 13, 55, 225, 907, 3637, 14559, 58249, 233011, \dots\]

This is a new sequence in OEIS, A302757, but an unexpectedly nice one. It obeys the recurrences

\[g(k)=4g(k-1)+2k-5\]

and

\[g(k)=6g(k-1)-9g(k-2)+4g(k-3)\]

and the formula

\[g(k)=\frac{2^{1+2k} - 6k + 7}{9}.\]

(The first found by me, the second two rapidly added by OEIS regular Colin Barker.) Based on this, it looks like the right size of board for a 2048-like game using these tiles is around \(3\times 3\). The usual \(4\times 4\) board would allow a total tile value of \(954437167\), big enough that you will get bored before you reach it.

Finally, as my paper notes, there are a couple other 2048-like games that my paper’s analysis is inapplicable to. They are 2048 circle of fifths (in which the tile values use modular arithmetic) and 2048 numberwang (in which random things happen including occasional unexpected tile combinations). So, if you want to play a web game while justifying the time as research, go play those!