问题

给定一个棋盘格局，找出所有的威胁点。威胁点是指双方各自落子后能形成必胜局面的点，例如冲四的一端（必胜，落子后立刻形成五子连珠）、活三的两端（落子后形成活四，若对方此步不胜则下一回合必胜）。例如下面这个棋盘中标“x”的位置。

┌┬┬┬┬┬┬┬┬┬┬┬┬┬┐

├┼┼┼┼┼┼┼┼┼┼┼┼┼┤

├┼┼┼┼┼┼┼┼┼┼┼┼┼┤

├┼┼┼┼┼┼┼┼┼┼┼┼┼┤

├┼┼┼┼┼┼┼┼┼┼┼┼┼┤

├┼┼┼┼┼┼┼┼┼┼x┼┼┤

├┼┼┼┼┼┼┼┼┼●┼┼┼┤

├┼┼┼x○○○○●┼┼┼┼┤

├┼┼┼┼┼┼┼●┼┼┼┼┼┤

├┼┼┼┼┼┼x┼┼┼┼┼┼┤

├┼┼┼┼┼┼┼┼┼┼┼┼┼┤

├┼┼┼┼┼┼┼┼┼┼┼┼┼┤

├┼┼┼┼┼┼┼┼┼┼┼┼┼┤

├┼┼┼┼┼┼┼┼┼┼┼┼┼┤

└┴┴┴┴┴┴┴┴┴┴┴┴┴┘

在AI程序的搜索中，如果出现这些威胁点，必须快速找到，以便裁剪掉其他着法。 因为有威胁点时仍着于其他位置总会导致不利。

朴素方法

简单的解决方法是按照规则进行遍历。我相信大部分人初次上手编写程序都是这样解决的，我也一样，毕竟过早优化是万恶之源。 但是最终你会发现这一过程的速度对AI的表现而言是至关重要的。

首先容易想到的解决方案是向量化。 用位棋盘（bitboard）作格局表示，将棋盘分为黑、白两盘，每一盘都是225个比特，可以装在uint16_t [16]中，或一个YMM寄存器__m256i中。 通过_mm256_slli_epi16/_mm256_srli_epi16（VPSLLW/VPSRLW）等向量指令对整个棋盘进行移动、对齐，然后进行逻辑与，寻找活四、冲四、活三。 这样节省了遍历盘面的开销，但由于棋形复杂（冲四、活三都不一定是连续的，可能有眼），程序并不简单，仍然需要比较长时间。

三进制编码

2014年，我独立发现了一个解决方法，并运用于kalscope第二版“Dolanaar”起的评估函数中。 这个程序是我本科时练习调优的习作，但也在当时取得了不错的棋力。

我将棋盘的每条阳线（横向、纵向的线）分开看待。 一条阳线上有15格，我将一行上所有可能的格局都列出，提前计算威胁点，形成查找表。 但是以位棋盘表示的话，一条阳线的编码可达，对应查找表尺寸达到2 GB。 注意到位棋盘编码中有大量冗余，以2比特编码了3种情况：空“┼”0b00、白子“○”0b01、黑子“●”0b10，而0b11是非法的。 要实现紧凑编码，需要采用三进制计数，0表示空，1表示白子，2表示黑子，每个三进制位表示一个格子。

进制转换涉及大量除模运算，由二进制位棋盘转三进制开销大，是不现实的。 注意到棋盘格局并非突然出现，而是总由空棋盘逐步落子形成，三进制表示可以增量维护。 空棋盘编码为0；在第位落白子，即编码加；在第位落黑子，即编码加。搜索过程中进行回退，则将增加的编码重新减去。 要高效实现，只需另记一个三的各幂次查找表power3。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
constexpr int power3[16] {
 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907
};
int triboard_h[15] {};
int triboard_v[15] {};
uint16_t threat_lut[14348907] { ... }; // pre-generated.

