每日算法 — 使用java实现斗兽棋：PIMC确定性化采样与不完全信息决策

斗兽棋真正的难点：你看不见对方的牌

斗兽棋规则很直观：象 > 狮 > 虎 > 豹 > 狼 > 狗 > 猫 > 鼠，大吃小，同级互吃；鼠能吃象；棋盘上有河，鼠可下水、象不可过河。如果双方棋子明置，这就是一个标准的 Alpha-Beta 搜索问题，随便写写就能赢。

但真实对局里对方的棋子是暗的。你知道”对方剩 5 个棋子”，但不知道哪一个在哪个位置——甚至不知道具体是哪 5 个（只有被吃掉的那些是公开信息）。这是一个典型的不完全信息零和博弈（imperfect-information zero-sum game），Minimax 在这里直接失效：因为它默认自己知道完整局面，而你不知道。

业界主流解法之一是 PIMC（Perfect Information Monte Carlo，完美信息蒙特卡洛）：把不完全信息问题”假装”成完全信息问题——确定化采样（determinization）出若干种可能的世界，在每个世界里用完全信息搜索求解，然后对这些世界的决策投票。

本文用 Java 实现完整流程：信念状态建模、约束一致的确定性化采样、带置换表的 Alpha-Beta 求解、以及”信息增益修正”来缓解 PIMC 的策略融合缺陷。

一、把棋盘和棋子抽象成状态

斗兽棋是 7×9 的棋盘（中间两条河）。用一维索引 pos = y * 7 + x 简化坐标。棋子编码：

public final class Piece {
    public static final int ELEPHANT = 1, LION = 2, TIGER = 3, LEOPARD = 4,
                             WOLF = 5, DOG = 6, CAT = 7, RAT = 8;

    /** 战斗结果：>0 表示 a 赢，<0 表示 b 赢，0 表示同级互吃（双方都死） */
    public static int fight(int a, int b) {
        if (a == RAT && b == ELEPHANT) return 1;      // 鼠吃象
        if (a == ELEPHANT && b == RAT) return -1;     // 象被鼠吃
        if (a == b) return 0;                          // 同级同归于尽
        return a < b ? 1 : -1;                         // 编号越小等级越高
    }
}

用编号大小表示等级有个好处：a < b 即 a 更强，战斗判定退化成一次比较 + 两个特例。

二、信念状态：把”不知道”表示成可枚举的集合

关键在于如何表示不确定性。不能只存”对方有 5 个棋子”，要存”这些棋子可能在哪些位置”。我用了两级表示：

1. 棋子级：对方还活着哪些棋子类型（由已吃掉的棋子反推）；
2. 位置级：每个位置是”确定是己方的”、”确定是对方的”、”未知”。

public final class Belief {
    /** 棋盘上每个格子的可见状态：0=空, 1=己方, 2=对方已知, 3=未知（可能有对方棋子） */
    final byte[] cellState;
    /** 对方剩余棋子类型集合（从 8 种里减掉已确认被吃的） */
    final Set<Integer> enemyRemaining;
    /** 未知格子集合，大小必须等于 enemyRemaining.size() */
    final List<Integer> unknownCells;
    /** 对方已确认被吃掉的数量（公开信息） */
    final int enemyLost;
}

约束一致性检查：unknownCells.size() 必须恰好等于 enemyRemaining.size()，否则这个信念本身矛盾。这是确定性化采样的第一道校验：

boolean isConsistent() {
    if (unknownCells.size() != enemyRemaining.size()) return false;
    // 未知格子里已观察到对方移动动过的次数约束（移动过说明那里肯定有棋子）
    return true;
}

更精细的实现会记录运动约束：某个未知格子如果在上一步有棋子从那里出发，那它必然曾包含一枚棋子。这些约束会大幅收窄采样空间，但实现复杂度上升。本文先用基础版本。

三、确定性化采样：从信念中随机抽一个”具体世界”

/** 从信念中随机采样一个具体局面：把 enemyRemaining 随机分配到 unknownCells */
static Set<Integer> sampleWorld(Belief b, Random rnd) {
    Set<Integer> placed = new HashSet<>();
    List<Integer> cells = new ArrayList<>(b.unknownCells);
    List<Integer> pieces = new ArrayList<>(b.enemyRemaining);

    // 有偏采样：优先把"高级棋子"放到离我方将/帅近的位置（对方更可能这么布阵）
    // 这里用简单的偏向打乱，避免所有采样都均匀分布导致评估失准
    pieces.sort((x, y) -> Integer.compare(y, x));  // 强的在前

    for (int i = 0; i < pieces.size(); i++) {
        int idx = rnd.nextInt(cells.size());       // 均匀抽样位置
        placed.add(cells.get(idx) * 16 + pieces.get(i));   // 编码：位置*16 + 棋子
        cells.remove(idx);
    }
    return placed;
}

