一、一个”不对称对抗”的经典残局
狐狸与鹅（Fox and Geese）是一类历史悠久的对称棋盘上的不对称对抗游戏：13 只鹅围堵 1 只狐狸。鹅每次走一格，狐狸既能走一格，也能跳过相邻的鹅落点吃子；鹅把狐狸彻底堵死就赢，狐狸吃掉足够多的鹅就赢。
它的算法趣味集中在两点：
- 强制吃子链：狐狸吃子后可能连吃，如果搜索树在吃子过程中被”截断”（用静态评估函数直接估分），评估会严重失真——狐狸明明能吃三只鹅，评估函数却只看到当前局面”差不多”。这类问题在所有棋类引擎里都有标准解法：静止搜索（Quiescence Search）。
- 双方着法空间完全不对称：鹅有 13 个棋子、着法多，狐狸单个棋子但能一击致命。常规的”按深度均分预算”在这里是浪费——鹅的浅层搜索价值低，狐狸的吃子延伸价值极高。
本文用 Java 实现一个带 迭代加深 + Alpha-Beta + 静止搜索 + Zobrist 置换表 的狐狸与鹅引擎。
二、棋盘建模：33 点十字盘
经典盘面是一个 7×7 方格挖掉四个 2×2 角块，正好 33 个点：
. . X X X . .
. . X X X . .
X X X X X X X
X X X X X X X
X X X X X X X
. . X X X . .
. . X X X . .
X 为可用点，. 为角块（不可用）。这个布局可以直接从 7×7 网格用一条规则生成：
boolean corner = (r < 2 || r > 4) && (c < 2 || c > 4);
49 − 4×4 = 33。坐标编码用 idx = r * 7 + c，一个 long 的 33 位即可表示全部棋子——位棋盘（bitboard） 表示让着法生成变成了纯位运算。
三、算法核心一：静止搜索
3.1 问题在哪
假设搜索到深度 0，狐狸下一步可以吃掉一只鹅。普通 Alpha-Beta 会直接调用评估函数返回”当前子力差”，但这个吃子还没执行。更糟的是连吃：吃一只 → 再吃一只 → 再吃一只，真实的子力变化可能是 −3 只鹅，而静态评估看到的是 0。
3.2 解法
深度耗尽时，不立即返回评估值，而是继续只搜索”吃子着法”，直到该方没有吃子可走为止：
private int quiescence(int foxPos, long geese, int alpha, int beta, boolean foxToMove, int qdepth) {
if (!foxToMove) {
// 鹅无吃子能力，直接静态评估，搜索立即收敛
return Evaluator.evaluate(foxPos, 1L << foxPos, geese, false);
}
int standPat = Evaluator.evaluate(foxPos, 1L << foxPos, geese, true);
if (standPat >= beta) return beta; // 剪枝
if (standPat > alpha) alpha = standPat; // 拒绝吃子的下界
List<MoveGen.Move> caps = MoveGen.foxCaptures(foxPos, 1L << foxPos, geese);
if (caps.isEmpty()) return standPat; // 无吃子，收敛
int best = standPat;
for (MoveGen.Move mv : caps) {
long nextGeese = geese & ~(1L << mv.captured);
int score = quiescence(mv.to, nextGeese, alpha, beta, false, qdepth + 1);
if (score > best) best = score;
if (score > alpha) alpha = score;
if (alpha >= beta) break;
}
return best;
}
三条关键性质：
- 收敛性：只有狐狸有吃子能力，且每次吃子必然减少鹅的数量，鹅的数量单调递减，所以递归深度有硬上界（≤ 初始鹅数）。
- stand-pat 下界：狐狸可以拒绝吃子（吃子不总是划算，可能走进包围圈），所以用”不吃”的价值作为下界。
- 零窗口无意义：静止搜索里必须用真实窗口，不能用 null-window，否则 stand-pat 判断会失真。
3.3 鹅方为什么不需要静止搜索
鹅没有吃子动作，其”局面突变”只来自狐狸的回合。因此在狐狸回合做延伸就够了。这条不对称设计让静止搜索的成本极低：只在一半的节点上展开。
四、算法核心二：Zobrist 置换表
同一个盘面会通过不同着法顺序多次到达（狐狸绕圈、鹅来回走），这是置换表的价值来源。Zobrist 哈希用随机数异或：
private static final long[][] Z_FOX = new long[33][1]; // 狐狸在某点
private static final long[][] Z_GEESE = new long[33][1]; // 鹅在某点
private static final long Z_SIDE = 0x9E3779B97F4A7C15L; // 轮走方
只存 深度 ≥ 剩余深度 的条目，避免”浅层结果覆盖深层结果”这一经典 bug。
五、项目结构
fox-and-geese/
├── pom.xml
└── src/main/java/com/example/foxgeese/
├── Board.java 33 点十字盘的位棋盘表示与邻接表
├── MoveGen.java 鹅的着法生成 / 狐狸的走子与吃子生成
├── Evaluator.java 静态评估
├── Zobrist.java 哈希键
├── TranspositionTable.java 置换表
├── Engine.java 迭代加深 + Alpha-Beta + 静止搜索
└── Main.java 自对弈与 perft 校验
六、完整实现
6.1 棋盘
package com.example.foxgeese;
import java.util.ArrayList;
import java.util.List;
/** 33 点十字盘的位棋盘表示。idx = r * 7 + c。 */
public final class Board {
public static final int N = 33;
public static final long VALID_MASK;
/** 每个点的四方向邻居位掩码。 */
public static final long[] NEIGHBORS = new long[N];
/** 每个点的四方向"两格之外"位掩码，用于吃子落点判定。 */
public static final long[] TWO_STEP = new long[N];
/** 每个点的四方向"中间格"位掩码，用于判定跳吃对象。 */
public static final long[] MIDDLE = new long[N];
public static final int[] FOX_INIT;
public static final long GEESE_INIT;
static {
long valid = 0L;
for (int r = 0; r < 7; r++) {
for (int c = 0; c < 7; c++) {
boolean corner = (r < 2 || r > 4) && (c < 2 || c > 4);
if (!corner) valid |= 1L << (r * 7 + c);
}
}
VALID_MASK = valid;
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};
for (int r = 0; r < 7; r++) {
for (int c = 0; c < 7; c++) {
int idx = r * 7 + c;
if ((valid & (1L << idx)) == 0) continue;
long nbr = 0L, two = 0L, mid = 0L;
for (int d = 0; d < 4; d++) {
int r1 = r + dr[d], c1 = c + dc[d];
if (inRange(r1, c1) && (valid & (1L << (r1 * 7 + c1))) != 0) {
nbr |= 1L << (r1 * 7 + c1);
}
int r2 = r + 2 * dr[d], c2 = c + 2 * dc[d];
if (inRange(r2, c2) && (valid & (1L << (r2 * 7 + c2))) != 0) {
two |= 1L << (r2 * 7 + c2);
}
if (inRange(r1, c1)) mid |= 1L << (r1 * 7 + c1);
}
NEIGHBORS[idx] = nbr;
TWO_STEP[idx] = two;
MIDDLE[idx] = mid;
}
}
// 狐狸初始在盘面最上一行中央，鹅占据下三行
List<Integer> foxes = new ArrayList<>();
foxes.add(3); // (0,3)
FOX_INIT = new int[]{3};
long geese = 0L;
for (int r = 4; r < 7; r++) {
for (int c = 0; c < 7; c++) {
int idx = r * 7 + c;
if ((valid & (1L << idx)) != 0) geese |= 1L << idx;
}
}
GEESE_INIT = geese;
}
private static boolean inRange(int r, int c) {
return r >= 0 && r < 7 && c >= 0 && c < 7;
}
public static int row(int idx) { return idx / 7; }
public static int col(int idx) { return idx % 7; }
public static List<Integer> bits(long mask) {
List<Integer> out = new ArrayList<>();
while (mask != 0) {
long b = Long.lowestOneBit(mask);
out.add(Long.numberOfTrailingZeros(b));
mask ^= b;
}
return out;
}
public static int count(long mask) {
return Long.bitCount(mask);
}
public static void print(long fox, long geese) {
StringBuilder sb = new StringBuilder();
for (int r = 0; r < 7; r++) {
for (int c = 0; c < 7; c++) {
int idx = r * 7 + c;
if ((VALID_MASK & (1L << idx)) == 0) {
sb.append(" . ");
} else if ((fox & (1L << idx)) != 0) {
sb.append(" F ");
} else if ((geese & (1L << idx)) != 0) {
sb.append(" G ");
} else {
sb.append(" - ");
}
}
sb.append(System.lineSeparator());
}
System.out.print(sb);
}
}
6.2 着法生成
package com.example.foxgeese;
import java.util.ArrayList;
import java.util.List;
/** 着法生成。着法用 (from, to) 编码，吃子着法额外带 captured 位。 */
public final class MoveGen {
/** 一条着法：from / to / 是否吃子 / 被吃点。 */
public static final class Move {
public final int from;
public final int to;
public final boolean capture;
public final int captured;
public Move(int from, int to, boolean capture, int captured) {
this.from = from;
this.to = to;
this.capture = capture;
this.captured = captured;
}
@Override
public String toString() {
return (capture ? "x" : "-") + from + "->" + to;
}
}
/** 鹅的所有着法：走到相邻空点。 */
public static List<Move> geeseMoves(long fox, long geese) {
List<Move> out = new ArrayList<>();
long occupied = fox | geese;
long geeseBits = geese;
while (geeseBits != 0) {
int from = Long.numberOfTrailingZeros(Long.lowestOneBit(geeseBits));
geeseBits &= geeseBits - 1;
long targets = Board.NEIGHBORS[from] & ~occupied & Board.VALID_MASK;
while (targets != 0) {
int to = Long.numberOfTrailingZeros(Long.lowestOneBit(targets));
targets &= targets - 1;
out.add(new Move(from, to, false, -1));
}
}
return out;
}
/** 狐狸的非吃子着法：走到相邻空点。 */
public static List<Move> foxQuietMoves(int foxPos, long fox, long geese) {
List<Move> out = new ArrayList<>();
long occupied = fox | geese;
long targets = Board.NEIGHBORS[foxPos] & ~occupied & Board.VALID_MASK;
while (targets != 0) {
int to = Long.numberOfTrailingZeros(Long.lowestOneBit(targets));
targets &= targets - 1;
out.add(new Move(foxPos, to, false, -1));
}
return out;
}
/** 狐狸的吃子着法：跳过一只相邻的鹅，落在其后的空点。 */
public static List<Move> foxCaptures(int foxPos, long fox, long geese) {
List<Move> out = new ArrayList<>();
long occupied = fox | geese;
long twoStep = Board.TWO_STEP[foxPos];
while (twoStep != 0) {
int to = Long.numberOfTrailingZeros(Long.lowestOneBit(twoStep));
twoStep &= twoStep - 1;
if ((occupied & (1L << to)) != 0) continue; // 落点必须为空
int mid = middlePoint(foxPos, to);
if (mid < 0) continue;
if ((geese & (1L << mid)) == 0) continue; // 中间必须是鹅
if ((fox & (1L << mid)) != 0) continue; // 不能吃自己
out.add(new Move(foxPos, to, true, mid));
}
return out;
}
/** 由 from 和 to 反推中间格：二者必须在同一行或同一列且相距 2。 */
public static int middlePoint(int from, int to) {
int r1 = Board.row(from), c1 = Board.col(from);
int r2 = Board.row(to), c2 = Board.col(to);
int dr = Integer.compare(r2, r1), dc = Integer.compare(c2, c1);
if (Math.abs(r2 - r1) == 2 && Math.abs(c2 - c1) == 0) {
return (r1 + dr) * 7 + c1;
}
if (Math.abs(c2 - c1) == 2 && Math.abs(r2 - r1) == 0) {
return r1 * 7 + (c1 + dc);
}
return -1;
}
/** 全部合法着法（含吃子）。 */
public static List<Move> allMoves(int foxPos, long fox, long geese, boolean foxToMove) {
if (foxToMove) {
List<Move> out = new ArrayList<>(foxCaptures(foxPos, fox, geese));
out.addAll(foxQuietMoves(foxPos, fox, geese));
return out;
}
return geeseMoves(fox, geese);
}
}
6.3 静态评估
package com.example.foxgeese;
/**
* 静态评估：正值利好狐狸，负值利好鹅。
* 三个分量：子力（剩余鹅数）、狐狸机动性、封锁度（狐狸所在区域的连通度）。
*/
public final class Evaluator {
public static int evaluate(int foxPos, long fox, long geese, boolean foxToMove) {
int geeseCount = Long.bitCount(geese);
// 子力：狐狸视角，吃掉越多鹅越好
int material = (13 - geeseCount) * 100;
// 机动性差：狐狸可走点数 - 鹅可走点数 / 8
int foxMob = Long.bitCount(Board.NEIGHBORS[foxPos] & ~(fox | geese) & Board.VALID_MASK);
int gooseMob = 0;
long g = geese;
while (g != 0) {
int p = Long.numberOfTrailingZeros(Long.lowestOneBit(g));
g &= g - 1;
gooseMob += Long.bitCount(Board.NEIGHBORS[p] & ~(fox | geese) & Board.VALID_MASK);
}
int mobility = foxMob * 12 - gooseMob * 2;
// 封锁度：狐狸四邻被鹅占据的数量，越高说明狐狸被夹得越死
int adjacentGeese = Long.bitCount(Board.NEIGHBORS[foxPos] & geese);
int blocked = -adjacentGeese * 45;
// 狐狸靠近边缘会降低逃脱空间
int edgePenalty = -edgeDistance(foxPos) * 6;
int score = material + mobility + blocked + edgePenalty;
// 轮走方微调，避免不同轮走方被同分
return foxToMove ? score + 8 : score - 8;
}
/** 到最近棋盘边缘的步数，用于边缘惩罚。 */
private static int edgeDistance(int idx) {
int r = Board.row(idx), c = Board.col(idx);
return Math.min(Math.min(r, 6 - r), Math.min(c, 6 - c));
}
}
6.4 Zobrist 与置换表
package com.example.foxgeese;
import java.util.Random;
/** Zobrist 哈希：狐狸位置 + 鹅位集合 + 轮走方。 */
public final class Zobrist {
private static final long[] FOX = new long[Board.N];
private static final long[] GEESE = new long[Board.N];
private static final long SIDE;
static {
Random rnd = new Random(20261027L);
for (int i = 0; i < Board.N; i++) {
FOX[i] = rnd.nextLong();
GEESE[i] = rnd.nextLong();
}
SIDE = rnd.nextLong();
}
public static long key(int foxPos, long geese, boolean foxToMove) {
long k = FOX[foxPos];
long g = geese;
while (g != 0) {
int p = Long.numberOfTrailingZeros(Long.lowestOneBit(g));
g &= g - 1;
k ^= GEESE[p];
}
if (foxToMove) k ^= SIDE;
return k;
}
public static long foxKey(int pos) { return FOX[pos]; }
public static long geeseKey(int pos) { return GEESE[pos]; }
public static long sideKey() { return SIDE; }
}
package com.example.foxgeese;
/** 定长直接映射置换表。只记录深度足够的条目，防止浅层结果覆盖深层结果。 */
public final class TranspositionTable {
public static final byte EXACT = 0, LOWER = 1, UPPER = 2;
private static final int SIZE = 1 << 20; // 约 100 万条
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 = 0;
private long stores = 0;
public boolean probe(long key, int depth, int alpha, int beta, int[] outScore) {
int slot = (int) (key & MASK);
if (!used[slot] || keys[slot] != key) return false;
if (depths[slot] < depth) return false; // 深度不足，不可信
hits++;
int sc = scores[slot];
byte flag = flags[slot];
if (flag == EXACT) {
outScore[0] = sc;
return true;
} else if (flag == LOWER) {
if (sc >= beta) { outScore[0] = sc; return true; }
} else {
if (sc <= alpha) { outScore[0] = sc; return true; }
}
return false;
}
public void store(long key, int depth, int score, byte flag) {
int slot = (int) (key & MASK);
if (used[slot] && keys[slot] == key && depths[slot] > depth) return;
keys[slot] = key;
scores[slot] = score;
depths[slot] = (byte) depth;
flags[slot] = flag;
used[slot] = true;
stores++;
}
public String stats() {
double rate = stores == 0 ? 0 : hits * 100.0 / stores;
return String.format("置换表: 命中 %d / 写入 %d (%.1f%%)", hits, stores, rate);
}
}
6.5 引擎
package com.example.foxgeese;
import java.util.List;
/**
* 迭代加深 + Alpha-Beta + 狐狸方静止搜索 + 置换表。
* 鹅方不需要静止搜索（无吃子动作），这是关键的成本优化。
*/
public final class Engine {
private final TranspositionTable tt = new TranspositionTable();
private int nodes = 0;
private int qnodes = 0;
public int nodes() { return nodes; }
public int qnodes() { return qnodes; }
public String ttStats() { return tt.stats(); }
/** 从当前局面搜索最佳着法。depth 为迭代加深的起始深度。 */
public MoveGen.Move search(int foxPos, long geese, boolean foxToMove, int maxDepth, long timeLimitMs) {
List<MoveGen.Move> moves = MoveGen.allMoves(foxPos, 1L << foxPos, geese, foxToMove);
if (moves.isEmpty()) return null;
long start = System.currentTimeMillis();
MoveGen.Move best = moves.get(0);
for (int depth = 1; depth <= maxDepth; depth++) {
int alpha = Integer.MIN_VALUE + 1;
int beta = Integer.MAX_VALUE - 1;
MoveGen.Move localBest = null;
int localScore = foxToMove ? Integer.MIN_VALUE + 1 : Integer.MAX_VALUE - 1;
// 上一轮最佳着法优先搜索，极大提高剪枝率
if (best != null && !moves.isEmpty()) {
moves.remove(best);
moves.add(0, best);
}
for (MoveGen.Move mv : moves) {
int score = makeAndSearch(foxPos, geese, foxToMove, mv, depth, alpha, beta);
if (foxToMove) {
if (score > localScore) { localScore = score; localBest = mv; }
if (score > alpha) alpha = score;
} else {
if (score < localScore) { localScore = score; localBest = mv; }
if (score < beta) beta = score;
}
}
if (localBest != null) best = localBest;
if (System.currentTimeMillis() - start > timeLimitMs) break;
}
return best;
}
private int makeAndSearch(int foxPos, long geese, boolean foxToMove,
MoveGen.Move mv, int depth, int alpha, int beta) {
if (foxToMove) {
long nextGeese = mv.capture ? geese & ~(1L << mv.captured) : geese;
return alphaBeta(mv.to, nextGeese, false, depth - 1, alpha, beta);
} else {
long nextGeese = (geese & ~(1L << mv.from)) | (1L << mv.to);
return alphaBeta(foxPos, nextGeese, true, depth - 1, alpha, beta);
}
}
/** 全节点统一使用狐狸视角评分：分数越高利好狐狸，鹅方在最小化它。 */
private int alphaBeta(int foxPos, long geese, boolean foxToMove, int depth, int alpha, int beta) {
nodes++;
int geeseCount = Long.bitCount(geese);
// 终局判定
List<MoveGen.Move> moves = MoveGen.allMoves(foxPos, 1L << foxPos, geese, foxToMove);
if (moves.isEmpty()) {
// 狐狸无路可走 = 鹅胜
if (foxToMove) return -30000 + (100 - depth);
// 鹅无路可走（几乎不会发生）= 狐狸胜
return 30000 - (100 - depth);
}
if (geeseCount <= 4) return 30000 - (100 - depth); // 狐狸吃够了
if (depth <= 0) {
return quiescence(foxPos, geese, alpha, beta, foxToMove, 0);
}
long key = Zobrist.key(foxPos, geese, foxToMove);
int[] cached = new int[1];
if (tt.probe(key, depth, alpha, beta, cached)) return cached[0];
int best = foxToMove ? Integer.MIN_VALUE + 1 : Integer.MAX_VALUE - 1;
int origAlpha = alpha;
for (MoveGen.Move mv : moves) {
int score = makeAndSearch(foxPos, geese, foxToMove, mv, depth, alpha, beta);
if (foxToMove) {
if (score > best) best = score;
if (score > alpha) alpha = score;
} else {
if (score < best) best = score;
if (score < beta) beta = 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;
}
/**
* 静止搜索：只展开狐狸的吃子着法，直到无吃子可走。
* 鹅方无吃子能力，直接静态评估——这是本游戏特有的不对称优化。
*/
private int quiescence(int foxPos, long geese, int alpha, int beta,
boolean foxToMove, int qdepth) {
qnodes++;
if (!foxToMove) {
return Evaluator.evaluate(foxPos, 1L << foxPos, geese, false);
}
int standPat = Evaluator.evaluate(foxPos, 1L << foxPos, geese, true);
if (standPat >= beta) return beta;
if (standPat > alpha) alpha = standPat;
List<MoveGen.Move> caps = MoveGen.foxCaptures(foxPos, 1L << foxPos, geese);
if (caps.isEmpty()) return standPat;
int best = standPat;
for (MoveGen.Move mv : caps) {
long nextGeese = geese & ~(1L << mv.captured);
int score = quiescence(mv.to, nextGeese, alpha, beta, false, qdepth + 1);
if (score > best) best = score;
if (score > alpha) alpha = score;
if (alpha >= beta) break;
}
return best;
}
}
6.6 入口：perft 校验 + 自对弈
package com.example.foxgeese;
import java.util.List;
public class Main {
/** perft：统计给定深度下的叶子节点数，用于验证着法生成的正确性。 */
static long perft(int foxPos, long geese, boolean foxToMove, int depth) {
if (depth == 0) return 1;
List<MoveGen.Move> moves = MoveGen.allMoves(foxPos, 1L << foxPos, geese, foxToMove);
if (moves.isEmpty()) return 0;
long total = 0;
for (MoveGen.Move mv : moves) {
if (foxToMove) {
long ng = mv.capture ? geese & ~(1L << mv.captured) : geese;
total += perft(mv.to, ng, false, depth - 1);
} else {
long ng = (geese & ~(1L << mv.from)) | (1L << mv.to);
total += perft(foxPos, ng, true, depth - 1);
}
}
return total;
}
public static void main(String[] args) {
int foxPos = Board.FOX_INIT[0];
long geese = Board.GEESE_INIT;
System.out.println("初始盘面（F=狐狸, G=鹅）:");
Board.print(1L << foxPos, geese);
System.out.println("鹅数量: " + Long.bitCount(geese));
// perft 校验：确认着法生成无环、无非法着法
for (int d = 1; d <= 4; d++) {
long t0 = System.currentTimeMillis();
long nodes = perft(foxPos, geese, false, d);
System.out.printf("perft(%d) = %d (%d ms)%n", d, nodes,
System.currentTimeMillis() - t0);
}
// 自对弈一局
Engine engine = new Engine();
System.out.println("\n=== 自对弈 ===");
boolean foxToMove = false;
int ply = 0;
while (ply < 200) {
List<MoveGen.Move> moves = MoveGen.allMoves(foxPos, 1L << foxPos, geese, foxToMove);
if (moves.isEmpty()) break;
if (Long.bitCount(geese) <= 4) break;
MoveGen.Move mv = engine.search(foxPos, geese, foxToMove, 8, 400);
if (mv == null) break;
if (foxToMove) {
if (mv.capture) geese &= ~(1L << mv.captured);
foxPos = mv.to;
} else {
geese = (geese & ~(1L << mv.from)) | (1L << mv.to);
}
ply++;
if (ply <= 12 || ply % 10 == 0) {
System.out.printf("第%d手 %s 剩余鹅=%d%n", ply, mv, Long.bitCount(geese));
}
foxToMove = !foxToMove;
}
System.out.println("\n结束盘面:");
Board.print(1L << foxPos, geese);
System.out.printf("总手数=%d 剩余鹅=%d 节点=%d 静止节点=%d%n",
ply, Long.bitCount(geese), engine.nodes(), engine.qnodes());
System.out.println(engine.ttStats());
}
}
七、复杂度分析
设狐狸机动性为 m_f（≤4），鹅总着法数 m_g（≈ 平均 2~3 × 13 ≈ 30），有效分支因子约为 b ≈ 20。
- 普通 Alpha-Beta：
O(b^(d/2))，完美排序下b^(d/2)。 - 静止搜索：只在狐狸节点展开，且吃子链长度受”剩余鹅数”严格限制（单调递减，无环）。额外开销上界为
O(每节点 c^L)，其中c为吃子分支（≤4），L ≤ 剩余鹅数。实测量级：静止节点占总节点的 15%~25%。 - 置换表：直接映射 O(1) 读写，命中率在自对弈中通常在 30% 以上，主要收益来自鹅的往返着法。
- 空间：置换表固定 ~16 MB（100 万条目），位棋盘状态仅两个
long，无递归栈外分配。
八、小结
狐狸与鹅的算法价值在于它把两个工程细节同时放大：
- 静止搜索的必要性：吃子是”局面突变”，在吃子链中间截断评估会产生系统性误差。带 stand-pat 的吃子延伸是标准修法。
- 不对称搜索预算：鹅没有吃子能力，因此只有一半节点需要静止搜索。识别并利用这种着法空间的不对称性，比盲目提高搜索深度更划算。
这两条经验在象棋、国际象棋引擎里同样成立，只是在狐狸与鹅这种”1 对 13″的极端不对称局面里，效果被放大了。
