\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}
The 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 boards,
 $\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.
Due to a newly generated 2-tile or 4-tile in board $B_2$,
$sum(B_2)>sum(B_1')$, that is $sum(B_2)>sum(B_1)$.
Figure \ref{2048merge1} and Figure \ref{2048merge2} show transition
examples with and without a merge. 

\begin{figure}[ht]
    \begin{center}
	\include{pic/2048merge1}
	\caption{2048 transition  example with a merge, where $sum(B_1)=sum(B_1')=46$,
	 $sum(B_2)=48>sum(B_1')$.}
    \label{2048merge1}
    \end{center}
\end{figure}
\begin{figure}[ht]
    \begin{center}
	\include{pic/2048merge2}
	\caption{2048 transition  example without a merge, where $sum(B_1)=sum(B_1')=62$,
	 $sum(B_2)=64>sum(B_1')$.}
    \label{2048merge2}
    \end{center}
\end{figure}


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 satisfies (\ref{condition}),
the claim follows by applying Theorem \ref{judgmentTheorem}.
\end{IEEEproof}

%\input{material/2048prove}