void make(int x, int y, int color) {
    triboard_h[y] += power3[x] << color;
    triboard_v[x] += power3[y] << color;
}
void unmake(int x, int y, int color) {
    triboard_h[y] -= power3[x] << color;
    triboard_v[x] -= power3[y] << color;
}
void find_threat() {
    for (int y = 0; y < 15; y++) {
        uint16_t threat = threat_lut[triboard_h[y]];
        while (threat) {
            int x = std::countr_zero(threat);

            // do something to the threat (x,y).

            threat &= threat - 1;
        }
    }
    // another loop for vertical lines.
    // TODO: how about diagonal / anti-diagonal lines?
}

查找表threat_lut紧密编码了15格阳线的所有可能格局，仅占据27.4 MB内存。

这个方法为标准15路棋盘设计，但彼时Gomocup规则是20路棋盘，导致这个方法无效，不然当时可能我也会去参赛。 我不确定是否有其他人率先发现了类似方法，不过我确实注意到最近赢下Gomocup大赛冠军的Rapfi也在程序的一些地方使用了这一技巧。

这个方法不完美。它只适用于固定15格的阳线，用在Gomocup的20格规则就会导致查找表过大。 另外，阴线（对角、反对角线）每一条都有不同长度，如果生硬套用15格阳线的查找表会导致误报。例如在总长度只有4格的阴线上，即使形成活三也不构成威胁，因为棋盘边界会自然堵截它。这该如何处理？

十年前的我没有给出答案，留下一个未解难题。

偏斜三进制编码

去年，我指导博士研究生郭泓锐完成了Cambricon-U，采用偏斜二进制编码实现了在SRAM中原位计数的功能。 偏斜记数法不仅可以用于二进制，也可用于三进制，解决上述三进制编码遗留的阴线表示问题。

偏斜三进制允许数位中暂时存在一个“3”而不向前进位。 计数时，如果各数位中不存在“3”，则将最低位递增1； 如果各数位中存在“3”，将“3”归零并向前进位。 在这样的计数规则下，容易发现偏斜三进制存在以下两项性质：

  • 各数位上最多存在一个“3”；
  • 如果存在“3”，在“3”的右侧各位（更低位）一定全都是“0”。

我们以“0”表示空格，“1”表示白子，“2”表示黑子，“3”表示棋盘边界，即可自然而紧凑地将各种长度的阴线编入到查找表中。 阴线的长度不满15格时，只使用高位，将边界置“3”，更低位置“0”。 查找表内各项按照偏斜三进制计数顺序编纂：

