121 lines
5.5 KiB
TeX
121 lines
5.5 KiB
TeX
\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}
|