每日算法 — 使用java实现六角棋：虚拟连接扩展与H-search威胁树求解

六角棋（Hex）的棋盘是菱形排列的六边形格，双方各自连接自己的两条对边，谁先连成通路谁赢。规则简单到可以用一句话说完，但它的求解难度极高——甚至被证明是 PSPACE 完全的。正因为如此，人类高手和早期程序并不靠”算到底”，而是靠一种极漂亮的结构化推理：虚拟连接（virtual connection）。本文用 Java 实现虚拟连接扩展与 H-search 威胁树，这套思路能在很浅的搜索深度下找到强制胜的棋路。

一、棋盘与胜负条件

Hex 棋盘是 N × N 的菱形，每个格有 6 个邻居。用”轴向坐标”或简单的行列坐标都能表达，为了代码清晰这里用行列坐标 + 六邻居偏移：

• 左上、右上、左、右、左下、右下；
• 我方（+1）目标：连接上边到下边；
• 对方（-1）目标：连接左边到右边。

朴素判定用并查集做连通块合并（很多实现到这里就停了），但那是静态判定：只能回答”当前是否已连成”。真正难的是”接下来我该怎么走才能连成”。

二、虚拟连接：不落子也知道能连上

2.1 定义

设两格 a、b。若”无论对方下在哪里，我总能形成 a、b 之间的通路”，则称 a、b 虚拟连接，记为 a ⋈ b。

最关键的一条规则是二桥（two-bridge）：若 a、b 之间存在两个相邻的空格 c1、c2，且 a、b 都与 c1、c2 相邻，则 a、b 虚拟连接。

a ⋈ b  ⇐  存在 c1, c2 相邻，a~c1, a~c2, b~c1, b~c2 均为相邻格

为什么成立？假设对方下在 c1，我就下 c2，于是 a → c2 → b 这条通路中，c2 已归我，c1 归对方，但 c2 与 a、b 都相邻，通路成立。对方若下在 c1、c2 之外，我先占 c1，同理。注意 c1、c2 必须彼此相邻——这是二桥的核心条件，很多实现漏掉它。

2.2 为什么虚拟连接是”真正安全”的

虚拟连接不需要真的落子，它只是逻辑承诺。它的价值在于：

1. 不消耗资源：建立虚拟连接只需”两个空位”，不用实际占格；
2. 抗干扰：对方必须连下两手才能破坏（一手破坏一个空位，另一手再抢另一个）；
3. 可组合：虚拟连接可以串联——a ⋈ b、b ⋈ c 则 a ⋈ c。

因此虚拟连接的图可以在空棋盘上预先算出来，构成一张”潜在通路图”。AI 只需在这张图上找通路，而不必考虑具体的落子顺序。

三、代码：棋盘、并查集与虚拟连接

package com.example.hex;

import java.util.*;

public class HexBoard {
    public final int n;                    // 棋盘边长
    public final int[][] cells;            // 0 空，+1 我方，-1 对方
    // 六邻居偏移：左上、右上、左、右、左下、右下
    public static final int[] DR = {-1, -1, 0, 0, 1, 1};
    public static final int[] DC = {0, 1, -1, 1, -1, 0};

    public HexBoard(int n) {
        this.n = n;
        this.cells = new int[n][n];
    }

    public boolean in(int r, int c) { return r >= 0 && r < n && c >= 0 && c < n; }

    public HexBoard copy() {
        HexBoard b = new HexBoard(n);
        for (int r = 0; r < n; r++) System.arraycopy(cells[r], 0, b.cells[r], 0, n);
        return b;
    }

    /** 邻居列表 */
    public List<int[]> neighbors(int r, int c) {
        List<int[]> res = new ArrayList<>(6);
        for (int d = 0; d < 6; d++) {
            int nr = r + DR[d], nc = c + DC[d];
            if (in(nr, nc)) res.add(new int[]{nr, nc});
        }
        return res;
    }

