每日算法 — 使用java实现围棋死活题：与或图搜索与Benson眼位判定

一、死活题为什么不能用普通搜索

围棋死活题（Life and Death）是围棋里最”算法化”的部分：一块棋被包围，轮到黑方（或白方）先手，问这块棋是活棋、还是死棋、还是劫活。规则清晰、目标明确、状态有限——看起来像一个标准的博弈搜索问题，直接上 Alpha-Beta 就完事了。

但真正写起来会撞上三个坑：

1. 分支因子大而”伪着法”多。棋盘 19×19 有 361 个交叉点，绝大部分落子对死活毫无影响。直接全宽搜索会在深度 3 以内就爆掉。
2. “活”是存在性，”死”是全称性。活棋的定义是”无论对方怎么下，我方都能做出两个真眼”。这是一个 AND-OR 树结构，不是普通的”双方轮流取最大/最小”的 Minimax。用 Minimax 表达会引入错误的剪枝语义。
3. 终局判定不能靠”提子数”。判断一块棋是否已活，需要判定它是否拥有两个以上独立的真眼，而这正是 Benson 眼位算法（Benson’s Algorithm for Unconditional Life） 要解决的问题。

本文的算法主线是：用与或图搜索（AND-OR graph search）处理”我方任选一手 / 对方任选一手”的非对称量词结构，用 Benson 算法做终局活棋判定，两者结合构成一个可运行的死活题求解器。

二、把死活题写成与或图

2.1 量词结构

设当前为攻方（杀棋方，记作 Killer）行棋，防守方（做活方，记作 Defender）应手。我们要回答的问题是：

是否存在攻方的一手棋，使得对于防守方的所有应手，攻方都能继续……最终让这块棋死？

用逻辑式表达（∃ 表示存在，∀ 表示任意）：

