五子棋的mcts实现

武汉大学人工智能大作业。蒙特卡洛树搜索实现五子棋。

github仓库：https://github.com/Hooo1941/Gobang_MCTS/

问题分析与可行思路

实现目标

包括五子棋棋盘界面、人人对弈、人机对弈、机器与
机器对弈的设计、禁手规则的设计。

重点是蒙特卡洛树搜索的实现。

软件模块设计

软件源代码分为6个模块。

1. mainwindow.ui 和 mainwindow.cpp 实现了主菜单。
2. game.cpp 实现了界面的绘制和事件的处理。
3. gamemodel.cpp 实现了对棋盘数组操作和判断状态的函数。
4. config.h 定义了一些可修改的配置。
5. forbid.cpp 实现了禁手规则的判断。
6. ai.cpp 实现了蒙特卡洛树搜索。

界面设计思路

界面设计使用C++，Qt实现，可以跨平台运行。

初始界面设计如图，设计3个按钮进入不同模式。

棋盘设计：

包含背景图，已下棋子和最近走子的绘制，指针位置指示。

算法详细设计

界面类与棋盘设计

棋盘模块包括棋盘状态和当前玩家，棋盘状态用二维vector实现，更新棋盘时调用禁手判断。

界面绘制和鼠标事件捕捉使用Qt库处理，鼠标移动时取距离最近点绘制指针提示，点击时调用
棋盘模块更新棋盘，再调用界面重绘函数。

记录最后一个落的子，绘制落子提示。

禁手算法设计

三三禁手和四四禁手指横、竖和两条斜线出现了两个活三或活四、冲四。
长连禁手指一子落下形成连续六子或六子以上相连。

我将每一个方向的禁手判断用一个循环处理，向两边遍历，枚举禁手的每一种情况。

实例代码：

for (j = 0; j <= 9; j++) //横活三判断
{
	if (map[x][j] == 0 && map[x][j + 5] == 0) //活三判断，不能是死三/眠三
	{
		if (map[x][j + 1] == 1 && map[x][j + 2] == 1 && map[x][j + 3] == 1 &&
			map[x][j + 4] == 0 && (y == j + 1 || y == j + 2 || y == j + 3))
			fb33_1 = 1;
		if (map[x][j + 1] == 1 && map[x][j + 2] == 1 && map[x][j + 4] == 1 &&
			map[x][j + 3] == 0 && (y == j + 1 || y == j + 2 || y == j + 4))
			fb33_1 = 1;
		if (map[x][j + 1] == 1 && map[x][j + 3] == 1 && map[x][j + 4] == 1 &&
			map[x][j + 2] == 0 && (y == j + 1 || y == j + 3 || y == j + 4))
			fb33_1 = 1;
		if (map[x][j + 2] == 1 && map[x][j + 3] == 1 && map[x][j + 4] == 1 &&
			map[x][j + 1] == 0 && (y == j + 2 || y == j + 3 || y == j + 4))
			fb33_1 = 1;
	}
}

for (int i = 0; i < 6; i++) // 竖长连判断，根据当前落子往后遍历6个棋子，有一种符合就算长连禁手
{
	if (y - i >= 0 && y - i + 5 < kBoardSizeNum &&
		map[x][y - i] == map[x][y - i + 1] &&
		map[x][y - i] == map[x][y - i + 2] &&
		map[x][y - i] == map[x][y - i + 3] &&
		map[x][y - i] == map[x][y - i + 4] &&
		map[x][y - i] == map[x][y - i + 5])
		ol++;
}

当出现禁手时，程序会弹框提示，如图

特别要注意的是，若一个位置下棋可以五连，则无视三三和四四禁手。

蒙特卡洛树搜索的实现

算法优点

蒙特卡洛树搜索可以较为有效地解决一些探索空间巨大的问题。MCTS可以随时停止，适用于各种棋盘游戏，包括五子棋。自2006年以来，最优秀的程序围棋全部使用蒙特卡洛树搜索。

算法实现

蒙特卡洛模拟对局就是从某一棋局出发，随机走棋。有人形象地比喻，让两个傻子下棋，他们只懂得棋规，不懂得策略，最终总是可以决出胜负。这个胜负是有偶然性的。但是如果让成千上万对傻子下这盘棋，那么结果的统计还是可以给出该棋局的固有胜率和胜率最高的着法。

蒙特卡洛树搜索包含选择(Selection)，拓展(Expansion)，模拟(Simulation)，反向传播(Backpropagation)四个步骤。搜索函数如下：

time_t start = time(nullptr);
// 周围两圈有棋子即为可考虑点
std::vector<std::pair<int, int>> available;
for (int i = 0; i < kBoardSizeNum; i++)
	for (int j = 0; j < kBoardSizeNum; j++)
		if (check(map, i, j, playerFlag))
			available.emplace_back(std::make_pair(i, j));
node *root = new node;
root->playerFlag = !playerFlag;
root->pos = std::make_pair(-1, -1);
while (time(nullptr) - start < kAIDelay)
{
	path.clear();
	node *leaf = selection(root);
	if (leaf->visit > 0 && leaf->children.empty())
		leaf = expansion(leaf);
	int score = simulation();
	backPropagation(score);
}
node *pNode;
pNode = *std::max_element( // 选择胜率最大的点
	root->children.begin(),
	root->children.end(),
	// UCB实现选择
	[](const node *a, const node *b) {
		return a->win / (double)a->visit < b->win / (double)b->visit;
	});
