|
 |
 |
 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},\ 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.

  |
 |
 |
 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.

  |
 |
 |
 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},\ 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$, is 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.

  |
 |
 |
 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},\ 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.