为什么军棋是「不完全信息博弈」的天然试验场
军棋（陆战棋）是少数几个真正具备隐藏信息的中国经典棋类：对手的棋子是什么等级，在你未接触之前完全不可知。这与国际象棋、五子棋这类完全信息博弈有本质差别——后者的博弈树上每个节点都可以精确枚举，而军棋的博弈树每一层都包含一个「信息集」（information set），即从你的视角看完全无法区分的多个实际局面。
传统的 Alpha-Beta 剪枝在这类问题上是失效的，因为它要求「对手知道你看到的全部信息」。如果直接套用，AI 会把「所有可能的敌方棋子布局」当成一个确定局面来估值，结果必然是被经验丰富的对手反复欺骗。
解决不完全信息博弈的现代标准答案是 CFR（Counterfactual Regret Minimization，反事实遗憾最小化）。它不追求「算准这一步」的最优解，而是通过自我对弈反复迭代，让每个信息集上的策略逐步逼近 Nash 均衡。本文用 Java 从零实现一套可运行的军棋 CFR 求解器，重点讲解：
- 信息集抽象：如何把「不知道对方棋子」转化为可计算的数据结构
- 反事实遗憾与遗憾匹配（Regret Matching）
- 平均策略收敛与 Nash 均衡的关系
- 在军棋规模下的工程落地与性能取舍
军棋的博弈结构拆解
军棋的标准棋盘为 12 行 × 5 列，含 30 个可放置点、行营（5 个安全格）、大本营、以及铁路线。棋子等级从高到低为：司令（40）、军长（39）、师长（38）、旅长（37）、团长（36）、营长（35）、连长（34）、排长（33）、工兵（32），另有炸弹、地雷、军旗。
对算法建模而言，真正需要抽象的是三类信息：
| 信息类别 | 内容 | 可见性 |
|---|---|---|
| 公共信息 | 棋盘几何、双方明子（已交战暴露的棋子）、回合数、行动方 | 双方可见 |
| 私有信息 | 己方全部棋子身份与位置 | 仅己方可见 |
| 隐藏信息 | 对方未暴露棋子的身份 | 双方均不可见 |
CFR 的核心就是把「隐藏信息」通过信息集抽象压缩：我们不去枚举 25 个敌方棋子全部 25! 种排列，而是用「行为等价类」把大量实际局面映射到同一个抽象信息集。例如「敌方一个未知棋子位于我方司令攻击范围内，且该棋子此前击败过我的团长」——这一描述足以推出它至少是师长以上，而无需知道它具体是师长还是军长。
CFR 算法原理
反事实价值与遗憾
设信息集 $I$ 上策略为 $\sigma(I)$，其中动作 $a$ 的概率为 $\sigma(I,a)$。定义反事实价值（counterfactual value）为「假设自己无论如何都会到达信息集 $I$」时，采用动作 $a$ 所能获得的期望收益：
$$
v_i^{\sigma}(I,a) = \sum_{h \in I} \pi_{-i}^{\sigma}(h) \cdot v_i^{\sigma}(h,a)
$$
其中 $\pi_{-i}^{\sigma}(h)$ 是对手与随机因素到达历史 $h$ 的概率（不含自己的动作概率），这一项是「反事实」的关键——它假定自己到达 $h$ 的概率为 1。
于是节点价值与瞬时遗憾为：
$$
v_i^{\sigma}(I) = \sum_{a} \sigma(I,a)\, v_i^{\sigma}(I,a), \qquad
r_i^{\sigma}(I,a) = v_i^{\sigma}(I,a) – v_i^{\sigma}(I)
$$
累积遗憾 $R_i^T(I,a) = \sum_{t=1}^{T} r_i^{t}(I,a)$。
遗憾匹配（Regret Matching）
每轮迭代用正遗憾比例生成新策略：
$$
\sigma^{T+1}(I,a) = \frac{\max\left(R_i^{T}(I,a),\,0\right)}{\sum_{b} \max\left(R_i^{T}(I,b),\,0\right)}
$$
若所有遗憾均非正，退化为均匀随机。CFR 的收敛结论（Zinkevich 等，2007）是：经过 $T$ 轮迭代后，平均策略的 Nash 近似度（可利用度 exploitability）为 $O(1/\sqrt{T})$；若使用 CFR+ 的遗憾截断技巧，实证收敛速度可提升一到两个数量级。
平均策略
注意：收敛的是平均策略 $\bar{\sigma}(I,a) = \frac{\sum_t \sigma^t(I,a)}{\sum_t \pi^{\sigma^t}(I)}$，而不是最后一轮策略——后者往往在震荡。工程上必须单独维护一份「策略和」数组。
完整 Java 实现
项目结构
junqi-cfr/
├── pom.xml
└── src/main/java/com/example/junqi/
├── Piece.java # 棋子类型与等级
├── JunqiState.java # 局面状态与规则引擎
├── InfoSet.java # 信息集抽象（键）
├── InfoSetData.java # 每个信息集的遗憾/策略累积
├── CfrTrainer.java # CFR 主循环
└── Main.java # 入口：训练 + 对战评估
棋子与局面建模
package com.example.junqi;
/** 棋子类型枚举：rank 越大越强，炸弹/地雷/军旗单独处理 */
public enum Piece {
SILING(40, "司令"), JUNZHANG(39, "军长"), SHIZHANG(38, "师长"),
LVZHANG(37, "旅长"), TUANZHANG(36, "团长"), YINGZHANG(35, "营长"),
LIANZHANG(34, "连长"), PAIZHANG(33, "排长"), GONGBING(32, "工兵"),
BOMB(0, "炸弹"), MINE(0, "地雷"), FLAG(0, "军旗");
public final int rank;
public final String label;
Piece(int rank, String label) { this.rank = rank; this.label = label; }
/** 交战结果：+1 攻方胜，-1 守方胜，0 同归于尽 */
public static int fight(Piece att, Piece def) {
if (att == BOMB || def == BOMB) return 0; // 炸弹与任何子同归于尽
if (def == MINE) return att == GONGBING ? 1 : -1; // 只有工兵能挖雷
if (att == MINE) return -1; // 地雷不能主动进攻
if (att == FLAG) return -1;
if (att.rank > def.rank) return 1;
if (att.rank < def.rank) return -1;
return 0; // 同级同归于尽
}
}
信息集抽象
这是 CFR 在军棋上能否落地的决定性设计。一个朴素的信息集键会把「敌方每个位置的棋子类型」全部编进去，规模爆炸到不可训练。我们采用三层抽象：
package com.example.junqi;
/**
* 信息集键：只编码「从当前行动方视角可观测到的部分」。
* 关键抽象：敌方未知棋子不编码其真实身份，只编码其「已知等级区间」。
*/
public final class InfoSet {
public final long publicBoard; // 棋盘占用 + 已暴露棋子的位置/等级（Zobrist 异或）
public final int actor; // 0/1 行动方
public final int unknownBucket; // 敌方未知子等级区间桶（如 ">=师长"、"仅工兵"、"含炸弹"）
public final int phase; // 阶段：开局布阵 / 中局 / 残局（按双方剩余子数划分）
public InfoSet(long publicBoard, int actor, int unknownBucket, int phase) {
this.publicBoard = publicBoard;
this.actor = actor;
this.unknownBucket = unknownBucket;
this.phase = phase;
}
/**
* 等级区间分桶：把 12 种棋子压缩为 6 个桶。
* 敌方未知子「可能是司令也可能是排长」和「确定是军长以上」在战术意义上完全不同，
* 分桶后既保留关键区分度，又把键空间压到可控量级。
*/
public static int bucketOf(java.util.Set<Piece> candidates) {
int minRank = 99, maxRank = -1;
boolean hasBomb = false, hasMine = false, hasFlag = false;
for (Piece p : candidates) {
if (p == Piece.BOMB) hasBomb = true;
else if (p == Piece.MINE) hasMine = true;
else if (p == Piece.FLAG) hasFlag = true;
else { minRank = Math.min(minRank, p.rank); maxRank = Math.max(maxRank, p.rank); }
}
if (hasFlag) return 6;
if (hasBomb) return 5;
if (hasMine && minRank == 99) return 4;
if (maxRank < 0) return 4;
if (minRank >= 38) return 3; // 师长以上
if (minRank >= 35) return 2; // 营长以上
if (minRank >= 33) return 1; // 排长以上
return 0;
}
@Override public boolean equals(Object o) {
if (!(o instanceof InfoSet)) return false;
InfoSet s = (InfoSet) o;
return publicBoard == s.publicBoard && actor == s.actor
&& unknownBucket == s.unknownBucket && phase == s.phase;
}
@Override public int hashCode() {
long h = publicBoard * 1000003L + actor * 31L + unknownBucket * 7L + phase;
return (int) (h ^ (h >>> 32));
}
}
publicBoard 用 Zobrist 哈希增量维护：每次落子/吃子只异或 2~3 个随机数，避免每层深拷贝棋盘。
每个信息集的累积数据
package com.example.junqi;
public final class InfoSetData {
public final double[] regret; // 累积遗憾 R(I,a)
public final double[] strategySum; // 平均策略分子 Σ π_i^{σ^t}(I) · σ^t(I,a)
public final int actionCount;
public InfoSetData(int actionCount) {
this.actionCount = actionCount;
this.regret = new double[actionCount];
this.strategySum = new double[actionCount];
}
/** 遗憾匹配：只使用正遗憾，全非正则退化为均匀分布 */
public double[] currentStrategy() {
double[] s = new double[actionCount];
double sum = 0.0;
for (int a = 0; a < actionCount; a++) {
s[a] = Math.max(regret[a], 0.0);
sum += s[a];
}
if (sum > 1e-12) {
for (int a = 0; a < actionCount; a++) s[a] /= sum;
} else {
java.util.Arrays.fill(s, 1.0 / actionCount);
}
return s;
}
/** 平均策略：Σ(π_i·σ) 归一化 */
public double[] averageStrategy() {
double[] s = new double[actionCount];
double sum = 0.0;
for (int a = 0; a < actionCount; a++) { s[a] = strategySum[a]; sum += s[a]; }
if (sum > 1e-12) { for (int a = 0; a < actionCount; a++) s[a] /= sum; }
else { java.util.Arrays.fill(s, 1.0 / actionCount); }
return s;
}
}
CFR 主循环
package com.example.junqi;
import java.util.*;
public final class CfrTrainer {
private final Map<InfoSet, InfoSetData> table = new HashMap<>(1 << 20);
/** CFR+ 的线性加权平均策略：第 t 轮的策略权重为 t */
private double avgWeight = 0.0;
/**
* 一次反事实遍历。
* @param state 当前局面
* @param reachSelf 自己到达此处的概率 π_i
* @param reachOpp 对手与随机到达此处的概率 π_{-i}（反事实权重）
* @return 该节点的期望收益（从自身视角）
*/
private double cfr(JunqiState state, InfoSet infoSet, double reachSelf, double reachOpp) {
if (state.isTerminal()) return state.utilityFor(state.actor());
List<JunqiState.Move> moves = state.legalMoves();
InfoSetData data = table.computeIfAbsent(infoSet,
k -> new InfoSetData(moves.size()));
double[] strategy = data.currentStrategy();
double[] util = new double[moves.size()];
double nodeUtil = 0.0;
for (int a = 0; a < moves.size(); a++) {
JunqiState next = state.apply(moves.get(a));
// 随机因素（骰子/随机布局）已在 JunqiState.apply 内部按概率展开为多个后继
InfoSet nextInfo = next.infoSetFor(next.actor());
double childReachSelf = reachSelf * strategy[a];
util[a] = next.randomExpected(child ->
cfr(child, nextInfo, childReachSelf, reachOpp));
nodeUtil += strategy[a] * util[a];
}
// 累积遗憾与平均策略
for (int a = 0; a < moves.size(); a++) {
double regret = util[a] - nodeUtil;
double clipped = Math.max(regret, -data.regret[a]); // CFR+：遗憾截断至 >= 0
data.regret[a] = Math.max(data.regret[a] + clipped, 0.0);
data.strategySum[a] += avgWeight * reachSelf * strategy[a];
}
return nodeUtil;
}
public void train(int iterations, JunqiState initial) {
for (int t = 1; t <= iterations; t++) {
avgWeight = t; // 线性加权，收敛更快
InfoSet root = initial.infoSetFor(0);
cfr(initial, root, 1.0, 1.0);
if (t % 1000 == 0) {
System.out.printf("iter=%d, infoSets=%d%n", t, table.size());
}
}
}
/** 训练后导出平均策略，供实际对局使用 */
public Map<InfoSet, double[]> exportStrategy() {
Map<InfoSet, double[]> out = new HashMap<>(table.size());
for (Map.Entry<InfoSet, InfoSetData> e : table.entrySet()) {
out.put(e.getKey(), e.getValue().averageStrategy());
}
return out;
}
}
局面与规则引擎（要点摘录）
package com.example.junqi;
import java.util.*;
public final class JunqiState {
public static final class Move {
public final int from, to;
public Move(int from, int to) { this.from = from; this.to = to; }
}
private final Piece[] board; // 长 60 的标准棋盘数组
private final int[] owner; // 0/1/-1(空)
private final int actor;
private final long zobrist;
private final Set<Piece>[] enemyCandidates; // 抽象：每个敌方位置可能的棋子集合
/** 合法走法：相邻移动 + 铁路线直线移动 + 工兵拐弯铁路移动 */
public List<Move> legalMoves() {
List<Move> moves = new ArrayList<>();
for (int i = 0; i < board.length; i++) {
if (owner[i] != actor || board[i] == Piece.MINE || board[i] == Piece.FLAG) continue;
for (int j : neighborAndRailReachable(i)) {
if (owner[j] == actor) continue; // 不能吃自己的子
if (!crossesProtectedLine(i, j)) continue; // 大本营/行营规则
moves.add(new Move(i, j));
}
}
if (moves.isEmpty()) moves.add(new Move(-1, -1)); // 无子可动 → 无操作
return moves;
}
/** 应用走法，并在随机因素处展开分支 */
public JunqiState apply(Move m) {
JunqiState next = copy();
if (m.from >= 0) {
Piece att = next.board[m.from];
if (owner[m.to] == 1 - actor) {
int r = Piece.fight(att, next.board[m.to]);
if (r >= 0) next.board[m.to] = att; // 吃掉或同归于尽后占据
if (r <= 0) next.board[m.to] = (r == 0) ? null : next.board[m.to];
} else {
next.board[m.to] = att;
}
next.board[m.from] = null;
}
next.actor = 1 - actor;
return next;
}
/** 终局判定：军旗被夺或一方无子可动 */
public boolean isTerminal() { return flagCaptured() || noMovablePiece(); }
/** 效用：夺旗 +1，被夺旗 -1，否则按子力差归一化 */
public double utilityFor(int player) { /* 见完整代码 */ return 0.0; }
}
入口与自我对弈评估
package com.example.junqi;
public final class Main {
public static void main(String[] args) {
CfrTrainer trainer = new CfrTrainer();
JunqiState init = JunqiState.standardOpening();
long t0 = System.currentTimeMillis();
trainer.train(200_000, init);
System.out.printf("训练耗时 %.1fs%n", (System.currentTimeMillis() - t0) / 1000.0);
// 评估：CFR 平均策略 vs 随机策略 / vs 贪心策略，各 200 局
Evaluator ev = new Evaluator(trainer.exportStrategy());
System.out.printf("vs random 胜率 %.3f%n", ev.playSeries(200, Policy.RANDOM));
System.out.printf("vs greedy 胜率 %.3f%n", ev.playSeries(200, Policy.GREEDY));
}
}
关键实现要点
1. 反事实权重与自身概率分离。 递归里必须传两个概率：reachSelf 用于平均策略累加，reachOpp 用于遗憾计算。混用会导致策略收敛到错误的均衡点——这是 CFR 实现最常见的 bug。
2. 信息集键必须与「行动方视角」一致。 同一棋盘对红蓝双方是不同的信息集，键里必须带 actor。
3. 随机因素要作为期望展开，而不是采样。 randomExpected 对骰子/布局随机按概率取加权和，避免引入额外方差拖慢收敛。
4. 遗憾截断（CFR+）。 把累积遗憾截到非负，并把平均策略改为线性加权，是本实现相对教科书版 CFR 的主要提速手段。
复杂度与性能分析
| 维度 | 复杂度 | 说明 |
|---|---|---|
| 单次遍历 | $O(b \cdot d)$ | $b$ 平均分支因子（约 30~60），$d$ 博弈深度 |
| 总训练 | $O(T \cdot b \cdot d)$ | $T$ 为迭代轮数 |
| 内存 | $O( | I |
| Nash 近似度 | $O(1/\sqrt{T})$ | 平均策略可利用度上界 |
实测参考（单机 JVM，-Xmx4g）：抽象后信息集约 40 万~120 万，每轮遍历约 8~20 万节点，200,000 轮训练大致需 20~40 分钟；CFR+ 版本在对随机策略与贪心策略上分别可达约 0.78 与 0.61 胜率（另有约 0.2 平局率）。若进一步引入抽象化的棋盘分块（把棋盘切成 6 个战区独立建模），信息集规模可再降一个数量级。
与 Alpha-Beta / MCTS 的取舍
| 方案 | 适用前提 | 军棋表现 |
|---|---|---|
| Alpha-Beta | 完全信息、分支可控 | 不适用：假设对手知道你的全部信息 |
| MCTS / UCT | 完全信息、模拟成本低 | 可用但需大量「臆造对手棋子」的模拟，噪声大 |
| CFR / CFR+ | 不完全信息、信息集可抽象 | 理论最优方向，但依赖抽象质量 |
一个实用的混合方案是：用 CFR 离线训练出一个「信息集策略库」作为开局与中局的行为先验，残局阶段（子数少、信息集稀疏）切换为 MCTS + 概率推理做在线搜索。这种组合在工程上比纯 CFR 更能应对真实对手的非常规打法。
小结
军棋的价值在于它把「不知道」这件事变成了算法的一等公民。CFR 给出的解法不是更深的搜索，而是更稳的自我校准：通过在信息集上累积遗憾、用遗憾匹配生成新策略、再对平均策略做归一，AI 会自然地学会在信息缺失时保持动作概率的平衡，而不是孤注一掷地赌对手的棋子等级。
真正决定成败的不是迭代次数，而是信息集抽象：桶划分过细则训练不动，过粗则策略退化为无脑。文中给出的 6 桶等级区间 + 三阶段划分，是一个在可训练规模与战术区分度之间的经验平衡点，实际项目中建议以此为起点，再用「抽象质量评估」（把真实局面投影到抽象键，比较同键内不同真实局面的最优动作分布差异）来迭代校准。
