引言
中国象棋是两人对弈的策略棋类游戏，棋盘由9条竖线和10条横线交叉组成，双方各执16枚棋子。与围棋相比，中国象棋具有更明确的战术目标和更小的分支因子。本文将使用Java实现基于蒙特卡洛树搜索（MCTS）与UCB1公式的中国象棋AI，通过随机模拟评估局面，逐步构建搜索树以选择最优走法。
算法原理
蒙特卡洛树搜索（MCTS）
MCTS通过迭代构建搜索树，在有限时间内找到近似最优解。算法包含四个阶段：
- 选择（Selection）：从根节点出发，使用UCB1公式选择子节点直到到达叶子节点
- 扩展（Expansion）：为叶子节点添加一个或多个未探索的子节点
- 模拟（Simulation）：从新扩展的节点出发进行随机对弈直到终局
- 回传（Backpropagation）：将模拟结果沿路径回传到根节点，更新各节点的访问次数和胜率
UCB1公式
UCB1（Upper Confidence Bound 1）平衡了 exploitation（利用已知高胜率节点）和 exploration（探索访问次数少的节点）：
[ \text{UCB1}(v_i) = \frac{w_i}{n_i} + c \sqrt{\frac{\ln N}{n_i}} ]
其中 ( w_i ) 是节点 ( i ) 的胜场数，( n_i ) 是访问次数，( N ) 是父节点访问次数，( c ) 是探索常数（通常取 ( \sqrt{2} )）。
中国象棋局面评估
在模拟阶段，由于完整对弈到终局耗时较长，通常采用快速评估函数截断模拟：
[ \text{eval}(s) = \sum_{piece} \text{value}(piece) + \text{position_bonus}(piece) ]
Java实现
import java.util.*;
/**
* 棋子类型枚举
*/
enum PieceType {
KING(10000), // 将/帅
ROOK(900), // 车
HORSE(400), // 马
CANNON(450), // 炮
ELEPHANT(200), // 相/象
GUARD(200), // 士/仕
PAWN(100); // 兵/卒
private final int baseValue;
PieceType(int baseValue) { this.baseValue = baseValue; }
public int getBaseValue() { return baseValue; }
}
/**
* 棋子类
*/
class Piece {
PieceType type;
boolean isRed; // true=红方(下方), false=黑方(上方)
int row, col;
public Piece(PieceType type, boolean isRed, int row, int col) {
this.type = type;
this.isRed = isRed;
this.row = row;
this.col = col;
}
public Piece copy() {
return new Piece(type, isRed, row, col);
}
}
/**
* 走法表示
*/
class Move {
int fromRow, fromCol;
int toRow, toCol;
Piece captured; // 被吃掉的棋子
public Move(int fr, int fc, int tr, int tc) {
this.fromRow = fr; this.fromCol = fc;
this.toRow = tr; this.toCol = tc;
}
@Override
public String toString() {
return String.format("(%d,%d)->(%d,%d)", fromRow, fromCol, toRow, toCol);
}
}
/**
* 棋盘状态
*/
class BoardState {
private static final int ROWS = 10;
private static final int COLS = 9;
private Piece[][] board;
private boolean redToMove;
// 位置奖励表（简化版，红方视角）
private static final int[][] PAWN_BONUS = {
{0,0,0,0,0,0,0,0,0},
{50,50,50,50,50,50,50,50,50},
{40,40,40,40,40,40,40,40,40},
{30,30,30,30,30,30,30,30,30},
{20,20,20,20,20,20,20,20,20},
{10,10,10,10,10,10,10,10,10},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0}
};
public BoardState() {
board = new Piece[ROWS][COLS];
redToMove = true;
initializeBoard();
}
private BoardState(Piece[][] board, boolean redToMove) {
this.board = board;
this.redToMove = redToMove;
}
/**
* 初始化标准开局
*/
private void initializeBoard() {
// 黑方（上方）
String[] blackLayout = {
"RNHEKHENR",
".........",
".C.....C.",
"P.P.P.P.P",
".........",
".........",
"p.p.p.p.p",
".c.....c.",
".........",
"rnhekhenr"
};
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
char ch = blackLayout[r].charAt(c);
if (ch == '.') continue;
boolean isRed = Character.isLowerCase(ch);
PieceType type = charToType(ch);
board[r][c] = new Piece(type, isRed, r, c);
}
}
}
private PieceType charToType(char ch) {
switch (Character.toLowerCase(ch)) {
case 'r': return PieceType.ROOK;
case 'n': return PieceType.HORSE;
case 'h': return PieceType.HORSE; // 兼容不同记谱
case 'e': return PieceType.ELEPHANT;
case 'b': return PieceType.ELEPHANT;
case 'g': return PieceType.GUARD;
case 'a': return PieceType.GUARD;
case 'k': return PieceType.KING;
case 'c': return PieceType.CANNON;
case 'p': return PieceType.PAWN;
default: return null;
}
}
public Piece[][] getBoard() { return board; }
public boolean isRedToMove() { return redToMove; }
/**
* 生成当前玩家的所有合法走法
*/
public List<Move> generateLegalMoves() {
List<Move> moves = new ArrayList<>();
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
Piece p = board[r][c];
if (p != null && p.isRed == redToMove) {
moves.addAll(generatePieceMoves(p));
}
}
}
return moves;
}
/**
* 生成某枚棋子的所有合法走法
*/
private List<Move> generatePieceMoves(Piece p) {
List<Move> moves = new ArrayList<>();
int r = p.row, c = p.col;
switch (p.type) {
case KING:
// 将/帅：在九宫内一格移动
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
if (Math.abs(dr) + Math.abs(dc) != 1) continue;
int nr = r + dr, nc = c + dc;
if (isInPalace(nr, nc, p.isRed) && canMoveTo(nr, nc, p.isRed)) {
moves.add(new Move(r, c, nr, nc));
}
}
}
// 照面：将帅在同列且中间无子
int enemyKingRow = findEnemyKingRow(p.isRed);
if (enemyKingRow != -1 && c == board[enemyKingRow][c].col) {
boolean clear = true;
int start = Math.min(r, enemyKingRow) + 1;
int end = Math.max(r, enemyKingRow);
for (int i = start; i < end; i++) {
if (board[i][c] != null) { clear = false; break; }
}
if (clear) moves.add(new Move(r, c, enemyKingRow, c));
}
break;
case ROOK:
// 车：直线移动，隔子不能吃（除非炮的规则）
for (int[] dir : new int[][]{{-1,0},{1,0},{0,-1},{0,1}}) {
int nr = r + dir[0], nc = c + dir[1];
while (inBounds(nr, nc)) {
if (board[nr][nc] == null) {
moves.add(new Move(r, c, nr, nc));
} else {
if (board[nr][nc].isRed != p.isRed) {
moves.add(new Move(r, c, nr, nc));
}
break;
}
nr += dir[0]; nc += dir[1];
}
}
break;
case HORSE:
// 马：日字形，需要检查蹩马腿
int[][] horseDirs = {{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
int[][] horseBlocks = {{-1,0},{-1,0},{0,-1},{0,1},{0,-1},{0,1},{1,0},{1,0}};
for (int i = 0; i < horseDirs.length; i++) {
int br = r + horseBlocks[i][0], bc = c + horseBlocks[i][1];
if (!inBounds(br, bc) || board[br][bc] != null) continue;
int nr = r + horseDirs[i][0], nc = c + horseDirs[i][1];
if (inBounds(nr, nc) && canMoveTo(nr, nc, p.isRed)) {
moves.add(new Move(r, c, nr, nc));
}
}
break;
case CANNON:
// 炮：直线移动，吃子需要隔一个棋子
for (int[] dir : new int[][]{{-1,0},{1,0},{0,-1},{0,1}}) {
int nr = r + dir[0], nc = c + dir[1];
boolean foundPlatform = false;
while (inBounds(nr, nc)) {
if (!foundPlatform) {
if (board[nr][nc] == null) {
moves.add(new Move(r, c, nr, nc));
} else {
foundPlatform = true;
}
} else {
if (board[nr][nc] != null) {
if (board[nr][nc].isRed != p.isRed) {
moves.add(new Move(r, c, nr, nc));
}
break;
}
}
nr += dir[0]; nc += dir[1];
}
}
break;
case ELEPHANT:
// 相/象：田字格，不能过河
int[][] eleDirs = {{-2,-2},{-2,2},{2,-2},{2,2}};
int[][] eleBlocks = {{-1,-1},{-1,1},{1,-1},{1,1}};
for (int i = 0; i < eleDirs.length; i++) {
int nr = r + eleDirs[i][0], nc = c + eleDirs[i][1];
int br = r + eleBlocks[i][0], bc = c + eleBlocks[i][1];
if (!inBounds(nr, nc) || board[br][bc] != null) continue;
if ((p.isRed && nr > 4) || (!p.isRed && nr < 5)) continue; // 不能过河
if (canMoveTo(nr, nc, p.isRed)) {
moves.add(new Move(r, c, nr, nc));
}
}
break;
case GUARD:
// 士/仕：斜向一格，在九宫内
for (int dr = -1; dr <= 1; dr += 2) {
for (int dc = -1; dc <= 1; dc += 2) {
int nr = r + dr, nc = c + dc;
if (isInPalace(nr, nc, p.isRed) && canMoveTo(nr, nc, p.isRed)) {
moves.add(new Move(r, c, nr, nc));
}
}
}
break;
case PAWN:
// 兵/卒：向前一格，过河后可左右
int forward = p.isRed ? -1 : 1;
int nr = r + forward;
if (inBounds(nr, c) && canMoveTo(nr, c, p.isRed)) {
moves.add(new Move(r, c, nr, c));
}
// 过河后可左右移动
if ((p.isRed && r < 5) || (!p.isRed && r > 4)) {
for (int dc = -1; dc <= 1; dc += 2) {
int nc = c + dc;
if (inBounds(r, nc) && canMoveTo(r, nc, p.isRed)) {
moves.add(new Move(r, c, r, nc));
}
}
}
break;
}
return moves;
}
private boolean inBounds(int r, int c) {
return r >= 0 && r < ROWS && c >= 0 && c < COLS;
}
private boolean isInPalace(int r, int c, boolean isRed) {
if (c < 3 || c > 5) return false;
if (isRed) return r >= 7 && r <= 9;
return r >= 0 && r <= 2;
}
private boolean canMoveTo(int r, int c, boolean isRed) {
return inBounds(r, c) && (board[r][c] == null || board[r][c].isRed != isRed);
}
private int findEnemyKingRow(boolean isRed) {
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (board[r][c] != null && board[r][c].type == PieceType.KING && board[r][c].isRed != isRed) {
return r;
}
}
}
return -1;
}
/**
* 执行走法并返回新状态
*/
public BoardState applyMove(Move move) {
Piece[][] newBoard = new Piece[ROWS][COLS];
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (board[r][c] != null) newBoard[r][c] = board[r][c].copy();
}
}
Piece moved = newBoard[move.fromRow][move.fromCol];
move.captured = newBoard[move.toRow][move.toCol];
newBoard[move.toRow][move.toCol] = moved;
newBoard[move.fromRow][move.fromCol] = null;
moved.row = move.toRow;
moved.col = move.toCol;
return new BoardState(newBoard, !redToMove);
}
/**
* 局面评估函数
*/
public double evaluate() {
double score = 0;
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
Piece p = board[r][c];
if (p == null) continue;
double value = p.type.getBaseValue();
// 位置奖励
if (p.type == PieceType.PAWN) {
int bonusRow = p.isRed ? r : (ROWS - 1 - r);
value += PAWN_BONUS[bonusRow][c];
}
// 机动性奖励
List<Move> moves = generatePieceMoves(p);
value += moves.size() * 5;
if (p.isRed) score += value;
else score -= value;
}
}
return redToMove ? score : -score;
}
/**
* 检查游戏是否结束
*/
public boolean isGameOver() {
boolean redKing = false, blackKing = false;
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (board[r][c] != null && board[r][c].type == PieceType.KING) {
if (board[r][c].isRed) redKing = true;
else blackKing = true;
}
}
}
return !redKing || !blackKing;
}
public BoardState copy() {
Piece[][] newBoard = new Piece[ROWS][COLS];
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (board[r][c] != null) newBoard[r][c] = board[r][c].copy();
}
}
return new BoardState(newBoard, redToMove);
}
}
/**
* MCTS节点
*/
class MCTSNode {
BoardState state;
Move move; // 到达此节点的走法
MCTSNode parent;
List<MCTSNode> children;
double wins;
int visits;
List<Move> untriedMoves;
public MCTSNode(BoardState state, Move move, MCTSNode parent) {
this.state = state;
this.move = move;
this.parent = parent;
this.children = new ArrayList<>();
this.wins = 0;
this.visits = 0;
this.untriedMoves = state.generateLegalMoves();
}
/**
* UCB1值计算
*/
public double ucb1(double explorationConstant) {
if (visits == 0) return Double.MAX_VALUE;
double winRate = wins / visits;
double exploration = explorationConstant * Math.sqrt(Math.log(parent.visits) / visits);
return winRate + exploration;
}
/**
* 选择最佳子节点
*/
public MCTSNode selectChild(double explorationConstant) {
return children.stream()
.max(Comparator.comparingDouble(n -> n.ucb1(explorationConstant)))
.orElse(null);
}
/**
* 扩展一个新子节点
*/
public MCTSNode expand() {
if (untriedMoves.isEmpty()) return null;
Move move = untriedMoves.remove(untriedMoves.size() - 1);
BoardState newState = state.applyMove(move);
MCTSNode child = new MCTSNode(newState, move, this);
children.add(child);
return child;
}
/**
* 更新节点统计
*/
public void update(double result) {
visits++;
wins += result;
}
}
/**
* MCTS中国象棋AI
*/
public class ChineseChessMCTS {
private static final double EXPLORATION_CONSTANT = Math.sqrt(2);
private static final int MAX_SIMULATION_DEPTH = 50;
private final Random random = new Random();
/**
* 搜索最优走法
* @param rootState 当前局面
* @param iterations 迭代次数
*/
public Move search(BoardState rootState, int iterations) {
MCTSNode root = new MCTSNode(rootState.copy(), null, null);
for (int i = 0; i < iterations; i++) {
MCTSNode node = root;
// 1. 选择
while (node.untriedMoves.isEmpty() && !node.children.isEmpty()) {
node = node.selectChild(EXPLORATION_CONSTANT);
}
// 2. 扩展
if (!node.untriedMoves.isEmpty()) {
node = node.expand();
}
// 3. 模拟
double result = simulate(node.state);
// 4. 回传
while (node != null) {
node.update(result);
result = 1 - result; // 切换视角
node = node.parent;
}
}
// 返回访问次数最多的走法
return root.children.stream()
.max(Comparator.comparingInt(n -> n.visits))
.map(n -> n.move)
.orElse(null);
}
/**
* 快速模拟对弈
*/
private double simulate(BoardState state) {
BoardState simState = state.copy();
int depth = 0;
while (!simState.isGameOver() && depth < MAX_SIMULATION_DEPTH) {
List<Move> moves = simState.generateLegalMoves();
if (moves.isEmpty()) break;
// 优先选择吃子走法
Move bestMove = moves.get(random.nextInt(moves.size()));
for (Move m : moves) {
if (m.captured != null) {
bestMove = m;
break;
}
}
simState = simState.applyMove(bestMove);
depth++;
}
// 返回结果（从原始玩家视角）
double eval = simState.evaluate();
return Math.max(0, Math.min(1, (eval + 5000) / 10000));
}
/**
* 主程序：演示MCTS对弈
*/
public static void main(String[] args) {
BoardState board = new BoardState();
ChineseChessMCTS ai = new ChineseChessMCTS();
System.out.println("=== 中国象棋MCTS AI演示 ===");
System.out.println("初始局面：");
printBoard(board);
// AI计算最优走法
System.out.println("\n红方AI思考中...");
Move bestMove = ai.search(board, 5000);
System.out.println("AI选择走法: " + bestMove);
board = board.applyMove(bestMove);
System.out.println("\n执行后局面：");
printBoard(board);
// 分析各候选走法的统计信息
System.out.println("\n=== 候选走法统计 ===");
MCTSNode root = new MCTSNode(board.copy(), null, null);
for (int i = 0; i < 3000; i++) {
// 简要搜索获取统计
}
}
private static void printBoard(BoardState board) {
Piece[][] b = board.getBoard();
for (int r = 0; r < 10; r++) {
for (int c = 0; c < 9; c++) {
if (b[r][c] == null) {
System.out.print("· ");
} else {
char ch = pieceToChar(b[r][c]);
System.out.print(ch + " ");
}
}
System.out.println();
}
}
private static char pieceToChar(Piece p) {
char c;
switch (p.type) {
case KING: c = 'k'; break;
case ROOK: c = 'r'; break;
case HORSE: c = 'n'; break;
case CANNON: c = 'c'; break;
case ELEPHANT: c = 'e'; break;
case GUARD: c = 'g'; break;
case PAWN: c = 'p'; break;
default: c = '?';
}
return p.isRed ? Character.toUpperCase(c) : c;
}
}
算法优化策略
1. 快速走法生成
MCTS的性能严重依赖于走法生成的速度。通过预计算各棋子的移动模板和位棋盘表示，可以将走法生成复杂度从 ( O(n^2) ) 降到 ( O(n) )。
2. 渐进式扩展（Progressive Widening）
当合法走法过多时，先评估少量候选走法，随着模拟次数增加逐步扩展更多选择。这避免了在开局阶段浪费计算资源在低质量走法上。
3. 先验知识注入
通过训练策略网络为每个走法提供先验概率，在UCB公式中用先验概率替代均匀分布，可以显著提升搜索效率：
[ \text{PUCT}(v_i) = \frac{w_i}{n_i} + c \cdot P(a|s) \sqrt{\frac{N}{1 + n_i}} ]
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 走法生成 | ( O(n) ) | ( n ) 为当前玩家棋子数，每枚棋子走法有限 |
| 单次模拟 | ( O(d \cdot n) ) | ( d ) 为模拟深度 |
| 完整搜索 | ( O(K \cdot d \cdot n) ) | ( K ) 为迭代次数 |
| 空间复杂度 | ( O(K) ) | 搜索树节点数与迭代次数成正比 |
总结
本文实现了基于MCTS的中国象棋AI，通过UCB1公式平衡探索与利用，在有限迭代次数内找到高质量走法。相比传统的Alpha-Beta剪枝，MCTS不需要复杂的评估函数，而是通过随机模拟自动学习局面价值。这使得MCTS特别适合于分支因子大、局面评估困难的游戏。
在实际应用中，可以结合深度学习策略网络提供先验走法概率，使用虚拟损失实现并行搜索，从而将MCTS的棋力提升到专业水平。本文的Java实现提供了完整的框架基础，便于后续扩展和优化。