查找表
十进制编号 偏斜三进制编号 棋盘格局 威胁点
0 000000000000000 ├┼┼┼┼┼┼┼┼┼┼┼┼┼┤ 0b000000000000000
1 000000000000001 ├┼┼┼┼┼┼┼┼┼┼┼┼┼○ 0b000000000000000
2 000000000000002 ├┼┼┼┼┼┼┼┼┼┼┼┼┼● 0b000000000000000
3 000000000000003 ├┼┼┼┼┼┼┼┼┼┼┼┼┤▒ 0b000000000000000
4 000000000000010 ├┼┼┼┼┼┼┼┼┼┼┼┼○┤ 0b000000000000000
5 000000000000011 ├┼┼┼┼┼┼┼┼┼┼┼┼○○ 0b000000000000000
6 000000000000012 ├┼┼┼┼┼┼┼┼┼┼┼┼○● 0b000000000000000
7 000000000000013 ├┼┼┼┼┼┼┼┼┼┼┼┼○▒ 0b000000000000000
8 000000000000020 ├┼┼┼┼┼┼┼┼┼┼┼┼●┤ 0b000000000000000
9 000000000000021 ├┼┼┼┼┼┼┼┼┼┼┼┼●○ 0b000000000000000
10 000000000000022 ├┼┼┼┼┼┼┼┼┼┼┼┼●● 0b000000000000000
11 000000000000023 ├┼┼┼┼┼┼┼┼┼┼┼┼●▒ 0b000000000000000
12 000000000000030 ├┼┼┼┼┼┼┼┼┼┼┼┤▒▒ 0b000000000000000
13 000000000000100 ├┼┼┼┼┼┼┼┼┼┼┼○┼┤ 0b000000000000000
14 000000000000101 ├┼┼┼┼┼┼┼┼┼┼┼○┼○ 0b000000000000000
15 000000000000102 ├┼┼┼┼┼┼┼┼┼┼┼○┼● 0b000000000000000
16 000000000000103 ├┼┼┼┼┼┼┼┼┼┼┼○┤▒ 0b000000000000000
17 000000000000110 ├┼┼┼┼┼┼┼┼┼┼┼○○┤ 0b000000000000000
18 000000000000111 ├┼┼┼┼┼┼┼┼┼┼┼○○○ 0b000000000000000
19 000000000000112 ├┼┼┼┼┼┼┼┼┼┼┼○○● 0b000000000000000
20 000000000000113 ├┼┼┼┼┼┼┼┼┼┼┼○○▒ 0b000000000000000
21 000000000000120 ├┼┼┼┼┼┼┼┼┼┼┼○●┤ 0b000000000000000
22 000000000000121 ├┼┼┼┼┼┼┼┼┼┼┼○●○ 0b000000000000000
23 000000000000122 ├┼┼┼┼┼┼┼┼┼┼┼○●● 0b000000000000000
24 000000000000123 ├┼┼┼┼┼┼┼┼┼┼┼○●▒ 0b000000000000000
25 000000000000130 ├┼┼┼┼┼┼┼┼┼┼┼○▒▒ 0b000000000000000
26 000000000000200 ├┼┼┼┼┼┼┼┼┼┼┼●┼┤ 0b000000000000000
27 000000000000201 ├┼┼┼┼┼┼┼┼┼┼┼●┼○ 0b000000000000000
28 000000000000202 ├┼┼┼┼┼┼┼┼┼┼┼●┼● 0b000000000000000
29 000000000000203 ├┼┼┼┼┼┼┼┼┼┼┼●┤▒ 0b000000000000000
30 000000000000210 ├┼┼┼┼┼┼┼┼┼┼┼●○┤ 0b000000000000000
31 000000000000211 ├┼┼┼┼┼┼┼┼┼┼┼●○○ 0b000000000000000
32 000000000000212 ├┼┼┼┼┼┼┼┼┼┼┼●○● 0b000000000000000
33 000000000000213 ├┼┼┼┼┼┼┼┼┼┼┼●○▒ 0b000000000000000
34 000000000000220 ├┼┼┼┼┼┼┼┼┼┼┼●●┤ 0b000000000000000
35 000000000000221 ├┼┼┼┼┼┼┼┼┼┼┼●●○ 0b000000000000000
36 000000000000222 ├┼┼┼┼┼┼┼┼┼┼┼●●● 0b000000000000000
37 000000000000223 ├┼┼┼┼┼┼┼┼┼┼┼●●▒ 0b000000000000000
38 000000000000230 ├┼┼┼┼┼┼┼┼┼┼┼●▒▒ 0b000000000000000
39 000000000000300 ├┼┼┼┼┼┼┼┼┼┼┤▒▒▒ 0b000000000000000
40 000000000001000 ├┼┼┼┼┼┼┼┼┼┼○┼┼┤ 0b000000000000000
41 000000000001001 ├┼┼┼┼┼┼┼┼┼┼○┼┼○ 0b000000000000000
42 000000000001002 ├┼┼┼┼┼┼┼┼┼┼○┼┼● 0b000000000000000
43 000000000001003 ├┼┼┼┼┼┼┼┼┼┼○┼┤▒ 0b000000000000000
44 000000000001010 ├┼┼┼┼┼┼┼┼┼┼○┼○┤ 0b000000000000000
45 000000000001011 ├┼┼┼┼┼┼┼┼┼┼○┼○○ 0b000000000000000
… … … …
138 000000000010110 ├┼┼┼┼┼┼┼┼┼○┼○○┤ 0b000000000001000
… … … …
174 000000000011100 ├┼┼┼┼┼┼┼┼┼○○○┼┤ 0b000000000100010
175 000000000011101 ├┼┼┼┼┼┼┼┼┼○○○┼○ 0b000000000000010
176 000000000011102 ├┼┼┼┼┼┼┼┼┼○○○┼● 0b000000000100000
177 000000000011102 ├┼┼┼┼┼┼┼┼┼○○○┤▒ 0b000000000100000
… … … …
21523354 222223000000000 ●●●●●▒▒▒▒▒▒▒▒▒▒ 0b000000000000000
21523355 222230000000000 ●●●●▒▒▒▒▒▒▒▒▒▒▒ 0b000000000000000
21523356 222300000000000 ●●●▒▒▒▒▒▒▒▒▒▒▒▒ 0b000000000000000
21523357 223000000000000 ●●▒▒▒▒▒▒▒▒▒▒▒▒▒ 0b000000000000000
21523358 230000000000000 ●▒▒▒▒▒▒▒▒▒▒▒▒▒▒ 0b000000000000000

