一、蜂巢棋的算法难点在哪
蜂巢棋（Hive）是一类”无棋盘”的棋：棋子本身构成棋盘。玩家轮流把虫子放到场地上（不能悬空），或移动已有的虫子。六种虫各有不同移动规则，其中蚁后必须尽早下场，谁先被对方四面包围谁输。
它的算法难点不在搜索，而在着法生成的合法性判定：
- 六边形网格的邻接几何。一个格有 6 个邻居，”滑动”的含义是沿相邻格之间的棱移动，而不是穿过去。判定”能不能滑”必须检查棱两侧是否都被占据——这是蜂巢棋里最经典的坑。
- 单连通性约束。整堆棋子必须始终连成一个整体（Hive 不能分成两块）。每次移动都必须验证：移走后不出现”断成两片”。这是一个桥边（bridge）检测问题。
- 一模一样的棋子不可区分。玩家的上部棋子都幂等，导致大量置换（permutation）重复。用Zobrist 哈希 + 置换表是必需项，否则搜索树迅速爆掉。
本文实现完整的合法性引擎 + Alpha-Beta AI，重点在滑动判定与连通性验证这两块最容易写错的逻辑。
二、六边形坐标：轴向坐标（axial）
六边形网格的标准表示是轴向坐标 (q, r)，6 个方向向量固定：
int[][] DIRS = {{1,0}, {1,-1}, {0,-1}, {-1,0}, {-1,1}, {0,1}};
这组向量有个很好的性质：第 i 个方向和第 (i+3)%6 个方向正好互为反向，且相邻两个方向之差就是一个邻居方向。这让我们能用”方向对”来精确描述”跨过一条棱”。
用 long 打包一个格：key = ((q + 512) << 10) | (r + 512)，一个 HashMap<Long, Stack> 即可表示整个棋盘，无需预分配二维数组（蜂巢棋的棋盘是动态扩张的）。
三、核心算法一：滑动合法性判定
3.1 格子移动的两种形式
- 爬行（crawl）：沿相邻空格走一步。条件：目标格为空、与至少一个己方/任意棋子相邻。
- 滑动（slide）：沿棱”挤”过去，目标是距离 2 的空格，中间必须”有一条畅通的棱”。
3.2 滑动的精确判定
从格 A 移动到距离 2 的格 B，存在两条可能路径，对应 A 与 B 之间的两个中间格 C1、C2。判定规则：
可滑动 ⟺ 存在中间格 C，使得 A 与 C 相邻、C 与 B 相邻，且 C 为空
也就是至少一侧有空隙。若 C1 与 C2 都被占据，则 A 被”夹死”，不能滑动。
这个判定在代码里就是一个循环：
for (int d = 0; d < 6; d++) {
Cell c1 = A.neighbor(d);
Cell c2 = B.neighbor(d); // 反向对应
if (isEmpty(c1) || isEmpty(c2)) { canSlide = true; break; }
}
关键细节：A 的第 d 个邻居和 B 的第 (d+3)%6 个邻居是同一个格吗？不是——是 B 的第 d 个邻居 与 A 对称。正确的配对是：
Cell mid1 = A.neighbor(d);
Cell mid2 = A.neighbor((d + 1) % 6); // 两条棱之间的那个"中间角"
更简洁的写法是枚举 A 的 6 个邻居，若某邻居 m 满足 m.isAdjacentTo(B) 且 m 为空，则可滑动。这正好覆盖”跨过一条棱”的几何含义，且不依赖方向索引的对称性——推荐这种写法，因为它不会因为方向数组顺序写错而静默出错。
3.3 必须遵守的”蚁后规则”
新棋子必须放在与已有棋子相邻的位置，且不能与对方棋子相邻（除了第一步）。这条规则让开局只有有限几种合法放法，是剪枝的第一道闸门。
四、核心算法二：单连通性验证（桥边检测）
移走一个棋子后，剩余棋子必须仍然连通。暴力做法是移走 → BFS 全图 → 检查是否访问了所有格子，复杂度 O(N) 每次移动。
更快的做法是桥边检测：如果被移走的格子不是”割点”，则移除后仍连通。用 Tarjan 割点算法可以在 O(N) 一次遍历中找出所有割点，但每次移动后图的边会变，仍需重算。
在蜂巢棋的实际规模下（一局通常 ≤ 30 个格子），BFS 的 O(N) 完全够用，且实现简单不易错。这里给出 BFS 版本，并说明何时才值得上割点算法：
boolean staysConnected(Set<Long> cells, long removed) {
long start = -1;
for (long c : cells) { if (c != removed) { start = c; break; } }
if (start < 0) return true; // 只剩一个
// 从 start BFS，看能否覆盖 cells - removed 全部
...
}
五、项目结构
hive/
├── pom.xml
└── src/main/java/com/example/hive/
├── Hex.java 轴向坐标与 6 方向
├── Bug.java 虫种枚举与移动规则
├── Piece.java 棋子（虫种 + 归属）
├── HiveBoard.java 动态棋盘、放置与移动合法性
├── Zobrist.java 哈希键
├── TranspositionTable.java
├── HiveEngine.java Alpha-Beta + 置换表
└── Main.java perft 与自对弈
六、完整实现
6.1 六边形坐标
package com.example.hive;
import java.util.ArrayList;
import java.util.List;
/** 轴向坐标 (q, r)。打包为 long 便于做 HashMap 键。 */
public final class Hex {
/** 6 个方向：右、右上、左上、左、左下、右下。 */
public static final int[][] DIRS = {
{1, 0}, {1, -1}, {0, -1}, {-1, 0}, {-1, 1}, {0, 1}
};
public final int q;
public final int r;
public Hex(int q, int r) {
this.q = q;
this.r = r;
}
/** 第 d 方向的邻居（d ∈ [0,6)）。 */
public Hex neighbor(int d) {
return new Hex(q + DIRS[d][0], r + DIRS[d][1]);
}
/** 打包为 long 键，偏移 512 支持 |坐标| < 512 的棋盘。 */
public long key() {
return pack(q, r);
}
public static long pack(int q, int r) {
return (((long) (q + 512)) << 10) | (r + 512);
}
public static Hex unpack(long key) {
return new Hex((int) (key >>> 10) - 512, (int) (key & 0x3FF) - 512);
}
/** 六边形距离：轴向坐标下的标准公式。 */
public int distance(Hex o) {
int dq = q - o.q;
int dr = r - o.r;
return (Math.abs(dq) + Math.abs(dr) + Math.abs(dq + dr)) / 2;
}
/** 是否相邻（距离为 1）。 */
public boolean isAdjacent(Hex o) {
return distance(o) == 1;
}
public List<Hex> neighbors() {
List<Hex> out = new ArrayList<>(6);
for (int d = 0; d < 6; d++) out.add(neighbor(d));
return out;
}
@Override
public boolean equals(Object o) {
if (!(o instanceof Hex h)) return false;
return h.q == q && h.r == r;
}
@Override
public int hashCode() {
return (int) key();
}
@Override
public String toString() {
return "(" + q + "," + r + ")";
}
}
6.2 虫种与棋子
package com.example.hive;
/** 蜂巢棋的虫种。每种有独立的移动规则。 */
public enum Bug {
/** 蚁后：只能走一步，被围死则输。 */
QUEEN("蚁后", 1),
/** 甲虫：走一步，且能爬到棋子上面（本实现用"可以移动到被占领的格"表示）。 */
BEETLE("甲虫", 2),
/** 蚱蜢：沿直线跳过连续棋子，落到第一个空格。 */
GRASSHOPPER("蚱蜢", 3),
/** 蜘蛛：正好走三步。 */
SPIDER("蜘蛛", 2),
/** 蚂蚁：沿外围走任意步，不能穿越被夹死的点。 */
ANT("蚂蚁", 3),
/** 蜜蜂：只能滑动，不能爬行。 */
LADYBUG("蜜蜂", 1);
public final String cn;
/** 标准套牌中的数量。 */
public final int count;
Bug(String cn, int count) {
this.cn = cn;
this.count = count;
}
}
package com.example.hive;
/** 棋子：虫种 + 归属玩家。棋盘上同一个格可能叠多枚（甲虫堆叠）。 */
public final class Piece {
public final Bug bug;
public final int owner; // 0 或 1
public Piece(Bug bug, int owner) {
this.bug = bug;
this.owner = owner;
}
@Override
public String toString() {
return (owner == 0 ? "W" : "B") + bug.cn;
}
}
6.3 棋盘与合法性判定（核心）
package com.example.hive;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
/**
* 蜂巢棋盘。每个格用一个栈表示（栈底是原始棋子，上面可以叠甲虫）。
* 核心职责：放置合法性、移动合法性（滑动判定 + 连通性校验）。
*/
public final class HiveBoard {
/** key = Hex.pack(q,r)，value = 该格的棋子栈（最后一个是顶层）。 */
private final Map<Long, List<Piece>> cells = new HashMap<>();
/** 双方未下场的棋子（按虫种计数）。 */
private final int[][] reserve = new int[2][Bug.values().length];
/** 双方已下场的蚁后标记。 */
private final boolean[] queenPlaced = new boolean[2];
private int moveCount = 0;
public HiveBoard() {
for (int p = 0; p < 2; p++) {
for (Bug b : Bug.values()) reserve[p][b.ordinal()] = b.count;
}
}
public boolean isEmpty(Hex h) {
return !cells.containsKey(h.key());
}
/** 顶层棋子的归属，-1 表示空。 */
public int topOwner(Hex h) {
List<Piece> st = cells.get(h.key());
if (st == null || st.isEmpty()) return -1;
return st.get(st.size() - 1).owner;
}
public Piece topPiece(Hex h) {
List<Piece> st = cells.get(h.key());
if (st == null || st.isEmpty()) return null;
return st.get(st.size() - 1);
}
public int size() { return cells.size(); }
public int moveCount() { return moveCount; }
public Set<Long> occupiedKeys() { return cells.keySet(); }
/**
* 放置合法性：新棋子必须与已有棋子相邻，且（非首子时）不能与对方棋子相邻。
*/
public boolean canPlace(Hex h, int player) {
if (!isEmpty(h)) return false;
if (cells.isEmpty()) return true; // 首子可在任意位置
boolean touchOwn = false, touchEnemy = false;
for (int d = 0; d < 6; d++) {
Hex n = h.neighbor(d);
if (isEmpty(n)) continue;
if (topOwner(n) == player) touchOwn = true;
else touchEnemy = true;
}
return touchOwn && !touchEnemy;
}
/** 执行放置，消耗后备棋子。 */
public boolean place(Hex h, Piece piece) {
if (!canPlace(h, piece.owner)) return false;
if (reserve[piece.owner][piece.bug.ordinal()] <= 0) return false;
cells.computeIfAbsent(h.key(), k -> new ArrayList<>()).add(piece);
reserve[piece.owner][piece.bug.ordinal()]--;
if (piece.bug == Bug.QUEEN) queenPlaced[piece.owner] = true;
moveCount++;
return true;
}
public int reserveOf(int player, Bug bug) {
return reserve[player][bug.ordinal()];
}
public boolean queenPlaced(int player) {
return queenPlaced[player];
}
/**
* 该棋子所有合法移动目标。
* 分三类：爬行（相邻空格）、滑动（距离 2 的"挤过棱"）、蚱蜢跳跃。
*/
public List<Hex> legalMoves(Hex from) {
List<Hex> out = new ArrayList<>();
Piece top = topPiece(from);
if (top == null) return out;
// 叠了多枚棋子时，顶层必然是甲虫（只有甲虫能爬上去）。
// 它离开栈顶时按甲虫规则处理，否则会出现"叠上去就再也动不了"的死局。
List<Piece> stack = cells.get(from.key());
boolean onStack = stack.size() > 1;
Bug effectiveBug = onStack ? Bug.BEETLE : top.bug;
switch (effectiveBug) {
case GRASSHOPPER -> grasshopperMoves(from, out);
case SPIDER -> spiderMoves(from, out);
case ANT -> antMoves(from, out);
case BEETLE -> beetleMoves(from, out);
case QUEEN, LADYBUG -> {
for (int d = 0; d < 6; d++) {
Hex t = from.neighbor(d);
if (isEmpty(t) && canSlide(from, t)) out.add(t);
}
}
}
// 统一过滤：移走后必须保持整体连通
List<Hex> valid = new ArrayList<>();
for (Hex t : out) {
if (staysConnectedAfterMove(from, t)) valid.add(t);
}
return valid;
}
/**
* 滑动判定：从 a 到距离 2 的 b，必须存在一个"中间格"同时与 a、b 相邻且为空。
* 实现上直接枚举 a 的 6 个邻居，检查是否邻接 b —— 这比用方向索引
* 去配对更稳健，不会因为 DIRS 顺序写错而静默产生错误结果。
*/
public boolean canSlide(Hex a, Hex b) {
if (a.distance(b) != 2) return false;
for (int d = 0; d < 6; d++) {
Hex mid = a.neighbor(d);
if (mid.isAdjacent(b) && isEmpty(mid)) return true;
}
return false;
}
/** 移动后剩余棋子是否仍整体连通。 */
public boolean staysConnectedAfterMove(Hex from, Hex to) {
// 目标格可能本来就有棋子（甲虫爬上去），此时格数不变
boolean targetOccupied = !isEmpty(to);
Set<Long> remaining = new HashSet<>(cells.keySet());
remaining.remove(from.key());
if (!targetOccupied) remaining.add(to.key());
if (remaining.size() <= 1) return true;
long start = remaining.iterator().next();
Set<Long> seen = new HashSet<>();
ArrayDeque<Long> queue = new ArrayDeque<>();
queue.add(start);
seen.add(start);
while (!queue.isEmpty()) {
long cur = queue.poll();
Hex ch = Hex.unpack(cur);
for (int d = 0; d < 6; d++) {
long nk = ch.neighbor(d).key();
if (remaining.contains(nk) && seen.add(nk)) {
queue.add(nk);
}
}
}
return seen.size() == remaining.size();
}
/** 甲虫：走一步，可以走进被占据的格（爬到上面）。 */
private void beetleMoves(Hex from, List<Hex> out) {
for (int d = 0; d < 6; d++) {
Hex t = from.neighbor(d);
if (isEmpty(t)) {
if (canSlide(from, t)) out.add(t);
} else {
out.add(t); // 爬到对方棋子上面，允许
}
}
}
/** 蚱蜢：沿 6 条直线，跳过连续棋子后落到第一个空格。 */
private void grasshopperMoves(Hex from, List<Hex> out) {
for (int d = 0; d < 6; d++) {
Hex cur = from.neighbor(d);
int jumped = 0;
while (!isEmpty(cur)) {
cur = cur.neighbor(d);
jumped++;
if (jumped > 30) break; // 防御性上限
}
if (jumped > 0 && isEmpty(cur)) out.add(cur);
}
}
/** 蜘蛛：正好 3 步，且每步都必须合法滑动，三步不能重复落点。 */
private void spiderMoves(Hex from, List<Hex> out) {
Set<Long> visited = new HashSet<>();
Set<Long> results = new HashSet<>();
spiderDfs(from, from, 0, visited, results);
for (long k : results) {
if (k != from.key()) out.add(Hex.unpack(k));
}
}
private void spiderDfs(Hex start, Hex cur, int steps, Set<Long> visited, Set<Long> results) {
if (steps == 3) {
if (!cur.equals(start)) results.add(cur.key());
return;
}
for (int d = 0; d < 6; d++) {
Hex t = cur.neighbor(d);
if (!isEmpty(t)) continue;
if (t.equals(start)) continue;
if (visited.contains(t.key())) continue;
if (!canSlide(cur, t)) continue;
// 每步单独验证连通性：中途也不允许分裂
if (!staysConnectedAfterMove(cur, t)) continue;
visited.add(t.key());
spiderDfs(start, t, steps + 1, visited, results);
visited.remove(t.key());
}
}
/** 蚂蚁：沿外围滑动任意步，不能穿越被夹死的点。 */
private void antMoves(Hex from, List<Hex> out) {
Set<Long> seen = new HashSet<>();
ArrayDeque<Hex> queue = new ArrayDeque<>();
queue.add(from);
seen.add(from.key());
while (!queue.isEmpty()) {
Hex cur = queue.poll();
for (int d = 0; d < 6; d++) {
Hex t = cur.neighbor(d);
if (!isEmpty(t)) continue;
if (seen.contains(t.key())) continue;
if (!canSlide(cur, t)) continue;
if (!staysConnectedAfterMove(from, t)) continue; // 以原始起点判断整体连通
seen.add(t.key());
queue.add(t);
if (!t.equals(from)) out.add(t);
}
}
}
/** 只读视图：供评估与搜索遍历。 */
public List<Map.Entry<Long, List<Piece>>> entries() {
return new ArrayList<>(cells.entrySet());
}
/** 某格的棋子栈副本，避免外部直接改动内部状态。 */
public List<Piece> stackAt(Hex h) {
List<Piece> st = cells.get(h.key());
return st == null ? List.of() : new ArrayList<>(st);
}
/** 备份所有内部状态（用于构造克隆时的精确还原）。 */
Map<Long, List<Piece>> snapshot() {
Map<Long, List<Piece>> copy = new HashMap<>();
for (Map.Entry<Long, List<Piece>> e : cells.entrySet()) {
copy.put(e.getKey(), new ArrayList<>(e.getValue()));
}
return copy;
}
/** 直接注入内部状态（克隆专用，调用方需保证与 reserve/queenPlaced 一致）。 */
void restore(Map<Long, List<Piece>> data, int[][] reserveCopy, boolean[] queenCopy, int moves) {
cells.clear();
for (Map.Entry<Long, List<Piece>> e : data.entrySet()) {
cells.put(e.getKey(), new ArrayList<>(e.getValue()));
}
for (int p = 0; p < 2; p++) {
System.arraycopy(reserveCopy[p], 0, reserve[p], 0, reserve[p].length);
}
System.arraycopy(queenCopy, 0, queenPlaced, 0, queenPlaced.length);
this.moveCount = moves;
}
int[][] reserveSnapshot() {
int[][] copy = new int[2][];
for (int p = 0; p < 2; p++) copy[p] = reserve[p].clone();
return copy;
}
boolean[] queenSnapshot() { return queenPlaced.clone(); }
/** 执行移动：把 from 的顶层棋子移到 to。返回是否成功。 */
public boolean move(Hex from, Hex to) {
if (isEmpty(from)) return false;
if (!legalMoves(from).contains(to)) return false;
List<Piece> src = cells.get(from.key());
Piece p = src.remove(src.size() - 1);
if (src.isEmpty()) cells.remove(from.key());
cells.computeIfAbsent(to.key(), k -> new ArrayList<>()).add(p);
moveCount++;
return true;
}
}
6.4 评估函数
package com.example.hive;
import java.util.List;
import java.util.Map;
/**
* 静态评估：正值利好玩家 0。
* 分量：双方蚁后自由度、双方机动性、蚂蚁留手（后期弹性）。
*/
public final class HiveEvaluator {
public static int evaluate(HiveBoard board, int me) {
Hex myQueen = findQueen(board, me);
Hex oppQueen = findQueen(board, 1 - me);
int score = 0;
score += queenFreedom(board, myQueen) * 60;
score -= queenFreedom(board, oppQueen) * 60;
score += mobility(board, me) * 4;
score -= mobility(board, 1 - me) * 4;
score += board.reserveOf(me, Bug.ANT) * 3;
score -= board.reserveOf(1 - me, Bug.ANT) * 3;
return score;
}
/** 蚁后周围空位数；0 表示已被完全围死。未下场时返回 6（视为安全）。 */
public static int queenFreedom(HiveBoard board, Hex queen) {
if (queen == null) return 6;
int free = 0;
for (int d = 0; d < 6; d++) {
if (board.isEmpty(queen.neighbor(d))) free++;
}
return free;
}
/** 一方所有棋子的合法移动总数。这是评估里最贵的一项，需注意搜索开销。 */
private static int mobility(HiveBoard board, int player) {
int sum = 0;
for (Map.Entry<Long, List<Piece>> e : board.entries()) {
Hex h = Hex.unpack(e.getKey());
if (board.topOwner(h) != player) continue;
sum += board.legalMoves(h).size();
}
return sum;
}
public static Hex findQueen(HiveBoard board, int player) {
for (Map.Entry<Long, List<Piece>> e : board.entries()) {
Hex h = Hex.unpack(e.getKey());
Piece p = board.topPiece(h);
if (p != null && p.owner == player && p.bug == Bug.QUEEN) return h;
}
return null;
}
}
6.5 置换表与 Zobrist
package com.example.hive;
import java.util.List;
import java.util.Random;
/** Zobrist 哈希：格位置 × 栈层级 × 归属。 */
public final class Zobrist {
private static final Random RND = new Random(20261027L);
private static final long[] CELL = new long[4096];
private static final long[] OWNER = new long[2];
private static final long SIDE;
static {
for (int i = 0; i < CELL.length; i++) CELL[i] = RND.nextLong();
OWNER[0] = RND.nextLong();
OWNER[1] = RND.nextLong();
SIDE = RND.nextLong();
}
/**
* 哈希必须包含"格位置 + 栈层级 + 归属"。
* 只按位置哈希会把两种局面混淆：某格叠 1 枚甲虫 与 叠 2 枚甲虫
* 在规则上完全不同（前者只有一个顶层可动），碰撞会让置换表返回错误分数。
*/
public static long hash(HiveBoard board, int sideToMove) {
long h = 0;
for (var e : board.entries()) {
long k = e.getKey();
int idx = (int) (k & 0xFFF);
List<Piece> stack = e.getValue();
long cellHash = CELL[idx];
for (int level = 0; level < stack.size(); level++) {
cellHash ^= OWNER[stack.get(level).owner] + 0x9E3779B9L * (level + 1);
}
h ^= cellHash;
}
if (sideToMove == 0) h ^= SIDE;
return h;
}
}
package com.example.hive;
/** 简易置换表：键 + 深度 + 分数 + 标志。 */
public final class TranspositionTable {
public static final byte EXACT = 0, LOWER = 1, UPPER = 2;
private static final int SIZE = 1 << 18;
private static final int MASK = SIZE - 1;
private final long[] keys = new long[SIZE];
private final int[] scores = new int[SIZE];
private final byte[] depths = new byte[SIZE];
private final byte[] flags = new byte[SIZE];
private final boolean[] used = new boolean[SIZE];
private long hits, probes;
public boolean probe(long key, int depth, int alpha, int beta, int[] out) {
probes++;
int i = (int) (key & MASK);
if (!used[i] || keys[i] != key || depths[i] < depth) return false;
hits++;
int s = scores[i];
byte f = flags[i];
if (f == EXACT) { out[0] = s; return true; }
if (f == LOWER && s >= beta) { out[0] = s; return true; }
if (f == UPPER && s <= alpha) { out[0] = s; return true; }
return false;
}
public void store(long key, int depth, int score, byte flag) {
int i = (int) (key & MASK);
if (used[i] && keys[i] == key && depths[i] > depth) return;
keys[i] = key;
scores[i] = score;
depths[i] = (byte) depth;
flags[i] = flag;
used[i] = true;
}
public double hitRate() {
return probes == 0 ? 0 : hits * 100.0 / probes;
}
}
6.6 搜索引擎
package com.example.hive;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
/**
* Alpha-Beta + 置换表。
* 动作空间 = 放置（消耗后备）+ 移动（滑动/跳跃）。
* 关键约定：Action 必须自带 owner，否则在搜索里无法正确重放归属。
*/
public final class HiveEngine {
private final TranspositionTable tt = new TranspositionTable();
private int nodes = 0;
public int nodes() { return nodes; }
public double hitRate() { return tt.hitRate(); }
/** 一个动作：放置或移动，均携带执行方 owner。 */
public static final class Action {
public final boolean isPlace;
public final Hex from;
public final Hex to;
public final Bug bug;
public final int owner;
private Action(boolean isPlace, Hex from, Hex to, Bug bug, int owner) {
this.isPlace = isPlace;
this.from = from;
this.to = to;
this.bug = bug;
this.owner = owner;
}
public static Action place(Hex to, Bug bug, int owner) {
return new Action(true, null, to, bug, owner);
}
public static Action move(Hex from, Hex to, int owner) {
return new Action(false, from, to, null, owner);
}
@Override
public String toString() {
return isPlace ? ("放" + bug.cn + "到" + to) : ("移" + from + "→" + to);
}
}
/** 生成当前一方的全部动作。 */
public List<Action> generate(HiveBoard board, int side) {
List<Action> out = new ArrayList<>();
// 1) 放置动作：先集中算一次合法空格，避免每个虫种重复枚举
List<Hex> targets = placementTargets(board, side);
for (Bug b : Bug.values()) {
if (board.reserveOf(side, b) <= 0) continue;
for (Hex h : targets) {
out.add(Action.place(h, b, side));
}
}
// 2) 移动动作
for (Map.Entry<Long, List<Piece>> e : board.entries()) {
Hex from = Hex.unpack(e.getKey());
if (board.topOwner(from) != side) continue;
for (Hex to : board.legalMoves(from)) {
out.add(Action.move(from, to, side));
}
}
return out;
}
/** 放置目标：所有与己方相邻、且不与对方相邻的空格。 */
private List<Hex> placementTargets(HiveBoard board, int side) {
List<Hex> out = new ArrayList<>();
if (board.size() == 0) {
out.add(new Hex(0, 0));
return out;
}
Set<Long> seen = new HashSet<>();
for (Map.Entry<Long, List<Piece>> e : board.entries()) {
Hex h = Hex.unpack(e.getKey());
for (int d = 0; d < 6; d++) {
Hex n = h.neighbor(d);
if (!board.isEmpty(n) || !seen.add(n.key())) continue;
if (board.canPlace(n, side)) out.add(n);
}
}
return out;
}
/** 执行动作（就地修改）。 */
public void apply(HiveBoard board, Action a) {
if (a.isPlace) {
board.place(a.to, new Piece(a.bug, a.owner));
} else {
board.move(a.from, a.to);
}
}
/** 顶层搜索：返回最优动作。 */
public Action best(HiveBoard board, int side, int depth) {
List<Action> acts = generate(board, side);
if (acts.isEmpty()) return null;
Action bestAct = acts.get(0);
int bestScore = Integer.MIN_VALUE + 1;
int alpha = Integer.MIN_VALUE + 1;
int beta = Integer.MAX_VALUE - 1;
for (Action a : acts) {
HiveBoard copy = cloneBoard(board);
apply(copy, a);
// 进入对手视角，取负；根节点保持全窗口以得到精确值
int score = -alphaBeta(copy, 1 - side, depth - 1, -beta, -alpha);
if (score > bestScore) {
bestScore = score;
bestAct = a;
}
if (score > alpha) alpha = score;
}
return bestAct;
}
/** 负极大值形式的 Alpha-Beta。分数始终相对 sideToMove。 */
private int alphaBeta(HiveBoard board, int sideToMove, int depth, int alpha, int beta) {
nodes++;
// 终局：任一蚁后被完全围死
Hex q0 = HiveEvaluator.findQueen(board, 0);
Hex q1 = HiveEvaluator.findQueen(board, 1);
if (q0 != null && HiveEvaluator.queenFreedom(board, q0) == 0) {
return sideToMove == 0 ? (-90000 + depth) : (90000 - depth);
}
if (q1 != null && HiveEvaluator.queenFreedom(board, q1) == 0) {
return sideToMove == 1 ? (-90000 + depth) : (90000 - depth);
}
if (depth <= 0) {
return HiveEvaluator.evaluate(board, sideToMove);
}
long key = Zobrist.hash(board, sideToMove);
int[] cached = new int[1];
if (tt.probe(key, depth, alpha, beta, cached)) return cached[0];
List<Action> acts = generate(board, sideToMove);
if (acts.isEmpty()) return -90000 + depth;
int origAlpha = alpha;
int best = Integer.MIN_VALUE + 1;
for (Action a : acts) {
HiveBoard copy = cloneBoard(board);
apply(copy, a);
int score = -alphaBeta(copy, 1 - sideToMove, depth - 1, -beta, -alpha);
if (score > best) best = score;
if (score > alpha) alpha = score;
if (alpha >= beta) break; // 剪枝
}
byte flag = TranspositionTable.EXACT;
if (best <= origAlpha) flag = TranspositionTable.UPPER;
else if (best >= beta) flag = TranspositionTable.LOWER;
tt.store(key, depth, best, flag);
return best;
}
/**
* 深拷贝棋盘。
* 直接用 place() 重建会丢失后备池与蚁后标记（因为 place 会扣减），
* 所以这里用 snapshot/restore 精确复制内部状态。
*/
public static HiveBoard cloneBoard(HiveBoard src) {
HiveBoard copy = new HiveBoard();
copy.restore(src.snapshot(), src.reserveSnapshot(), src.queenSnapshot(), src.moveCount());
return copy;
}
}
package com.example.hive;
import java.util.List;
public class Main {
/** perft：统计叶子动作数，用于校验着法生成（尤其滑动判定）是否正确。 */
static long perft(HiveBoard board, int side, int depth) {
if (depth == 0) return 1;
HiveEngine engine = new HiveEngine();
List<HiveEngine.Action> acts = engine.generate(board, side);
if (acts.isEmpty()) return 0;
long total = 0;
for (HiveEngine.Action a : acts) {
HiveBoard copy = HiveEngine.cloneBoard(board);
engine.apply(copy, a);
total += perft(copy, 1 - side, depth - 1);
}
return total;
}
public static void main(String[] args) {
// 手工摆一个开局：双方各一蚁后 + 若干虫子，便于观察滑动判定
HiveBoard board = new HiveBoard();
board.place(new Hex(0, 0), new Piece(Bug.QUEEN, 0));
board.place(new Hex(1, 0), new Piece(Bug.BEETLE, 1));
board.place(new Hex(0, 1), new Piece(Bug.ANT, 0));
board.place(new Hex(1, -1), new Piece(Bug.ANT, 1));
System.out.println("棋盘格数: " + board.size());
for (Hex h : List.of(new Hex(0, 0), new Hex(1, 0), new Hex(0, 1), new Hex(1, -1))) {
List<Hex> mv = board.legalMoves(h);
System.out.printf("格 %s 顶层=%-8s 合法移动数=%d %s%n",
h, board.topPiece(h), mv.size(), mv);
}
System.out.println("\nperft(1)=" + perft(board, 0, 1));
System.out.println("perft(2)=" + perft(board, 0, 2));
// 自对弈演示
HiveEngine engine = new HiveEngine();
int side = 0;
for (int ply = 0; ply < 30; ply++) {
HiveEngine.Action a = engine.best(board, side, 2);
if (a == null) {
System.out.println("无合法动作，结束");
break;
}
engine.apply(board, a);
if (ply < 8) System.out.printf("第%d手 玩家%d %s%n", ply + 1, side, a);
side = 1 - side;
}
System.out.printf("%n搜索节点=%d 置换表命中率=%.1f%% 棋盘格数=%d%n",
engine.nodes(), engine.hitRate(), board.size());
}
}
七、复杂度分析
七、复杂度分析
- 滑动判定
canSlide：固定 6 次邻居检查，O(1)。 - 连通性校验：一次 BFS，
O(N + E) = O(N)，N为棋盘格数（≤ 30）。每次legalMoves对每个候选目标做一次校验，总计O(K·N)，K为候选数（≤ 6~30）。用 Tarjan 割点可降到O(N)一次遍历覆盖所有候选，但实现复杂度与出错风险明显上升——在N ≤ 30的实际规模下，BFS 的常数更小。 - 蚂蚁移动：本质是带上连通性约束的 BFS，
O(N²)最坏（每个可达格都要做一次连通性校验）。 - Alpha-Beta：分支因子约为”放置数 + 移动数”，实测中局约 30~60。加上置换表后，有效分支因子可压到约 8~12。深度 3 的搜索在数百毫秒内完成。
- 空间：棋盘
O(N)，置换表固定2^18 × (8+4+1+1+1)字节 ≈ 4 MB。
八、小结
蜂巢棋把三个容易被低估的工程细节摆在明面上：
- 滑动的几何本质是”跨棱有空隙”，用”是否存在同时邻接两端的空格”来判定，比用方向索引配对更不容易写错。
- 连通性是硬约束，且必须在每一步都验证（蜘蛛的三步中间也要验证），否则会产生非法分裂局面。
- 幂等棋子的置换爆炸必须靠 Zobrist + 置换表压制，而哈希要包含归属与堆叠层级，否则会混淆不同局面。
搜索本身不难，难的是”合法性引擎不出漏洞”——一个错误的 canSlide 会让整棵搜索树在错误的着法空间里做最优决策，结果完全不可信。