采样次数的选择是 PIMC 的核心超参。经验值：

原因是 PIMC 的误差来源主要是策略融合缺陷（strategy fusion），不是采样噪声——加采样数并不能修复它。

四、单个世界内用 Alpha-Beta 求解

在每个确定化的世界里，问题变成完全信息博弈，可以直接上 Alpha-Beta：

public final class AlphaBeta {
    private static final int INF = 1_000_000;
    private final Map<Long, TTEntry> tt = new HashMap<>();   // 置换表

    /** 迭代加深：从深度 1 逐步加深，超时即用上一层结果 */
    public int search(Board b, int maxDepth, long deadlineNanos) {
        int best = 0;
        for (int d = 1; d <= maxDepth; d++) {
            try {
                best = rootSearch(b, d, deadlineNanos);
            } catch (TimeUp e) {
                break;                        // 超时就用上一层的完整结果
            }
        }
        return best;
    }

    private int rootSearch(Board b, int depth, long deadline) {
        int bestMove = -1, bestVal = -INF, alpha = -INF;
        for (int mv : b.generateMoves()) {
            if (System.nanoTime() > deadline) throw new TimeUp();
            b.makeMove(mv);
            int v = -negamax(b, depth - 1, -INF, -alpha, deadline);
            b.unmakeMove(mv);
            if (v > bestVal) { bestVal = v; bestMove = mv; }
            alpha = Math.max(alpha, v);
        }
        return bestMove;
    }

    /** 负极大形式：子节点取负号，alpha/beta 也随之取反，代码量减半 */
    private int negamax(Board b, int depth, int alpha, int beta, long deadline) {
        if (depth == 0) return Evaluator.evaluate(b);
        if (System.nanoTime() > deadline) throw new TimeUp();

        long key = b.zobristKey();
        TTEntry e = tt.get(key);
        if (e != null && e.depth >= depth) {
            if (e.flag == EXACT) return e.value;
            if (e.flag == LOWER) alpha = Math.max(alpha, e.value);
            if (e.flag == UPPER) beta = Math.min(beta, e.value);
            if (alpha >= beta) return e.value;
        }

        int bestVal = -INF;
        for (int mv : b.generateMovesOrdered()) {      // 吃子优先 + 置换表最佳着法优先
            b.makeMove(mv);
            int v = -negamax(b, depth - 1, -beta, -alpha, deadline);
            b.unmakeMove(mv);
            if (v > bestVal) bestVal = v;
            alpha = Math.max(alpha, v);
            if (alpha >= beta) break;                   // beta 截断
        }
        storeTT(key, depth, bestVal, alpha, beta);
        return bestVal;
    }

    static class TimeUp extends RuntimeException { TimeUp() { super(null, null, false, false); } }
}

为什么用负极大形式（Negamax）：Max 层和 Min 层的代码结构完全相同，只是符号取反。这消除了”对面视角”的重复逻辑，是写博弈搜索时的标准做法——尤其当评估函数从”红方视角”改成”当前行动方视角”后，一个函数就能处理两层。

置换表的三种标志位：EXACT（精确值）、LOWER（下界，因 beta 截断）、UPPER（上界，因 alpha 未提升）。三者都存才安全，只存值会导致剪枝错误。

五、多世界投票：PIMC 的决策聚合

每个采样世界给出一个”最优着法”，最终要选出全局最优着法。不能简单取众数——因为不同世界里的优势差异悬殊，应该按”该世界中的得分”加权：

public static int pimcDecide(Belief belief, Board realBoard, int samples, int depth, long budget) {
    Map<Integer, Double> scoreSum = new HashMap<>();
    Map<Integer, Integer> voteCount = new HashMap<>();
    Random rnd = new Random();

    for (int s = 0; s < samples; s++) {
        Set<Integer> world = sampleWorld(belief, rnd);
        Board virtual = realBoard.withEnemyPlacement(world);   // 填入采样到的对方棋子
        AlphaBeta ab = new AlphaBeta();
        int mv = ab.search(virtual, depth, budget / samples);

        // 关键：用真实对局视角的"虚拟世界得分"作为权重，而非简单的 1 票
        double value = ab.lastRootValue();      // 该世界下此着法的评价值
        scoreSum.merge(mv, value, Double::sum);
        voteCount.merge(mv, 1, Integer::sum);
    }

    // 综合：平均得分 + 票数的小幅加成（票数高说明多世界一致认可）
    int best = -1; double bestScore = -Double.MAX_VALUE;
    for (int mv : scoreSum.keySet()) {
        double avg = scoreSum.get(mv) / voteCount.get(mv);
        double score = avg + 0.15 * voteCount.get(mv);     // 0.15 为一致性奖励系数
        if (score > bestScore) { bestScore = score; best = mv; }
    }
    return best;
}