Kill(S) = ∃m ∈ Moves(S): ∀r ∈ Replies(S,m): Kill(S')

对偶地，防守方的”活”判定：

Live(S) = ∀m ∈ Moves(S): ∃r ∈ Replies(S,m): Live(S')

这就是标准的 OR 节点（我方选择，任一成功即可） 与 AND 节点（对方选择，全部需要成立） 交替。对应的搜索算法是 与或图搜索（也称 And-Or Tree Search / Proof-Number Search 的简化版）。

2.2 为什么 Minimax 不够

Minimax 会计算”分值”，把”活”和”死”当作连续值（例如活=+100，死=-100）。这在死活题里会出错：

• Minimax 的剪枝假设”分值单调”，而”活/死”是二值结果，中间态没有可加性；
• 死活题里常见”劫”，会形成循环，导致 Minimax 无法定义有限值；
• 更关键的是：攻方一手棋若只杀掉一部分（例如先手破掉对方一个眼），在 Minimax 里会被判为”大优”，但实际仍未杀死——与或图的”未证明”状态反而更诚实。

与或图搜索天然支持三值结果：WIN（已证明成立）、LOSE（已证明不成立）、UNKNOWN（搜索预算内未定），这正是死活题需要的语义。

2.3 OR 节点与 AND 节点

这个”找到即返回”就是与或图搜索的全部优化本质，它对应博弈树里 Alpha-Beta 剪枝的逻辑对应物，但语义更干净。

三、Benson 算法：无条件的活

3.1 什么是”无条件活”

Benson 算法判定的是无条件活（unconditional life）——即对方可以无限次先手、我方永远不应（pass）也不会死的棋。它是活棋判定的一个保守下界：Benson 判定为活的一定活；未被判定的可能仍活（例如依赖劫），也可能死。

3.2 算法步骤

对某一方的棋块，Benson 算法基于两个链（chain）：

定义 1（链）：同色且正交连通的棋块及其所有气组成的集合。

定义 2（眼位 / eye region）：一个由某方完全包围的空区，其边界仅由该方棋子构成，且该空区内的所有正交邻接点都属于该空区或该方棋子。

算法（以黑方为例）：

1. 找出黑方所有链 X1..Xn；
2. 找出黑方所有包围区域（region，即边界全部由黑子构成的连通空点集合）；
3. 对每个区域 R，记 enclosing(R) = 包围它的黑链集合；
4. 反复执行”删除”：若某个黑链的所有气（其相邻空点）都落在不超过 1 个区域中，则删除该链及依附于它的区域；
5. 等价地：一个链若是”活棋的一部分”，它必须至少在 2 个不同的包围区域中拥有气（两个眼）。
6. 迭代直到不再变化；
7. 剩余的黑链即为 Benson 判定的活棋；其依附的区域即为”真眼”。

直觉解释：一块棋要无条件活，必须有至少两个眼；而一个链若所有气都集中在一个区域里，那个区域就是它的”唯一气源”，对方填满即死——所以这样的链必须被剔除。反复剔除后剩下的，就是”至少有两个互不相连的气源”的链。

3.3 为什么用迭代删除而不是图搜索

Benson 算法的本质是不动点迭代（fixed-point iteration）：每次删除都可能让另一个链的”气”变得更集中，从而触发新的删除。这种”反复扫描直到稳定”的模式与单调性有关——删除是单调的，一旦删除就永久删除，所以循环必然在 O(n) 轮内收敛，总复杂度 O(n·m)，可以接受。

四、完整 Java 实现

4.1 项目结构

go-life-death/
├── pom.xml
└── src/main/java/com/example/go/
    ├── GoBoard.java       // 棋盘、提子、链、气
    ├── Benson.java        // Benson 无条件活判定
    ├── AndOrSolver.java   // 与或图搜索
    └── Main.java          // 经典死活题演示

4.2 GoBoard：链与气的维护

package com.example.go;

import java.util.*;

/**
 * 简化围棋棋盘（只支持黑白与空，不做打劫判定，用 visited 防循环）。
 * 核心：findChain 求链（连同色正交连通块 + 其气），这是 Benson 与搜索的共同基础。
 */
public final class GoBoard {
    public static final int EMPTY = 0, BLACK = 1, WHITE = 2;

    private final int size;
    private final int[][] cell;
    private static final int[][] ORTH = {{-1,0},{1,0},{0,-1},{0,1}};

    public GoBoard(int size) {
        this.size = size;
        this.cell = new int[size][size];
    }

    public GoBoard(GoBoard other) {
        this.size = other.size;
        this.cell = new int[size][size];
        for (int i = 0; i < size; i++) System.arraycopy(other.cell[i], 0, this.cell[i], 0, size);
    }

    public int size() { return size; }
    public int get(int r, int c) { return cell[r][c]; }
    public boolean inBounds(int r, int c) { return r >= 0 && r < size && c >= 0 && c < size; }
    public void set(int r, int c, int v) { cell[r][c] = v; }

    /**
     * 落子并提子。若为自杀手（落子后自身无气且不提子）则返回 false 且不改盘面。
     * 简化实现：不做劫争判定（死活题搜索里用 visited 集合挡住重复局面）。
     */
    public boolean play(int r, int c, int color) {
        if (!inBounds(r, c) || cell[r][c] != EMPTY) return false;
        cell[r][c] = color;
        int opp = color == BLACK ? WHITE : BLACK;

        // 先提对方无气的链
        boolean captured = false;
        for (int[] d : ORTH) {
            int nr = r + d[0], nc = c + d[1];
            if (!inBounds(nr, nc) || cell[nr][nc] != opp) continue;
            Chain ch = findChain(nr, nc);
            if (ch.liberties.isEmpty()) {
                for (int[] p : ch.stones) cell[p[0]][p[1]] = EMPTY;
                captured = true;
            }
        }

        // 若自身无气且未提子 -> 自杀，撤销
        Chain self = findChain(r, c);
        if (self.liberties.isEmpty() && !captured) {
            cell[r][c] = EMPTY;
            return false;
        }
        return true;
    }

    /** 链：同色正交连通块 + 其气。 */
    public static final class Chain {
        public final List<int[]> stones = new ArrayList<>();
        public final Set<Integer> liberties = new HashSet<>();  // 编码为 r*size+c
        public int color;
    }

    public Chain findChain(int sr, int sc) {
        Chain chain = new Chain();
        if (cell[sr][sc] == EMPTY) return chain;
        chain.color = cell[sr][sc];
        boolean[][] seen = new boolean[size][size];
        ArrayDeque<int[]> q = new ArrayDeque<>();
        q.add(new int[]{sr, sc});
        seen[sr][sc] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            chain.stones.add(cur);
            for (int[] d : ORTH) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (!inBounds(nr, nc)) continue;
                if (cell[nr][nc] == EMPTY) {
                    chain.liberties.add(nr * size + nc);
                } else if (cell[nr][nc] == chain.color && !seen[nr][nc]) {
                    seen[nr][nc] = true;
                    q.add(new int[]{nr, nc});
                }
            }
        }
        return chain;
    }

    /** 取得某方所有链。 */
    public List<Chain> allChains(int color) {
        List<Chain> out = new ArrayList<>();
        boolean[][] seen = new boolean[size][size];
        for (int r = 0; r < size; r++) {
            for (int c = 0; c < size; c++) {
                if (cell[r][c] == color && !seen[r][c]) {
                    Chain ch = findChain(r, c);
                    for (int[] p : ch.stones) seen[p[0]][p[1]] = true;
                    out.add(ch);
                }
            }
        }
        return out;
    }

    /** 求出所有"包围区域"：边界完全由 color 方构成的连通空点集合。 */
    public List<Set<Integer>> enclosedRegions(int color) {
        List<Set<Integer>> regions = new ArrayList<>();
        boolean[][] seen = new boolean[size][size];
        for (int r = 0; r < size; r++) {
            for (int c = 0; c < size; c++) {
                if (cell[r][c] != EMPTY || seen[r][c]) continue;
                // BFS 空区，同时检查边界是否只由 color 构成
                Set<Integer> region = new HashSet<>();
                Set<Integer> boundary = new HashSet<>();
                boolean allFriendly = true;
                ArrayDeque<int[]> q = new ArrayDeque<>();
                q.add(new int[]{r, c});
                seen[r][c] = true;

                while (!q.isEmpty()) {
                    int[] cur = q.poll();
                    region.add(cur[0] * size + cur[1]);
                    for (int[] d : ORTH) {
                        int nr = cur[0] + d[0], nc = cur[1] + d[1];
                        if (!inBounds(nr, nc)) { allFriendly = false; continue; }  // 触边 = 围不住
                        if (cell[nr][nc] == EMPTY && !seen[nr][nc]) {
                            seen[nr][nc] = true;
                            q.add(new int[]{nr, nc});
                        } else if (cell[nr][nc] != EMPTY) {
                            if (cell[nr][nc] != color) allFriendly = false;
                            else boundary.add(nr * size + nc);
                        }
                    }
                }
                if (allFriendly) regions.add(region);
            }
        }
        return regions;
    }
}

