人工智能四子棋编程作业实验报告

交叉信息研究院张楚珩 2016311417

问题描述

编写一个重力四子棋的AI。本次作业中重力四子棋的基本规则如下：

棋盘为宽为$N$，高为$M$的矩形棋盘，其中$M,N\in[9, 12]$；
棋盘上有一个随机的禁止着点，这个点上不能落子；
每次着子都必须落到最下方空的格点上；
获胜条件为一方的棋子在橫、竖、斜任意方向上能够连成四子，则该方获胜；如果棋盘上所有棋子落满时仍没有任意一方达到获胜条件则视为平局；

基本思路

经过调查研究，比较好的解决方案主要有$\alpha$-$\beta$剪枝和蒙特卡洛方法。$\alpha$-$\beta$剪枝方法需要对于该游戏的先验知识才能构造出比较好的局面评估函数，而局面评估函数的有效性对于最后的结果影响较大。而蒙特卡洛方法则较少地基于专家知识，它通过自身的模拟对弈的结果来评估各个节点的优劣；同时近年来，包括AlphaGo在内的诸多博弈AI都利用蒙特卡洛方法并且取得了更好的效果。考虑到自己对于该游戏并不熟悉，同时也希望编写的程序有较高的水平，因此在这里采用蒙特卡洛方法。

本次实验主要以信心上界树算法（UCT）为框架，算法结构如下所示。

$$ \begin{aligned} & 1. \text{function } UCTSearch(s_0) \\ & 2. \quad 以状态 s_0\text{创建根节点}v_0 \\ & 3. \quad while \text{ 尚未用完计算时长 } do \\ & 4. \quad \quad v_l \leftarrow TreePolicy(v_0) \\ & 5. \quad \quad \Delta \leftarrow DefaultPolicy(s(v_l)) \\ & 6. \quad \quad Backup(v_l, \Delta) \\ & 7. \quad end \text{ } while \\ & 8. \quad return \text{ } a(BestChild(v_0, 0)) \end{aligned} $$ 该算法在每个while循环中（4-6行）都使用蒙特卡洛方法选择一天路径去探索。其中第四行TreePolicy函数的目的是选择一个节点往下搜索，其主要方式为如果该节点的子节点还有没被探索过就探索这个节点，如果该节点的所有子节点都被探索过，那么就去使用BestChild函数找其最优的子节点。第五行按照等概率在每一步的可行动集中选择一个行动，然后反复行动直到到达终止状态，并且反馈终止状态的收益。第六行将收益顺着搜索节点的路径向上反馈。第八行和TreePolicy函数中使用到的BestChild函数按照如下公式选择一个最佳的扩展节点，该公式能够将搜索的资源尽可能多地分配到较优的节点中，但同时也能兼顾去探索被访问次数比较少的节点。 $$ BestChild ={arg\max}_{v'\in \text{children of }v} (\dfrac{Q(v')}{N(v')} + c \sqrt{\dfrac{2 \ln (N(v))}{N(v')}}) $$

实现过程

确定公式中的参数$c$

公式中参数$c$控制着模型利用（exploitation）和探索（exploration）的比例，$c$越大越倾向于探索被探索次数比较少的节点；$c$越小越倾向于探索之前探索效果较好的节点。根据测试，每轮能够运行的搜索次数大概在200w左右（即$N(v)\approx2e6$），平均来说$N\approx 2e5$。令$Q(v')$为每次累计的胜负计数，即每次经过$v'$的一条路径获胜则$Q(v')\leftarrow Q(v') + 1$，失败则$Q(v')\leftarrow Q(v') - 1$。因此，第一项$\dfrac{Q(v')}{N(v')}$大概数量级为$0.1$；第二项的数量级大概为$0.01$。因此参数设定大概在$1\sim 10$即可。

改进最终结果的选择函数

原算法中最后返回结果的时候仍然使用BestChild函数，但最后返回结果的时候我们并不希望它再去探索，而是直接利用最后的结果。因此算法第八行中，我们将BestChild用以下的BestSolution代替，将其鼓励探索的部分去掉。 $$ BestSolution ={arg\max}_{v'\in \text{children of }v} (\dfrac{Q(v')}{N(v')}) $$

在TreePolicy中增加剪枝

通过观察发现，模型对于对手的必胜情形判断较差，比如在某一个位置落子之后对手就能在其上方落子而获胜时程序还是会在此处落子。这是因为在TreePolicy中，它认为在每一步中自己或者对方在任何一列落子都是有一定概率的，都会兼顾探索新的节点。因此我们做了如下改进，在某一处落子直接会获胜的情形下，我们直接将对其他扩展情形剪枝，只考虑这种必胜情形。

改进评价函数$Q(v')$

最开始我们采用了最简单的方式：每次搜索之后如果己方获胜则$Q(v')\leftarrow Q(v') + 1$，如果己方失败则$Q(v')\leftarrow Q(v') - 1$，如果达成平局则$Q(v')\leftarrow Q(v') $。由于相邻两层代表的不同的落子方，因此Backup函数中将评价函数向回传播的时候使用公式$Q(v_{s-1})\leftarrow Q(v_s)$，其中$v_{s-1}$是$v_s$的父节点。这个函数无法区分以某个节点代表的行动方式行动之后是需要过很多步才获胜/失败，还是很快地就会获胜/失败。因此能够区别对待在该步落子之后立马就会获胜/失败的情形，我们对于很快获胜/失败的给予更多的奖励/惩罚。因此，如果如果某个节点直接导致棋局的结束，那么就$Q(v')\leftarrow Q(v') \pm P$，其中$P>1$。相应地，Backup函数的传递方式变为 $$ Q(v_{s-1})\leftarrow \begin{cases}

||Q(v_s)| - 1| & Q(v_s) \le -2 \

||Q(v_s)| - 1| & Q(v_s) \ge 2 \
Q(v_s) & otherwise \end{cases} $$

程序加速

由于程序测试要求在3s内给出结果，因此如果程序能够运行地更快就能探索更多的路径，给出更好的落子结果。我们观察到，程序运行较慢的主要花费在对变量分配内存上。因此这里把搜索节点的内存提前分配好，从而提高了程序的运行速度。

实验结果与分析

如附录中图一所示，我们的程序在先手的情况下10/10次能够打败100.dll（最强的）测试点，在后手的情况下5/10次能够打败100.dll测试点。可以认为，我们的AI水平高于最强的测试点AI。

改进与总结

总结

更加熟悉了C++语言的编程；
了解了蒙特卡洛树搜索方法；

改进

对于公式中的参数$c$可以进一步地调参确定其最佳的数值。具体做法可以使使用不同的参数产生不同的策略，让它们进行单循环赛来确定最佳的参数；
仿照这里的剪枝方法，还可以在TreePolicy中增加更多的相应规则或者对于局面的评价，来使得程序能够更快更好的选择子节点进行探索；
这里的DefaultPolicy使用了等概率随机搜索的方法来探索每个节点的输赢概率，其实还可以使用启发式的来进行搜索，使得相应的搜索更有效率；
评价函数的规则可以进一步改进，我们相信还会有比这里更好的评价函数的设计。

zhangchuheng123/Connect4

人工智能 四子棋 编程作业 实验报告