投票机制背后有个重要洞察：如果某个着法在 80% 的采样世界里都是最优，说明它对未知信息不敏感——这正是”稳健”的定义。反之，一个只在 20% 世界里极优、其余世界里很差的着法，是”赌运气”。

六、PIMC 的致命缺陷与缓解

PIMC 有一个理论上无法彻底解决的问题：策略融合缺陷。它假设”所有玩家都能看到真实信息并采用最优策略”，但实际对手做不到。这会导致 AI 高估某些信息性着法的价值——因为对手在真实信息下会有”正确反应”，但在不完全信息下反而可能做出错误反应。

经典案例：信息性着法。假设你的虎在河边，可以过河吃对方一个子，但你不知道河边那块石头上是不是鼠（鼠能吃虎）。PIMC 会这样算：在 50% 采样世界里河边是鼠，我过河就死；在另 50% 是猫，我过河就赢。平均下来收益为正，于是 AI 选择过河。

但更好的选择是”先不动，等对方暴露信息”。这个价值 PIMC 完全看不到——因为它在每个独立世界里都当对方是全知的。

缓解手段有三条，其中最实用的是信息增益加分（information value）：

/** 评估一个着法带来的信息增益：走完之后有多少未知格子被消解 */
static double infoGain(Belief before, Belief after) {
    int resolved = before.unknownCells.size() - after.unknownCells.size();
    return resolved * 40.0;      // 每个被消解的未知格子折合 40 分
}

// 在决策聚合时叠加：
double score = avgValue + infoGainBonus + 0.15 * voteCount;

另一个手段是在采样中加入对手的”非最优性”假设：对对手的着法选择加入随机噪声（softmax 采样而非 argmax），模拟真实玩家的失误。这会显著改善对局表现，但也让搜索不再严格可复现。

最根本的解法是 CFR（反事实遗憾最小化）系列算法——直接在不完全信息博弈树上求解近似纳什均衡，不做确定性化。本文的博客里已有斗兽棋的 CFR 文章，可对照阅读：PIMC 胜在实现简单、可复用已有搜索代码；CFR 胜在理论正确、无策略融合缺陷，但收敛慢且实现复杂。

七、完整工程结构

jungle-chess/
├── pom.xml
└── src/main/java/jungle/
    ├── Piece.java       // 战斗判定与等级
    ├── Board.java       // 7×9 棋盘、河流、移动生成、Zobrist
    ├── Belief.java      // 信念状态与一致性校验
    ├── Sampler.java     // 确定性化采样
    ├── AlphaBeta.java   // 置换表 + 迭代加深 + 负极大
    ├── Pimc.java        // 多世界投票 + 信息增益修正
    └── Main.java        // 人机对局

Main 的决策入口：

public static void main(String[] args) {
    Board board = Board.initial();
    Belief belief = Belief.fromHiddenOpponent(board);
    while (!board.isTerminal()) {
        if (board.sideToMove() == Board.ENEMY) {
            // 对方行为未知：用随机合法着法模拟
            board.makeMove(board.randomMove());
        } else {
            int mv = Pimc.pimcDecide(belief, board, 30, 6, 200_000_000L);  // 200ms 预算
            board.makeMove(mv);
            belief = belief.observe(board);      // 从公开信息更新信念
        }
    }
    System.out.println("结果: " + board.result());
}

八、复杂度与实测表现

设采样数 S、每个世界的搜索节点数 N：

• 时间：O(S · N)。取 S=30、N≈20000（Alpha-Beta + 置换表在 6 层深度的典型节点数），约 60 万次评估，实测 150~250ms。
• 空间：置换表每条 (long key, int value, byte depth, byte flag) 约 16 字节，30 个世界 × 2 万条 ≈ 10MB——因此每个世界要独立建置换表，不能跨世界复用（不同世界的哈希键含义不同，跨世界复用会污染结果）。

这是 PIMC 实现最容易犯的错误之一：为了省内存把置换表设成全局共享，结果不同世界的搜索结果互相污染，决策质量反而比不用置换表更差。

九、这个框架的迁移价值

PIMC 的通用形式是”信念状态 + 确定化 + 完全信息求解 + 决策聚合“。任何”部分可观察”的决策问题都能套用：

• 卡牌游戏（掼蛋、斗地主：对手手牌分布采样）
• 资源竞标（不知对手预算时的出价）
• 军事推演（雷达探测有噪声）
• 自动驾驶的交互场景（其他车辆的意图未知）

理解它的三个误差来源——采样噪声（可通过增加采样数缓解）、策略融合缺陷（无法通过增加采样数缓解）、评估函数偏差（可通过调参缓解）——比记住”PIMC”这个缩写重要得多。在错误的方向上增加算力，是这类问题的最大陷阱。