斗兽棋（Jungle / Dou Shou Qi）只有 7×9 个格子、16 枚棋子，看起来简单得不像需要算法。但它的状态空间并不小：棋子种类 8 种、每方各 8 枚、还要记录”谁吃掉了谁”，一盘棋的合法局面数以亿计。想在棋盘上做出绝对正确的 AI（不说”我觉得这步好”，而是”这步必胜/必败”），唯一可靠的办法是逆推分析（Retrograde Analysis）——先标记所有终局，然后反向往回推，像多米诺一样把每个局面的胜负标签扩散出去。
这套方法在棋类 AI 里叫”残局库（Endgame Tablebase）”，在博弈论里叫逆向归纳（Backward Induction）。本文将用 Java 完整实现一个可运行的斗兽棋逆推引擎，并讨论它在”层级克制”规则下的两处必须小心处理的地方。
一、规则摘要与状态编码
1.1 必要规则
为了聚焦算法，这里采用竞技斗兽棋的标准规则子集：
- 棋盘 7 列 × 9 行；红方在下三行，蓝方在上三行，中间三行是”河”。
- 棋子等级：象 8 > 狮 7 > 虎 6 > 豹 5 > 狼 4 > 狗 3 > 猫 2 > 鼠 1。
- 大吃小；鼠可以吃象（唯一跨级反制）；鼠下水后不能被陆上棋子吃，但可以被对方的鼠吃。
- 狮、虎可以横/竖跳河（河中有鼠时不可跳）。
- 进入对方兽穴即胜；吃光对方棋子也胜。
1.2 状态的最小编码
逆推需要把所有中间状态放进哈希表，因此编码必须紧凑。四类信息缺一不可：
- 每枚棋子的位置（16 枚，含被吃标记）；
- 轮到谁走（1 bit）；
- 狮虎跳河的通道是否被鼠堵住（可由鼠位置推导，不必单独存）。
用”每格 5 bit”的位置编码即可：0 表示被吃，1..63 表示格子。16 枚棋子 × 5 bit = 80 bit，超出 long，因此用两个 long 或一个 byte[] 作 key。
package com.example.jungle;
/** 棋子类型与归属 */
public enum PieceType {
ELEPHANT(8, "象"), LION(7, "狮"), TIGER(6, "虎"), LEOPARD(5, "豹"),
WOLF(4, "狼"), DOG(3, "狗"), CAT(2, "猫"), RAT(1, "鼠");
public final int rank;
public final String cn;
PieceType(int rank, String cn) { this.rank = rank; this.cn = cn; }
}
public class Piece {
public final int side; // 0=红, 1=蓝
public final PieceType type;
public int pos; // 0..62 合法格，-1 表示已被吃
public final int homeIndex; // 在 16 枚中的固定序号，用于编码
public Piece(int side, PieceType type, int pos, int homeIndex) {
this.side = side; this.type = type; this.pos = pos; this.homeIndex = homeIndex;
}
}
1.3 状态与哈希
package com.example.jungle;
import java.util.Arrays;
/** 不可变局面：棋子位置 + 走子方 */
public final class State {
public static final int COLS = 7, ROWS = 9;
final byte[] pos = new byte[16]; // 固定序号的棋子位置，-1 = 被吃
final byte side; // 0 or 1
public State(byte[] pos, byte side) {
System.arraycopy(pos, 0, this.pos, 0, 16);
this.side = side;
}
/** Zobrist 哈希：随机数表按 (棋子序号, 格子) 与走子方异或 */
private static final long[][] Z = new long[16][64];
private static final long Z_SIDE;
static {
java.util.Random rnd = new java.util.Random(0xC0FFEEL);
for (int i = 0; i < 16; i++) for (int j = 0; j < 64; j++) Z[i][j] = rnd.nextLong();
Z_SIDE = rnd.nextLong();
}
private long hash = 0L;
private boolean hashed = false;
public long hash() {
if (hashed) return hash;
long h = 0L;
for (int i = 0; i < 16; i++) h ^= Z[i][pos[i] + 1]; // +1 使 -1 落到 0 列
if (side == 1) h ^= Z_SIDE;
this.hash = h; this.hashed = true;
return h;
}
@Override public boolean equals(Object o) {
if (!(o instanceof State)) return false;
State s = (State) o;
return s.side == side && Arrays.equals(s.pos, pos);
}
@Override public int hashCode() { return Long.hashCode(hash()); }
}
注意：Zobrist 只用于快速索引，冲突时仍要靠
equals精确比较。逆推库规模可能上百万，HashMap的开销会成为瓶颈，生产版应换成开放寻址的自定义哈希表。
二、逆推分析的原理
2.1 三种标签
给每个局面打三种标签之一：
- WIN：轮到走子的一方存在一步，能走到对方的 LOSE 局面；
- LOSE：轮到走子的一方所有走法都走到对方的 WIN 局面；
- UNKNOWN：尚未确定（可能在循环中等同于和棋）。
2.2 逆向扩散的两个规则
从所有终局出发（终局对”刚走完这一步的人”来说是胜/负），反过来推：
- 若局面
s有一步走到 LOSE，则s是 WIN —— 一步定胜负。 - 若局面
s的所有子局面都是 WIN，则s是 LOSE —— 走投无路。
为了高效执行规则 2，给每个局面维护一个计数器 remaining[s] = 它还没被证明为 WIN 的子局面数。初始等于合法走法数；每当我们发现一个新 WIN 子局面，就给它所有前驱减 1；减到 0 即判定 LOSE。
这就是标准的 BFS 式逆推（Retrograde BFS）：入队的元素是”新确定标签的局面”，按层扩散。
package com.example.jungle;
import java.util.*;
public class RetrogradeSolver {
public static final byte WIN = 1, LOSE = -1, UNKNOWN = 0;
private final Map<State, Byte> label = new HashMap<>();
private final Map<State, Integer> remaining = new HashMap<>(); // 未证 WIN 的子局面计数
private final Deque<State> queue = new ArrayDeque<>();
/** 步骤1：枚举所有终局并标注 */
public void seedTerminals(List<State> terminals) {
for (State t : terminals) {
// 终局：上一手走子方获胜，因此"轮到走子的这一方"是 LOSE
label.put(t, LOSE);
queue.add(t);
}
}
/** 步骤2：逆推扩散 */
public void propagate() {
while (!queue.isEmpty()) {
State s = queue.poll();
byte lb = label.get(s);
if (lb == LOSE) {
// s 是 LOSE -> 所有前驱都是 WIN（前驱走一步即可到达 s）
for (State pred : predecessors(s)) {
if (label.getOrDefault(pred, UNKNOWN) != UNKNOWN) continue;
label.put(pred, WIN);
queue.add(pred);
}
} else if (lb == WIN) {
// s 是 WIN -> 前驱的"剩余计数"减一，减到 0 则前驱 LOSE
for (State pred : predecessors(s)) {
if (label.getOrDefault(pred, UNKNOWN) != UNKNOWN) continue;
int rem = remaining.computeIfAbsent(pred, k -> successors(k).size()) - 1;
remaining.put(pred, rem);
if (rem == 0) {
label.put(pred, LOSE);
queue.add(pred);
}
}
}
}
}
public byte query(State s) { return label.getOrDefault(s, UNKNOWN); }
}
2.3 关键难点：前驱从哪来
逆推要求枚举”能一步到达 s 的局面”。这不像正向搜索那样简单——你不能从 s 反推走法，而必须正向生成后反向登记。工程上有两种做法：
做法 A（枚举全部状态，建完整前驱表）：对每个可达局面正向生成子局面，登记 child -> parent 的反向边。代价是必须先枚举出全部可达状态，内存需求大。
做法 B（增量生成）：不预建前驱表，而是在 predecessors(s) 里现场生成：因为斗兽棋的走法是局部的（相邻格、跳河），可以从 s 出发”逆向应用每个可能的走法”——即把某枚棋子放回它可能来自的位置，并检查该局面是否合法。局部性让这种做法可行。
本文采用做法 B 的简化版：用”撤销一步走法”来生成前驱。
/** 撤销式前驱生成：对 s 中每枚棋子，尝试把它"放回"所有可能的来处 */
private List<State> predecessors(State s) {
List<State> out = new ArrayList<>(32);
byte mover = (byte) (1 - s.side); // 上一手是对方走的
for (int i = 0; i < 16; i++) {
if (s.pos[i] < 0) continue;
if (ownerOf(i) != mover) continue;
int to = s.pos[i];
for (int from : possibleOrigins(to)) {
byte[] np = s.pos.clone();
np[i] = (byte) from;
State cand = new State(np, mover);
if (!geomLegal(cand)) continue; // 落点合法性
// 若 to 处是吃子，则被吃的棋子需要"复活"到 to，这由 undoCapture 处理
out.add(cand);
}
}
// 再补充"吃子前驱"：假设 s 的某个空位原本有对方棋子被吃
out.addAll(capturePredecessors(s, mover));
return out;
}
capturePredecessors 需要额外处理”被吃棋子复活”，这是逆推里最容易出错的地方：吃子在正向是合并操作，在逆向是分裂操作，必须穷举所有可能”曾在目标格上被吃掉”的对方棋子。为了控制复杂度，实践中通常把”吃子”视作一个整体走法，用走法签名匹配而非逐枚盲试。
2.4 循环与和棋
斗兽棋存在循环（双方来回走子，类似象棋的长将）。逆推 BFS 跑完后，所有仍是 UNKNOWN 的局面就是循环区间内的局面：它们既不能被证明 WIN，也不能被证明 LOSE。工程上标为 DRAW（和棋/循环），并且这正是”AI 该避免危险局面”的信息来源——在实战里，UNKNOWN 局面通常意味着”小心，别走进对方的必胜区”。
/** 逆推结束后，将所有 UNKNOWN 视为循环和棋 */
public Map<State, Byte> finalizeDraws() {
Map<State, Byte> result = new HashMap<>(label);
// 未标记的局面 = 循环
return result;
}
三、完整的求解器骨架
把上面几块拼起来，就是一个可运行的逆推引擎：
package com.example.jungle;
import java.util.*;
public class Main {
public static void main(String[] args) {
BoardSetup setup = new BoardSetup();
List<State> terminals = setup.enumerateTerminals();
System.out.println("终局数 = " + terminals.size());
RetrogradeSolver solver = new RetrogradeSolver();
solver.seedTerminals(terminals);
long t0 = System.currentTimeMillis();
solver.propagate();
long ms = System.currentTimeMillis() - t0;
System.out.printf("逆推完成，耗时 %d ms%n", ms);
// 验证：查询一个已知必胜/必败局面
State s = setup.initialState();
byte lb = solver.query(s);
System.out.println("初始局面标签 = " +
(lb == RetrogradeSolver.WIN ? "WIN" : lb == RetrogradeSolver.LOSE ? "LOSE" : "DRAW/UNKNOWN"));
}
}
3.1 一个具体的”残局逆推”例子
全盘逆推对资源要求高，实战中更常用的是残局库：只对”棋子数 ≤ 4″的局面做逆推。这时状态数可以从亿级降到十万级，一次跑完缓存到磁盘，之后查询 O(1)。
/** 4 子残局：红方 2 子 vs 蓝方 2 子，穷举全部摆放后逆推 */
public class SmallEndgame {
private static final int RED_DEN = 3 * State.COLS + 3; // 红方兽穴（下三行中央）
private static final int BLUE_DEN = 5 * State.COLS + 3; // 蓝方兽穴（上三行中央）
/** 4 子摆法：C(63,4) 个格子组合 × C(4,2) 种归属划分 */
public static void build() {
RetrogradeSolver solver = new RetrogradeSolver();
List<State> terminals = new ArrayList<>();
int[] cells = new int[4];
for (int a = 0; a < 63; a++)
for (int b = a + 1; b < 63; b++)
for (int c = b + 1; c < 63; c++)
for (int d = c + 1; d < 63; d++) {
cells[0] = a; cells[1] = b; cells[2] = c; cells[3] = d;
// 4 个格子中选 2 个归红方（其余归蓝方）：共 6 种划分
for (int redMask = 0; redMask < 16; redMask++) {
if (Integer.bitCount(redMask) != 2) continue;
byte[] pos = new byte[16];
Arrays.fill(pos, (byte) -1);
// 约定：序号 0..7 为红方，8..15 为蓝方
int ri = 0, bi = 8;
for (int k = 0; k < 4; k++) {
if ((redMask & (1 << k)) != 0) pos[ri++] = (byte) cells[k];
else pos[bi++] = (byte) cells[k];
}
for (byte side = 0; side < 2; side++) {
State st = new State(pos, side);
if (isTerminal(st)) terminals.add(st);
}
}
}
System.out.println("4 子残局终局数 = " + terminals.size());
solver.seedTerminals(terminals);
solver.propagate();
}
/** 终局判定：任一方棋子进入对方兽穴 */
static boolean isTerminal(State s) {
for (int i = 0; i < 16; i++) {
if (s.pos[i] < 0) continue;
int den = (i < 8) ? BLUE_DEN : RED_DEN;
if (s.pos[i] == den) return true;
}
return false;
}
}
说明：
RetrogradeSolver里的successors/geomLegal/possibleOrigins属于棋规几何层，与逆推算法本身无关，本文只保留其签名。实现要点是：geomLegal检查落点是否在盘内、是否跨河违规（鼠入水/出水规则）、目标格是否为己方棋子；possibleOrigins只需返回落点的 4 邻域加上狮虎跳河的两个对岸格——局部性是这一步可行的前提，也是斗兽棋逆推比围棋容易得多的根本原因。
四、复杂度与工程权衡
| 维度 | 全盘逆推 | 4 子残局 |
|---|---|---|
| 状态数 | 10^8 量级 |
10^5 量级 |
| 内存 | 数 GB（需紧凑编码） | 几十 MB |
| 构建时间 | 小时级 | 分钟级 |
| 查询 | O(1) |
O(1) |
| 实用场景 | 学术/离线 | 对局中实时调用 |
三个决定性工程决策：
- 编码优先于算法。逆推的瓶颈几乎总是内存与哈希开销。
byte[16]每状态 16 字节，加上HashMap的桶开销约 48 字节，10^7状态就是 500 MB。把位置压成5 bit * 16 = 80 bit（两long）并自建开放寻址表，同样规模能降到约 200 MB。 - 分层逆推。不要一次搞全盘。先做 3 子、4 子、5 子的残局库，逐层递增，每层验证正确性；一旦某层出现逻辑错误（例如吃子复活处理不对），会在小规模上立刻暴露。
- UNKNOWN 不是失败。逆推跑完后剩下的 UNKNOWN 不是”没算出来”，而是有意义的结论——这些局面在完美对弈下进入循环。实战 AI 用它们做”避险”，比强行标注胜负更正确。
五、逆推与正向搜索的取舍
| 特性 | 逆推分析 | Alpha-Beta / MCTS |
|---|---|---|
| 结论强度 | 绝对正确（在给定规则与初始化下） | 启发式，有强弱但无保证 |
| 构建成本 | 一次性高 | 每步都低 |
| 适应规则变更 | 需重建整库 | 改评估函数即可 |
| 适合阶段 | 残局 | 中局/开局 |
| 内存 | 大 | 小 |
斗兽棋的实际 AI 常见做法是混合：开局/中局用 Alpha-Beta + 局面评估（活动性、棋子价值、兽穴距离），进入残局后切换到逆推库查询精确胜负。这个切换点由”剩余棋子数 ≤ 5″触发。工程上这是最划算的组合——把昂贵的精确计算用在真正需要精确的阶段。
六、总结
斗兽棋的”逆推分析”教会我们的，是一个比具体棋规更通用的思维模型：
- 先把终局写清楚。很多博弈算法失败不是因为搜索不深，而是终局定义含糊（什么算赢？什么算和？）。逆推要求你把终局枚举成显式列表，这一步逼迫规则精确化。
- 用”计数减到零”代替”遍历所有子局面”。
remaining计数器是逆推效率的核心——它把”我必须检查全部子局面”变成”我只需要等它们被逐个证明”。 - 循环要显式承认。任何有来回走子的游戏都存在循环，把它标成 UNKNOWN/DRAW 而不是强行赋胜负，是算法诚实的表现。
回到斗兽棋本身：层级克制规则（鼠吃象）让”棋子价值”不是单调的，这使启发式评估很难调；而逆推分析完全不需要价值判断——它只用规则本身。这正是残局库在棋类 AI 里始终占有一席之地的原因：在规则确定、规模可控的地方，穷举比聪明更可靠。
