Maximal score for the 2048 game

Question

t's been weeks (months?) since the 2048 game--by Gabriele Cirulli--took Internet by storm. I have an explicit integer $X$ which is greater or equal than any score of this game. Possibly my $X$ is the actual maximal score, I don't know, it may go either way. Thus my question: what is the maximal possible score for game 2048? (I'll provide $X$ in an answer below, as a SPOILER; it was quite straightforward to get $X$, and similar upper bounds for a way larger family of similar games). If $X$ is not sharp than sharper bounds are welcome too.

BTW, have anybody published an upper bound for 2048 on Internet or elsewere? (If there is a respective link then I'd like to see the article).

---

REMARK: While the earlier nice post:

  Expected halting time for "The 2^n Game" (aka 2048) -- with random moves

is related to the game 2048, this post and my question and my answer below are otherwise not related. It's nice to know about both posts, but that's all.

The other two posts mentioned provided a construction but not a proof that it provides maximum, and there is no other proof of a specific lower bound there. Their style seems to be of the type: I cannot do it better (without even attempting a mathematical proof of a bound). Please, show me in those posts that it's otherwise (a feeling that a construction is the best is not a proof).

PS:   I'd like to see a quote of an essential moment of a rigorous proof of an upper bound for a maximal tile.

I'll clarify the simple issue of an upper bound for the total sum:

Since I have my bound for the maximal tile, let me follow it with an upper bound for the total sum. Actually, it is obtained as corollary to a maximal configuration (even if such a configuration can be fictitious--nevertheless, all tiles have values not exceeding the respective tiles of the fictitious configuration).

Once again, it will be easier to consider the general templates (see the answer below) and the logarithmic notation.

Consider $\ A=A_0=A_1=\ldots$ and $\ \forall_{n=0\ 1\ \ldots}\ |A_n|=b\ $ be finite (the playing board is finite so-to-speak). Consider an arbitrary non-negative integer $n$. For each $\ x\in A_n\ $ consider one of its oldest ancestors. By permuting sets $\ A_n\ $ we may assume that $\ x\ $ itself is always its ancestor whenever there is an ancestor for $\ x.\ $ Now let $\ \xi\ $ be the set of all $\ y\in A_n\,\ $ different from $\ x,\ $ for which there is an ancestor at least as old as the one for $\ x.\ $. Then $\ x\ $ has all its ancestors in $\ A(x) := A\setminus\xi.\ $ Observe that functions (moves) preserve $\ A(x).\ $ Thus we can consider the induced template for $\ A(x)\ $ and the respective bound:

$$h_n(x)\ =\ (b-|\xi|) + S - 1$$

That's all.

REMARK The permutation argument is obvious in the context of templates while it feels messy in the special case of the game 2048.

REMARK Let me repeat what I said from the start, that the whole thing is straightforward. A simple proof when it appears in a result+proof combination can still have a value (when the theorem is significant). @Pietro's above comment is too sketchy. The @David's post math.stackexchange.com/a/902535/448 still doesn't mention some points, as simple as the whole thing is (see my comment over there at stackexchange). But anyway, a complete proof, with all essential moments was already provided by me below (and also above for the total sum), and in an extended generality. David's post simply repeats my obvious main idea--anyway, there is perhaps but one sensible way, but for details.

Answer 1

 |
 |
 |
 v   SPOILER
 |
 |
 |
 |
 v   SPOILER
 |

The game 2048 is played on a 4x4 board. At each turn a tile which has value 2 or 4 is set on an empty square (by a random program or by a Player 0); then an Internaut (Player 1) uses one of the directional buttons to merge some pairs of tiles of equal value $2^k$ (within each proper pair) so that such a pair is replaced by a new tile of value $2^{k+1}$. The exact description is easily obtained on Internet. The goal is to obtain a tile which has a maximal value (the sum of tiles is considered too as a tie-break; I'll ignore here this auxiliary goal).

We assume here that the two players 0 and 1 cooperate(!) as best as possible.

Thus each tile has a value which is a power of 2 which makes sense psychologically but I will use a logarithmic scale. Thus in the logarithmic version I'll talk about checkers (instead of tiles), and about their degree or height (instead of value). Then the height of the merging checkers will increase by 1 (instead of tiles being multiplied by 2). And there will be no checkerboard :-) -- see the details just below.

I'll introduce a notion of template which can be associated with many similar games, and which easily provides an explicit bound on the maximal score (possibly not sharp). Let $S\in\mathbb R$ be an arbitrary fixed real. A template is a pair of two sequences (of moves and heights):

$$m_k : A_k\rightarrow A_{k+1},\quad h_k : A_k \rightarrow \mathbb R\quad(k=0\ 1\ ...)$$

such that:

• $\ \sup(h_0)\ \le\ S$
• $\ \forall_{k>0}\forall_{x\in A_k}\ (m_{k-1}^{-1}(x)=\emptyset\ \Rightarrow\ h_k(x) \le S)$
• $\ \forall_{k>0}\forall_{x\in A_k}\ \left(\ m_k^{-1}\left(x\right)\ne\emptyset\ \Rightarrow\ h_k\left(x\right) \le \sup \left(h_{k-1}|\,\,m_{k-1}^{-1}\left(x\right)\right)\ +\ \min\!\left(2,\ \left|m_{k-1}^{-1}(x)\right|\right) - 1\ \right)$

When $\ 0\le k\le n\ $ and $\ x\in A_n$, let's introduce the ancestors:

$$p_k(x) := (m_{n-1}\circ\ \ldots\ \circ\ m_k)^{-1}(x)$$

In particular, $\ p_n(x) = \{x\}\ $ for every $\ x\in A_n$. An upper bound for games similar to 2048 follows immediately from the following simple observation about the maximal size of a generation of ancestors, defined as follows:

$$\forall_{x\in A_n}\ \pi(x)\ :=\ \max_{0\le k\le n} |p_k(x)|$$

Of course $\ \pi(x) \ge 1$.

Theorem: $$\forall_{n=0\ 1\ \ldots}\forall_{x\in A_n}\quad h_n(x)\ \le\ \pi(x) - 1 + S$$

or equivalently:

$$\forall_{n=0\ 1\ \ldots}\forall_{x\in A_n}\quad \pi(x)\ \ge\ h_n(x) + 1 - S$$

Proof (by induction on $n$):   The theorem holds when $\ h_n(x)\le S$ Now assume that the theorem holds whenever $\ h_n(t)\le S+n-1,\ $ where $n$ is a positive integer. Thus let's consider an arbitrary $x$ such that $\ h_n(x) \le S+n,\ $ where $n$ is still an arbitrary positive integer. If necessary we may go down the line of single ancestors so that we end with an ancestor $x'$ for which $\ h_n(x')=h_n(x) \le S+n\ $ for which has at least to different parents $\ y\ z\in A_k\ $ in the respective previous set. Looking still at older generations, one of the parents, say $y$, has ancestors at least as old as the other one, $z$. Thus:

$$\pi(x)\ \ge\ 1 + \pi(z) \ge 1 + (h_n(z) + 1 - S)\ \ge\ 1 + (h_n(x) - S)\ =\ h_n(x) + 1 - S$$

End of the proof.

Now we get the promised upper bound:

Corollary Let b be a non-negative integer (a finite cardinality) such that $\ \forall_{n=0\ 1\ \ldots}\ |A_n| = b$. Then:

$$\forall_{n=0\ 1\ \ldots}\forall_{x\in A_n}\quad h_n(x)\ \le\ b-1+S$$

Application to the game 2048:   We may set $\ S := 2 =\log_2(4)\ $ and $\ b:=16.\ $ Then the logarithmic bound is $16 - 1 + 2\ =\ 17$ or the standard (exponential) game-2048 upper bound for any single (maximal) tile is $\ 2^{17}$.

One could discuss a bit how and when a game ends but this answer is already long enough.