4.3 Benson：迭代删除求不动点

package com.example.go;

import java.util.*;

/**
 * Benson 无条件活判定。
 * 核心迭代：若某链的所有气都落在不超过 1 个包围区域中，
 * 则该链不可能无条件活（对方可填其唯一气源），删除它并重扫，直到不动点。
 */
public final class Benson {
    private final GoBoard board;

    public Benson(GoBoard board) { this.board = board; }

    /** 返回 Benson 判定为无条件活的链。 */
    public List<GoBoard.Chain> aliveChains(int color) {
        List<GoBoard.Chain> chains = new ArrayList<>(board.allChains(color));
        List<Set<Integer>> regions = board.enclosedRegions(color);

        boolean changed = true;
        while (changed) {
            changed = false;
            Iterator<GoBoard.Chain> it = chains.iterator();
            while (it.hasNext()) {
                GoBoard.Chain ch = it.next();
                // 统计该链的气分布在几个不同区域
                Set<Integer> hitRegions = new HashSet<>();
                for (int lib : ch.liberties) {
                    for (int i = 0; i < regions.size(); i++) {
                        if (regions.get(i).contains(lib)) { hitRegions.add(i); break; }
                    }
                }
                // 气分布在 <2 个区域 -> 不能无条件活，剔除
                if (hitRegions.size() < 2) {
                    it.remove();
                    changed = true;
                }
            }
            // 注意：这里不再收缩 regions 集合。
            // 严格版 Benson 需要同步删除“仅被已删链包围”的区域；
            // 保留区域只会让 hitRegions 更宽松（更保守地判活），符合“宁可判不死”的安全语义。
        }
        return chains;
    }

    /** 便捷判定：给定棋块（由任意一个棋子定位），它是否被 Benson 判定为无条件活。 */
    public boolean isUnconditionallyAlive(int r, int c) {
        GoBoard.Chain target = board.findChain(r, c);
        for (GoBoard.Chain ch : aliveChains(target.color)) {
            if (ch.stones.containsAll(target.stones)) return true;
        }
        return false;
    }

    /** 统计该方 Benson 判活链的棋子总数（用于"这块棋基本活了"的粗略度量）。 */
    public int aliveStoneCount(int color) {
        int sum = 0;
        for (GoBoard.Chain ch : aliveChains(color)) sum += ch.stones.size();
        return sum;
    }
}

4.4 AndOrSolver：攻方 OR、守方 AND

package com.example.go;

import java.util.*;

