[TOC]

蔡严正

本文分享如何在 https://www.saiblo.net/game/3 环境下实现基于传统方法的重力四子棋策略。

类似分享：

传统方法：https://github.com/zhc7/ConnectFour https://github.com/jiegec/FourChess

神经网络方法：https://github.com/GoodCoder666/katac4

如果你选修清华大学计算机系相关课程，并且正在做与本仓库相同的作业，请先自己实现后再参考。在课程允许参考的前提下，参考本仓库后，务必在 README 和代码注释中记录参考本仓库的内容。

原始的重力四子棋介绍与求解方法见 http://blog.gamesolver.org/

6 行 7 列的原始四子棋已经可以被 $\alpha-\beta$ 剪枝彻底搜出来了。saiblo 平台的规模设置是，将棋盘的长与宽都设置成在范围 [9, 12] 的随机整数，并设置一个禁入点。日后，这个范围还可以继续增大，且禁入点可以设置任意个数，这样可以断绝一搜到底的可能。

对于四子棋，很难搞出一种手工估值函数，可以保证越接近末盘，评估的误差越小。在这种情况下使用 $\alpha-\beta$ 剪枝时，容易出现搜的层数增加，效果反而变差的情况。所以这里采用蒙特卡罗树搜索的方式。

蒙特卡罗树搜索的简介见 https://blog.csdn.net/qq_41033011/article/details/109034887

棋盘表示直接关系到程序运行效率。高水平的传统方法策略几乎都有基于位运算优化的棋盘。原始 idea 来源于 http://blog.gamesolver.org/solving-connect-four/06-bitboard/ 与 http://blog.gamesolver.org/solving-connect-four/09-anticipate-losing-moves。

我们使用 3 个 uint64 表示一个位图，位图的相邻 16 bit 表示一列的情况，使用两个位图（当前方的棋子与全部棋子）表示当前棋盘。这种表示下：

• 可以方便地获取可下点的位置，具体的原理是，011...1 + 1 = 100...0。引入禁入点后，经过一些处理，这种模式仍然有效。
• 获取每列的可下点后，可以进一步获得每列的第二可下点，第三可下点。（程序里命名为 atop、utop 与 htop，至于为啥是这仨名字，是我随便起的）
• 可以方便的判断哪里有三。原理与上述网站中的一致，我使用 https://godbolt.org/ 进行实验，最终试出一种汇编行数较小的实现方式，并最终应用在策略里。
• 可以数子数。

当前的实现下，棋盘最大可以扩展到 13 行 12 列。

基础的模拟策略是纯随机。删去完全不合理的下法并适当增加选择偏好，可以使模拟策略更接近最优策略，从而大幅提高棋力。

我们目前采用如下的策略：

1. 必赢（可下点和我方有三的位置重合），下这个位置并赢得比赛。（这种情况，只会在根节点出现，其他都会视作另一方的）
2. 必输（可下点和敌方有三的位置有多处重合），输掉比赛。
3. 必输（可下点和敌方有三的位置重合，且同一列第二可下点和敌方有三的位置重合），输掉比赛。
4. 迫手（可下点和敌方有三的位置重合，同一列第二可下点和敌方有三的位置不重合），必须下此处。
5. 禁入（第二可下点和敌方有三的位置重合），不能下此处。如果没有可下的位置，输掉比赛。
6. 同列两步杀（非禁入列的第二可下点与第三可下点均与我方有三的位置重合），赢得比赛。
7. 将可下位置分成敌方禁入列与非敌方禁入列两类，非敌方禁手的优先级更高。同一优先级的下法选择随机。

敌方禁入列是四子棋下棋过程中的重要“资源”，可以减少敌方的行动空间。7 可以让程序在模拟时，减少浪费禁入列的情况，但也可能会使程序过于保守，放弃“弃子争先”的机会。该思路最早出处是 https://mp.weixin.qq.com/s/cj5TisuhQvkXXy7LGZyDbQ，造就一代目榜一 cheng 。再使用位运算进行优化，以及 MCTS 的常数优化技巧，可以达到二代目榜一 frvdec 的水平。

6 是两步杀中，方便进行计算的特例（只需要额外维护第三可下点）。两步杀的引入可以 缓解 7 保守的问题，但我没有想出计算完整两步杀的高效方法（普通方法是填上子看对方是否必输）。最终使用 6，保证模拟效率的同时优化了策略，效果突出。

在模拟策略中，还可以追踪双方所下的棋是否是唯一可下的棋（迫手），从而可以将节点标注为必赢/必输/平局节点。这些信息可以沿着搜索树逐层向上传播，提供剪枝机会，减少无谓搜索。

需要注意的是，对每次模拟的评分，除了输赢外，还有与已下子数相关的评分。棋子数的评分可以在剪枝的时候，提供一个默认下法，避免程序在发现自己要输的时候摆烂。此外，如果模拟的评分只有输赢，会在探索初期出现无法区分各个子节点的情况，从而导致系统性地先探索靠左列/靠右列，导致棋力下降；引入了棋子数后可以避免这个问题。

树搜索变成图搜索。

https://github.com/lightvector/KataGo/blob/master/docs/GraphSearch.md

效果突出。在棋力与终局枚举上均有大幅提升。搜索节点越多，效果越明显。与优化良好的 MCTS 相比，MCGS 可以提前 3-4 步完成终局枚举。

• 拒绝智能指针，使用两个 vector 分别表示有向无环图的节点和边，节点中设置整数变量，表示该节点第一条边的下标，节点所属的边连续排布。这种设计下，节点的选择阶段，可以保证访存连续。然而，这种设计在节点的扩展阶段需要将所有孩子一起初始化。
• 拒绝 std::unordered_map，手搓哈希表，数据结构课上讲的线性试探哈希表就很好。哈希采用 zobrist 哈希，效率较高且冲突概率低。

这点容易想到。常见做法是移动树根（或者有向无环图的起点）、然后删除废弃的节点。然而经过观察发现，复用节点的规模，通常明显小于废弃节点的规模。

所以我们采取类似 copy on write 的策略，每次新建有向无环搜索图，从新起点开始对原图进行递归拷贝，然后删除原图。降低时间开销的同时，保证新图的访存连续性。

从新节点开始的递归拷贝可以保证拷贝规模小，但还是可能丢弃有用信息。想象搜索极端不平衡的情况，一个分支搜索深度达到5，但最后选择了搜索深度是1的分支。目前的做法会丢弃整个大分支，但其中必然有许多节点可以作为当前起点的子节点。这可能是未来的改进方向。

将扩展后节点的初值，设置成所有孩子节点值（模拟值或者已有的值）的平均值。这么做的好处是减少程序运行过程中节点值的方差。这种做法对于四子棋这种分支数较小的棋类可以使用，其他的棋类效果可能不好。

经过观察，普通 UCT 在达到百万级别的搜索量时，会出现探索过于不均衡的情况，因此使用 PUCT 作为搜索的公式。每个动作的初始概率设置成相等。

当使用 PUCT 选择孩子节点时，如果节点是未扩展状态，那么用孩子节点模拟值与本节点已有的值取平均后再代入公式。好处是减少方差。

经过实战检验，调整 PUCT 超参与最终选择方式的超参。