IAI实验三报告：重力四子棋

张凯文 计12 2021010729

算法思路

本次实验我主要使用了 UCT 信心上限树算法（蒙特卡洛树搜索 + UCB 估值）。树搜索的过程主要分为以下四步：选举、扩展、随机模拟、反向传播。具体来说，这四个步骤分别表示：

• 选举(selection) 是根据当前获得所有子节点的统计结果，选择一个最优的子节点。在 UCT 算法中，选择最优子节点的原则基于 UCB 信心上限估值，由下列公式给出对当前各个子节点价值置信区间的上限，以此平衡对已知结果的**利用(exploitation)和对未知结果的探索(exploration)**：

  $$
  v_i+c\sqrt{\cfrac{2\ln N}{\ln n_i}}
  $$

  其中 $v_i$ 是第 $i$ 个子节点的当前价值，$N$ 是当前节点的总探索次数，$n_i$ 是第 $i$ 个孩子的探索次数， $c$ 是可调节的参数， $c$ 越大将越倾向于“探索”。

• 扩展(expansion) 是当我们搜到当前树的边界后，向外继续扩展子节点。

• 随机模拟(simulation) 对新加入的子节点，通过随机模拟游戏直到决出胜负（或平局）来对节点当前价值进行评估。

• 反向传播(Back-Propagation) 根据随机模拟的结果，更新当前节点及其所有父节点的探索总数和价值。

算法的伪代码如下：

算法实现

我在 UCT.h / UCT.cpp 中实现了 UCT 类，按照上述伪代码给出的逻辑实现了：

• search：搜索主函数，根据当前棋局进行 UCT 树搜索，在限定时间内给出当前搜索结果中的最优的下一步走棋位置；
• treePolicy：若当前节点可扩展，则调用 expand 扩展子节点；否则选出最优子节点直到能够扩展或终止节点；
• defaultPolicy：对当前节点随机模拟，返回收益；
• getStatus：获取当前节点状态（胜利、失败、平局或未完结）；
• update：根据走子的列和走子方更新棋盘。

在 State.h / State.cpp 中实现了状态节点类 State，包括下列方法：

• bestChild：根据 UCB 估值给出当前节点的最优子节点；
• expand：扩展子节点；
• terminate：判定节点是否是终止节点；
• action：返回当前节点对应的走子位置；
• mustPlay：判定当前棋局是否有必胜/必堵位置；
• mustNotPlay：判定给定走子位置是否是必不能下的位置（下了对方就赢了），详见下方优化尝试；
• clearMustNotPlay：一次性清除当前节点必不能下的位置（除非清楚后无路可走）。

优化与尝试

逻辑特判与剪枝

• 若当前棋盘存在必胜位置（己方已连成三子）或必堵位置（对方已连成三子），那么不再搜索，直接在对应位置落子；
• 上述策略可以进一步应用到 expand 扩展子节点的剪枝中：若在扩展节点时发现存在必胜或必堵位置，则直接选择该子节点并清空其他选择；
• 在观察某些失败棋局时发现，AI 有时存在“送子”现象，即在某个位置落子后，对方紧接着在其落子位置上方落子即可取胜，若非万不得已，在这样的位置落子显然是“利人不利己”的，因此可以将这样的位置判定为“必不能下”的位置。在根节点处，一次性清除根节点必不能下的位置，即有可能剪掉大量不用搜索的分支。这一策略也可以进一步应用在搜索树的任一节点处，即在建立节点时就清掉这类“必不能下”的位置；但由于这种情况在总体模拟中出现可能性并不多，而每次判断本身会耗时，带来的总体收益也并不明显，甚至有所下滑。

性能提升

在大量实验后发现，对 AI 实际胜率影响最大的还是搜索节点数，因此搜索效率的提升至关重要。对此，我也进行了一定优化：

• 节点重复利用：开辟一块节点池，在第一次走子 new 申请完空间后暂不释放，在下一次走子时即可不用重新用 new 申请空间，可重复利用之前的空间更改参数即可，以此节省大量内存申请、释放所需的时间；
• 在 UCT 类中以静态变量统一存储 board 和 top，避免在每个状态节点中反复申请存储。

其他尝试

我也尝试对参数 $c$ 的选取策略进行优化。我们知道，$c$ 选的越大 AI 越倾向于探索未知区域，$c$ 选的越小 AI 越倾向于利用已经探索过的信息。考虑人类下棋时的一般规律，在开局时一般倾向于探索开辟局面，在后期一般倾向于利用信息，因此在选择节点时也可以利用类似策略，对 $c$ 采用指数或线性衰减策略，如： $c=c_0 e^{\alpha t}$。但简单尝试后发现效果并不显著，甚至有所下滑，因为在开局时在相近位置堆叠形成优势也可能是重要的，因此最终放弃这一尝试，固定 $c = 0.9$。（事实上，实验表明，保证搜索效率的情况下 UCT 搜索的结果已经表现非常非常好，而以我们的下棋水平，基于人类先验的许多“优化”很可能都是负优化）。

测试结果

在 saiblo 上与偶数编号 AI 的批量测试结果如下，仅在与 94 号 AI 的对决中小输一局：

并且我的 AI 发挥非常稳定，在与高水平测试 AI 的批量测试中胜率如下：

下面是这两次批量测试的截图：

总结

本次作业是我第一次接触 AI 博弈，我亲手实现了 UCT 算法，花了大量时间 debug（一旦 UCT 算法中有一个小的逻辑错误，加上各种 trick 调优胜率也很难上 90%），并在反复观察、总结 AI 对局中不断实验优化，体会到剪枝优化与模拟效率间平衡的重要性，在这一过程中收获颇丰，最终测试结果也比较令人满意。再次感谢马老师和助教的指导！