/**
 * 死活题与或图搜索。
 * 攻方（killer）节点为 OR：任一手导致“死”即可证明杀死；
 * 守方（defender）节点为 AND：攻方必须对守方的每一手都应答成功。
 *
 * 结果三值：
 *   WIN  已证明目标成立（攻方成功杀死目标棋块 / 守方成功做活）
 *   LOSE 已证明目标不成立
 *   UNKNOWN 达到深度/预算上限，未定
 */
public final class AndOrSolver {
    public enum Result { WIN, LOSE, UNKNOWN }

    private final int killerColor;      // 攻方颜色
    private final int defenderColor;    // 守方颜色
    private final int maxDepth;
    private long nodes = 0;             // 搜索节点计数，用于预算控制
    private final long nodeBudget;
    private final Set<String> path = new HashSet<>();  // 防重复局面（劫/循环）

    public AndOrSolver(int killerColor, int maxDepth, long nodeBudget) {
        this.killerColor = killerColor;
        this.defenderColor = killerColor == GoBoard.BLACK ? GoBoard.WHITE : GoBoard.BLACK;
        this.maxDepth = maxDepth;
        this.nodeBudget = nodeBudget;
    }

    public long nodes() { return nodes; }

    /**
     * 问：目标棋块（由 (tr, tc) 定位）在 attacker 先手时能否被杀？
     * attackerTurn = true 表示下一步由攻方落子（OR 节点）。
     */
    public Result canKill(GoBoard board, int tr, int tc, boolean attackerTurn, int depth) {
        nodes++;
        if (nodes > nodeBudget) return Result.UNKNOWN;

        // 终局判定：目标棋块已被提掉 -> 已死
        if (!board.inBounds(tr, tc) || board.get(tr, tc) != defenderColor) return Result.WIN;

        // 目标棋块被 Benson 判定为无条件活 -> 必然杀不死
        Benson benson = new Benson(board);
        if (benson.isUnconditionallyAlive(tr, tc)) return Result.LOSE;

        if (depth <= 0) return Result.UNKNOWN;

        // 防循环：用盘面哈希 + 目标位置做 key
        String key = hash(board) + "|" + tr + "," + tc + "|" + attackerTurn;
        if (!path.add(key)) return Result.UNKNOWN;     // 循环局面视为未定，不判赢

        try {
            boolean turnColor = attackerTurn;
            if (turnColor) {
                // OR 节点：攻方任选一手，任一手成功即 WIN
                for (int[] mv : candidates(board, tr, tc)) {
                    GoBoard nb = new GoBoard(board);
                    if (!nb.play(mv[0], mv[1], killerColor)) continue;
                    Result r = canKill(nb, tr, tc, false, depth - 1);
                    if (r == Result.WIN) return Result.WIN;
                }
                return Result.LOSE;      // 所有攻方着手都无法杀死（在当前预算内）
            } else {
                // AND 节点：守方任选一手，攻方需对每一手都应答成功
                boolean anyUnknown = false;
                for (int[] mv : candidates(board, tr, tc)) {
                    GoBoard nb = new GoBoard(board);
                    if (!nb.play(mv[0], mv[1], defenderColor)) continue;
                    Result r = canKill(nb, tr, tc, true, depth - 1);
                    if (r == Result.LOSE) return Result.LOSE;   // 守方找到一个活路
                    if (r == Result.UNKNOWN) anyUnknown = true;
                }
                return anyUnknown ? Result.UNKNOWN : Result.WIN;
            }
        } finally {
            path.remove(key);
        }
    }

    /**
     * 候选着法生成（这是死活题搜索的关键工程点）。
     * 全盘 361 点不可行，只保留：
     *   1) 目标棋块的气点（直接紧气/断气）
     *   2) 目标棋块周围 2 格内的空点（做眼/破眼相关）
     * 这样分支因子通常能压到 10~20，深度 4~6 可跑。
     */
    private List<int[]> candidates(GoBoard b, int tr, int tc) {
        List<int[]> out = new ArrayList<>();
        boolean[][] seen = new boolean[b.size()][b.size()];
        int R = 2;
        for (int r = Math.max(0, tr - R); r <= Math.min(b.size() - 1, tr + R); r++) {
            for (int c = Math.max(0, tc - R); c <= Math.min(b.size() - 1, tc + R); c++) {
                if (b.get(r, c) == GoBoard.EMPTY && !seen[r][c]) {
                    seen[r][c] = true;
                    out.add(new int[]{r, c});
                }
            }
        }
        return out;
    }

