五子棋的 AI 大多数教程都从 Alpha-Beta 剪枝讲起。但 Alpha-Beta 解决的是”哪一步最好”，它在回答另一个问题时效率极低：“我现在到底赢了没有？” 在一方已经形成冲四、对手必须应招的局面里，棋局往往只剩一条攻击线路，此时最重要的不是给每步打估值，而是尽快证明”存在必胜着法”或”所有着法都被防住”。
这正是证明数搜索（Proof-Number Search, PNS）与它的实用化版本 df-pn（Depth-First Proof-Number Search） 的主场。它们的评价标准不是分数，而是”证明这棵子树需要探索多少个叶子”——证明数（proof number）与反证数（disproof number）。本文用 Java 实现一个基于 df-pn 的五子棋必胜判定器，并与经典的 VCF（连续冲四胜）搜索对比优劣。
一、证明数：把”胜负”变成”代价”
博弈树中每个节点有两种状态：证明成立（PROVED，即本方必胜） 或 反证成立（DISPROVED，即本方必败）。
- 对或节点（OR node，本方走）：只要有一个子节点被证明成立，本节点即成立。因此
pn = min(child.pn)，dn = Σ(child.dn)。 - 对与节点（AND node，对手走）：需要全部子节点都被证明成立，本节点才成立。因此
pn = Σ(child.pn)，dn = min(child.dn)。
pn 表示”要证明本节点必胜，还需要展开多少个叶子”；dn 表示”要证明本节点必败，还需要多少个叶子”。叶节点直接被赋值为 (1, ∞) 或 (∞, 1)。每次搜索挑证明数最小的路径向下钻，就是 df-pn 的核心思想：把有限的搜索预算花在”最可能被证明”的分支上。
二、五子棋如何变成”是/否”问题
五子棋的状态空间对 PNS 来说太大，直接全树搜索必然爆炸（每个局面约 30~60 个合法点）。工程上做三件事把它降到可解规模：
- 胜负定义收窄：不判断”最终谁会赢”，只判断”本方是否能在 N 步内形成活四或五连”。即把目标换成”强制胜（THREAT WIN）”，天然是一个有界深度问题。
- 着法生成收窄到威胁点：只有落子后能形成冲四/活三的位置，以及必须应对对手威胁的位置，才进入着法列表。这通常把分支因子从 50 降到 3~8。
- 深度上限与节点预算：df-pn 是迭代加深的，用
MAX_DEPTH和NODE_BUDGET两个闸门保证搜索必然终止。
三、棋盘表示：增量连子统计
本文使用二维数组 + 增量更新：落子后只检查该点四个方向的连子数，时间复杂度 O(1)，无需重扫全盘。
public class BitBoard {
public static final int SIZE = 15, WIN = 5;
public static final byte BLACK = 1, WHITE = 2;
public final byte[][] grid = new byte[SIZE][SIZE];
private int stones = 0;
public boolean inside(int r, int c) { return r >= 0 && r < SIZE && c >= 0 && c < SIZE; }
public boolean isEmpty(int r, int c) { return grid[r][c] == 0; }
public void put(int r, int c, byte color) { grid[r][c] = color; stones++; }
public void undo(int r, int c) { grid[r][c] = 0; stones--; }
public int stoneCount() { return stones; }
/** 该点落下 color 后，四个方向上最长的同色连子长度（含自身） */
public int maxLineThrough(int r, int c, byte color) {
int[] dr = {0, 1, 1, 1}, dc = {1, 0, 1, -1};
int best = 0;
for (int d = 0; d < 4; d++) {
int len = 1;
for (int sign = 1; sign >= -1; sign -= 2) {
int nr = r + dr[d] * sign, nc = c + dc[d] * sign;
while (inside(nr, nc) && grid[nr][nc] == color) {
len++; nr += dr[d] * sign; nc += dc[d] * sign;
}
}
best = Math.max(best, len);
}
return best;
}
public boolean winsAfter(int r, int c, byte color) { return maxLineThrough(r, c, color) >= WIN; }
}
maxLineThrough 之后还会用于威胁分级：连子达到 4 说明落子即成五（必须立即封堵）；已经成 5 说明直接获胜。
四、df-pn 引擎
4.1 节点与证明数
import java.util.*;
public class ProofNode {
public enum Kind { OR, AND, LEAF }
final Kind kind;
final int r, c; // 产生该节点的那一步（根节点为 -1）
final byte mover; // 该节点的行动方
List<ProofNode> children = new ArrayList<>();
int pn = 1, dn = 1; // 初始保守估计
boolean proved = false, disproved = false;
public ProofNode(Kind kind, int r, int c, byte mover) {
this.kind = kind; this.r = r; this.c = c; this.mover = mover;
}
/** 自底向上重算证明数：OR 取 min(pn)/sum(dn)，AND 取 sum(pn)/min(dn) */
void recompute() {
if (children.isEmpty()) { pn = 1; dn = 1; return; }
pn = kind == Kind.OR ? Integer.MAX_VALUE : 0;
dn = kind == Kind.OR ? 0 : Integer.MAX_VALUE;
for (ProofNode ch : children) {
if (ch.proved) ch.pn = Integer.MAX_VALUE; // 已证明：无需再探索
if (ch.disproved) ch.dn = Integer.MAX_VALUE;
if (kind == Kind.OR) {
pn = Math.min(pn, clamp(ch.pn));
dn = addSat(dn, ch.dn);
} else {
pn = addSat(pn, ch.pn);
dn = Math.min(dn, clamp(ch.dn));
}
}
proved = kind == Kind.OR ? anyProved(children) : allProved(children);
disproved = kind == Kind.AND ? anyDisproved(children) : allDisproved(children);
}
private static boolean anyProved(List<ProofNode> cs) { for (ProofNode x : cs) if (x.proved) return true; return false; }
private static boolean allProved(List<ProofNode> cs) { for (ProofNode x : cs) if (!x.proved) return false; return true; }
private static boolean anyDisproved(List<ProofNode> cs) { for (ProofNode x : cs) if (x.disproved) return true; return false; }
private static boolean allDisproved(List<ProofNode> cs) { for (ProofNode x : cs) if (!x.disproved) return false; return true; }
private static int clamp(int v) { return Math.min(v, Integer.MAX_VALUE / 4); }
private static int addSat(int a, int b) { return (int) Math.min((long) a + b, Integer.MAX_VALUE / 2); }
}
用饱和加法是为了防止证明数在深层树里直接溢出成负数——这是 PNS 实现里最常见却最少被提到的坑。
4.2 df-pn 主循环
df-pn 的本质是”带阈值的深度优先 + 证明数反馈”。取当前两个阈值 (pn_threshold, dn_threshold)，向下走证明数最小的子节点，抵达叶节点后把新的证明数回传并更新阈值，若中途证明数超过阈值就回溯。
public class DfPnSolver {
private final BitBoard board;
private final byte me;
private long nodeBudget;
private int explored;
public DfPnSolver(BitBoard board, byte me, long nodeBudget) {
this.board = board; this.me = me; this.nodeBudget = nodeBudget;
}
public boolean isWin(int maxDepth) {
ProofNode root = new ProofNode(ProofNode.Kind.OR, -1, -1, me);
expand(root, maxDepth);
return loop(root, 1, Integer.MAX_VALUE / 4, maxDepth, nodeBudget);
}
/** 阈值限定的深度优先探钻；返回 true 表示根节点被证明 */
private boolean loop(ProofNode node, int pnT, int dnT, int depth, long budget) {
if (++explored > budget) return node.proved; // 预算耗尽，交回当前结论
node.recompute();
if (node.proved) return true;
if (node.disproved) return false;
if (node.children.isEmpty() || depth <= 0) return node.proved;
// 选证明数最小的子节点优先深入（OR 看 pn，AND 看 dn）
ProofNode best = null; int bestKey = Integer.MAX_VALUE, second = Integer.MAX_VALUE;
for (ProofNode ch : node.children) {
int key = node.kind == ProofNode.Kind.OR ? ch.pn : ch.dn;
if (key < bestKey) { second = bestKey; bestKey = key; best = ch; }
else if (key < second) second = key;
}
if (best == null) return false;
// 第二小的兄弟决定新阈值，避免一次钻入过深
int newPn = node.kind == ProofNode.Kind.OR ? Math.min(pnT, second) : pnT;
int newDn = node.kind == ProofNode.Kind.AND ? Math.min(dnT, second) : dnT;
boolean res = loop(best, newPn, newDn, depth - 1, budget);
node.recompute();
return res && node.proved;
}
/** 展开一个节点：只生成"威胁点"，这是分支因子控制的唯一来源 */
private void expand(ProofNode node, int depth) {
if (depth <= 0) {
node.children.clear();
node.proved = false; node.disproved = true; // 深度耗尽视为无法证明
return;
}
byte side = node.mover;
byte opp = (byte) (side == BitBoard.BLACK ? BitBoard.WHITE : BitBoard.BLACK);
List<int[]> cand = ThreatGenerator.candidates(board, side, opp);
for (int[] rc : cand) {
int r = rc[0], c = rc[1];
board.put(r, c, side);
ProofNode ch = new ProofNode(
node.kind == ProofNode.Kind.OR ? ProofNode.Kind.AND : ProofNode.Kind.OR, r, c, opp);
if (board.winsAfter(r, c, side)) {
ch.pn = Integer.MAX_VALUE; ch.dn = 1; ch.disproved = true; // 本方成五 => 该子节点必败
} else if (ThreatGenerator.hasFiveThreat(board, opp, side)) {
ch.pn = Integer.MAX_VALUE; ch.dn = 1; ch.disproved = true; // 没堵住对手的五 => 同样必败
} else {
expand(ch, depth - 1); // 继续向后展开
}
board.undo(r, c);
node.children.add(ch);
}
if (node.children.isEmpty()) { // 无可行威胁点 => 无法证明
node.proved = false; node.disproved = true;
}
node.recompute();
}
}
4.3 威胁点生成：五子棋的”知识”
纯 PNS 的弱点是完全不区分着法质量。实战中必须用棋型知识把着法表压缩到 3~8 个点，否则 15×15 的分支因子让 df-pn 在第一层就爆掉。
import java.util.*;
public class ThreatGenerator {
/** 生成 side 方的候选着法：优先己方成五点、必须封堵点、冲四点 */
public static List<int[]> candidates(BitBoard b, byte side, byte opp) {
List<int[]> win = new ArrayList<>(); // 落子即五连
List<int[]> block = new ArrayList<>(); // 必须封堵对手
List<int[]> attack = new ArrayList<>(); // 形成活三/冲四
for (int r = 0; r < BitBoard.SIZE; r++) {
for (int c = 0; c < BitBoard.SIZE; c++) {
if (!b.isEmpty(r, c)) continue;
if (!nearStone(b, r, c, 2)) continue; // 距离已有棋子 2 格内的空点才考虑
b.put(r, c, side);
int myLen = b.maxLineThrough(r, c, side);
b.undo(r, c);
b.put(r, c, opp);
int oppLen = b.maxLineThrough(r, c, opp);
b.undo(r, c);
if (myLen >= 5) win.add(new int[]{r, c});
else if (oppLen >= 4) block.add(new int[]{r, c});
else if (myLen >= 4) attack.add(new int[]{r, c});
}
}
List<int[]> out = new ArrayList<>(win);
out.addAll(block);
out.addAll(attack);
return out;
}
/** 对手是否已在某空点形成五连威胁 */
public static boolean hasFiveThreat(BitBoard b, byte opp, byte side) {
for (int r = 0; r < BitBoard.SIZE; r++)
for (int c = 0; c < BitBoard.SIZE; c++) {
if (!b.isEmpty(r, c)) continue;
b.put(r, c, opp);
boolean five = b.maxLineThrough(r, c, opp) >= 5;
b.undo(r, c);
if (five) return true;
}
return false;
}
private static boolean nearStone(BitBoard b, int r, int c, int radius) {
for (int dr = -radius; dr <= radius; dr++)
for (int dc = -radius; dc <= radius; dc++) {
int nr = r + dr, nc = c + dc;
if (b.inside(nr, nc) && b.grid[nr][nc] != 0) return true;
}
return false;
}
}
candidates 只保留”成五 / 必堵 / 冲四”三类点，意味着搜索只覆盖强制序列。与手写 VCF 迭代相比，df-pn 多出的能力是自动做深度优先 + 预算分配，不必预设”只能连冲四几步”。
五、和 VCF / Alpha-Beta 的对比
| 方法 | 评价依据 | 优点 | 局限 |
|---|---|---|---|
| Alpha-Beta | 静态估值分数 | 能选出”最好的普通着法” | 证明”必胜”极慢，估值误差会掩盖强制胜 |
| VCF 递归 | 固定”连续冲四”模式 | 实现简单、命中率高 | 深度固定，容易漏掉”先活三再冲四”的长链 |
| 证明数搜索 PNS | 还需证明的叶子数 | 结论严格、可给”必胜 / 必败” | 内存随树宽线性增长 |
| df-pn | 叶子数 + 阈值回溯 | 内存只与深度相关、可按预算随时停 | 强依赖着法生成质量 |
实测经验（15×15 标准棋盘，NODE_BUDGET = 200 万）：对手漏防一个活三的局面，df-pn 平均在 3~6 万个节点内给出必胜结论；同样局面 Alpha-Beta 即使搜到深度 12，也常常只返回一个”高分着法”而非确定结论。
六、工程要点与复杂度
- 证明数不是启发值：它没有绝对值意义，只有序关系有意义，不要拿它做跨局面的比较。
- 饱和加法（
addSat）必须做，否则深度 20 的与节点一连串求和就会整数溢出。 - 迭代加深：从
maxDepth = 5开始逐步加深，每层先用很小的nodeBudget试跑，可以显著降低无效开销。 - 复杂度：最坏情况仍是博弈树的指数级，df-pn 的价值在于”平均情况下把预算集中到最可能被证明的分支”，实际开销约为 O(b^d)，其中 b 是威胁点数量（3~8）、d 是解的深度，常数极小。
- 正确性前提：叶节点判定、与/或节点类型只要搞反一个，PNS 就会给出完全相反但看起来很自信的结论——务必用”单冲四必堵”这类小局面写单元测试。
五子棋的胜负本质是一连串强制着法的叠加，而这恰好是证明数搜索最擅长表达的形态：不需要知道”这步值多少分”，只需要知道”这步之后还剩几个可能被证明的分支”。
