用python编写1024游戏(3)

继这篇blog后，我们来尝试实现ai版的1024游戏。

背景

先来认识两个概念：树状搜索(Tree-Searching)和评价函数(Evaluate Function)

树状搜索

以象棋为例子、下棋的过程可以看作是棋局变化的过程。假设某时刻某个棋局，接下来可以移动棋子的方式有k种，每种移动方式会导致另外一种棋局。故整个下棋的过程可以用一棵n叉树来描述。目前的局面称为“根局面”(Root Position)或“根结点”(Root Node)，后续分支称为“后续局面”(Successor Position)或“后续结点”(Successor Nodes)。

理论上可以从最初的局面开始生成n叉树，直至所有叶子节点满足游戏结束的条件为止，但随着生成层次增加，计算的次数迅速上升，往往会超出当前应用场景的接受范围。所以在一些复杂的游戏当中，会对搜索层次进行限制。同时，可以对某些特定算法进行“剪枝”优化，根据某些条件终止当前路径的搜索以减少分支数。

评估函数

假设当前局面对应的n叉树已经生成，如何选择对自己最有利的下一步呢？在此我们引入一个评估函数，该函数输入一个局面，返回对该局面的评估值，表示当前路径下可以获得的优势。我们对下一步所有可能出现的情况进行评估，然后根据评估值最大的局面来走棋。

注意到某局面的评估值依赖于下一步的所有可能出现的局面的评估值（是它们的和），这些可能出现的局面又依赖于在下一步可能出现的局面的评估值。所以我们需要从叶子节点开始计算评估值，然后回溯到顶层的同时更新父节点的评估值。

思路

首先，很明显，玩1024的过程可以用一棵n叉树来描述。游戏状态的变化按照规则：

if 棋盘上存在格子的值为1024:
    游戏状态=胜利
elif 棋盘上存在剩余空格 或者 棋盘上依然存在可以合并的元素:
    游戏状态=未结束
else:
    游戏状态=失败

设棋盘大小为4*4

, 每一回合的平均空格数为4*4/2，大部分回合都可以朝4个方向滑动，那么随着搜索层数的增长，节点的个数如下增长：

层数    节点个数
0       1
1       32
2       1024
3       32768
4       1048576

仅四层节点个数便达到百万级别（我没算错的话），所以我们必须采用启发式搜索。

---

接下来我们大致写出整个ai游戏过程：

游戏开始-> ai下棋-> 游戏结束

具体其中的 ai下棋 过程：

初始化-> 随机出现数字-> 评估当前局面-> 执行滑动，局面改变-> 随即出现数字-> ... -> 游戏结束

用循环和判断语句描述一下：

while 未结束：
    随机出现一个数字
    获得最优滑动方向
    执行滑动，局面改变

---

关键在 获得最优滑动方向 这一步。具体化一下：

def 获得最优滑动方向:
    for 方向 in 当前有意义的滑动方向:
        执行滑动
        方向.累计值 = 评估当前局面
    return 最大累计值的方向

其中 评估当前局面 思路如下所示：

def 评估当前局面:
    if 无需继续搜索:
        return 当前局面的评估函数值

    累计值 = 0
    for 随机数字 in 当前剩余的空格: # 注意循环嵌套的顺序
        for 方向 in 当前有意义的滑动方向:
            执行滑动，局面改变
            累计值 += 评估当前局面
    return 累计值

这是一个深度优先搜索，可以用递归或者栈来实现，后续文章会有实例代码。

---

注意到 当前有意义的滑动方向 这一步。如何获得这个方向序列呢？我们来思考一下。“局面改变”是指：

存在空单元格被占 or 存在元素被合并

于是我们可以获得两个判断“可移动”的条件

当前方向上存在空单元格
当前方向上存在可合并单元格

---

接下来观察 计算评估函数值部分。设评估值为H, 影响因子（决定评估值得因素）的值为A, B, C…，它们的权重为a, b, c, …，则有：

H = aA + bB + cC + ...

可以写成：

H(x) = aA(x) + bB(x) + cC(x) + ...

其中x代表当前局面。

我们暂时简单地设计一些影响因子函数，例如“当前局面的剩余空格数”，“当前累计的总分”，“形成可组合的对数”等等。然后根据实验来调整权重。

---

好了，说完思路，接下来将采用python实现。