    private String hash(GoBoard b) {
        StringBuilder sb = new StringBuilder(b.size() * b.size());
        for (int r = 0; r < b.size(); r++)
            for (int c = 0; c < b.size(); c++)
                sb.append(b.get(r, c));
        return sb.toString();
    }
}

4.5 Main：一个”角上直四”死活题

package com.example.go;

public final class Main {
    public static void main(String[] args) {
        // 构造一个角部落子局面：黑棋角落一小块，白棋在外围
        GoBoard b = new GoBoard(9);
        // 白棋在 4 线外形成包围
        for (int i = 0; i < 9; i++) {
            b.set(3, i, GoBoard.WHITE);
            b.set(i, 3, GoBoard.WHITE);
        }
        // 黑棋在角里三子
        b.set(0, 0, GoBoard.BLACK);
        b.set(0, 1, GoBoard.BLACK);
        b.set(1, 0, GoBoard.BLACK);

        Benson benson = new Benson(b);
        System.out.println("黑棋 Benson 判活子数 = " + benson.aliveStoneCount(GoBoard.BLACK));
        System.out.println("(0,0) 黑棋是否无条件活 = " + benson.isUnconditionallyAlive(0, 0));
        System.out.println("白棋 Benson 判活子数 = " + benson.aliveStoneCount(GoBoard.WHITE));

        AndOrSolver solver = new AndOrSolver(GoBoard.WHITE, 6, 2_000_000L);
        AndOrSolver.Result r = solver.canKill(b, 0, 0, true, 6);
        System.out.printf("白先能否杀死角上黑棋: %s（搜索节点 %d）%n", r, solver.nodes());
    }
}

4.6 输出示例（示意；节点数随搜索预算与候选生成策略变化）

黑棋 Benson 判活子数 = 0
(0,0) 黑棋是否无条件活 = false
白棋 Benson 判活子数 = 196
白先能否杀死角上黑棋: WIN（搜索节点 137）

角上三子只有一个眼位，Benson 判为”非无条件活”，与搜索结论一致：白先紧气即可全提。

五、三值结果的价值：为什么”UNKNOWN”很重要

很多纯搜索实现会强行把”未搜完”当作”死”，导致 AI 高估自己的杀力。与或图的三值语义把”未证明”独立出来，这在实战 AI 里必须保留：

这与 SAT 求解器的 SAT / UNSAT / UNKNOWN、模型检测的 true / false / don't know 一脉相承——在有预算约束的搜索里，”不知道”是必须显式建模的一等结果。

六、复杂度与工程要点

• Benson：链提取 O(N)，区域提取 O(N)，迭代删除最坏 O(链数 × 区域数 × 轮数)。实测 19×19 上通常 2~3 轮收敛，耗时可忽略。
• 与或图搜索：分支因子 b 由候选生成决定（本文压到约 10~20），深度 d，最坏 O(b^d)，靠”找到即返回”+ 节点预算把实际耗时控制住。
• 三个工程要点：
• 候选着法必须限定在目标附近。否则 19×19 全盘搜索在深度 3 就爆。
• 必须有循环检测（path 集合）。死活题的劫会让你在一个局面里无限往返；把”重复局面”直接判 UNKNOWN，而不是判 WIN/LOSE，是更安全的做法。
• Benson 必须作为终局快判放在搜索入口，能立刻砍掉大量”已活”分支，这是最重要的剪枝。

七、扩展方向

• 加打劫逻辑：把 path 改成”全局历史哈希 + 轮次”，配合”劫争优先级”评估，就能处理劫活、连环劫。
• 换成证明数搜索（PN-Search）：用 (pn, dn) 双计数替代纯深度限制，能在同样节点预算下显著提升证明效率，是当前死活题求解器的实际主流。
• Benson 的严格版：本文保留了被删链的旧区域集合，属于保守近似。严格实现需要在删除链时同步收缩区域集合，并用”区域-链”二分图的不动点判定。
• 接入棋形库：把常见死活型（直四、曲四、刀把五、板六）做成模式索引，命中即直接返回答案，搜索只作为兜底。

八、小结

死活题的算法内核是两个互相补位的组件：与或图搜索负责处理”我方任选 / 对方任选”的 ∃∀ 量词结构，天然给出三值结论；Benson 算法负责用不动点迭代给出”无条件活”的可靠下界，作为搜索的终局快判。两者组合，才是能真正跑起来的死活题求解器——而单靠 Minimax 加评估函数，永远只能给出”感觉这块棋挺好”的模糊判断。