一、游戏规则与算法问题的转化
六角棋（Hex）是 1952 年由丹麦数学家 Piet Hein 发明、后由 John Nash 独立提出的二人完全信息博弈。棋盘由边长 N 的菱形六角网格构成，共 N × N 个格子：
- 玩家 A 需要把棋盘东侧与西侧连通；
- 玩家 B 需要把棋盘北侧与南侧连通。
棋盘铺满时的第一步等价于一个漂亮的性质：没有平局，必有一方胜利。原因在于，如果把黑色棋子与东、西两块”虚拟边界”看作一个整体，白色棋子与北、南两块虚拟边界看作另一个整体，那么两种连通在拓扑上必然有一个成立（这是 Brouwer 不动点定理在离散网格上的化身）。
从算法角度看，这个游戏能讲清三件事：
- 连通性判定：用并查集或 BFS 在网格上判断胜负，这是最基础的图论能力；
- 状态编码：六角网格不是矩形网格，邻居关系必须特殊处理，可以用”位图 + 边界哑节点”的方式把判定做到 O(1) 次 BFS；
- 开局策略：第一手下天元（中心）的理论最优性，以及第二手的对称应对。
本文用 Java 从零实现一套可交互、可对战的 Hex，并实现一个基于单步胜率评估 + 威胁计数的 AI。
二、六角网格的数据结构与邻居关系
六角网格有两种常见坐标系：轴向坐标（axial） 与 偏移坐标（offset）。我们使用轴向坐标 (q, r)，其中 q 为列，r 为行，菱形棋盘满足 0 ≤ q < N、0 ≤ r < N。
轴向坐标下，六个邻居的固定偏移为：
(+1, 0) (-1, 0) (0, +1) (0, -1) (+1, -1) (-1, +1)
因此菱形棋盘在视觉上是一个”斜的”菱形。这在实现中非常方便，因为行列范围都是长方形，不需要做奇怪的裁剪。
public final class HexBoard {
public static final int EMPTY = 0;
public static final int RED = 1; // 东-西连通
public static final int BLUE = 2; // 北-南连通
// 六个邻居的轴向坐标偏移
private static final int[] DQ = {+1, -1, 0, 0, +1, -1};
private static final int[] DR = {0, 0, +1, -1, -1, +1};
private final int n; // 棋盘边长
private final int[] cells; // 长度 n * n
private int moveCount;
public HexBoard(int n) {
this.n = n;
this.cells = new int[n * n];
}
public int size() {
return n;
}
public boolean inRange(int q, int r) {
return q >= 0 && q < n && r >= 0 && r < n;
}
public int get(int q, int r) {
return inRange(q, r) ? cells[r * n + q] : -1;
}
/** 落子，返回是否成功。 */
public boolean place(int q, int r, int player) {
if (!inRange(q, r) || cells[r * n + q] != EMPTY) {
return false;
}
cells[r * n + q] = player;
moveCount++;
return true;
}
public void undo(int q, int r) {
if (inRange(q, r) && cells[r * n + q] != EMPTY) {
cells[r * n + q] = EMPTY;
moveCount--;
}
}
public boolean isFull() {
return moveCount == n * n;
}
public int moveCount() {
return moveCount;
}
}
注意 get 对越界返回 -1，而不是抛异常。这样在扫描邻居时可以自然跳过边界，省掉大量 if。
三、胜负判定：并查集方案
最直观的判定方式是并查集。我们为两个玩家各建一个并查集，并引入两个”虚拟节点”作为目标端点：
- 红方（东-西）：左侧
q == 0的所有格子都并到WEST，右侧q == n-1的所有格子都并到EAST； - 蓝方（北-南）：
r == 0的格子并到NORTH，r == n-1的格子并到SOUTH。
每落一子，把它与六个同色邻居合并。合并后检查 WEST 与 EAST 是否同根，若是则红方胜。
public final 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 boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) {
return false;
}
if (rank[ra] < rank[rb]) {
int t = ra; ra = rb; rb = t;
}
parent[rb] = ra;
if (rank[ra] == rank[rb]) {
rank[ra]++;
}
return true;
}
public boolean connected(int a, int b) {
return find(a) == find(b);
}
}
并查集的增量判定非常快，但它有个致命问题：无法撤销。搜索树回溯时需要撤销落子，并查集做不到（除非用可持久化并查集，代价高）。因此下面的 AI 使用 BFS，因为 BFS 天然支持”落子 → 判定 → 撤销”的临时修改。
/** 并查集 + 边界哑节点的完整实现（仅用于对局判定，不做搜索）。 */
public final class UnionFindJudge {
private static final int[] DQ = {+1, -1, 0, 0, +1, -1};
private static final int[] DR = {0, 0, +1, -1, -1, +1};
private final HexBoard board;
private final int n;
private final UnionFind redUf;
private final UnionFind blueUf;
private final int westDummy, eastDummy, northDummy, southDummy;
public UnionFindJudge(HexBoard board) {
this.board = board;
this.n = board.size();
int total = n * n + 4;
this.redUf = new UnionFind(total);
this.blueUf = new UnionFind(total);
int base = n * n;
this.westDummy = base;
this.eastDummy = base + 1;
this.northDummy = base + 2;
this.southDummy = base + 3;
}
/** 落子后调用，返回获胜方（0 表示无人获胜）。 */
public int placeAndJudge(int q, int r, int player) {
if (!board.place(q, r, player)) {
return 0;
}
int idx = r * n + q;
if (player == HexBoard.RED) {
if (q == 0) redUf.union(idx, westDummy);
if (q == n - 1) redUf.union(idx, eastDummy);
for (int d = 0; d < 6; d++) {
int nq = q + DQ[d], nr = r + DR[d];
if (board.get(nq, nr) == HexBoard.RED) {
redUf.union(idx, nr * n + nq);
}
}
return redUf.connected(westDummy, eastDummy) ? HexBoard.RED : 0;
} else {
if (r == 0) blueUf.union(idx, northDummy);
if (r == n - 1) blueUf.union(idx, southDummy);
for (int d = 0; d < 6; d++) {
int nq = q + DQ[d], nr = r + DR[d];
if (board.get(nq, nr) == HexBoard.BLUE) {
blueUf.union(idx, nr * n + nq);
}
}
return blueUf.connected(northDummy, southDummy) ? HexBoard.BLUE : 0;
}
}
}
复杂度：每次落子合并至多 8 组关系，O(α(n²)) 近似常数。整局 O(n²・α)。
四、BFS 判定：可撤销、可复用的方案
BFS 判定把两个边界当作源点集合，判断能否扩散到对侧边界。它需要 visited 数组，但我们可以每次使用一个版本号（stamp） 数组避免重复清零——这是竞赛和工程里都极常用的技巧。
public final class BfsJudge {
private static final int[] DQ = {+1, -1, 0, 0, +1, -1};
private static final int[] DR = {0, 0, +1, -1, -1, +1};
private final int n;
private final int[] stamp;
private int currentStamp = 0;
public BfsJudge(int n) {
this.n = n;
this.stamp = new int[n * n];
}
/**
* 判断指定玩家是否已经形成贯通路径。
* 使用整型数组的队列而非 ArrayDeque，避免大量对象分配。
*/
public boolean hasWon(int[] cells, int player) {
int[] queue = new int[n * n];
int head = 0, tail = 0;
currentStamp++;
// 把起始边界的本方棋子全部入队
for (int i = 0; i < n; i++) {
int q = (player == HexBoard.RED) ? 0 : i;
int r = (player == HexBoard.RED) ? i : 0;
if (cells[r * n + q] == player) {
stamp[r * n + q] = currentStamp;
queue[tail++] = r * n + q;
}
}
while (head < tail) {
int idx = queue[head++];
int q = idx % n, r = idx / n;
// 到达目标边界即获胜
if (player == HexBoard.RED && q == n - 1) return true;
if (player == HexBoard.BLUE && r == n - 1) return true;
for (int d = 0; d < 6; d++) {
int nq = q + DQ[d], nr = r + DR[d];
if (nq < 0 || nq >= n || nr < 0 || nr >= n) continue;
int nIdx = nr * n + nq;
if (stamp[nIdx] != currentStamp && cells[nIdx] == player) {
stamp[nIdx] = currentStamp;
queue[tail++] = nIdx;
}
}
}
return false;
}
}
复杂度：O(n²) 时间、O(n²) 空间，但因 stamp 技巧免去每次清零的开销。
五、AI 设计：威胁计数 + 单步胜率评估
Hex 的搜索空间随 n 指数增长（n=11 时有约 11! 量级的对局分支），纯 alpha-beta 在无好的启发函数时表现糟糕。我们采用两层策略：
5.1 单步致胜与单步致败检测
这是最廉价也最有效的剪枝：
- 若我方任意空点落子即可连通 → 立刻落子取胜；
- 若对方任意空点落子即可连通 → 必须堵住该点；
- 若对方有多个致胜点（双重威胁）→ 局面已基本必败，选一个堵住以减少损失。
import java.util.ArrayList;
import java.util.List;
public final class HexAI {
private static final int[] DQ = {+1, -1, 0, 0, +1, -1};
private static final int[] DR = {0, 0, +1, -1, -1, +1};
private final int n;
private final int me;
private final int opp;
private final BfsJudge judge;
public HexAI(int n, int me) {
this.n = n;
this.me = me;
this.opp = (me == HexBoard.RED) ? HexBoard.BLUE : HexBoard.RED;
this.judge = new BfsJudge(n);
}
public int[] chooseMove(HexBoard board) {
List<int[]> empties = collectEmpties(board);
if (empties.isEmpty()) {
return null;
}
// 开局：天元（中心）
if (board.moveCount() == 0) {
int c = n / 2;
return new int[]{c, c};
}
// 1. 自己能赢就赢
for (int[] mv : empties) {
board.place(mv[0], mv[1], me);
boolean win = judge.hasWon(board.cellsSnapshot(), me);
board.undo(mv[0], mv[1]);
if (win) return mv;
}
// 2. 对手能赢就堵
List<int[]> oppWins = new ArrayList<>();
for (int[] mv : empties) {
board.place(mv[0], mv[1], opp);
boolean win = judge.hasWon(board.cellsSnapshot(), opp);
board.undo(mv[0], mv[1]);
if (win) oppWins.add(mv);
}
if (oppWins.size() == 1) {
return oppWins.get(0);
}
// 3. 一般情况下用启发式评分
return bestByHeuristic(board, empties);
}
private List<int[]> collectEmpties(HexBoard board) {
List<int[]> list = new ArrayList<>();
for (int r = 0; r < n; r++) {
for (int q = 0; q < n; q++) {
if (board.get(q, r) == HexBoard.EMPTY) {
list.add(new int[]{q, r});
}
}
}
return list;
}
private int[] bestByHeuristic(HexBoard board, List<int[]> empties) {
int[] best = empties.get(0);
double bestScore = Double.NEGATIVE_INFINITY;
for (int[] mv : empties) {
board.place(mv[0], mv[1], me);
double score = evaluate(board);
board.undo(mv[0], mv[1]);
if (score > bestScore) {
bestScore = score;
best = mv;
}
}
return best;
}
/**
* 我方视角的启发式评估：
* 连接度：我方最长连通链的"有效长度"
* 威胁度：对方最有希望的一条链上的棋子数
*/
private double evaluate(HexBoard board) {
return chainScore(board, me) * 1.0 - chainScore(board, opp) * 0.9;
}
/** 用双端 BFS 粗估某方从起始边到目标边的"最短板"。 */
private int chainScore(HexBoard board, int player) {
int[] cells = board.cellsSnapshot();
int reach = 0;
for (int i = 0; i < n; i++) {
int q = (player == HexBoard.RED) ? 0 : i;
int r = (player == HexBoard.RED) ? i : 0;
if (cells[r * n + q] == player) {
reach += 1 + bfsDepth(cells, q, r, player);
}
}
return reach;
}
/** 从 (sq, sr) 出发 BFS，返回能到达的最远"目标方向"距离。 */
private int bfsDepth(int[] cells, int sq, int sr, int player) {
boolean[] visited = new boolean[n * n];
int[] queue = new int[n * n];
int head = 0, tail = 0;
queue[tail++] = sr * n + sq;
visited[sr * n + sq] = true;
int best = 0;
while (head < tail) {
int idx = queue[head++];
int q = idx % n, r = idx / n;
int progress = (player == HexBoard.RED) ? q : r;
best = Math.max(best, progress);
for (int d = 0; d < 6; d++) {
int nq = q + DQ[d], nr = r + DR[d];
if (nq < 0 || nq >= n || nr < 0 || nr >= n) continue;
int nIdx = nr * n + nq;
if (!visited[nIdx] && cells[nIdx] == player) {
visited[nIdx] = true;
queue[tail++] = nIdx;
}
}
}
return best;
}
}
这里需要一个 cellsSnapshot() 方法，把内部数组以只读方式暴露出来。为了不破坏封装，我们提供一个拷贝方法：
// 在 HexBoard 中追加
public int[] cellsSnapshot() {
return cells.clone();
}
注意：每步 clone 一次是 O(n²) 的拷贝开销。若追求极致性能，可改为提供一个直接访问的包内可见引用，或让 BfsJudge 直接持有 HexBoard 引用。本文优先保证代码清晰与可读性。
5.2 启发式函数的改进方向
上面的 chainScore 只是”最远的推进距离”之和，过于朴素。实际工程中常用桥（bridge）检测：在六角网格上，相邻两个同色棋子若同时有两块空格作为”公共邻居”，则形成一座桥，对方无法单步切断。桥越多，连通势能越大。
/**
* 桥检测：若 a 与 b 同色，且存在两个共同空邻居，
* 则 a-b 之间形成桥（对方需要两步才能切断）。
*/
private int countBridges(int[] cells, int player) {
int bridges = 0;
for (int r = 0; r < n; r++) {
for (int q = 0; q < n; q++) {
if (cells[r * n + q] != player) continue;
for (int d = 0; d < 6; d++) {
int nq = q + DQ[d], nr = r + DR[d];
if (nq < 0 || nq >= n || nr < 0 || nr >= n) continue;
if (cells[nr * n + nq] != player) continue;
// 统计两个格子的共同空邻居数量
int common = 0;
for (int e = 0; e < 6; e++) {
int aq = q + DQ[e], ar = r + DR[e];
if (aq < 0 || aq >= n || ar < 0 || ar >= n) continue;
if (cells[ar * n + aq] != HexBoard.EMPTY) continue;
// 该空点是否同时与 (nq, nr) 相邻
for (int f = 0; f < 6; f++) {
if (nq + DQ[f] == aq && nr + DR[f] == ar) {
common++;
break;
}
}
}
if (common >= 2) bridges++;
}
}
}
return bridges / 2; // 每条桥被数了两次
}
把 countBridges 加入评估函数，AI 的棋力会有明显提升——因为它开始理解”哪些连接是不可切断的”，而不是纯粹贪心推进。
六、完整可运行的主程序
import java.util.Scanner;
public final class HexGame {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = 7; // 默认 7×7
HexBoard board = new HexBoard(n);
HexAI redAI = new HexAI(n, HexBoard.RED);
HexAI blueAI = new HexAI(n, HexBoard.BLUE);
UnionFindJudge judge = new UnionFindJudge(board);
int turn = HexBoard.RED;
int winner = 0;
while (winner == 0 && !board.isFull()) {
int[] mv;
if (turn == HexBoard.RED) {
System.out.print("红方落子 (q r): ");
int q = in.nextInt(), r = in.nextInt();
mv = new int[]{q, r};
} else {
mv = blueAI.chooseMove(board);
System.out.printf("蓝方(AI)落子: (%d, %d)%n", mv[0], mv[1]);
}
winner = judge.placeAndJudge(mv[0], mv[1], turn);
printBoard(board);
turn = (turn == HexBoard.RED) ? HexBoard.BLUE : HexBoard.RED;
}
if (winner == HexBoard.RED) {
System.out.println("红方（东-西）胜利！");
} else if (winner == HexBoard.BLUE) {
System.out.println("蓝方（北-南）胜利！");
} else {
System.out.println("棋盘已满。");
}
}
/** 用字符画打印菱形棋盘。 */
private static void printBoard(HexBoard b) {
int n = b.size();
for (int r = 0; r < n; r++) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < r; i++) sb.append(' ');
for (int q = 0; q < n; q++) {
int v = b.get(q, r);
sb.append(v == HexBoard.EMPTY ? '.' : v == HexBoard.RED ? 'R' : 'B');
sb.append(' ');
}
System.out.println(sb);
}
System.out.println();
}
}
七、胜负判定的正确性论证
为什么”棋盘铺满必有一方获胜”？形式化地说明：
设红方检查东西连通、蓝方检查南北连通。把棋盘外的东西两侧边界染红、南北两侧边界染蓝。铺满后，每个格子都属于红或蓝。由平面图的对偶性质，红路径（东西贯通）与蓝路径（南北贯通）在拓扑上不能同时不存在：若不存在红路径，则红区域被蓝区域分隔，蓝区域必然从北到南贯通。这正是 Hex 无平局的根本原因。
在代码层面，我们依赖 BfsJudge 的正确性：BFS 从起始边界出发，只沿同色格子扩散，若能触达对侧边界，说明存在一条同色路径。由于 BFS 遍历的是连通分量，触达即等价于存在路径，判定是充分必要的。
八、复杂度与工程要点
| 环节 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 并查集落子判定 | O(α(n²)) |
O(n²) |
近似常数，但不支持撤销 |
| BFS 胜负判定 | O(n²) |
O(n²) |
支持临时落子/撤销 |
| AI 单步致胜扫描 | O(n²) × O(n²) |
O(n²) |
每个空点跑一次 BFS |
| AI 启发式评估 | O(n⁴) 量级 |
O(n²) |
每步 clone + 双 BFS + 桥检测 |
几个实测经验：
n = 7时 AI 每步耗时约 20–50 ms，完全可以接受；n = 11时会升到数百毫秒，因为空点数从 49 涨到 121，且每次 BFS 规模变大。- stamp 技巧是性能关键：如果每次 BFS 都
new boolean[n*n]并清零，GC 压力会让 AI 明显变慢。 - 桥检测可以只在候选点附近计算（局部桥数），而不是全盘扫描，能把评估从
O(n⁴)降到O(n²)量级。 cellsSnapshot()的 clone 是隐性开销。若把BfsJudge改为接收int[] cells参数并直接从HexBoard取内部数组引用（构造函数传入），可以省掉全部拷贝。
九、延伸：从 Hex 到一般连通性博弈
Hex 的判定框架可以推广到很多同类游戏：
- Y 形棋：在三角棋盘上连接三个顶点，判定用三源 BFS；
- 桥牌类围堵游戏：判断”是否被对手完全切断”，等价于求最小割；
- 电子电路布线：判断两点是否连通，本质相同。
进一步地，若把”最短连通路径”作为目标，Hex 就变成了一个最短路问题：给每个空格赋代价 1、己方棋子赋代价 0、对方棋子赋不可通行，然后用 0-1 BFS 求己方从起始边到目标边的最小代价。这个代价其实是极好的评估函数——它直接告诉 AI”我还差几步能连通”。实现只需把队列换成双端队列：
import java.util.ArrayDeque;
import java.util.Deque;
/** 用 0-1 BFS 计算某方连通所需的"追加落子数"下界。 */
public int minAdditionalStones(int[] cells, int player) {
final int INF = Integer.MAX_VALUE;
int[] dist = new int[n * n];
java.util.Arrays.fill(dist, INF);
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
int q = (player == HexBoard.RED) ? 0 : i;
int r = (player == HexBoard.RED) ? i : 0;
int idx = r * n + q;
if (cells[idx] == player) {
dist[idx] = 0;
dq.addFirst(idx);
}
}
while (!dq.isEmpty()) {
int idx = dq.pollFirst();
int q = idx % n, r = idx / n;
if ((player == HexBoard.RED && q == n - 1) ||
(player == HexBoard.BLUE && r == n - 1)) {
return dist[idx];
}
for (int d = 0; d < 6; d++) {
int nq = q + DQ[d], nr = r + DR[d];
if (nq < 0 || nq >= n || nr < 0 || nr >= n) continue;
int nIdx = nr * n + nq;
if (cells[nIdx] == oppOf(player)) continue; // 对方棋子不可通行
int w = (cells[nIdx] == player) ? 0 : 1;
if (dist[idx] + w < dist[nIdx]) {
dist[nIdx] = dist[idx] + w;
if (w == 0) dq.addFirst(nIdx);
else dq.addLast(nIdx);
}
}
}
return INF;
}
private int oppOf(int player) {
return (player == HexBoard.RED) ? HexBoard.BLUE : HexBoard.RED;
}
这是 Hex AI 中最有价值的评估函数之一：双方 minAdditionalStones 的差值，就是”谁离胜利更近”的量化表达。它比”连通链长度”更准确，因为它考虑了绕行成本。
十、小结
本文从六角棋的规则出发，完整实现了：
- 轴向坐标的六边形邻居模型，用统一的 6 偏移数组处理所有格子；
- 并查集判定，
O(α)增量判断，适合正式对局； - stamp-BFS 判定，支持落子/撤销，适合搜索；
- 三层 AI 决策：单步取胜 → 单步封堵 → 启发式评估；
- 桥检测与 0-1 BFS 最小追加落子两个进阶评估手段。
算法要点浓缩成一句话：把”连通性”抽象成图论可达性问题，胜负判定就退化为一次 BFS；把”离赢还差多少”抽象成带权最短路，AI 就有了方向感。
