中国象棋残局是棋艺的精华所在，许多经典残局蕴含着深刻的算法思想。与完整对局不同，残局求解需要在有限子力下找到必胜或必和路径。本文用Java实现中国象棋残局库系统，核心采用逆向搜索（Retrograde Analysis）算法，从终局状态反向推导每个局面的最优结果。
一、残局库与逆向搜索原理
传统正向搜索从初始局面出发探索所有可能走法，在残局中往往效率低下。逆向搜索则反其道而行：
- 确定终局状态：将所有已分出胜负的局面（如将死、困毙）标记为已解决
- 反向传播：对每个已解决的局面，找到能一步到达它的前驱局面
- 逐步推导：根据前驱局面的所有后继是否已解决，判断该前驱的最优结果
局面分类为三种：胜（当前方必胜）、负（当前方必负）、和（双方最优则为和棋）。
二、Java核心实现
import java.util.*;
/**
* 中国象棋残局库：逆向搜索求解器
*/
public class XiangqiEndgameSolver {
// 棋子编码
static final int EMPTY = 0;
static final int RK = 1; // 红帅
static final int RA = 2; // 红仕
static final int RB = 3; // 红相
static final int RN = 4; // 红马
static final int RR = 5; // 红车
static final int RC = 6; // 红炮
static final int RP = 7; // 红兵
static final int BK = 8; // 黑将
static final int BA = 9; // 黑士
static final int BB = 10; // 黑象
static final int BN = 11; // 黑马
static final int BR = 12; // 黑车
static final int BC = 13; // 黑炮
static final int BP = 14; // 黑卒
// 局面结果状态
static final int UNKNOWN = 0;
static final int WIN = 1; // 当前行棋方必胜
static final int LOSE = 2; // 当前行棋方必负
static final int DRAW = 3; // 和棋
// 棋盘 10行 x 9列
static final int ROWS = 10;
static final int COLS = 9;
// Zobrist哈希用于局面唯一标识
private long[][][] zobristTable;
private Random zobristRand;
public XiangqiEndgameSolver() {
this.zobristRand = new Random(2024);
this.zobristTable = new long[ROWS][COLS][15];
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
for (int p = 0; p < 15; p++) {
zobristTable[r][c][p] = zobristRand.nextLong();
}
}
}
}
/**
* 局面表示类
*/
static class Position {
int[][] board = new int[ROWS][COLS];
int sideToMove; // 1=红方, 2=黑方
Position() {}
Position copy() {
Position p = new Position();
for (int i = 0; i < ROWS; i++) {
System.arraycopy(this.board[i], 0, p.board[i], 0, COLS);
}
p.sideToMove = this.sideToMove;
return p;
}
/**
* 计算Zobrist哈希值
*/
long hash(XiangqiEndgameSolver solver) {
long h = 0;
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (board[r][c] != EMPTY) {
h ^= solver.zobristTable[r][c][board[r][c]];
}
}
}
if (sideToMove == 2) {
h ^= 0xABCDEF1234567890L;
}
return h;
}
/**
* 判断当前方是否被将死
*/
boolean isCheckmated() {
// 简化版：先检查是否被将军
if (!isInCheck()) return false;
// 再检查是否有任何合法走法可以解除将军
List<Move> moves = generateAllMoves();
for (Move m : moves) {
Position next = makeMove(m);
if (!next.isInCheck()) {
return false;
}
}
return true;
}
/**
* 检查当前行棋方是否被将军（简化版）
*/
boolean isInCheck() {
// 找到己方将/帅位置
int kr = -1, kc = -1;
int myKing = (sideToMove == 1) ? RK : BK;
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (board[r][c] == myKing) {
kr = r; kc = c; break;
}
}
}
if (kr == -1) return true; // 无将=输
// 检查对方每个棋子是否能攻击到将/帅位置
int opponent = 3 - sideToMove;
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
int piece = board[r][c];
if (piece != EMPTY && getSide(piece) == opponent) {
if (canAttack(r, c, kr, kc, piece)) {
return true;
}
}
}
}
return false;
}
/**
* 判断piece在(fromR, fromC)能否攻击(toR, toC)（简化版核心逻辑）
*/
boolean canAttack(int fromR, int fromC, int toR, int toC, int piece) {
int dr = Math.abs(toR - fromR);
int dc = Math.abs(toC - fromC);
switch (piece) {
case RK: case BK: // 将/帅只能走一格，且不能出九宫
return dr <= 1 && dc <= 1 && dr + dc == 1;
case RR: case BR: // 车：直线，中间无阻挡
if (fromR == toR) {
int minC = Math.min(fromC, toC);
int maxC = Math.max(fromC, toC);
for (int c = minC + 1; c < maxC; c++) {
if (board[fromR][c] != EMPTY) return false;
}
return true;
} else if (fromC == toC) {
int minR = Math.min(fromR, toR);
int maxR = Math.max(fromR, toR);
for (int r = minR + 1; r < maxR; r++) {
if (board[r][fromC] != EMPTY) return false;
}
return true;
}
return false;
case RN: case BN: // 马：日字，无蹩脚
return (dr == 2 && dc == 1) || (dr == 1 && dc == 2);
case RP: case BP: // 兵/卒：向前，过河后可横走
int forward = (piece == RP) ? -1 : 1;
if (toR == fromR + forward && toC == fromC) return true;
boolean crossed = (piece == RP) ? (fromR < 5) : (fromR > 4);
if (crossed && toR == fromR && Math.abs(toC - fromC) == 1) return true;
return false;
default:
return false;
}
}
/**
* 生成当前方所有合法走法
*/
List<Move> generateAllMoves() {
List<Move> moves = new ArrayList<>();
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
int piece = board[r][c];
if (piece != EMPTY && getSide(piece) == sideToMove) {
generateMovesForPiece(r, c, piece, moves);
}
}
}
return moves;
}
void generateMovesForPiece(int r, int c, int piece, List<Move> moves) {
// 简化版：遍历所有目标位置检查合法性
for (int tr = 0; tr < ROWS; tr++) {
for (int tc = 0; tc < COLS; tc++) {
if (tr == r && tc == c) continue;
int target = board[tr][tc];
// 不能吃己方棋子
if (target != EMPTY && getSide(target) == sideToMove) continue;
if (canAttack(r, c, tr, tc, piece)) {
moves.add(new Move(r, c, tr, tc));
}
}
}
}
/**
* 执行走法返回新局面
*/
Position makeMove(Move m) {
Position next = copy();
next.board[m.toR][m.toC] = next.board[m.fromR][m.fromC];
next.board[m.fromR][m.fromC] = EMPTY;
next.sideToMove = 3 - sideToMove;
return next;
}
static int getSide(int piece) {
if (piece >= RK && piece <= RP) return 1;
if (piece >= BK && piece <= BP) return 2;
return 0;
}
}
/**
* 走法表示
*/
static class Move {
int fromR, fromC, toR, toC;
Move(int fr, int fc, int tr, int tc) {
this.fromR = fr; this.fromC = fc;
this.toR = tr; this.toC = tc;
}
}
/**
* 局面数据库条目
*/
static class Entry {
int result = UNKNOWN; // WIN/LOSE/DRAW
int distance = -1; // 到终局的距离（步数）
Move bestMove = null; // 最优走法
int unresolvedSucc = 0; // 未解决的后继局面数
Entry() {}
}
// 局面数据库：Zobrist哈希 -> 条目
private Map<Long, Entry> database = new HashMap<>();
/**
* 核心逆向搜索算法
*/
void retrogradeAnalysis(List<Position> initialPositions) {
Queue<Position> queue = new LinkedList<>();
// 第一步：标记所有终局局面
for (Position pos : initialPositions) {
long h = pos.hash(this);
Entry e = new Entry();
if (pos.isCheckmated()) {
// 被将死 = 当前方负
e.result = LOSE;
e.distance = 0;
database.put(h, e);
queue.add(pos);
} else {
// 非终局局面，初始化未解决后继数
List<Move> moves = pos.generateAllMoves();
e.unresolvedSucc = moves.size();
database.put(h, e);
}
}
System.out.println("Initial solved positions: " + queue.size());
// 第二步：逆向传播
int iteration = 0;
while (!queue.isEmpty()) {
Position solvedPos = queue.poll();
long solvedHash = solvedPos.hash(this);
Entry solvedEntry = database.get(solvedHash);
iteration++;
// 找到所有能一步到达solvedPos的前驱局面
// 前驱局面的行棋方是solvedPos的对方
List<Position> predecessors = findPredecessors(solvedPos);
for (Position pred : predecessors) {
long predHash = pred.hash(this);
Entry predEntry = database.get(predHash);
if (predEntry == null) {
predEntry = new Entry();
List<Move> predMoves = pred.generateAllMoves();
predEntry.unresolvedSucc = predMoves.size();
database.put(predHash, predEntry);
}
// 如果前驱局面已解决，跳过
if (predEntry.result != UNKNOWN) continue;
// 逆向推理逻辑
// solvedPos是前驱局面某个走法的结果
// 如果solvedPos对solvedPos的行棋方是WIN/LOSE
// 那么对前驱局面（行棋方相反）就是LOSE/WIN
if (solvedEntry.result == LOSE) {
// 后继局面对对方是LOSE，意味着对前驱方是WIN
// 因为前驱方走了一步让对方必负的棋
predEntry.result = WIN;
predEntry.distance = solvedEntry.distance + 1;
queue.add(pred);
} else if (solvedEntry.result == WIN) {
// 后继局面对对方是WIN，前驱方这个走法不好
// 减少未解决后继计数
predEntry.unresolvedSucc--;
// 如果所有后继都是对方WIN（即前驱方所有走法都导致对方WIN）
// 则前驱方必负
if (predEntry.unresolvedSucc == 0) {
predEntry.result = LOSE;
predEntry.distance = solvedEntry.distance + 1;
queue.add(pred);
}
} else if (solvedEntry.result == DRAW) {
// 如果某个后继是和棋，且暂时没发现WIN
// 标记为潜在DRAW（简化处理）
predEntry.unresolvedSucc--;
if (predEntry.unresolvedSucc == 0 && predEntry.result == UNKNOWN) {
predEntry.result = DRAW;
predEntry.distance = solvedEntry.distance + 1;
queue.add(pred);
}
}
}
}
System.out.println("Retrograde analysis completed after " + iteration + " iterations");
}
/**
* 查找前驱局面：所有side方走一步能到达pos的局面
* 这里简化实现：遍历pos的所有可能"反走法"
*/
List<Position> findPredecessors(Position pos) {
List<Position> preds = new ArrayList<>();
int opponent = 3 - pos.sideToMove; // 前驱局面的行棋方
// 对于pos中的每个棋子，假设它是上一步被对方走到这里的
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
int piece = pos.board[r][c];
if (piece != EMPTY && getOriginalSide(piece) == opponent) {
// 尝试将该棋子回退到所有可能的上一步位置
for (int pr = 0; pr < ROWS; pr++) {
for (int pc = 0; pc < COLS; pc++) {
if (pr == r && pc == c) continue;
// 构造前驱局面
Position pred = pos.copy();
pred.board[r][c] = EMPTY;
pred.board[pr][pc] = piece;
pred.sideToMove = opponent;
// 验证合法性：从pr,pc到r,c是否是piece的合法走法
if (pos.canAttack(pr, pc, r, c, piece)) {
preds.add(pred);
}
}
}
}
}
}
return preds;
}
static int getOriginalSide(int piece) {
return Position.getSide(piece);
}
/**
* 查询局面的最优结果
*/
Entry query(Position pos) {
long h = pos.hash(this);
return database.get(h);
}
/**
* 构建单马胜单士残局测试
*/
List<Position> buildTestEndgames() {
List<Position> positions = new ArrayList<>();
// 红方马对黑方士+将的多个初始局面
for (int kr = 0; kr < 3; kr++) {
for (int kc = 3; kc < 6; kc++) {
for (int nr = 0; nr < ROWS; nr++) {
for (int nc = 0; nc < COLS; nc++) {
if (nr == kr && nc == kc) continue;
Position pos = new Position();
pos.board[kr][kc] = BK;
pos.board[nr][nc] = RN;
pos.sideToMove = 2; // 黑方先行
positions.add(pos);
}
}
}
}
return positions;
}
public static void main(String[] args) {
XiangqiEndgameSolver solver = new XiangqiEndgameSolver();
// 构建测试残局面
List<Position> endgames = solver.buildTestEndgames();
System.out.println("Total endgame positions to analyze: " + endgames.size());
// 执行逆向搜索
long start = System.currentTimeMillis();
solver.retrogradeAnalysis(endgames);
long end = System.currentTimeMillis();
System.out.println("Analysis time: " + (end - start) + " ms");
System.out.println("Database size: " + solver.database.size());
// 统计结果
int winCount = 0, loseCount = 0, drawCount = 0, unknownCount = 0;
for (Entry e : solver.database.values()) {
switch (e.result) {
case WIN: winCount++; break;
case LOSE: loseCount++; break;
case DRAW: drawCount++; break;
default: unknownCount++;
}
}
System.out.println("WIN: " + winCount + ", LOSE: " + loseCount +
", DRAW: " + drawCount + ", UNKNOWN: " + unknownCount);
}
}
三、算法关键逻辑
逆向搜索的核心推理规则：
- 如果某个局面的任一后继对对方是必负（LOSE），则当前局面是必胜（WIN）
- 如果某个局面的所有后继对对方都是必胜（WIN），则当前局面是必负（LOSE）
- 如果存在和棋后继且没有必胜后继，则当前局面是和棋（DRAW）
这种从终局向初始状态反向推导的方式，避免了传统搜索在深局面时的指数爆炸问题。
四、Zobrist哈希与局面压缩
残局库可能包含数百万甚至上亿个局面，Zobrist哈希为每个局面提供几乎唯一的64位标识。结合哈希表存储，可以实现O(1)的局面查询。对于更大规模的残局库，通常采用完美哈希或磁盘数据库进行持久化存储。
五、复杂度分析
设残局涉及N个棋子，棋盘为10×9，则状态空间上界为 (15+1)^90，但实际合法局面远少于此。逆向搜索的时间复杂度与合法局面数和每个局面的平均分支因子成正比，通常为 O(S * b)，其中S是局面总数，b是分支因子。相比正向搜索的指数复杂度，逆向搜索只需线性遍历每个局面一次。
六、扩展方向
完整的中国象棋残局库需要处理更多棋子和更复杂的规则（如长将、自然限着等）。可以将残局库与在线搜索结合：开局查库，中局用搜索，残局再次查库。此外，压缩存储（如利用对称性减少局面数）和分布式计算是构建超大规模残局库的关键技术。