    /** 两个格子是否相邻 */
    public boolean adjacent(int r1, int c1, int r2, int c2) {
        for (int d = 0; d < 6; d++)
            if (r1 + DR[d] == r2 && c1 + DC[d] == c2) return true;
        return false;
    }
}

3.1 并查集连通判定

package com.example.hex;

import java.util.*;

/** 并查集：用于判定某方是否已连成通路 */
public class UnionFind {
    private final int[] parent;
    private final int[] rank;

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) parent[i] = i;
    }

    public int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]]; // 路径减半
            x = parent[x];
        }
        return x;
    }

    public void union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return;
        if (rank[ra] < rank[rb]) parent[ra] = rb;
        else if (rank[ra] > rank[rb]) parent[rb] = ra;
        else { parent[rb] = ra; rank[ra]++; }
    }
}

package com.example.hex;

import java.util.*;

public class WinChecker {
    /**
     * 判定 side 是否已连成通路。
     * side=+1：上边 → 下边；side=-1：左边 → 右边。
     * 用虚拟超级节点：把边界的己方格并入一个代表节点。
     */
    public static boolean hasWon(HexBoard b, int side) {
        int n = b.n;
        UnionFind uf = new UnionFind(n * n + 2);
        int topId = n * n, bottomId = n * n + 1;

        for (int r = 0; r < n; r++)
            for (int c = 0; c < n; c++) {
                if (b.cells[r][c] != side) continue;
                int id = r * n + c;
                // 六邻居合并
                for (int d = 0; d < 6; d++) {
                    int nr = r + HexBoard.DR[d], nc = c + HexBoard.DC[d];
                    if (!b.in(nr, nc)) continue;
                    if (b.cells[nr][nc] == side) uf.union(id, nr * n + nc);
                }
                // 边界连接
                if (side == 1) {
                    if (r == 0) uf.union(id, topId);
                    if (r == n - 1) uf.union(id, bottomId);
                } else {
                    if (c == 0) uf.union(id, topId);
                    if (c == n - 1) uf.union(id, bottomId);
                }
            }
        // 参数复用 top/bottom 作为两条对边的代表（与 side 绑定）
        return uf.find(topId) == uf.find(bottomId);
    }
}

3.2 二桥与虚拟连接的检测

package com.example.hex;

import java.util.*;

/** 虚拟连接（virtual connection）：不落子即保证的通路关系 */
public class VirtualConnection {
    private final HexBoard board;
    // 虚拟连接表：vc[a][b] 为 true 表示 a ⋈ b
    private final boolean[][] vc;

    public VirtualConnection(HexBoard board) {
        this.board = board;
        int n = board.n;
        this.vc = new boolean[n * n][n * n];
        build();
    }

    private void build() {
        int n = board.n;
        for (int r1 = 0; r1 < n; r1++)
            for (int c1 = 0; c1 < n; c1++) {
                if (board.cells[r1][c1] != 0) continue;   // 只对空格建虚拟连接
                for (int r2 = 0; r2 < n; r2++)
                    for (int c2 = 0; c2 < n; c2++) {
                        if (board.cells[r2][c2] != 0) continue;
                        if (r1 == r2 && c1 == c2) continue;
                        if (twoBridge(r1, c1, r2, c2)) vc[r1 * n + c1][r2 * n + c2] = true;
                    }
            }
        // 传递闭包：a⋈b 且 b⋈c ⇒ a⋈c
        closure();
    }

    /**
     * 二桥判定：a、b 之外是否存在两个"彼此相邻"的空格 c1、c2，
     * 使得 a、b 都与 c1、c2 相邻。
     */
    private boolean twoBridge(int r1, int c1, int r2, int c2) {
        int n = board.n;
        List<int[]> na = board.neighbors(r1, c1);
        List<int[]> nb = board.neighbors(r2, c2);

        for (int[] p : na) {
            if (board.cells[p[0]][p[1]] != 0) continue;
            // 排除端点自身
            if (p[0] == r2 && p[1] == c2) continue;
            for (int[] q : nb) {
                if (board.cells[q[0]][q[1]] != 0) continue;
                if (q[0] == r1 && q[1] == c1) continue;
                if (q[0] == p[0] && q[1] == p[1]) continue;      // 必须两个不同的空格
                if (!board.adjacent(p[0], p[1], q[0], q[1])) continue; // 两空格必须相邻
                return true;
            }
        }
        return false;
    }

