Josh's blog

Number shuffler addition

My current diversion of late has been Threes. You may have heard of the rip-off that spawned a thousand similar rip-offs, 2048. I will call this kind of game “number shufflers” even though the tiles don’t have to be numbers.

In both the original, and superior, game Threes, and the many derivations, you have a board of fixed size and a number of tiles. A tile is added after each move, and the game ends when no space remains, therefore it is in the player’s interest to eliminate tiles. The only way to do so is to combine “twins”—tiles with the same number/type. (Threes has the wrinkle that there are special “1” and “2” tiles that can only be combined as 1+2.) Combining two twins gives you a tile of the next type. With numbers, the resulting tile usuallly has the value of the sum of the previous two tiles. Thus as you create higher and higher tiles, you have fewer chances to combine them, and the tile values increase exponentially.

I got thinking about the large numbers possible in these games. It is known that presenting a gamer with huge numbers leads to reduced ability to compare them quickly. Who is going to sit down and compare all the digits for their three gajillion fantillion power level character against some other bazillionty level character, especially in the middle of an action-fight sequence? This is a problem avoided with Threes (et al) simply because the higher tiles are much rarer, and it is a puzzle game where you can take as much time as you like.

You could represent the tiles with simpler numbers—1, 2, 3, 4, etc, instead of the exponentially increasing 3, 6, 12, 24, and so on. But then the “addition” breaks. “Adding” two tiles of the same kind just gives you the next tile, not the sum of the two. For example, instead of \(1+1=2, 2+2=4, 4+4=8\), one has \(1\oplus1 = 2, 2\oplus2 = 3, 3\oplus3 = 4\). With a little thought it turns out it’s very easy to implement \(\oplus\) with a kind of twisted addition defined as follows:

$$a \oplus b := \log_2( 2^a + 2^b ) \quad\text{ for all } a, b.$$

For example, $$2 \oplus 2 = \log_2( 2^2 + 2^2 ) = \log_2(4+4) = \log_2 8 = 3.$$

It is easy to see that \(\oplus\) is commutative (swap inside the logarithm) and even associative:

$$\begin{align} (a \oplus b) \oplus c &= \log_2\left(2^{a\oplus b} + 2^c \right) \\ &= \log_2\left( 2^{\log_2(2^b + 2^c)} + 2^c \right) \\ &= \log_2(2^a + 2^b + 2^c) \end{align}$$

(similarly for the other arrangement). Most pleasingly, however, regular addition distributes over \(\oplus)\):

$$\begin{align} a + (b\oplus c) &= a + \log_2(2^b + 2^c) \\ &= \log_2 2^a + \log_2(2^b + 2^c) \\ &= \log_2 2^a(2^b + 2^c) \\ &= \log_2 (2^{a+b} + 2^{a+c}) \\ &= (a+b)\oplus (a+c).\end{align}$$

You get “fun” results if you add two different numbers, and it seems that there’s no identity element unless you include \(-\infty\) and assert that \(2^{-\infty} = 0\) (alternatively, \(\log 0 = -\infty\)). Thus

$$x \oplus (-\infty) = \log_2(2^x + 2^{-\infty}) = \log_2 (2^x + 0) = x.$$

Furthermore there are no inverse elements unless you escape the extended real line entirely. For example, \(\log_2(-1) = \frac{i\pi}{\ln 2}\), and therefore

$$\begin{align} 0 \oplus \frac{i\pi}{\ln 2} &= \log_2\left( 2^0 + e^{i\pi} \right) \\ &= \log_2(1 - 1) = -\infty.\end{align}$$

I should be doing work.