2048 游戏AI的实现思路

2048 游戏AI的实现思路

  最近玩2048玩上瘾了，一玩就停不下来。
  觉得这样玩个不停太浪费时间了，于是就想做个AI帮我玩2048。
  首先要做一个2048游戏，这个游戏的规则和玩法很简单，所以实现起来不复杂。(要注意的是，2 和 4 的出现概率分别是 0.1 和 0.9。)
  关键是如何实现AI！

游戏规律

  这个游戏想要通关(合成出2048)还是很简单的，只要让最大的那些数字按照从大到小的顺序始终呆在一个角落就可以了。
  比如 图1 中的这种情况，我只需要在现在这个 32 旁边再合成出一个 32，这两个 32 就能合并成一个 64。然后新合成的 64 和原来就有的 64 将会是挨在一起的，所以让这两个 64 合并就很轻松。合并之后得到一个 128，所以剩下的主要数字就是 2048、512、256、128。而且它们还都是挨在一起，按照从大到小的顺序排列的。游戏的下一步就是我再合成一个 128，这样就能一口气把 512、256、128 合成为一个 1024。

  那么，要如何让 AI 按照这样的规律来游戏呢？

  这个游戏的操作很简单，只有上移、下移、左移、右移这四种操作。而我的思路是让 AI 在当前局面的基础上，对这四种操作移动后的结果打分，返回分数最高的一种操作。

  现在，问题的关键在于如何评分。

位置加权评分方案

  一种思路是把棋盘的每个位置都设置一定的权重 \( w{xy} \)，那么评分 \( S \) 为各位置数值 \( v{xy} \) 的加权求和:

$$S = \sum_{x,y=1}^{x,y=4} w_{xy} \cdot v_{xy}$$

  可以预知 AI 会让大权重位置上的数值尽可能地大。实际的运行结果也是符合预想。

  接下来谈谈权重的值要怎么取。为了方便说明，我先给出经过测试效果比较好的一种权重取值。

$$\begin{bmatrix} 255 & 127 & 63 & 63 \\\\ 11 & 17 & 15 & 19 \\\\ 0 & 0 & 0 & 0 \\\\ -3 & -5 & -7 & -9 \end{bmatrix}$$

  第一行的权重给的最高，而且从左往右递减。为了让数值大的值尽量呆在这一行，所以这一行各个位置的权重都远远大于其他位置的权重。而又为了让数值最大的那个数字固定于角落不移动，所以这一行最左边位置的权重又远大于所有其他位置的权重。

  第二行的权重比第一行小得多，而且不呈递增或递减。这是因为这一行的数字最终要和上一行合并，如果权重呈现递增或者递减，会导致这一行的数字不常移动。如果这一行的数字不常移动，就难以保证相同的数字处于同一列，因此会出现如 图3 这样的效果。(注意：图片中展示程序的行和列与本文权重的行和列相反。上文给出的权重应当会让数值大的数字在第一行，而图中数值最大的数字正好在第一列。)

  可以看出各行数值最大的数字堆积于各行权重最大的位置，迟迟无法合并导致游戏失败。

  剩下两行的权值则是随意设置，只要各行之间的权值相差不要太小即可。

  但是如果只有这样的权值设置，会发现 AI 的运行效果不佳。从 图4 可以看出，数字的出现很有规律，AI 确实在按照权重来运行。

  进一步观察 图4 可以发现，权值最大的那两行位置上的数字，似乎差了一格就能把数字合并在一起。

  设置权重可以让数值大的数字尽量靠近一个角落，也可以让第二行的数字往第一行合并。但是合并的前提是，两行相同数值的数字要在同一列，而光靠设置权重则很难保证相邻两行的同数值数字能够并列。因此需要设置算法鼓励能够让相同数值的数字并列的操作。

让数值相同的数字在同一列

  这个思路实现起来不难，针对棋盘上每一列，统计其相邻且相同的数字的数目，折算后加入评分即可。这里给出一个算法：

for (int y = 0; y < 4; y++)
{
	int maxt = 0, t = 0, i = 0;
	for (int x = 0; x < 4 - 1; x++)
	{
		i = x + 1;
		while (board[i++][y] == board[x][y]) ++t;
		maxt = max(maxt, t);
		x += t;
	}
	result += 1.0e2 * t;    // 1.0e2为折算因子，数值越大则该项评分的“影响力”越大
}

鼓励增加棋盘上的空位

  如果本次操作能够增加棋盘上的空位，有助于游戏的继续，则加一点点优势分。
  经过测试，这个评分项目似乎能让 AI 的发挥更稳定。统计棋盘上空位的数目，折算后加入评分即可。

测试代码以及结果

  测试代码已经上传到 GitHub : https://github.com/cyanray/Game_2048_AI

  这个 AI 能够稳定地合成出 512 这个数字，偶尔运气好能合成出 1024，但是更好的成绩就没能做到了。

  反复修改权重也没能显著改善 AI 的发挥，可能还需要新的评分项目或者需要引入新的方案才能让 AI 有所提升。