引言
四国军棋是中国经典的四人棋盘游戏，两队玩家（上下家为一队，左右家为一队）在暗棋规则下对弈——每个玩家只能看到自己棋子的等级，无法看到对手和队友的棋子。本文用Java实现四国军棋的AI决策系统，讲解不完全信息博弈的核心挑战，以及信息集蒙特卡洛树搜索（ISMCTS）算法如何在信息缺失的情况下做出近似最优决策。
问题分析
四国军棋的核心规则
- 棋盘：17×12的公路/铁路/行营/大本营网格
- 棋子等级：司令 > 军长 > 师长 > 旅长 > 团长 > 营长 > 连长 > 排长 > 工兵 > 炸弹
- 暗棋规则：除己方棋子外，所有其他棋子以背面朝上显示
- 合作对抗：对家为队友，可互相掩护和配合
不完全信息博弈的挑战
与象棋、围棋等完全信息博弈不同，四国军棋的AI面临三大核心难题：
1. 信息隐藏：无法直接观察对手棋子的真实等级
2. 信念更新：需根据对弈历史不断修正对隐藏信息的概率估计
3. 团队协作：需在不暴露信息的前提下与队友协调策略
核心算法一：信息集与信念状态
在不完全信息博弈中，信息集（Information Set）定义为玩家无法区分的所有可能游戏状态的集合。对于四国军棋，每个信息集包含：
– 已观察到的棋盘布局
– 己方棋子的确切位置与等级
– 对手棋子的所有可能排列（需满足约束：每种等级的数量固定）
信念状态用概率分布表示：对每一个隐藏的棋子，维护其属于各等级的概率。
核心算法二：信息集蒙特卡洛树搜索（ISMCTS）
ISMCTS是MCTS在不完全信息博弈中的扩展，核心思想：
1. 确定化（Determinization）：从当前信息集中随机采样一个具体的完全信息状态
2. 标准MCTS：在该确定化实例上执行UCT搜索
3. 聚合更新：将搜索结果聚合回信息集节点，更新动作价值
完整Java实现
package sijunqi.ai;
import java.util.*;
/**
* 四国军棋AI决策系统
*
* 核心功能：
* 1. 信息集建模：维护对隐藏棋子等级的概率信念
* 2. 确定化采样：从信念状态生成合法的完全信息对局实例
* 3. ISMCTS搜索：在不完全信息下进行蒙特卡洛树搜索
* 4. 规则约束：确保采样符合四国军棋的棋子数量约束
*/
public class SijunqiAI {
// 棋子等级定义
public enum Rank {
GONG(0), PAI(1), LIAN(2), YING(3), TUAN(4),
LV(5), SHI(6), JUN(7), SI(8), ZHA(9), DI(10), QI(11);
public final int value;
Rank(int v) { this.value = v; }
public boolean beats(Rank other) {
if (this == ZHA || other == ZHA) return true; // 炸弹同归于尽
if (this == GONG && other == DI) return true; // 工兵挖地雷
if (this == QI) return false; // 军旗不能移动和吃子
return this.value > other.value;
}
}
// 棋盘位置
public static class Pos {
public final int row, col;
public Pos(int r, int c) { this.row = r; this.col = c; }
@Override public boolean equals(Object o) {
if (o instanceof Pos) { Pos p = (Pos)o; return row==p.row && col==p.col; }
return false;
}
@Override public int hashCode() { return row * 100 + col; }
@Override public String toString() { return "(" + row + "," + col + ")"; }
}
// 棋子
public static class Piece {
public final int owner; // 0=自己, 1=队友, 2=下家, 3=上家
public Rank rank; // 己方可见，对手为null
public boolean revealed; // 是否已暴露等级
public Pos pos;
public Piece(int owner, Rank rank, Pos pos) {
this.owner = owner;
this.rank = rank;
this.pos = pos;
this.revealed = owner == 0 || owner == 1; // 己方和队友默认可见
}
}
// 棋盘状态
public static class Board {
public static final int ROWS = 17, COLS = 12;
private Piece[][] grid;
public Board() {
grid = new Piece[ROWS][COLS];
}
public Piece get(Pos p) { return grid[p.row][p.col]; }
public void set(Pos p, Piece piece) { grid[p.row][p.col] = piece; }
/**
* 获取某玩家的所有棋子
*/
public List<Piece> getPiecesByOwner(int owner) {
List<Piece> list = new ArrayList<>();
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
Piece p = grid[r][c];
if (p != null && p.owner == owner) list.add(p);
}
}
return list;
}
}
/**
* 信念状态：对每个隐藏棋子维护等级概率分布
*/
public static class BeliefState {
// 每个未暴露棋子位置 -> 各等级的概率
public Map<Pos, double[]> beliefMap;
// 全局约束：各等级剩余数量
public Map<Rank, Integer> remainingCount;
public BeliefState() {
beliefMap = new HashMap<>();
remainingCount = new HashMap<>();
// 标准四国军棋：每方各有1司令、1军长、2师长、2旅长、2团长、2营长、3连长、3排长、3工兵、2炸弹、3地雷、1军旗
remainingCount.put(Rank.SI, 1);
remainingCount.put(Rank.JUN, 1);
remainingCount.put(Rank.SHI, 2);
remainingCount.put(Rank.LV, 2);
remainingCount.put(Rank.TUAN, 2);
remainingCount.put(Rank.YING, 2);
remainingCount.put(Rank.LIAN, 3);
remainingCount.put(Rank.PAI, 3);
remainingCount.put(Rank.GONG, 3);
remainingCount.put(Rank.ZHA, 2);
remainingCount.put(Rank.DI, 3);
remainingCount.put(Rank.QI, 1);
}
/**
* 根据观察到的对弈历史更新信念
* 例如：若某对手棋子吃掉了己方的师长，则该棋子至少为军长
*/
public void updateBelief(Pos opponentPos, Rank minRank) {
double[] probs = beliefMap.get(opponentPos);
if (probs == null) return;
// 将该位置所有低于 minRank 的概率设为0，然后重归一化
double sum = 0;
for (int i = 0; i < probs.length; i++) {
if (Rank.values()[i].value < minRank.value) {
probs[i] = 0;
}
sum += probs[i];
}
if (sum > 0) {
for (int i = 0; i < probs.length; i++) probs[i] /= sum;
}
}
}
/**
* MCTS树节点
*/
public static class MCTSNode {
public Pos from, to; // 该节点代表的动作
public MCTSNode parent;
public List<MCTSNode> children;
public int visits;
public double wins;
public boolean fullyExpanded;
public MCTSNode(Pos from, Pos to, MCTSNode parent) {
this.from = from;
this.to = to;
this.parent = parent;
this.children = new ArrayList<>();
this.visits = 0;
this.wins = 0;
}
/**
* UCB1值计算
*/
public double ucb1(double exploration) {
if (visits == 0) return Double.MAX_VALUE;
double exploitation = wins / visits;
double explore = exploration * Math.sqrt(Math.log(parent.visits) / visits);
return exploitation + explore;
}
}
private final int playerId;
private final double explorationConstant;
private final Random random;
public SijunqiAI(int playerId, double exploration) {
this.playerId = playerId;
this.explorationConstant = exploration;
this.random = new Random();
}
/**
* ISMCTS主算法
* 执行多次迭代：确定化 -> MCTS选择/扩展/模拟/回传
*/
public Pos[] decideMove(Board board, BeliefState belief, int iterations) {
MCTSNode root = new MCTSNode(null, null, null);
for (int i = 0; i < iterations; i++) {
// 步骤1：确定化 - 从信念状态采样一个具体的棋盘
Board determinized = sampleDeterminization(board, belief);
// 步骤2：MCTS选择
MCTSNode selected = select(root, determinized);
// 步骤3：扩展
MCTSNode expanded = expand(selected, determinized);
// 步骤4：模拟（随机 rollout）
double reward = simulate(expanded, determinized);
// 步骤5：回传
backpropagate(expanded, reward);
}
// 选择访问次数最多的动作
MCTSNode best = root.children.stream()
.max(Comparator.comparingInt(n -> n.visits))
.orElse(null);
return best != null ? new Pos[]{best.from, best.to} : null;
}
/**
* 从信念状态采样一个确定化实例
* 为每个隐藏棋子随机分配一个符合约束的等级
*/
public Board sampleDeterminization(Board board, BeliefState belief) {
Board sampled = new Board();
// 复制已知棋子
for (int r = 0; r < Board.ROWS; r++) {
for (int c = 0; c < Board.COLS; c++) {
Pos p = new Pos(r, c);
Piece piece = board.get(p);
if (piece != null) {
if (piece.owner == playerId || piece.owner == (playerId + 2) % 4) {
// 己方和队友的棋子完全已知
sampled.set(p, new Piece(piece.owner, piece.rank, p));
} else {
// 对手棋子：根据信念采样等级
Rank sampledRank = sampleRankFromBelief(p, belief);
sampled.set(p, new Piece(piece.owner, sampledRank, p));
}
}
}
}
return sampled;
}
/**
* 根据信念分布采样一个等级
*/
private Rank sampleRankFromBelief(Pos pos, BeliefState belief) {
double[] probs = belief.beliefMap.getOrDefault(pos,
Arrays.stream(Rank.values()).mapToDouble(r -> 1.0 / Rank.values().length).toArray());
double roll = random.nextDouble();
double cumsum = 0;
for (int i = 0; i < probs.length; i++) {
cumsum += probs[i];
if (roll <= cumsum) return Rank.values()[i];
}
return Rank.GONG;
}
/**
* MCTS选择阶段：递归选择UCB1值最高的子节点
*/
private MCTSNode select(MCTSNode node, Board board) {
while (!node.children.isEmpty() && node.fullyExpanded) {
node = node.children.stream()
.max(Comparator.comparingDouble(n -> n.ucb1(explorationConstant)))
.orElse(node);
}
return node;
}
/**
* MCTS扩展阶段：为当前节点添加一个未探索的子节点
*/
private MCTSNode expand(MCTSNode node, Board board) {
List<Pos[]> legalMoves = generateLegalMoves(board, playerId);
// 过滤已探索的动作
List<Pos[]> unexplored = new ArrayList<>();
for (Pos[] move : legalMoves) {
boolean found = false;
for (MCTSNode child : node.children) {
if (child.from.equals(move[0]) && child.to.equals(move[1])) {
found = true; break;
}
}
if (!found) unexplored.add(move);
}
if (unexplored.isEmpty()) {
node.fullyExpanded = true;
return node;
}
Pos[] move = unexplored.get(random.nextInt(unexplored.size()));
MCTSNode child = new MCTSNode(move[0], move[1], node);
node.children.add(child);
return child;
}
/**
* 生成某玩家的所有合法移动
*/
private List<Pos[]> generateLegalMoves(Board board, int owner) {
List<Pos[]> moves = new ArrayList<>();
List<Piece> pieces = board.getPiecesByOwner(owner);
for (Piece p : pieces) {
if (p.rank == Rank.DI || p.rank == Rank.QI) continue; // 地雷和军旗不能移动
// 公路移动（一步一格）
int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
for (int[] d : dirs) {
int nr = p.pos.row + d[0], nc = p.pos.col + d[1];
if (isValidMove(board, p.pos, new Pos(nr, nc), owner)) {
moves.add(new Pos[]{p.pos, new Pos(nr, nc)});
}
}
}
return moves;
}
/**
* 判定移动是否合法
*/
private boolean isValidMove(Board board, Pos from, Pos to, int owner) {
if (to.row < 0 || to.row >= Board.ROWS || to.col < 0 || to.col >= Board.COLS) return false;
Piece target = board.get(to);
if (target != null && target.owner == owner) return false; // 不能吃己方棋子
return true;
}
/**
* 模拟阶段：从当前节点随机 rollout 到终局
*/
private double simulate(MCTSNode node, Board board) {
// 简化模拟：执行若干步随机走法后评估局面
int currentPlayer = playerId;
Board simBoard = cloneBoard(board);
for (int step = 0; step < 20; step++) {
List<Pos[]> moves = generateLegalMoves(simBoard, currentPlayer);
if (moves.isEmpty()) break;
Pos[] move = moves.get(random.nextInt(moves.size()));
applyMove(simBoard, move[0], move[1]);
currentPlayer = (currentPlayer + 1) % 4;
}
return evaluateBoard(simBoard);
}
/**
* 局面评估函数
*/
private double evaluateBoard(Board board) {
double score = 0;
List<Piece> myPieces = board.getPiecesByOwner(playerId);
List<Piece> teamPieces = board.getPiecesByOwner((playerId + 2) % 4);
for (Piece p : myPieces) {
if (p.rank != null) score += p.rank.value * 10;
}
for (Piece p : teamPieces) {
if (p.rank != null) score += p.rank.value * 5; // 队友权重较低
}
return score;
}
private Board cloneBoard(Board board) {
Board clone = new Board();
for (int r = 0; r < Board.ROWS; r++) {
for (int c = 0; c < Board.COLS; c++) {
Pos p = new Pos(r, c);
Piece piece = board.get(p);
if (piece != null) {
clone.set(p, new Piece(piece.owner, piece.rank, p));
}
}
}
return clone;
}
private void applyMove(Board board, Pos from, Pos to) {
Piece attacker = board.get(from);
Piece defender = board.get(to);
if (defender == null) {
// 移动到空格
board.set(to, new Piece(attacker.owner, attacker.rank, to));
board.set(from, null);
} else if (attacker.rank.beats(defender.rank)) {
// 吃子成功
board.set(to, new Piece(attacker.owner, attacker.rank, to));
board.set(from, null);
} else {
// 同归于尽或失败
board.set(from, null);
if (attacker.rank == Rank.ZHA || defender.rank == Rank.ZHA) {
board.set(to, null); // 炸弹同归于尽
}
}
}
/**
* 回传阶段：将模拟结果更新到路径上的所有节点
*/
private void backpropagate(MCTSNode node, double reward) {
while (node != null) {
node.visits++;
node.wins += reward;
node = node.parent;
}
}
// ==================== 测试入口 ====================
public static void main(String[] args) {
System.out.println("===== 四国军棋AI决策系统 =====\n");
// 初始化棋盘（简化布局）
Board board = new Board();
// 放置己方棋子
board.set(new Pos(13, 1), new Piece(0, Rank.SI, new Pos(13, 1)));
board.set(new Pos(13, 3), new Piece(0, Rank.JUN, new Pos(13, 3)));
board.set(new Pos(13, 5), new Piece(0, Rank.ZHA, new Pos(13, 5)));
board.set(new Pos(14, 2), new Piece(0, Rank.GONG, new Pos(14, 2)));
// 放置隐藏的对手棋子
board.set(new Pos(3, 1), new Piece(2, null, new Pos(3, 1)));
board.set(new Pos(3, 3), new Piece(2, null, new Pos(3, 3)));
board.set(new Pos(4, 2), new Piece(2, null, new Pos(4, 2)));
// 初始化信念状态
BeliefState belief = new BeliefState();
belief.beliefMap.put(new Pos(3, 1), new double[]{0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.1,0.1,0.3,0.15});
belief.beliefMap.put(new Pos(3, 3), new double[]{0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.1,0.1,0.3,0.15});
belief.beliefMap.put(new Pos(4, 2), new double[]{0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.1,0.1,0.3,0.15});
// 创建AI并决策
SijunqiAI ai = new SijunqiAI(0, 1.414);
System.out.println("AI思考中（1000次迭代）...");
Pos[] move = ai.decideMove(board, belief, 1000);
if (move != null) {
System.out.println("AI决策结果：从 " + move[0] + " 移动到 " + move[1]);
} else {
System.out.println("未找到合法移动");
}
// 测试信念更新
System.out.println("\n【测试】信念更新");
System.out.println("假设对手 (3,1) 吃掉了己方的军长");
belief.updateBelief(new Pos(3, 1), Rank.JUN);
double[] updated = belief.beliefMap.get(new Pos(3, 1));
System.out.print("更新后概率分布: ");
for (int i = 0; i < updated.length; i++) {
if (updated[i] > 0) System.out.print(Rank.values()[i] + "=" + String.format("%.2f", updated[i]) + " ");
}
}
}
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 确定化采样 | O(N) | N为隐藏棋子数 |
| MCTS单次迭代 | O(treeDepth + simSteps) | 树搜索深度 + 模拟步数 |
| 总搜索时间 | O(iterations × (N + simSteps)) | 迭代次数控制总体复杂度 |
| 空间复杂度 | O(iterations × treeNodes) | 树节点存储 |
| 信念更新 | O(R) | R为等级种类数（固定12种） |
扩展与优化
- 神经网络估值：用策略网络和价值网络替代随机模拟和手工评估函数
- 对手建模：维护对手风格的概率模型（激进/保守），调整belief更新策略
- 通信协议：队友间通过走法编码传递有限的加密信息
- 历史嵌入：将多轮对弈历史编码为特征向量，输入神经网络
- 并行确定化：利用多线程同时评估多个确定化实例，加速ISMCTS
总结
本文用Java实现了四国军棋的AI决策系统，将不完全信息博弈中的核心难题——信息隐藏、信念更新和团队协作——通过信息集蒙特卡洛树搜索进行了系统化建模。ISMCTS的核心洞察在于：虽然无法直接处理无穷多的可能世界，但通过大量随机确定化和统计聚合，AI仍能在信息缺失的环境中做出稳健的近似最优决策。这一方法论广泛应用于扑克、桥牌和其他暗牌类游戏AI的设计中。