    /** Warshall 传递闭包：虚拟连接可串联 */
    private void closure() {
        int m = vc.length;
        for (int k = 0; k < m; k++) {
            if (board.cells[k / board.n][k % board.n] != 0) continue;
            for (int i = 0; i < m; i++) {
                if (!vc[i][k]) continue;
                for (int j = 0; j < m; j++)
                    if (vc[k][j]) vc[i][j] = true;
            }
        }
    }

    public boolean connected(int r1, int c1, int r2, int c2) {
        return vc[r1 * board.n + c1][r2 * board.n + c2];
    }
}

closure() 用 Warshall 算法，复杂度 O(V^3)（V = n²）。9×9 棋盘时 V = 81，约 53 万次操作，可以接受；更大的棋盘应改用分块或稀疏跳跃。

四、H-search：威胁树上的强制胜

虚拟连接给出的是”潜在通路”，H-search（也称 H 搜索、威胁空间搜索）则回答”我能不能强迫对方按我设想的方式应对”。

4.1 两类关键着法

• 威胁（threat）：我下一手后，如果对方不应，我立刻形成完整的连接胜势；
• 应对（defense）：唯一能化解该威胁的位置。

若我下的每一步都是”威胁”，而对方的应对都是”唯一被迫的”，这条路径就是强制胜（forced win）。

4.2 与或树的两种节点

H-search 本质是在与或树上搜索：

• 或节点（OR）：轮到我走，只要任一子局面胜，我就胜；
• 与节点（AND）：轮到对方走，必须所有子局面都胜（即对方每种应对都无法逃脱），我才能胜。

package com.example.hex;

import java.util.*;

public class HSearch {
    private final HexBoard root;
    private final int side;              // 我方 (+1 或 -1)
    private long nodes = 0;

    public HSearch(HexBoard root, int side) {
        this.root = root;
        this.side = side;
    }

    /** 入口：在 maxDepth 内寻找强制胜 */
    public boolean findForcedWin(HexBoard b, int depth) {
        nodes++;
        if (WinChecker.hasWon(b, side)) return true;
        if (WinChecker.hasWon(b, -side)) return false;
        if (depth <= 0) return false;

        // 或节点：尝试每个候选着法
        for (int[] mv : candidateMoves(b, side, depth)) {
            HexBoard nb = b.copy();
            nb.cells[mv[0]][mv[1]] = side;

            if (WinChecker.hasWon(nb, side)) return true;

            // 转到与节点：对方必须应对
            if (allResponsesFail(nb, depth - 1)) return true;
        }
        return false;
    }

