

\subsection{Acyclicity of the 2048 game}

The 2048 game consists of a 4$\times$4 grid board, totaling 16 squares.
 At the beginning of the game,  two squares are randomly filled
  with tiles of either 2 or 4.
  Players can make moves in four directions: \textit{up}, \textit{down},
   \textit{left}, and \textit{right}. 
   When a player chooses a direction, 
   all tiles will move in that direction until 
   they hit the edge or another tile. 
   If two tiles with the same number are adjacent 
   in the moving direction, they will merge into 
   a tile with the sum of the original numbers.
   Each tile can only participate in one merge operation per move.
   After each move, a new tile appears on a random empty square.
   The new tile is 2 with  probability 0.1, and 4 with probability 0.9.
The game ends when all squares are filled, and no valid merge operations can be made. 


\begin{theorem}
2048 game is acyclic between non-absorbing states.
\end{theorem}
\begin{IEEEproof}
 To apply Theorem \ref{judgmentTheorem}, what we need 
 to do is to assign a countable value to the 2048 game board 
 and demonstrate the properties of the 
 state transition probabilities in the 2048 game.


In the 2048 game, each tile has 16 potential values,
 including empty, and $2^k$, where $k\in\{1,2,3,\ldots,15\}$.
Using 4 bits to represent a tile, the game board is a 4$\times$4 matrix 
$B$. The corresponding tile is then computed as follows:
\begin{equation}
1\leq m\text{, }n \leq 4\text{, }tile_{m,n} =
\begin{cases}
0, & \text{if } B_{mn}=0; \\
 2^{B_{mn}}, & \text{otherwise.}  
\end{cases}
\label{equationTile}
\end{equation}
The sum of all tiles in the game board is
\begin{equation}
sum(B) = \sum_{m=1}^4\sum_{n=1}^4 tile_{mn}.
\end{equation}
A 64-bit long integer can uniquely represent any game board state.
\begin{equation}
long(B)= \sum_{m=1}^4\sum_{n=1}^416^{(m-1)*4+(n-1)}\cdot B_{mn}.
\end{equation}
We have 
\begin{equation}
long(B)<2^{64}.
\label{size}
\end{equation}
The size of the board space $\mathcal{B}$ is
$|\mathcal{B}|=2^{64}$.
Define a utility function on board,
\begin{equation}
u(B) = 2^{64}\cdot sum(B)+long(B).
\label{utility}
\end{equation}
It is easy to verify that 
$\forall B_1, B_2\in \mathcal{B}$,
if $B_1\neq B_2$, then $u(B_1)\neq u(B_2)$.
For all possible board,
 $\forall B\in \mathcal{B}$, calculate the utility value
 $u(B) $, and sort $B$ by $u(B) $ in ascending order.
 Let $I(B)$ be the index of the board $B$ after sorting,
 we have
 \begin{equation}
 \forall B_1, B_2\in \mathcal{B}, u(B_1)<u(B_2) \iff
 I(B_1)<I(B_2).
 \label{basis}
 \end{equation}
For any transition $\langle B_1, a, B_1', B_2\rangle$ in the 2048 game,
we have 
$sum(B_1)=sum(B_1')$  regardless of whether at least two tiles merge.
\highlight{需要昕闻画2048的状态迁移图，同一个状态包括两种后续情况，
一种是发生合并，一种是没发生合并的}


Due to a new generated 2-tile or 4-tile in board $B_2$,
$sum(B_2)>sum(B_1')$, that is $sum(B_2)>sum(B_1)$.

Based on (\ref{size}) and (\ref{utility}),
we have  $u(B_2)>u(B_1)$.
That means $I(B_2)>I(B_1)$.
The transition probability between non-absorbing state satisifies (\ref{condition}),
the claim follows by applying Theorem \ref{judgmentTheorem}.
\end{IEEEproof}

%\input{material/2048prove}

\subsection{Discussions}


















