\section{问题分析}

\subsection{2048游戏特点}
2048游戏是一个基于网格的数字合并游戏，具有以下特点：
\begin{itemize}
    \item 4×4的网格状态空间
    \item 四个基本动作：上、下、左、右
    \item 确定性的游戏规则和随机的数字生成
    \item 指数级增长的状态复杂度
    \item 决策时可以认为全局无状态性
    \item 对棋盘进行对称变换对游戏无影响
\end{itemize}

\subsection{问题及解决思路}
\subsubsection{棋盘上的数字表示}
在2048游戏中，方块上的数字呈指数增长（$2^1, 2^2, \dots$）。理论上，在一个 $4 \times 4$ 的棋盘上，可能出现的最大数字为 $2^{17}$。
这种巨大的范围和稀疏的分布，显然不利于神经网络进行有效学习和泛化。

为了解决此问题，我们可以对棋盘状态进行对数变换。
令棋盘状态为一个矩阵 $K \in \mathbb{N}$，
其中 $K_{i,j}$ 表示在 $(i,j)$ 位置的数字，空位记为 $1$ （2048游戏中不会有1出现，同时用1做掩码无需额外判断）。
我们定义一个新的状态表示矩阵 $K'$，其元素 $K'_{i,j}$ 通过以下映射获得：
\begin{equation}
    K'_{i,j} = \log_2(K_{i,j})
\end{equation}
通过这种对数变换，我们可以将指数增长的数值尺度压缩到一个线性、紧凑的整数范围。
这种方法同样适用于任意边长的矩形棋盘。

\subsubsection{棋盘压缩}
2048棋盘可以看做是一个平面图像，这个图像的8个旋转和镜像结果，
对于游戏而言是完全等价的。我们将每个图像的二面体群$D_4$的所有等价类进行合并，
即可显著压缩棋盘表示的空间，避免对等价局面进行重复搜索。
我们使用以下步骤，将二面体群的所有等价类压缩到同一哈希桶：
\begin{itemize}
    \item 对于给定的局面输入，获得其8种变换，覆盖$D_4$的所有元素：
        \begin{itemize}
            \item 原始图像 (R0): matrix
            \item 旋转90° (R90): \texttt{rotate\_90(matrix)}
            \item 旋转180° (R180): \texttt{rotate\_90(rotate\_90(matrix))}
            \item 旋转270° (R270): \texttt{rotate\_90(rotate\_90(rotate\_90(matrix)))}
            \item 水平翻转 (F): \texttt{flip\_horizontal(matrix)}
            \item 翻转后旋转90° (F+R90): \texttt{rotate\_90(flip\_horizontal(matrix))}
            \item 翻转后旋转180° (F+R180): \texttt{rotate\_90(rotate\_90(flip\_horizontal(matrix)))}
            \item 翻转后旋转270° (F+R270): \texttt{rotate\_90(rotate\_90(rotate\_90(flip\_horizontal(matrix))))}
        \end{itemize}
    \item 采用行优先方式，将矩阵拉平为1D向量
    \item 比较这些向量的字典序，将字典序最小的向量作为该图的范式
    \item 计算哈希，存储到哈希表或者搜索缓存
\end{itemize}
这种方案亦可推广到任意矩形棋盘。

\subsubsection{棋盘分数计算}
对于估值网络而言，一个准确的、有代表性的最终得分，是模型学习的重要依据，也是训练效果的关键因素。
然而，由于2048可能随机生成2或者4，这使得某一局面的最终分数存在不确定性。但是这不妨碍我们在计算得分时排除掉随机因素。
在计算盘面得分时，我们假设只会随机生成2，但在蒙特卡洛树搜索时，我们考虑2和4随机出现的概率。
这样既能够保证模型学习到随机数字情况下的决策，又能显著降低噪声，同时提高缓存命中率。

2048游戏的计分规则为，当两个较小的数字合并为一个较大数字时，增加等值于较大数字的分数 $\Delta S$。

合成一个数字，其奖励分数存在以下对应关系：
\begin{itemize}
    \item $\Delta S_4 = 4$
    \item $\Delta S_8 = 8$
    \item $\dots$
    \item $\Delta S_{2^n} = 2^n$
\end{itemize}

假设游戏仅随机生成数字2，则每个数字的累积分数价值为：
\begin{itemize}
    \item $V(2) = 0$ （2不能通过合成得到，其累积分数价值为0）
    \item $V(4) = 4$
    \item $V(8) = 4 + 4 + 8 = 16$ （涵盖了合成8用到的2个4的分数价值，以及合成8本身增加的分数价值）
    \item $V(16) = 16 + 16 + 16 = 48$
    \item $V(32) = 48 + 48 + 32 = 128$
    \item $V(64) = 128 + 128 + 64 = 320$
\end{itemize}

显然，对于一个大于2的数字 $N$，其累积分数价值 $V(N)$ 可以递归地表示为：

\begin{equation}
    V(N) = V\left(\frac{N}{2}\right) + V\left(\frac{N}{2}\right) + N
\end{equation}

同时，我们有基础情况：
\begin{equation}
    V(2) = 0
\end{equation}

将数值迁移到对数变化后的矩阵，令 $f(N') = V(2^{N'})$，则有：
\begin{equation}
    f(N') = 2 \cdot f(N'-1) + 2^{N'}
\end{equation}

将递推关系式 $f(N') = 2 \cdot f(N'-1) + 2^{N'}$ 展开：
\begin{align}
    f(N') &= 2 \cdot f(N'-1) + 2^{N'} \\
    &= 2 \cdot [2 \cdot f(N'-2) + 2^{N'-1}] + 2^{N'} \\
    &= 2^2 \cdot f(N'-2) + 2 \cdot 2^{N'-1} + 2^{N'} \\
    &= 2^2 \cdot f(N'-2) + 2^{N'} + 2^{N'} \\
    &= 2^2 \cdot f(N'-2) + 2 \cdot 2^{N'} \\
    &= \cdots \\
    &= 2^{N'-1} \cdot f(1) + (N'-1) \cdot 2^{N'} \\
    &= 2^{N'-1} \cdot 0 + (N'-1) \cdot 2^{N'} \\
    &= (N'-1) \cdot 2^{N'}
\end{align}

检查，当$N'=1$，即$N=2$时，有：
\begin{equation}
    f(1) = (1-1) \cdot 2^1 = 0
\end{equation}

该结果符合定义 $V(2) = 0$。

因此上述通项公式涵盖所有情况，数字 $N = 2^{N'}$ 的累积分数价值为：
\begin{equation}
    V(N) = (\log_2(N) - 1) \cdot N
\end{equation}
\begin{equation}
    V(N') = (N'-1) \cdot 2^{N'} \label{eq:log_value_formula}
\end{equation}