emit pos(pNode->pos.first, pNode->pos.second);
deleteAll(root);

选择

虽然通过蒙特卡罗方法可以近似估计一个状态的好坏，但我们依然无法对太多状态进行估算。因此，我们需要有选择的集中力量对决策树中的可能更有价值的那些节点进行估算。这就需要使用蒙特卡洛树搜索，它提供了一种选择机制，使我们能够尽量选择决策树中比较有潜力的节点进行蒙特卡洛模拟，从而使得树可以尽量集中在“较好”的策略上进行“生长”。

该程序选择选用的方法是UCT。UCT树的不规则性表示在搜索过程中既要充分利用已有的知识，给胜率高的节点更多的机会，又要考虑探索那些暂时胜率不高的兄弟节点。

一个节点的UCB计算公式为

$$\begin{aligned} \text{UCB} = \frac {w_{i}}{n_{i}}+c\sqrt {\frac {\ln N_{i}}{n_{i}}} \\ w_{i}\text{代表第i次移动后取胜的次数；} \\ n_{i}\text{代表第i次移动后仿真的次数；} \\ c\text{为探索参数—理论上等于}{\sqrt {2}}\text{；} \\ \text{在实际中通常可凭经验选择；} \\ t\text{代表仿真总次数，等于父节点的}n_{i} \\ \end{aligned}$$

程序会递归搜索树的每一层的UCB最大的点，直到叶子节点。程序会优先搜索没有访问过的点。

拓展

在所选的叶子节点L，如果已经能判定输赢，则该轮游戏结束，否则创建一个或多个子节点并选取其中一个节点C。

每一层的拓展节点是当前局面棋子的外两圈的空点。

仿真

程序的仿真策略是：将外两圈的点放到一个数组中，然后用std::random_shuffle打乱，让双方依次按顺序走子。

若数组走完没有分出胜负，则双方取胜次数都+0.5。否则胜利一方取胜次数+1，败方不增加取胜次数。

反向传播

在选择和拓展的时候，路径会被加到path数组，反向传播会根据仿真的输赢更新路径上的所有节点信息。

返回结果

程序使用多线程处理AI计算，使计算与界面渲染分离，到指定时间后，AI类会取访问量最大的节点，将这个节点位置emit，让界面类处理。

测试分析报告

调试过程

程序在我的电脑上平均5秒只能进行2万次仿真，若所有点都向下拓展，程序的选择就变得随机。

被局面的变化也并没有对胜率产生很大的影响。

于是我将程序的周围两圈设为可选节点，AI的正确率得到提升。

一开始我将UCB函数的常数C过大，导致每个节点探索次数都差不多，出现图上的这种现象：

而C过小又可能使AI陷入次优解，最终我将C设置为1.414。

返回的决策节点有多种选择：经过调试，访问量最大的节点和胜率最高的节点表现比UCB分数最高的节点更好。

UCB规则导致多轮迭代后每个子节点的UCB值相差不大，容易出现胜率低的节点因为选择次数不多而被选上。

我选择了访问量最大的节点，而不是胜率最高的节点，也不是UCB分数最高的节点。

从理论上分析，访问量不够大的节点，即使胜率高，也不够可靠（因为模拟次数不够多）。而访问量最大的节点，通常也有一定的胜率，由于UCB公式，会选择更多的高胜率节点。如果胜率不高是不会经常被选中的（访问量不会大）。所以采用访问量最大的节点，AI的表现会更加稳定。

成品展示

性能

程序编译后加上Qt运行库约占25MB，占用内存大约为60MB，内存管理良好。在i5-8265U处理器下，MCTS5秒可以进行1万到8万次仿真。

功能

程序可以同时输出搜索的一些信息（迭代次数，节点的经过次数和胜利次数，UCB值）。禁手算法与蒙特卡洛树搜索算法效率较高。

运行截图

存在问题与改进方向

1. 禁手规则设计有问题，有些不是禁手的被错误判断。如图

1. 在大棋盘中，AI的防守能力不够。在一边已经组成活三或四的情况下，对手没有去防守。（节点访问次数不够多，估值不可靠）
2. 没有算杀，不知道已经赢了。
3. AI的走子有些随机，每一步之间没有关联性。
4. 较优解与较劣解的子树可能有较大重叠， 此时MCTS无法发挥出优势且可能陷入局部最优。
5. 在棋盘绘制的事件中判断输赢并弹框，导致最后一步棋无法显示。

改进方案

1. 用递归的方式实现禁手的规则（但是会增加时间复杂度），禁手的规则过于复杂，很难用程序精准描述。
2. 与min-max搜索的决策函数，甚至深度学习等其他算法结合，有些局面随机走子并不能得出正确的结果，如冲四就比活三危险得多，当对方出现冲四的时候，策略应该是防守而不是拓展活三。 但随机走子的策略可能将冲四封死或先完成活三的连五，这是错误的策略。
3. 在一些必杀局面或必须要防守的局面介入，不使用AI的结果。
4. 将AI的线程改为多线程运行，提升程序效率。
5. 将棋盘保存方式从vector改为两个bitset，可以降低程序的时空复杂度。
6. 将胜利后的弹框改为信号触发，放在新的函数中。
7. 用开局库\cite{r1}等方法简化AI的运算、UCT RAVE\cite{r2} 等方法复用状态，提高程序效率。