Overview

整体思路是用强 AI 引擎找最佳点 dfs 形成必胜树，当局面能 VCT (Victory of Continuous Three) 求解的时候用 VCT 求解器求解，即叶子都能 VCT 求解。这样形成的必胜树总共 $111552$ 个结点，$34005$ 个叶子。

具体过程为：

把开局分裂（分裂到第三步）并行求解。
合并分裂的开局为一颗必胜树。
剪枝1：可以发现必胜树若某一个叶子是该黑走，那么我们可以直接删掉这个叶子（因为这个叶子的父亲是该白走，该白走的结点必定所有的可走点都是它的儿子，这个叶子不会再扩展下去，所以不用记录）
剪枝2：根据置换表，有相同局面的点可以直接用指针指过去，其子树不用记录。
扩展：这样得到的叶子有可能 VCT 计算时间长，因此把 VCT 计算时间长的叶子扩展出去记录下来。

VCT Solver

整个过程的关键是 VCT Solver 的效率。采用 Rapfi 的 Board 类来辅助 VCT 求解。

Board 类

Board 类的核心是记录了局面每个点位的类型。一个是 Line Level 的点位类型，一个是 4 个方向的 Line 的复合点位类型：

Pattern[who,x,y,dir]: 记录的是 $x,y$ 这个点 $who$ 在 $dir$ 方向上的类型：

/// Pattern is the type of a single line at one cell
enum Pattern : uint8_t {
    DEAD,  // X_.__X, can never make a five
    OL,    // OO.OOO, one step before overline
    B1,    // X.____, one step before B2
    F1,    // X_.___, one step before F2
    B2,    // XO.___, one step before B3
    F2,    // _O__._, one step before two F3
    F2A,   // _O_.__, one step before three F3
    F2B,   // _O.___, one step before four F3
    B3,    // XOO.__, one step before B4
    F3,    // _OO_._, one step before one F4
    F3S,   // __OO.__, one step before two F4
    B4,    // XOOO._X, one step before F5
    F4,    // _OOO._X, one step before two F5
    F5,    // XOO.OOX, making a five
    PATTERN_NB
};

Pattern 会对所有的点都实时更新，包括已经有子的点位。（在原 Rapfi 的实现中下过子的点是不更新的，这里是为了适配 VCT）。

程序启动的时候会用 dp 预处理出一个 lookuptable 用于记录一条线的形状对应的 Pattern 的映射表。映射表是 $uint64\to Pattern$ 的，key 是这条 Line 上的位置的情况，默认最中间的位置是 who，每两位记录一个位置：例如 XOO_O 就是 0b 11 10 10 00 10。

Pattern4[x,y,who]：记录的是这个点位的复合类型：

/// Pattern4 is the combined type of 4 lines at one cell
enum Pattern4 : uint8_t {
    NONE,            // Anything else
    FORBID,          // Forbidden point (for renju)
    L_FLEX2,         // F2+Any
    K_BLOCK3,        // B3+Any
    J_FLEX2_2X,      // F2x2
    I_BLOCK3_PLUS,   // B3x2 | B3+F2
    H_FLEX3,         // F3+Any
    G_FLEX3_PLUS,    // F3+F2 | F3+B3
    F_FLEX3_2X,      // F3x2
    E_BLOCK4,        // B4+Any
    D_BLOCK4_PLUS,   // B4+F2 | B4+B3
    C_BLOCK4_FLEX3,  // B4+F3
    B_FLEX4,         // F4 | F4S | B4x2
    A_FIVE,          // F5
    PATTERN4_NB
};

同样实时更新，但是只更新空位，四个方向的 Pattern 即可决定 Pattern4，也提前计算 $Pattern^4 \to Pattern4$。的映射。

每次落子的时候，更新这个子“上、下、右上、右下”四个方向周围的位置的 Pattern 和 Pattern4。

VCT 求解

求解的核心逻辑是黑棋的每一步必须下完后场面上存在至少一个活三，没有就算黑输（也就是说要堵对方的 4 的时候也要求自己的这一步下完之后场面上还有活三，无论是之前就有的还是这一次堵形成的）。这样可以保证白方每次的选择点数不超过 3，大大缩减搜索空间。具体过程看代码。

测试速度：几乎所有局面都能在 50ms 内完成 VCT vct_dep=12 层搜索。

必胜树 & 剪枝

原始必胜树

在用 Rapfi 指导找必胜树的过程中，需要严格保证所有必胜树的叶子结点是可以 VCT vct_dep 层求解的，如下图（黑色结点表示该黑走，白色结点表示该白走，VCT表示可以VCT求解）：

原始必胜树总计 $35196569$ 个结点，$34872519$ 个叶子结点。

一些实现细节：

所有叶子都是黑色的。这是因为在找必胜树的过程中，白色结点的 VCT 计算时间是黑色结点的很多倍（白色结点求 VCT 的时候黑方不一定有活三，所以可以选择的点有很多）。因此在白色结点不去计算 VCT，直接扩展下去。黑色结点才去计算 VCT，若有则不继续扩展。如果在白色也计算 VCT，总时间会 $\times 2$（白色结点计算一次 VCT 等价于所有儿子计算一次）。
同样会记录出现过的局面，如果出现过某种局面，就直接复制那个局面的子树过来。

剪枝 1

上面的必胜树可以优化掉黑色的 VCT 叶子结点，因为我们不关心白色走哪里，黑色都可以 VCT，所以黑色叶子节点可以剪掉，如图，VCT+1 表示这个白色结点的非儿子的后继局面都一定能 VCT 求解。。

此时总共 $35196569-34872519=324050$ 个结点，且叶子都是白色的。

剪枝 2

有相同的局面就删掉这颗子树（这个子树的根保留，相当于做一个软链接），并且指向相同局面的那个结点，如图。虚化的黑色结点表示复制结点，箭头指向和他局面同构的结点。

经过了上述两次剪枝，最终的树有如下性质，可以用来写验证程序：

对于黑结点：
1. 最多一个儿子。
2. 若没有儿子，则一定是一个复制结点。
对于白结点：
1. 其儿子要么是一个普通的黑结点，要么是一个复制结点。
2. 这个白色结点的非儿子的后继局面一定可以 VCT vct_dep 层求解。
对于复制结点：
1. 指向的点的 pre_order_dfs_number 一定比自己小。

最终形成的树总结点 $47580$ 个，有 $2618$ 个复制结点。

扩展

现在得到的必胜树叶子的求解时间可能过长，因此可以根据 VCT 来扩展必胜树叶子。同时要记录该结点的 VCT 求解的 vct_dep 是多少。比如剪枝后的树的叶节点 vct_dep=12，那么它扩展出去的儿子 vct_dep=11。为什么要记录这个？因为父亲和儿子用同样的 vct_dep 进行 VCT 求解的时候，儿子不一定比父亲快，但如果儿子用 vct_dep-1 求解，就一定比父亲快。这是因为如果用 vct_dep-1 求解能严格保证儿子的搜索空间是父亲的子集，否则儿子会多算一层导致时间开销变大。

经过测试，最终必胜树总结点 $111552$ 个，所有 VCT 求解时间在 20ms 内，压缩后程序占用磁盘 100KB，运行内存 $<20$ MB。

五子棋无禁手黑胜程序