前段时间，我在网上看到有人提出一种棋，类似五子棋，但连三即判负，在 5x5 棋盘里下棋。我想这种棋应该不难用计算机求解，毕竟状态空间比五子棋小得多，于是问了 AI，但似乎没有已知成果。找到了一篇博客，其中解决了包括 3x3 和 4x3 在内的许多游戏，但更大棋盘上的连三没有包括。倒是有一种双方用相同棋子（而非分执 X、O）的 Notakto 有许多研究。
于是我决定自己求解，现已完成，结论是后手必胜（总能让先手不得不连三）。源码在 GitHub 上，欢迎前往访问。程序代码完全古法手写。在这个 AI 满天飞的时代，我觉得手写一些代码还是比较有意思的。大多关键技术已在仓库 README 中详细介绍了，那里字比较多，本文则主要介绍我开发的过程，不再重复。文中所述的性能差距，均没有经过严谨的 benchmark，只是我手动打印的结果，受测试样本影响（如置换表大小有不同，且大多测试是在 4x4 上做的），可能有较大误差。我是民科，许多内容都是问 AI 得知的，也许有错误，敬请指出。
首先，介绍背景信息（这也是问 AI 才知道的，哈哈）。通用的五子棋统称「m,n,k-game」，在 mxn 棋盘里下棋，连 k 则胜。而一个游戏的 misère 版本，简单来说就是：按原本的规则要赢的人，按 misère 规则就输了。所以，我求解的反三子棋就是一种 m,n,k-game 的 misère 版本。
求解游戏，用什么算法好呢？AI 说，五子棋的求解用了证明数搜索。了解后，我决定使用 df-pn 以节省内存。它不支持平局，常用的解决办法是把平局看作某一方胜利，我也这么做了，平局看作先手胜。最初，我使用 16 位整数存储 phi、delta，把最大值看作无穷大，在加减法时特判。至于子节点的生成，我最初使用 TinyVec 的栈上数组保存，排序后去重。
df-pn 非常依赖置换表。最初的置换表非常简单，就是一项项的数组，每项包括指纹、phi、delta。此时我就琢磨怎样节省点空间，同时保证能检测出碰撞。灵机一动，想到用三进制编码哈希，再用上乘法哈希，使得哈希虽有 64 位，但去除高位后依然能保证单射，成功把指纹砍掉一半大小（详见 README）。如此一来，每项正好八字节，完美。这个哈希是我自己觉得最有趣的设计，简简单单就省去了不少空间，而且乘法常数也可以融合到查表中，零开销。
既有了哈希，再顺便实现规范化。棋盘旋转翻转是等价的，规范化就是让等价的局面拥有相同的哈希，便于不同的计算在置换表中共享。通过查表和增量计算（在棋盘状态中保存当前的八个哈希），我用 SIMD 同时算出八个等价局面的哈希，免于在棋盘上做复杂的旋转翻转（而且当时还没决定用不用位棋盘）。至于乘法的常数，我了解到斐波那契哈希，看着很牛逼，用之。但直到最后我才想到斐波那契哈希是要取高位才有用的，不过测试后发现换个恰当的斐波那契常数也只快了不到百分之一，问题不大。
置换表做了，那就要设计棋盘表示了，我选择了位棋盘，并用两个整数分别表示双方棋子。这样的好处是，可以抽象出位置的 bitset（Board 类型），同时可表示所有棋子、空位、下一步可下的位置之类，毕竟某一方的所有棋子也就是位置的集合。通过位运算，可以快速计算出落子不会导致连三的位置。
各组件齐全后，4x4 的反三子棋很快就成功解决了。但尝试解决 5x5 时发现 phi、delta 会溢出，只好改为 32 位。这导致置换表每项膨胀到了 12 字节。
现在看起来没有什么逻辑问题，只剩性能问题了。于是我下了个 samply 来分析（也尝试过 flamegraph，但静态的图像实在难以使用。感觉 samply 挺好用的），然后震惊地发现，除去初始化置换表外，最耗时的函数占了三分之一以上的用时，它似乎是……memcpy？！再一看它的调用者，包括栈上数组的初始化、插入，以及去重的排序。
栈上数组需要初始化，是 tinyvec 为了安全而牺牲性能导致的，改用 ArrayVec 就解决了。插入的耗时就麻烦些，其原因是棋盘状态包括了 512 位的增量哈希，要保存状态就必须复制。于是我决定将状态从不可变改为可变，递归时仅传入引用而非整个结构体，子节点中也仅存储走法而非完整状态，在递归前落子、递归后撤销即可。这大幅减少了 memcpy。至于去重，排序本身耗时就较多，我使用了类似布隆过滤器的结构，若阳性则线性扫描，直接消除了排序。这个去重方法我觉得也有点意思。
然后，火焰图的大头就来到了置换表的读取，接近一半的时间都花在这上面！由于从来没有想过内存读取的耗时，我最初只当是算法不够好（当然，后来发现算法确实有很大优化空间）。盯着火焰图看了一会后，我突然想到，这不就是缓存缺失的访存延迟吗？！久闻内存墙大名，这次终于见到，长知识了。问题的解决方法也很简单：预取。加了滑动窗口预取后，用时减少了近三分之一。除了算法外，这是最重要的优化。
说回添加预取前的时候，当时觉得算法不够好，又看 phi、delta 的无穷大实现很不优雅，灵机一动，想到了浮点数。浮点数天然支持无穷大，而且范围极大不怕溢出，也支持微调一些参数。这节省了许多代码量，也为后面置换表的压缩提供了铺垫。
为了采集更多信息、更好地判断优化的效果，我加入了统计功能（也许更早之前已经加了，具体时间忘了），可以统计各深度的：节点访问次数、最大 phi 与 delta、平均循环次数（df-pn 算法的内部情况）、平均子节点数（包括去重前后）、置换表读取和写入的次数和命中率。不过大部分数据看不出什么信息，哈哈。由于统计要花一点时间，所以可以关闭，最终的代码就关闭了。后来还加入了全局的统计，只统计最大 phi 与 delta、节点访问次数以节省时间，其中前者用于确认溢出没有发生（虽然估计上肯定没有，但这样更放心）。
预取优化了，接下来最好捏的软柿子是启发式评分，用于新节点的默认值。我用的评分方法非常简单：把空位全部填满我方棋子，看看横、竖、斜总共能形成几个连三，连三越多越难胜利，再加一个常数防止等于零，这就是 phi。而 delta 就是反过来而已。用启发式评分替换掉原始的固定一分后，访问节点数减少了近四分之一。这个分数显然有很大改进空间，不过有用就行了，我也不知道如何继续改进。
然后要优化什么呢？我认为是置换表，毕竟一项项的数组看上去实在太朴素了。先是压缩。浮点数是 32 位的，可以只存储 16 位，舍弃一些精度。有现成方案 f16、bf16，但我想多挤出一位有效数字，就把符号位去掉了，毕竟一定为正。此外，我直接截断而没有舍入，也没有管 NaN（反正不会出现）。截断不会混淆零、规格数、无穷，所以不会产生错误结果。节点访问次数在平局先手胜时略微增加，但在后手胜时却减少了近十分之一，不知为何。
接着就是置换表本身的结构了。我让表中的一项（应该叫「桶」了）存储七个局面的 phi、delta（为什么不是八个？为了给 RRPV 腾位置），把七个指纹放进 256 位的 SIMD 一次性查找，再加上 32 位的 RRPV，总共刚好对齐一个缓存行。用 RRIP 决定要踢出的局面。README 中有详细介绍这些内容。说实话，这些设计都是拍脑袋想的，看着很牛逼而已，没有经过详细的测试。新旧方案可以用泛型切换。问题解决之后，我重新把它们在一些局面对比测试了一下，发现使用 SIMD 的新方案在存储的总局面是原先方案的 7/8 的情况下，节点访问次数少了约四分之一，但时间却多花了一点儿。懒得详细测试了，就这样吧，反正已经解决了。
优化置换表时，我觉得 samply 看不到更多微架构的内容，无法了解具体的访存、分支预测等信息，于是又下了个 VTune 来分析。奈何我水平不够，看不出什么信息。
优化置换表后，看统计数据，我奇怪地发现：置换表的命中率确有增加，但总的情况居然劣化了，节点访问次数也增加！我想，这当是算法的问题，使得更多信息不一定能带来更好的结果。我怀疑搜索算法系统性地高估或低估了一些局面的分数，使得置换表中更精确的分数反而不利于走法排序。不知道怎么办，于是把《Game-Tree Search Using Proof Numbers: The First Twenty Years》这篇综述浏览了一遍，碰碰运气。看到了其中的 WPNS（Weak proof-number search，弱证明数搜索），一种解决有向无环图搜索树上分数因重复累积而过高的方法。相比其他方法，它非常简单，仅需修改 delta 累加方法：除了最大的外，其他子节点的 phi 全部限制为不超过 1。那就试试吧。我尝试了这个方法，在略调整常数后，效果奇好无比！节点访问次数直接降到了约四分之一！在这一修改面前，其他所有优化全部相形见绌。不过，当时遇到了一个奇怪的问题：我的代码中，最大子节点加了两次（有限制、无限制），若正确地减去，不知为何反而可能导致死循环（现在依然没有头绪）。而且我并不确定问题是否真的出在有向无环图上。但能用就行，毕竟速度的提升可是实打实的，也不会影响最终结果的正确性。
性能已经很好，再看看 profile，访存依然占了一些时间。于是做了最后一个优化：在生成子节点时，若可行的走法很少（即到了终局），就直接运行暴力搜索求出结果，而非从置换表中获取。这填充了一些从预取到访存的时间，同时免去了终局时运行完整 df-pn 递归的开销。
此时我已经不知道有什么优化可做了，因此开始确认最终求解的可行性。我随意取了几个 5x5 棋盘上的开局，发现已下了三子的开局可以在一两秒内解出，粗略算过去总耗时完全可接受，故准备构建深度为三的开局书。我很早就决定要构建开局书而非直接求解，因为直接求解需要很久时间，不知进度如何，也无法增量计算。此外，我主观猜测，在直接求解时，也许很浅的节点会被误踢出置换表，导致大量的重复计算；而构建开局书使得每次求解所遍历的节点数较少，置换表负担也会轻些。虽然置换表会导致不少多余的计算，但总的来说利大于弊。
简单微调各个参数，再加个搜索的超时检查，然后就是构建开局书。在我的笔记本上，构建深度为三的开局书，共有 904 个不等价的局面，要花十多分钟。我只计算了平局先手胜的结果。
有了开局书，就能轻松得出结论，5x5 反三子棋是后手必胜的。接下来的问题就是：如何确认结论是对的？我本想构建完整的证明树，但尝试后发现不太可行，遍历了一百多万个节点也没有结束，不知道总共会有多大，我就停止了。既然静态的证明树过大，那就搞动态的吧！于是我用 Ratatui 做了个可视化 TUI 界面，动态计算局面是否必胜，并给出必胜走法，又做了个命令行界面。具体用法详见 README。人工粗略测试后，没有找到 bug。
求解过程已经讲完了，情况就是这么个情况。如果 AI 没有漏掉什么信息，那我应该是首个求解出 5x5 反三子棋的人。但也可能早已有人解决了，不过没关系，重在过程：我首次了解了证明数搜索等概念，意识到了缓存的重要性，初步尝试了 samply、VTune，简单使用了 Ratatui……
最后，这个程序理论上不难扩展。扩展到 6x5 应该只需改个常量，扩展到 6x6 则是要把位棋盘从 32 位整数改为 64 位（哈希需要 58 位，能放得下，无需修改）。实现上不复杂，但若要求解，由于状态空间又翻了很多倍，恐怕不容易做到。至少我是懒得搞了。