\section{2048游戏的非遍历性证明}
\subsection{2048游戏编码规则}
为了完成从游戏到马尔可夫决策过程的转化，首先需要对局面进行排序，
需要给局面一一对应一个可以进行比较的值，通过这个值对局面进行排序。
需要保证的是，局面和大的排序靠后，如果局面和一样，则按照局面编码大小排序
2048的游戏棋盘是$4×4$的，每一个格子上都可以是${空格，2，4，8，16，32，64，128，256，512，1024，2048，4096，8192，16384，32768}$
这些数字，为了便于计算机内的保存本文将其一一对应为{0，1，2，3，4，5，6，7，8，9，10，11，12，13，14，15}，
因为在游戏中不存在面值为2^0=1的方块，于是在这里使用0来特别地对应上原先格子中空格的情况。这个游戏的状态是有限的，
有不超过16^16=2^64个状态，对于每一个棋盘局面本文可以执行 “上”，“下”，“左”，“右”这四个动作。 
执行动作之后将会把方块往动作方向移动，如果有两个相同幂次的方块碰撞会合并成为一个幂次加一的方块，
并且在一个空格位置随机生成一个2或者4的方块。本文将这个棋盘用一个1×16的数组B进行表示，
其中B中存放的是方块的幂次，空格用0表示，m表示数组下标。
$B_m∈{0，1，2，3，4，5，6，7，8，9，10，11，12，13，14，15}，0≤m≤15$。编码规则如下：

\begin{equation}
% 2048游戏局面编码
p=2^{64} \cdot \sum_{m=0}^{15} I(B_m \neq 0) \cdot 2^{B_m} + \sum_{m=0}^{15} (1 \ll 4m) \cdot B_m
\end{equation}

其中$\mathbb{I}(B_m≠0)$是指示函数，当B_m的值不为0的时候这个函数返回1，也就是说不统计棋盘中的空格格子，这个编码的含义是将棋盘映射成一个长整型的变量，
本文将这个结果放在比64bit更高的位置上，也就是 64-84bit的位置。这个编码的主要含义是，将局面所有数字之和放在高bit位置上，排序时局面之和大的排在后面，
状态转移时就是从小的下标转移到大的下标上。另外后面64bit就是局面的编码，来保证这个值的唯一性，一个局面会对应一个唯一的值。

\input{../pic/2048encode}

上面的图中的这个局面的编码$p=(1≪64)∙30784+0x FEDC 5432 0000 0020$。
本文是按照从下往上，从右往左的顺序给格子进行排列，右下角的格子是最低位，左上角的格子是最高位。
由此本文获得了一个有关状态的大小关系，还可以了解，对于两个不同的局面，通过这个排序可以获取每一个状态的排列后相应的下标。
特别的，本文将所有的死亡状态从序列中抽出放在状态转移的最大下标位置。

\subsection{2048游戏非终结状态的非遍历性证明}
首先能够很快得到2048游戏是不满足遍历性的这一结论，因为2048游戏本身具有众多的吸收态，因此根据定理3.2一定是不满足遍历性的。但是我们此处考虑非终结状态之间的转移关系的遍历性。
推论： 2048游戏非终结状态转移矩阵是非遍历性的。
证明：首先记2048游戏的马尔可夫决策过程在策略为π的情况下的状态转移矩阵为P_π，状态先后关系通过上面的编码方式确定，因为有吸收态存在于是可以将这个状态转移矩阵写成标准矩阵的形式：
\begin{equation}
% 带策略的马尔可夫链标准形式
[ P_\pi = \begin{pmatrix} Q_\pi & R_\pi \ 0 & I \end{pmatrix} ]
\end{equation}

根据游戏规则，两个相同幂次的方块碰撞会合并成为一个幂次加一的方块，
然后会在一个空格位置随机生成一个2或者4的方块，这一过程本文记为$S_i\to S_(i^')\to S_j$。
\input{../pic/2048example-p}

如图3.5所示根据我们的规则可以保证，状态在后的排序也靠后。也就是说在$S_i\to S_j$的过程中，能够保证$p_i<p_j$,
也就保证了非终结状态转移矩阵中状态转移总是小下标向大下标位置上转移的。在$S_i\to S_{i^{,}}$的过程中，局面和不发生变化。
分动作之后无方块合并和有方块合并两种情况来分别讨论。如果没有方块合并，那么场面上的方块面值不发生变化，如果发生了合并，
两个面值为2^n的方块合并为$2^{n+1}$面值的方块，总面值$\sum_{m=0}^{15} 2^{B_m}$不发生大小的变化。也就是说$p_i$与$p_{i^{,}}$在64bit以上是相同的，
如图所示。而在$S_{i^{'}}\to S_j$的过程中在空白的位置新生成了一个2或者4面值的方块，总面值$\sum_{m=0}^{15} 2^{B_m}$相较原状态总面值变大2或者4，
由于这个面值数在64bit-84bit位置上，所以$p_j>p_i ;p_j>p_{i^{,}}$。
通过这种转移关系我们可以认定，不存在向前转移的情况，因此，与圣彼得堡悖论类似，2048游戏的n步转移的$Q_π^{n}$矩阵是一个上三角矩阵。

因此根据本文的编码2048游戏的状态转移过程一直是满足从小的下标转移到大的下标上这一情况。
实际上任何不会向之前状态转移的过程都满足这个条件。在本文设计的状态转移下，状态对应下标只增不减，$q_ij>0$在$j-i>0$的条件下，
$j≤i$位置$q_{ij}$都是0，其中，i，j都是正整数。根据定理3.3，可以得到2048游戏的非终结状态之间的转移过程是非遍历的。