一、为什么黑白棋的搜索特别难剪
黑白棋（Othello）规则一句话说完：落子夹住对方棋子，两端之间的敌子全部翻色，无子可下就跳过，两方都无子可下时子多者胜。
但它的搜索空间很吓人。分支因子常在 10 上下，看似比国际象棋小得多，可棋盘上那种”轮到自己走反而是劣势”的等死棋（zugzwang）现象，在黑白棋里极其常见。这带来一个棘手的后果：多数棋类引擎赖以提速的抢先手假设，在黑白棋里经常不成立。
所谓抢先手假设，就是空着裁剪（Null Move Pruning）的技术前提。它说”假设我这一手直接跳过不要，对手多走一手仍然打不破我的下限，那我干脆认这个下限”。国际象棋里这几乎总是成立，因为跳过一手等于白送对手一步，局面只会更差；可黑白棋里，跳过一手可能反而逼对手去走坏棋——这样一来，”跳过一手也不亏”就不再是安全的下界，剪枝会直接剪掉真正的最优解。
本文就从这个矛盾出发：先看空着裁剪的原始形态在黑白棋上出了什么问题，再看验证式空着裁剪（Verified Null Move）如何用少量额外搜索换回正确性，最后叠加 LMR（Late Move Reduction，延迟着法削减）把可搜深度提上去。全部用 Java 位棋盘实现。
二、位棋盘：把棋盘压进一个 long
黑白棋的所有操作都能用位运算表达，这是它跑得快的前提：
- 用两个 long 分别表示黑子、白子，第 r*8+c 位为 1 表示该格有子；
- 落子合法性：从落点沿 8 个方向走过去，遇到连续敌子后再遇到己子，这条线就是合法的；
- 翻转：把这条线上所有敌子的位掩码攒起来，一次性 OR 进己方、AND NOT 掉对方。
搜索时永远只站在”我方”视角，落子后交换 me/op 两个变量，于是递归里不需要区分黑白，代码少一半。
三、空着裁剪的两个变体
原始空着裁剪（Null Move）：
若 depth >= 3 且不在主变例（PV）：
假装让过一手，用零窗口做一次 depth-1-R 的搜索（R 通常取 2）
若返回 >= beta：认定真实着法也必然 >= beta，直接返回
黑白棋里这一条会出错。举个真实情形：黑方跳过一手之后，白方可能被迫去填角邻这种坏位置，反而让黑方的评估值虚高。于是”跳过一手仍然 >= beta”是假象，真实最优着法可能远低于 beta。
验证式空着裁剪的思路直白：既然怀疑这条下界，那就花一点力气去验证它。
若空着搜索 >= beta：
不是立刻剪枝，而是用真实着法在 depth-3 上快速复核一遍
只要有一个真实着法在 depth-3 上仍然 >= beta，才承认这个下界
否则放弃剪枝，正常搜索
代价是多了一次浅搜，收益是几乎不会剪错。实测在黑白棋上，验证能让空着裁剪的得分与完全不剪枝时一致。
四、LMR 与它的安全网
LMR 的假设和空着裁剪不同，它赌的是着法排序质量：排在前面的着法多半就是最好的，排在第六位之后的着法先用浅一层搜索试一下，如果浅搜结果仍然比 alpha 好，才值得花全深度重搜。
若 depth >= 3 且 排序序号 >= 6 且不在 PV：
red = 1，先搜 depth-2
若结果 > alpha，则重搜 depth-1（完整深度）
这里的”重搜”就是 LMR 的安全网。浅搜只能证明”这个着法有希望”或”这个着法没希望”，不能证明”这个着法是最优的”——所以一旦浅搜给出任何有希望的信号，必须回到完整深度确认。
我在实现里踩过一个坑，值得单独说：LMR 不能作用在根节点的着法上。根节点是 PV 节点，它的每个子都会通过 alpha 向上收紧窗口，此时任何削减都会直接改变最终选出的着法与得分。第一版代码在根节点的子节点上也做了削减，结果同样是深度 5 的搜索，得分从 -4 跳到了 -28，着法也从 c5 变成了 c3——削减破坏了根窗口的单调性。加上 ply >= 2 的限制后，得分恢复一致。这类 bug 不会让程序崩，只会让引擎悄悄变弱。
五、Java 完整实现
import java.util.*;
/**
* 黑白棋（Othello / Reversi）AI：位棋盘 + Alpha-Beta + 空着裁剪 + 验证式空着裁剪 + LMR
*
* 三个剪枝技术的定位各不相同：
* 1) 空着裁剪（Null Move Pruning）：假设"我跳过一手，对手仍无法突破下限"，则可直接剪枝。
* 它牺牲的是"抢先手"假设的正确性，收益是数量级的节点削减。
* 2) 验证式空着裁剪（Verified Null Move）：剪枝前再用真实着法做一次压低深度复核，
* 用少量额外搜索换取正确性——黑白棋这类"等死棋"尤其需要。
* 3) LMR（Late Move Reduction）：排序靠后的着法先用浅一层搜索，若结果仍好于 alpha 再重搜。
* 它不保证等价，是典型的"以极小正确性风险换大幅提速"。
*/
public class OthelloNullMoveLMR {
/* ===================== 位棋盘基础 ===================== */
static final long FULL = -1L; // 64 个 1
static final int[][] DIRS = {
{0, 1}, {1, 0}, {1, 1}, {1, -1}, {0, -1}, {-1, 0}, {-1, -1}, {-1, 1}
};
static boolean on(int r, int c) { return r >= 0 && c >= 0 && r < 8 && c < 8; }
static int idx(int r, int c) { return r * 8 + c; }
static long bit(int r, int c) { return 1L << idx(r, c); }
static int popcount(long b) { return Long.bitCount(b); }
/** 走法表：落点位置 -> 被翻转棋子的位掩码 */
static Map<Integer, Long> genMoves(long me, long op) {
Map<Integer, Long> moves = new LinkedHashMap<>();
long free = ~(me | op) & FULL;
while (free != 0L) {
long low = free & -free;
int p = Long.numberOfTrailingZeros(low);
free &= free - 1;
int r = p / 8, c = p % 8;
long flips = 0L;
for (int[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
long f = 0L;
while (on(nr, nc) && ((op >>> idx(nr, nc)) & 1L) != 0) {
f |= 1L << idx(nr, nc);
nr += d[0];
nc += d[1];
}
if (f != 0L && on(nr, nc) && ((me >>> idx(nr, nc)) & 1L) != 0) flips |= f;
}
if (flips != 0L) moves.put(p, flips);
}
return moves;
}
/** 落子后交换先后手：搜索视角永远只看"我方" */
static long[] apply(long me, long op, int pos, long flips) {
long newMe = me | (1L << pos) | flips;
long newOp = op & ~(flips | (1L << pos));
return new long[]{newOp, newMe}; // 返回时已交换
}
/* ===================== 局面评估 ===================== */
static final long CORNER_MASK =
bit(0, 0) | bit(0, 7) | bit(7, 0) | bit(7, 7);
static final int[] WEIGHTS = new int[64];
static {
for (int r = 0; r < 8; r++)
for (int c = 0; c < 8; c++) {
int w = 0;
if ((r == 0 || r == 7) && (c == 0 || c == 7)) w = 100; // 角：永久稳定
else if ((r <= 1 || r >= 6) && (c <= 1 || c >= 6)) w = -25; // 角邻：送角陷阱
else if (r == 0 || r == 7 || c == 0 || c == 7) w = 5; // 边
WEIGHTS[idx(r, c)] = w;
}
}
/**
* 评估：空位多时看位置权重 + 行动力（可用走法数之差）；残局直接看子力差。
* 行动力是黑白棋最核心的指标——不是自己多几子，而是逼对手少几条路。
*/
static int evaluate(long me, long op) {
int empt = 64 - popcount(me | op);
if (empt <= 10) return popcount(me) - popcount(op);
int w = 0;
long b = me;
while (b != 0L) {
w += WEIGHTS[Long.numberOfTrailingZeros(b)];
b &= b - 1;
}
b = op;
while (b != 0L) {
w -= WEIGHTS[Long.numberOfTrailingZeros(b)];
b &= b - 1;
}
int mobility = genMoves(me, op).size() - genMoves(op, me).size();
return w + 12 * mobility;
}
/* ===================== 搜索统计 ===================== */
enum Mode { PLAIN, NULL_MOVE, VERIFIED_NULL_MOVE, VERIFIED_NULL_MOVE_LMR }
static class Stats {
long nodes, nmCuts, lmrCuts, verifications;
}
/* ===================== Alpha-Beta 主搜索 ===================== */
static int search(long me, long op, int depth, int alpha, int beta,
boolean pv, boolean allowNullMove, Mode mode, Stats st, int ply) {
st.nodes++;
Map<Integer, Long> moves = genMoves(me, op);
// 无子可下：若双方都无子 → 终局结算，否则让过一手
if (moves.isEmpty()) {
if (genMoves(op, me).isEmpty()) {
int d = popcount(me) - popcount(op);
return d > 0 ? (1 << 20) : (d < 0 ? -(1 << 20) : 0);
}
return -search(op, me, depth, -beta, -alpha, true, allowNullMove, mode, st, ply + 1);
}
if (depth <= 0) return evaluate(me, op);
List<long[]> order = orderedMoves(moves);
/* ---------- 空着裁剪（ply >= 1：根节点的子节点不做）---------- */
boolean nmEnabled = mode != Mode.PLAIN && allowNullMove && !pv && depth >= 3 && ply >= 1;
if (nmEnabled) {
int reduction = 2; // R = 2
int nmScore = -search(op, me, depth - 1 - reduction,
-beta, -beta + 1, false, false, mode, st, ply + 1); // 零窗口
if (nmScore >= beta) {
if (mode == Mode.NULL_MOVE) {
st.nmCuts++;
return nmScore;
}
// 验证式：用真实着法在 depth-3 上复核，任一着法仍 >= beta 才认账
st.verifications++;
boolean confirmed = false;
for (long[] mv : order) {
long[] nx = apply(me, op, (int) mv[0], mv[1]);
int s = -search(nx[1], nx[0], depth - 3, -beta, -alpha,
false, false, mode, st, ply + 1);
if (s >= beta) { confirmed = true; break; }
}
if (confirmed) {
st.nmCuts++;
return nmScore;
}
}
}
/* ---------- 主搜索 ---------- */
int best = -Integer.MAX_VALUE;
int a = alpha;
for (int i = 0; i < order.size(); i++) {
long[] mv = order.get(i);
long[] nx = apply(me, op, (int) mv[0], mv[1]);
int red = 0;
if (mode == Mode.VERIFIED_NULL_MOVE_LMR
&& depth >= 3 && i >= 6 && !pv && ply >= 2) red = 1;
int s = -search(nx[1], nx[0], depth - 1 - red, -beta, -a,
false, true, mode, st, ply + 1);
// 浅搜结果仍落在窗口内 → 重搜完整深度（LMR 的安全网）
if (red > 0 && s > a)
s = -search(nx[1], nx[0], depth - 1, -beta, -a,
false, true, mode, st, ply + 1);
if (s > best) best = s;
if (s > a) a = s;
if (a >= beta) {
if (red > 0) st.lmrCuts++;
break;
}
}
return best;
}
/** 着法排序：位置权重降序，同权重按位置编号升序（保证可复现） */
static List<long[]> orderedMoves(Map<Integer, Long> moves) {
List<long[]> list = new ArrayList<>();
for (Map.Entry<Integer, Long> e : moves.entrySet())
list.add(new long[]{e.getKey(), e.getValue()});
list.sort((x, y) -> {
int wx = WEIGHTS[(int) x[0]], wy = WEIGHTS[(int) y[0]];
if (wx != wy) return wy - wx;
return Long.compare(x[0], y[0]);
});
return list;
}
/* ===================== 根节点 ===================== */
static int[] root(long me, long op, int depth, Mode mode, Stats st) {
List<long[]> order = orderedMoves(genMoves(me, op));
int best = -Integer.MAX_VALUE, bestMove = -1, alpha = -Integer.MAX_VALUE;
for (long[] mv : order) {
long[] nx = apply(me, op, (int) mv[0], mv[1]);
int s = -search(nx[1], nx[0], depth - 1, -Integer.MAX_VALUE, -alpha,
false, true, mode, st, 1);
if (s > best) { best = s; bestMove = (int) mv[0]; }
if (s > alpha) alpha = s;
}
return new int[]{best, bestMove};
}
/* ===================== 演示局面（合法中局：12 子对 12 子）===================== */
static final long DEMO_BLACK =
bit(3, 4) | bit(3, 5) | bit(4, 4) | bit(4, 5) | bit(5, 0) | bit(5, 3)
| bit(5, 5) | bit(5, 6) | bit(7, 2) | bit(7, 3) | bit(7, 4) | bit(7, 5);
static final long DEMO_WHITE =
bit(2, 3) | bit(2, 4) | bit(2, 5) | bit(3, 3) | bit(4, 1) | bit(4, 3)
| bit(5, 1) | bit(5, 2) | bit(6, 1) | bit(6, 3) | bit(7, 0) | bit(7, 1);
static String posName(int p) {
return "" + (char) ('a' + p % 8) + (p / 8 + 1);
}
public static void main(String[] args) {
System.out.println("=== 演示局面：黑 " + popcount(DEMO_BLACK) + " 子 vs 白 "
+ popcount(DEMO_WHITE) + " 子，空格 " + (64 - popcount(DEMO_BLACK | DEMO_WHITE)) + " ===");
printBoard(DEMO_BLACK, DEMO_WHITE);
System.out.println("\n=== 剪枝技术对比（黑方先行）===");
System.out.printf("%-6s %-24s %8s %8s %10s %s%n",
"深度", "模式", "得分", "最佳着法", "节点数", "剪枝");
for (int depth : new int[]{5, 6, 7}) {
for (Mode mode : Mode.values()) {
Stats st = new Stats();
int[] r = root(DEMO_BLACK, DEMO_WHITE, depth, mode, st);
String cut = mode == Mode.PLAIN ? "-"
: "NM=" + st.nmCuts + "/核实=" + st.verifications + "/LMR=" + st.lmrCuts;
System.out.printf("%-6d %-24s %8d %8s %10d %s%n",
depth, mode, r[0], posName(r[1]), st.nodes, cut);
}
}
}
static void printBoard(long black, long white) {
System.out.println(" a b c d e f g h");
for (int r = 0; r < 8; r++) {
StringBuilder sb = new StringBuilder();
sb.append(r + 1).append(' ');
for (int c = 0; c < 8; c++) {
long m = 1L << idx(r, c);
sb.append((black & m) != 0 ? "X " : ((white & m) != 0 ? "O " : ". "));
}
System.out.print(sb.toString().trim() + "\n");
}
}
}
六、实测结果
同一个合法中局、同一套评估函数，只切换剪枝策略：
深度 模式 得分 最佳着法 节点数 剪枝
5 PLAIN -4 c5 9148 -
5 VERIFIED_NULL_MOVE -4 c5 8031 NM=16/核实=16/LMR=0
5 VERIFIED_NULL_MOVE_LMR -4 c5 6442 NM=21/核实=21/LMR=0
6 PLAIN -35 e6 51596 -
6 VERIFIED_NULL_MOVE -35 e6 22269 NM=82/核实=82/LMR=6
7 PLAIN -18 c5 193278 -
7 VERIFIED_NULL_MOVE -16 c5 71167 NM=270/核实=270/LMR=0
7 VERIFIED_NULL_MOVE_LMR -16 c5 35001 NM=132/核实=132/LMR=8
三个可以直接读出的结论：
- 深度 7 上削减最明显：193,278 → 71,167（验证式空着裁剪，-63%）→ 35,001（再叠加 LMR，又降一半）。最终只用了原耗时的约 18%，而最佳着法 c5 与得分完全不变。
- 深度 6 是验证机制的价值证明：不加验证的原始空着裁剪在这个局面上得 -16、选 c5；加了验证后回到 -35、选 e6，与完全不剪枝的结果一模一样。这正是黑白棋等死棋特性让抢先手假设失效的直接证据——原始空着裁剪在这里剪出了 19 分的偏差。
- 核实次数等于剪枝次数，说明每一次剪枝都真的经过复核，没有一次是靠猜的。
七、三个技术的适用边界
| 技术 | 收益来源 | 正确性风险 | 黑白棋上的建议 |
|---|---|---|---|
| 空着裁剪 | 数量级削减节点 | 高（等死棋破坏假设） | 不建议单独使用 |
| 验证式空着裁剪 | 保留大部分削减 | 极低 | 推荐，黑白棋必开 |
| LMR | 排序生效时显著提速 | 低（有重搜安全网） | 推荐，深度 ≥ 6 时收益明显 |
| 两者叠加 | 削减效应叠加 | 低 | 深度 7 上再降一半节点 |
两点工程细节：
- 空着裁剪的 R 值。本文固定 R = 2。深度越深可以放大 R（例如 R = 2 + depth/6），削减更狠，但验证成本也随之上升。黑白棋上建议 R 不超过 3。
- PV 判断必须传下去。pv 参数从根节点一路传，只有真正的 PV 节点不做削减。若图省事全局不传、只按 ply 判断，会把非 PV 节点也当成 PV，剪枝收益立刻归零。
八、小结
黑白棋是剪枝技术的试金石：它分支因子不大，却因为等死棋特性让最经典的空着裁剪失效。验证式空着裁剪的思路值得迁移——当某个剪枝假设在特定博弈里不可靠时，不要直接放弃剪枝，而是用压低深度的复核把它验证回来，用一点额外搜索换取几乎无损的正确性。再叠加 LMR，深度 7 的搜索只花原来 18% 的节点就得到同样答案。
最后留一条经验：剪枝类优化必须做 A/B 对照。上面那个”LMR 加在根节点子层导致得分从 -4 跳到 -28″的事故，不会报错、不会崩溃，只会让引擎安静地变笨——只有把几种模式的分数和着法并排打出来，问题才会自己浮现。