    /**
     * 与节点：对方的每一种"合理应对"都无法阻止我胜。
     * 这里只考虑"必须应对的威胁位置"，而非全部空位——这正是 H-search 的剪枝精髓。
     */
    private boolean allResponsesFail(HexBoard b, int depth) {
        List<int[]> threats = new ArrayList<>();
        List<int[]> otherEmpty = new ArrayList<>();

        for (int r = 0; r < b.n; r++)
            for (int c = 0; c < b.n; c++) {
                if (b.cells[r][c] != 0) continue;
                HexBoard t = b.copy();
                t.cells[r][c] = -side;
                // 若我（side）下一手在该空位就会赢，则该空位是"必须防守"的点
                if (wouldWinIfPlaced(t, side, r, c)) threats.add(new int[]{r, c});
                else otherEmpty.add(new int[]{r, c});
            }

        // 若我存在多个独立的必胜点（对方只能防一个），则直接成立
        if (threats.size() >= 2) {
            // 找出两个互不相干的必胜点：下其中一个后，另一个仍能赢
            for (int i = 0; i < threats.size(); i++)
                for (int j = i + 1; j < threats.size(); j++) {
                    HexBoard t = b.copy();
                    t.cells[threats.get(i)[0]][threats.get(i)[1]] = -side;
                    if (wouldWinIfPlaced(t, side, threats.get(j)[0], threats.get(j)[1]))
                        return true;
                }
        }

        // 否则对方只需防守这些点；逐个检查防守后我是否仍能强制胜
        if (!threats.isEmpty()) {
            for (int[] th : threats) {
                HexBoard d = b.copy();
                d.cells[th[0]][th[1]] = -side;
                if (!findForcedWin(d, depth)) return false;
            }
            return true;
        }

        // 无威胁：对方可以自由应对，尝试有限个高价值位置
        for (int[] e : otherEmpty) {
            HexBoard d = b.copy();
            d.cells[e[0]][e[1]] = -side;
            if (!findForcedWin(d, depth)) return false;
        }
        return !otherEmpty.isEmpty();
    }

    /** 若 side 在 (r,c) 落子是否立刻胜 */
    private boolean wouldWinIfPlaced(HexBoard b, int side, int r, int c) {
        HexBoard t = b.copy();
        t.cells[r][c] = side;
        return WinChecker.hasWon(t, side);
    }

    /**
     * 候选着法：优先选"能建立最多虚拟连接"的空格。
     * 用虚拟连接数作为着法排序键，能显著提高命中率。
     */
    private List<int[]> candidateMoves(HexBoard b, int side, int depth) {
        List<int[]> empties = new ArrayList<>();
        for (int r = 0; r < b.n; r++)
            for (int c = 0; c < b.n; c++)
                if (b.cells[r][c] == 0) empties.add(new int[]{r, c});

        // 按"落子后形成的虚拟连接数量"降序
        VirtualConnection vc = new VirtualConnection(b);
        empties.sort((p, q) -> Integer.compare(
                vcDegree(b, vc, q[0], q[1], side),
                vcDegree(b, vc, p[0], p[1], side)));

        int limit = Math.min(empties.size(), 24);
        return empties.subList(0, limit);
    }

    /** (r,c) 与我方已有棋子之间虚拟连接的数量 */
    private int vcDegree(HexBoard b, VirtualConnection vc, int r, int c, int side) {
        int cnt = 0;
        for (int rr = 0; rr < b.n; rr++)
            for (int cc = 0; cc < b.n; cc++)
                if (b.cells[rr][cc] == side && vc.connected(r, c, rr, cc)) cnt++;
        return cnt;
    }

    public long getNodes() { return nodes; }
}

五、主程序：从虚拟连接图到强制胜

package com.example.hex;

import java.util.*;

public class HexAI {
    public static void main(String[] args) {
        int n = 9;
        HexBoard b = new HexBoard(n);

        // 初始：我方（+1）在中心附近先手，对方（-1）在某处应一手
        b.cells[4][4] = 1;
        b.cells[3][4] = -1;

        // 1. 虚拟连接图：看看我方已建立的"潜在通路"
        VirtualConnection vc = new VirtualConnection(b);
        int links = 0;
        for (int r = 0; r < n; r++)
            for (int c = 0; c < n; c++)
                if (vc.connected(4, 4, r, c)) links++;
        System.out.println("中心格虚拟连接数 = " + links);

        // 2. H-search 找强制胜
        HSearch search = new HSearch(b, +1);
        boolean win = search.findForcedWin(b, 8);
        System.out.println("是否存在强制胜：" + win);
        System.out.println("搜索节点数：" + search.getNodes());

        // 3. 实战：每步选"虚拟连接增量最大"的空位
        HexBoard cur = b;
        int side = +1;
        for (int mv = 0; mv < 5; mv++) {
            int[] best = chooseByVc(cur, side);
            if (best == null) break;
            cur.cells[best[0]][best[1]] = side;
            System.out.printf("第%d手：%d侧落子 (%d,%d)%n", mv + 1, side, best[0], best[1]);
            if (WinChecker.hasWon(cur, side)) {
                System.out.println("获胜方：" + side);
                break;
            }
            side = -side;
        }
    }