该查找表共21523359项，紧密地编码了15格阳线和1到15格的所有阴线的各种格局，占41.1 MB内存。 使用方法稍加改动即可，将三进制位权重power3改为偏斜三进制位权重basesk3，该数列为OEIS A261547。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
constexpr int basesk3[16] {
    1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484, 7174453, 21523360
};
int sk3board_h[15] {};
int sk3board_v[15] {};
int sk3board_d[29] {};
int sk3board_a[29] {};
uint16_t threat_lut[21523359] { ... }; // pre-generated.
   
// set board bounds on init. 
void init() {
    for (int i = 0; i < 15; i++) {
        sk3board_d[i] = basesk3[13-i] * 3;
        sk3board_a[i] = basesk3[13-i] * 3;
    }
    for (int i = 15; i < 29; i++)
        sk3board_d[i] = basesk3[i-15] * 3;
        sk3board_a[i] = basesk3[i-15] * 3;
    }
}

void make(int x, int y, int color) {
    sk3board_h[y]      += basesk3[x]             << color;
    sk3board_v[x]      += basesk3[y]             << color;
    sk3board_d[14-x+y] += basesk3[x<y?y:x]       << color;
    sk3board_a[x+y]    += basesk3[x+y<15?14-y:x] << color;
}
void unmake(int x, int y, int color) {
    sk3board_h[y]      -= basesk3[x]             << color;
    sk3board_v[x]      -= basesk3[y]             << color;
    sk3board_d[14-x+y] -= basesk3[x<y?y:x]       << color;
    sk3board_a[x+y]    -= basesk3[x+y<15?14-y:x] << color;
}
void find_threat() {
    for (int y = 0; y < 15; y++) {
        uint16_t threat = threat_lut[sk3board_h[y]];
        while (threat) {
            int x = std::countr_zero(threat);

            // do something to the threat (x,y).

            threat &= threat - 1;
        }
    }
    // to process vertical, diagonal and anti-diagonal lines
}

这样，我们就将相当繁琐的威胁点检查问题完全转化成了增量维护四个方向的棋盘表示，然后进行表项查找。41 MB左右的查找表如今能够完全存放在L3缓存当中，可想而知速度是极快的。 上述示例中，find_threat还可以进一步向量化，乃至整个操作的开销可压缩至约百余个时钟周期。

同样的思路可以用于获胜检查、评价函数等。如果你准备使用类AlphaGo的架构，不妨尝试将神经网络第一层改为沿阴阳四线进行的一维卷积，用此方法可以直接以查找取代第一层卷积运算。