黑白棋（Othello / Reversi）的规则简单到一句话就能说完：夹住对方的棋子就翻转成自己的颜色，终局子多者胜。但它的搜索难度远超五子棋，原因在于盘面价值极不稳定——一个棋子在终局前可能被翻转四五次，中盘领先 20 子最后输掉是常态。这让”用评估函数做浅层 Alpha-Beta”的传统套路在黑白棋上效果很差。
真正让黑白棋 AI 产生质变的技术有两项：一项是 20 世纪 90 年代 Michael Buro 提出的 ProbCut（概率剪枝），另一项是 静态搜索延伸（selective search / extension） 处理强制翻转链。前者让搜索深度凭空涨 2~3 层，后者让评估不落在”翻转还没做完”的中间状态上。本文用 Java 把这两项技术落地，构造一个能跑赢大多数人类的黑白棋引擎。
一、为什么黑白棋不能用”常规”Alpha-Beta
先理解黑白棋的搜索特征：
- 分支因子大：中盘平均合法着法 10~12 个，比国际象棋（约 35）小，但比五子棋局部搜索大。
- 强制序列长：一次落子可能引发连续翻转，且”没有合法着法时自动跳过”意味着行动序列中会出现被动跳过回合，这打破了”奇数层=我方”的简单假设。
- 评估极不稳：子数差（disc differential）在开局和中盘几乎没有预测力，甚至反向（早期少吃子反而好，因为少子给了对方更少翻盘机会）。真正有预测力的是活动力（mobility）、稳定子（stable discs）、奇偶性（parity）。
所以黑白棋引擎的评估函数必须”分阶段加权”：开局和中盘几乎不看子数，只看活动力和角；残局（空格 < 12）才切换到精确的子数 + 稳定子。这种”评估函数随阶段切换”的特性，恰好让 ProbCut 的统计前提更容易满足——因为 ProbCut 只需要”浅层搜索的估值与深层搜索结果有统计相关性”，而不需要相关性在所有阶段都一致。
二、ProbCut 的核心思想
Alpha-Beta 的问题是：只要我搜到某个着法的值 ≥ β，我就立刻剪掉后面的兄弟节点。但为了确认”≥ β”，我必须把这一支搜到底。ProbCut 换了个角度：
我能不能先用一个浅层搜索（深度 d-2）粗略估一下？如果浅层结果已经足够好或足够坏，我就赌它在深层也会如此，直接剪枝。
具体地，设当前深度为 d，我在浅层 d-2 搜索得到估值 v。如果 v 显著优于 β（即 v 远大于 β），那么深层 d 的结果大概率也优于 β。既然大概率如此，我就可以直接返回”这是下界”，省掉整个深层搜索。
“显著”由两个统计参数决定：一个线性回归 v_d = a * v_{d-2} + b，和一个置信宽度 σ（残差标准差）。判定条件写成：
若是 MAX 节点： 若 v_{d-2} ≥ (β - b + σ) / a → 剪枝，返回下界 ≥ β
若是 MIN 节点： 若 v_{d-2} ≤ (α - b - σ) / a → 剪枝，返回上界 ≤ α
Buro 在原论文中给出的经验值：a ≈ 1.16、b ≈ -7.5（子数差单位），σ 约 1.0~1.5（与深度差有关）。
关键洞察：ProbCut 会犯错，但错误概率被 σ 控制。σ 越大越保守（漏剪机会多、错剪少），σ 越小越激进（剪得多、可能剪掉真正的好棋）。这个旋钮让你可以在”棋力”和”速度”之间连续调节，而不是像 Alpha-Beta 那样只有全对或全错。
2.1 为什么要在”每个着法”上做 ProbCut，而不是在节点上
更有效的做法是 Multi-ProbCut（多级概率剪枝）：对一个节点的每个候选手，用浅层搜索（d-2）算一遍分数；把分数按”更可能超过 β”的顺序排序，然后只对排序靠前的那几个着法做深层验证。如果前几个深层验证都失败（都 ≤ β），后面大概率也失败，可以整体放弃。
这实际上把 ProbCut 和着法排序（move ordering）合成了一件事。这也是现代黑白棋引擎（如 Edax）的标准做法。
三、静态搜索延伸：处理强制翻转链
黑白棋的”静态评估”有个致命问题：如果你在盘面还处于”翻转中途”的状态调用评估函数，得到的子数差毫无意义。解决办法是搜索层”延伸”——在进入叶子之前，如果存在强制着法（合法着法只有 1 个，或是必须吃子否则失去角），就继续向下搜，直到底层稳定。
/**
* 静态搜索（quiescence）：当剩余合法着法极少或处于强制翻转状态时，
* 继续深入到盘面稳定为止，避免在"翻转未完成"的中间态取值。
*/
private int quiesce(Board b, int alpha, int beta, int color) {
int moves = b.countLegalMoves(color);
if (moves == 0) {
// 自己无着法；若对方也无着法则终局，直接精确计分
if (b.countLegalMoves(-color) == 0) return b.finalScore(color);
// 否则轮到对方，注意层级翻转（此处用递归而非取负，避免奇偶错乱）
return -quiesce(b, -beta, -alpha, -color);
}
if (moves > 1) {
// 有多选择时不是强制序列，用静态估值即可
return b.evaluate(color);
}
// 唯一合法着法 => 强制延伸，继续搜
Board next = b.playOnlyMove(color);
int val = -quiesce(next, -beta, -alpha, -color);
return Math.max(val, b.evaluate(color)); // 延伸结果不劣于静态估值
}
这里有一个黑白棋特有的坑：“跳过回合”会破坏 negamax 的层级对称性。如果一方无合法着法而另一方有，直接 return -search(...) 会让搜索深度计数的奇偶性偏移，导致同一节点在不同路径上以不同深度被访问、置换表命中出错。正确做法是只让”跳过”不消耗深度（在进入下一层时把 depth 保持不变），本文在 search 中用 passFlag 参数处理。
四、完整项目结构
othello-probcut/
├── src/com/example/othello/
│ ├── Board.java // 位棋盘表示、合法着法生成、翻转、评估
│ ├── ProbCutSearch.java // Alpha-Beta + ProbCut + 静态搜索 + 置换表
│ └── Main.java // 自对弈测试与统计
└── README.md
4.1 位棋盘与合法着法生成
黑白棋用 64 位整数表示盘面是最优雅的：long black, long white。合法着法生成靠”移位 + 掩码”一次性算出所有方向：
package com.example.othello;
public class Board {
long black, white;
static final long NOT_A = 0xFEFEFEFEFEFEFEFEL; // 屏蔽 A 列，防止向左移位绕回
static final long NOT_H = 0x7F7F7F7F7F7F7F7FL; // 屏蔽 H 列
public Board(long black, long white) { this.black = black; this.white = white; }
public long occupied() { return black | white; }
/** 计算 color(1=黑,-1=白) 的所有合法着法 */
public long legalMoves(int color) {
long my = color == 1 ? black : white;
long opp = color == 1 ? white : black;
long empty = ~(my | opp);
long moves = 0;
// 8 个方向，每个方向：先扩展到连续对方棋子，再要求落点为空且倒推一步是自己的子
moves |= shift(opp, 1, NOT_H) & empty;
moves |= shift(opp, -1, NOT_A) & empty;
moves |= shift(opp, 8, -1L) & empty;
moves |= shift(opp, -8, -1L) & empty;
moves |= shift(opp, 9, NOT_H) & empty;
moves |= shift(opp, 7, NOT_A) & empty;
moves |= shift(opp, -7, NOT_H) & empty;
moves |= shift(opp, -9, NOT_A) & empty;
return moves;
}
/** 单方向扩展：opp 沿 dir 连续延伸，直到遇到自己的子则返回该子再往前一格 */
private long shift(long opp, int dir, long mask) {
long x = opp;
for (int i = 0; i < 6; i++) {
long t = (dir > 0 ? x << dir : x >>> (-dir)) & mask;
x |= t;
}
// 再往前一格即"落点"
return (dir > 0 ? x << dir : x >>> (-dir)) & mask;
}
注意 shift 里循环 6 次而不是 1 次：这是批量延伸的关键——因为可能连续夹住 2~6 个对方棋子，必须把”对方棋子链”整体向前推移，最后一格才是落点。如果只移一次，只能识别”紧邻夹一子”的情况，会漏掉大量合法着法。
掩码 NOT_A / NOT_H 用于防止左右移位时从 H 列绕回 A 列（64 位整数的行是连续的，A 列再左移一格会跑到上一行的 H 列，这是位棋盘的经典陷阱）。
4.2 翻转与执行
/** 在 pos 落子并返回新盘面（不改自身） */
public Board play(int pos, int color) {
long flip = 0;
for (int dir : new int[]{1, -1, 8, -8, 9, 7, -7, -9}) {
long line = 0, x = pos;
long mask = dir == 1 || dir == 9 || dir == -7 ? NOT_H
: dir == -1 || dir == -9 || dir == 7 ? NOT_A : -1L;
while (true) {
x = dir > 0 ? x << dir : x >>> (-dir);
if ((x & mask) == 0) break;
long bit = 1L << Long.numberOfTrailingZeros(x);
if ((bit & (color == 1 ? black : white)) != 0) { flip |= line; break; }
if ((bit & (color == 1 ? white : black)) == 0) break; // 空格，这条线无效
line |= bit;
}
}
long myNew = (color == 1 ? black : white) | flip | pos;
long oppNew = (color == 1 ? white : black) & ~flip;
return color == 1 ? new Board(myNew, oppNew) : new Board(oppNew, myNew);
}
这段 play 用 numberOfTrailingZeros 逐位推进，读起来比位运算宏更清晰。注意最后一行 & ~flip：翻转是把对方棋子从对方盘面拿走、加到自己盘面，两个操作必须同时发生。
4.3 评估函数：分阶段加权
// 位置权重表（角最高，C 位和 X 位是陷阱，给负分）
static final int[] POS_WEIGHT = {
100, -25, 10, 5, 5, 10, -25, 100,
-25, -50, -2, -2, -2, -2, -50, -25,
10, -2, 1, 1, 1, 1, -2, 10,
5, -2, 1, 0, 0, 1, -2, 5,
5, -2, 1, 0, 0, 1, -2, 5,
10, -2, 1, 1, 1, 1, -2, 10,
-25, -50, -2, -2, -2, -2, -50, -25,
100, -25, 10, 5, 5, 10, -25, 100
};
/** 分阶段评估：中盘看活动力+角，残局看子数+稳定子 */
public int evaluate(int color) {
int empties = Long.bitCount(~occupied());
long my = color == 1 ? black : white;
long opp = color == 1 ? white : black;
if (empties <= 12) {
// 残局：子数差 + 稳定子加权
int discDiff = Long.bitCount(my) - Long.bitCount(opp);
int stableDiff = Long.bitCount(stable(my)) - Long.bitCount(stable(opp));
return discDiff * 2 + stableDiff * 3 + parityBonus(empties);
}
// 中盘：活动力权重最高，其次是角与位置
int mobility = Long.bitCount(legalMoves(color)) - Long.bitCount(legalMoves(-color));
int corner = cornerCount(my) - cornerCount(-color);
int posScore = 0;
for (long m = my; m != 0; m &= m - 1) {
posScore += POS_WEIGHT[Long.numberOfTrailingZeros(m)];
}
return mobility * 8 + corner * 20 + posScore;
}
/** 稳定子：从四角出发，沿边和内部扩展的不可翻转子（简化版） */
long stable(long discs) {
long stable = 0;
// 四个角一旦占住就是稳定的
long corners = 0x8100000000000081L;
stable = discs & corners;
// 从每个角沿边和斜线扩展：若相邻格子也被占且朝向角落的线已满，则稳定
for (int i = 0; i < 4; i++) {
stable = expandStable(stable, discs);
}
return stable;
}
评估函数里 mobility * 8 + corner * 20 这组权重不是拍脑袋来的：在黑白棋中，活动力每多 1 个合法着法，胜率提升远比多 1 个子显著；角的权重必须压倒性地高，因为角子永久稳定且能提供边上的锚点。而 C 位（角旁边）和 X 位（对角斜邻）给负分，是因为占这两个位置等于把角送给对手。
五、ProbCut 搜索主体
package com.example.othello;
public class ProbCutSearch {
// ProbCut 回归参数：估值 = A * 浅层估值 + B，残差标准差 SIGMA
static final double A = 1.16;
static final double B = -7.5;
static final double SIGMA = 1.4;
long nodes = 0;
long probCutSuccess = 0;
/** 入口：negamax + ProbCut + 静态搜索 */
public int search(Board b, int depth, int alpha, int beta, int color) {
nodes++;
// 终局直接精确计分
if (b.isTerminal()) return b.finalScore(color);
// 自己无着法：跳过回合，深度不减（保持奇偶性）
if (b.legalMoves(color) == 0) {
return -search(b, depth, -beta, -alpha, -color);
}
if (depth <= 0) return quiesce(b, alpha, beta, color);
// ---- ProbCut 尝试：只在深度足够时启用 ----
if (depth >= 5) {
int shallowDepth = depth - 2;
// 浅层搜索得到精确值 v（用全窗口以保证统计意义）
int v = search(b, shallowDepth, -WIN, WIN, color);
// 上界式剪枝：若 v 已远超 beta，深层结果极可能也超
double cutBeta = (beta - B + SIGMA) / A;
if (v >= cutBeta) {
probCutSuccess++;
return beta; // 返回下界 >= beta
}
// 下界式剪枝
double cutAlpha = (alpha - B - SIGMA) / A;
if (v <= cutAlpha) {
probCutSuccess++;
return alpha; // 返回上界 <= alpha
}
}
// ---- 常规 Alpha-Beta + 着法排序 ----
long moves = b.legalMoves(color);
int best = -WIN;
int[] ordered = orderMoves(b, moves, color);
for (int mv : ordered) {
Board nb = b.play(1L << mv, color);
int val = -search(nb, depth - 1, -beta, -alpha, -color);
if (val > best) best = val;
if (val > alpha) alpha = val;
if (alpha >= beta) break; // beta 剪枝
}
return best;
}
/** 着法排序：先用 ProbCut 浅层分数排序，再按位置权重兜底 */
int[] orderMoves(Board b, long moves, int color) {
int n = Long.bitCount(moves);
int[] pos = new int[n];
int[] score = new int[n];
int k = 0;
for (long m = moves; m != 0; m &= m - 1) {
int p = Long.numberOfTrailingZeros(m);
pos[k] = p;
// 浅层估值（depth=1）作为排序键
Board nb = b.play(1L << p, color);
score[k] = -search(nb, 1, -WIN, WIN, -color);
k++;
}
// 按分数降序插入排序（n <= 12，插入排序最快）
for (int i = 1; i < n; i++) {
int sp = pos[i], ss = score[i], j = i - 1;
while (j >= 0 && score[j] < ss) { pos[j + 1] = pos[j]; score[j + 1] = score[j]; j--; }
pos[j + 1] = sp; score[j + 1] = ss;
}
return pos;
}
static final int WIN = 1000000;
}
代码里有几处刻意的设计选择，值得说明：
为什么 ProbCut 的浅层搜索用全窗口 (-WIN, WIN)？ 因为 ProbCut 的统计模型是”浅层精确估值 v 与深层精确估值 v_d 的线性关系”。如果你用窄窗口搜索，浅层可能直接返回一个”至少 ≥ β”的边界值而不是真值，回归模型就失效了，剪枝判定会系统性偏错。这是很多 ProbCut 实现出错的地方。
为什么要 return beta 而不是 return v？ 因为 ProbCut 给出的是”下界”而非精确值。返回 beta 是fail-hard 风格的保守返回值——只要保证调用方看到”≥ β”就会剪枝，具体返回 β 还是 β+1 不影响最终结果（fail-soft 实现会返回更精确的边界，但需要额外记账）。
为什么 depth >= 5 才启用？ 深度 4 及以下时 depth-2 太浅（只剩 2~3 层），浅层估值的噪声占比过高，ProbCut 的错误率会飙升。这是 Buro 论文里的经验阈值，实践中 4~6 之间都有人用，深度越大裁决越可靠。
六、主程序与实测
package com.example.othello;
public class Main {
public static void main(String[] args) {
// 标准开局：黑在 d4(27), e5(28)；白在 e4(36), d5(35)
Board start = new Board(0x0000000810000000L, 0x0000001008000000L);
ProbCutSearch ai = new ProbCutSearch();
long t0 = System.nanoTime();
int bestMove = -1, bestVal = -1000000;
for (long m = start.legalMoves(1); m != 0; m &= m - 1) {
int p = Long.numberOfTrailingZeros(m);
Board nb = start.play(1L << p, 1);
int v = -ai.search(nb, 8, -1000000, 1000000, -1);
if (v > bestVal) { bestVal = v; bestMove = p; }
}
long t1 = System.nanoTime();
System.out.printf("最佳着法 = %c%d, 估值 = %d%n",
(char) ('A' + bestMove % 8), 8 - bestMove / 8, bestVal);
System.out.printf("搜索节点 = %d, 耗时 = %.2f s%n", ai.nodes, (t1 - t0) / 1e9);
System.out.printf("ProbCut 成功剪枝 = %d 次 (%.1f%%)%n",
ai.probCutSuccess, 100.0 * ai.probCutSuccess / ai.nodes);
}
}
在 depth=8、i7-8700 上的典型结果：
最佳着法 = C4, 估值 = 8
搜索节点 = 41200, 耗时 = 0.19 s
ProbCut 成功剪枝 = 9130 次 (22.2%)
关掉 ProbCut（把 depth >= 5 改成 depth >= 99）后同一着法的节点数会涨到 11 万左右、耗时 0.5 s。约 2.7 倍的加速，换来的是极小概率（< 1%）的剪枝误判。这个性价比在全世界的棋类 AI 里都算优秀。
七、复杂度分析与参数调优
时间复杂度。Alpha-Beta 在完美着法排序下是 O(b^(d/2))，黑白棋 b≈10、d=8 时理论下界约 10^4 个节点。ProbCut 进一步把有效深度打折：因为它在 d-2 层就做了裁决，等效地把”需要全宽搜索的层数”减少了约 2 层，实测加速比通常在 2~3 倍，与本文数据吻合。
空间复杂度。位棋盘表示让盘面只占 16 字节，递归深度 = 搜索深度（本文 8~12），栈空间可忽略。置换表按 2^20 项、每项 16 字节约占 16 MB。
参数调优的经验值：
| 参数 | 推荐范围 | 说明 |
|---|---|---|
| A | 1.10 ~ 1.20 | 越小越激进（容易剪到真棋） |
| B | -8 ~ -6 | 与深度差的”层数惩罚”相关 |
| SIGMA | 1.0 ~ 1.8 | 关键安全旋钮，越大越保守 |
| 启用深度 | 4 ~ 6 | 低于 4 层噪声太大 |
SIGMA 是唯一必须实测的参数。调优方法：跑 500 局自对弈，统计”ProbCut 判定为 ≥ β 而深层实际 < β”的比例，目标是控制在 0.5%~1%。超过这个比例就该调大 SIGMA。
三个容易踩的坑：
- 跳过回合不消耗深度。如前所述，若把”跳过”当成正常一层递减，深度预算会被白吃，同等时间下搜索深度实际少 1~2 层。
play必须返回新盘面。ProbCut 大量依赖”回溯后原盘面不变”，如果原地修改盘面，剪枝路径上的状态污染会导致结果完全不可预测。- 着法排序的浅层搜索不能计入节点统计用于剪枝判定。排序用的浅层搜索本身会产生大量节点，如果这些节点也参与 ProbCut 的成功率统计，会让加速比虚高、掩盖真实的失效率。
八、ProbCut 的普适意义
ProbCut 看起来是”黑白棋专属技巧”，但它的思想——用便宜的浅层搜索做统计预测，替代昂贵的精确搜索——已经越界到很多领域：
- 国际象棋引擎：ProbCut 是 Crafty、Fruit 等引擎的标配，配合多级 ProbCut（Multi-ProbCut）进一步提速；
- 围棋 MCTS：AlphaGo 的”快速走子策略（rollout policy）”本质上是同一思路的低保真版本——用一个廉价策略预测节点的胜率；
- 超参数搜索：Hyperband 用”低保真训练 + 逐轮淘汰”（successive halving）来省算力，这是 ProbCut 在机器学习里的镜像；
- 数据库查询优化：用采样估算基数（cardinality estimation）来决定是否执行昂贵的精确计划，同样是”廉价估计替代昂贵精确”。
共同前提只有一个：存在一个与目标高度相关、成本低得多的代理指标。当这个前提成立时，”先粗后精”几乎总是赢过”一路精算”。
黑白棋之所以是理解这套思想的最佳载体，是因为它的分支因子适中（可以人工推演）、评估函数有明显的阶段切换（能亲眼看到 ProbCut 在中盘和残局表现不同），而且有公开的强引擎（Edax）作为对照基准。如果你想继续深入，下一步值得做的是：给置换表加 Zobrist 哈希、把评估函数换成”学习得到的权重向量”（用逻辑回归在百万局自对弈数据上拟合），以及实现 Multi-ProbCut 里的”多级阈值”版本。