    /** 选择落点：最大化"新建立的虚拟连接数"，同时避免给对方留下二桥 */
    static int[] chooseByVc(HexBoard b, int side) {
        int n = b.n;
        int[] best = null;
        int bestScore = -1;
        for (int r = 0; r < n; r++)
            for (int c = 0; c < n; c++) {
                if (b.cells[r][c] != 0) continue;
                HexBoard t = b.copy();
                t.cells[r][c] = side;
                VirtualConnection vc = new VirtualConnection(t);

                int mine = 0, theirs = 0;
                for (int rr = 0; rr < n; rr++)
                    for (int cc = 0; cc < n; cc++) {
                        if (t.cells[rr][cc] == 0) continue;
                        int cnt = 0;
                        for (int r2 = 0; r2 < n; r2++)
                            for (int c2 = 0; c2 < n; c2++)
                                if (t.cells[r2][c2] == 0 && vc.connected(rr, cc, r2, c2)) cnt++;
                        if (t.cells[rr][cc] == side) mine += cnt;
                        else theirs += cnt;
                    }
                int score = mine * 2 - theirs; // 攻守兼顾
                if (score > bestScore) { bestScore = score; best = new int[]{r, c}; }
            }
        return best;
    }
}

六、复杂度与正确性

正确性上的三个要点：

1. 二桥的空格必须彼此相邻。这是虚拟连接成立的前提，漏掉会把”一格双邻”误判成二桥。
2. 虚拟连接必须传递闭包。a ⋈ b、b ⋈ c 蕴含 a ⋈ c，不做闭包会漏掉长链通路。
3. H-search 的与节点必须”全胜”。只要有对方一种应对能逃脱，”强制胜”就不成立——这里不能用”任一应对失败即成立”。

七、为什么 H-search 比普通搜索强

普通 Alpha-Beta 在 Hex 上几乎无用：

• 估值函数难写：Hex 的胜负是”连通性”，不是子力；
• 分支太宽：9×9 棋盘有 81 个空位，b^d 爆炸；
• 深搜不划算：Hex 的胜负往往在 20 手后才明朗。

H-search 的优势来自两层约化：

1. 虚拟连接把”落子顺序”约化为”逻辑关系”：不必模拟每一步，只需知道”这两点一定能连上”；
2. 威胁与应对把分支约化为”强制路径”：对方通常只有 1~2 个必须防守点，分支因子从 ~80 降到 ~2。

这也是 Hex 求解器的经典架构：虚拟连接提供远见，威胁树提供强制力。两者结合，浅搜索即可找到人类高手级别的棋路。

八、工程实现细节

1. 虚拟连接增量化：每落一子只需更新受影响的局部区域（该子 6 邻域内的格），而非全量重建。这一步能把单步开销从 O(V³) 降到 O(N)。
2. 二桥的方向性：注意 c1、c2 相对 a、b 的位置关系，某些方向上两空格相邻条件更强（形成”锐角”二桥），检测时不必区分，统一按”相邻即成立”处理即可。
3. 威胁去重：多个威胁点可能共享同一条连接，需要判断”两个威胁是否独立”，只有独立才构成双威胁（双威胁是强制胜的最常见形态）。
4. 与或树的方向要一致：side 与 -side 的角色在递归中必须交替，混用会导致逻辑反转，这是最容易出的 bug。

Hex 的美妙之处在于：它的规则简单到可以用一句话说明，却需要”虚拟连接”这种高度抽象的推理才能下好。算法层面，它完美示范了用结构代替搜索的思路——当状态空间大到无法穷举时，找到正确的抽象层（这里是虚拟连接关系），比优化搜索本身更有效。