引言
中国象棋是流传千年的双人博弈游戏，规则精炼却蕴含极深的策略空间。其状态复杂度约为 $10^{40}$，远超国际象棋，这使得暴力搜索完全不可行。本文将用 Java 实现一个具备基础 AI 能力的中国象棋引擎，核心围绕 Alpha-Beta 剪枝搜索 与 Zobrist 哈希置换表 两大算法展开，读者将完整理解从棋局表示、着法生成到智能决策的全链路设计。
一、棋局表示：一维数组与位运算
中国象棋棋盘为 $9 \times 10$ 的交叉点。采用长度为 256 的一维数组（$16 \times 16$）进行表示，以边界哨兵简化越界判断：真实棋盘从数组索引 0x33（第3行第3列）开始布局，四周填充无效值作为边界。
/**
* 棋盘表示类：使用256长度的一维数组，以16x16网格包裹真实9x10棋盘
* 真实棋盘起始索引为0x33(第3行第3列)，边界填充无效棋子作为哨兵
*/
public class Board {
// 棋子编码：低4位表示类型，第5位表示颜色（0红1黑）
static final int EMPTY = 0;
static final int KING = 1, ADVISOR = 2, BISHOP = 3;
static final int KNIGHT = 4, ROOK = 5, CANNON = 6, PAWN = 7;
static final int RED = 0, BLACK = 16;
// 256长度棋盘数组，索引计算：sq = (row + 3) * 16 + (col + 3)
private final int[] squares = new int[256];
// 初始棋盘布局（从黑方视角的第0行到第9行）
private static final String INIT_FEN =
"rnbakabnr/9/1c5c1/p1p1p1p1p/9/9/P1P1P1P1P/1C5C1/9/RNBAKABNR w";
public Board() {
loadFen(INIT_FEN);
}
/**
* 从FEN字符串加载棋局
* @param fen 标准中国象棋FEN格式字符串
*/
private void loadFen(String fen) {
Arrays.fill(squares, -1); // 边界哨兵
String[] parts = fen.split(" ");
String[] rows = parts[0].split("/");
for (int i = 0; i < 10; i++) {
int col = 0;
for (char c : rows[i].toCharArray()) {
if (Character.isDigit(c)) {
col += c - '0';
} else {
int sq = ((i + 3) << 4) + (col + 3);
squares[sq] = charToPiece(c);
col++;
}
}
}
}
private int charToPiece(char c) {
return switch (Character.toLowerCase(c)) {
case 'k' -> KING;
case 'a' -> ADVISOR;
case 'b' -> BISHOP;
case 'n' -> KNIGHT;
case 'r' -> ROOK;
case 'c' -> CANNON;
case 'p' -> PAWN;
default -> EMPTY;
} | (Character.isLowerCase(c) ? BLACK : RED);
}
public int getPiece(int sq) { return squares[sq]; }
public void setPiece(int sq, int pc) { squares[sq] = pc; }
/**
* 将二维坐标(row, col)转换为一维数组索引
*/
public static int coordToSq(int row, int col) {
return ((row + 3) << 4) + (col + 3);
}
/**
* 从数组索引反推二维坐标
*/
public static int sqToRow(int sq) { return (sq >> 4) - 3; }
public static int sqToCol(int sq) { return (sq & 15) - 3; }
}
二、着法生成：规则引擎与预计算偏移量
着法生成的核心是为每种棋子根据其走棋规则，枚举所有合法目标位置。利用预计算的偏移量数组，可避免复杂的分支判断。
/**
* 着法生成器：预计算各类棋子的偏移量，按规则生成所有合法着法
*/
public class MoveGenerator {
// 王/将的偏移量（只能在九宫内，上下左右）
private static final int[] KING_DELTA = {-16, 16, -1, 1};
// 士/仕的偏移量（斜向）
private static final int[] ADVISOR_DELTA = {-17, -15, 15, 17};
// 象/相的偏移量（田字格）
private static final int[] BISHOP_DELTA = {-34, -30, 30, 34};
// 象眼偏移量（用于塞象眼判断）
private static final int[] BISHOP_EYE_DELTA = {-17, -15, 15, 17};
// 马的偏移量（日字格，8个方向）
private static final int[] KNIGHT_DELTA = {-33, -31, -18, -14, 14, 18, 31, 33};
// 马腿偏移量（8个方向对应的蹩马腿位置）
private static final int[] KNIGHT_LEG_DELTA = {-17, -15, -17, -15, 15, 17, 15, 17};
private final Board board;
private final List<Move> moves = new ArrayList<>();
public MoveGenerator(Board board) { this.board = board; }
/**
* 生成指定方的所有合法着法
* @param side 当前方（RED或BLACK）
* @return 合法着法列表
*/
public List<Move> generateMoves(int side) {
moves.clear();
for (int sq = Board.coordToSq(0, 0); sq <= Board.coordToSq(9, 8); sq++) {
int pc = board.getPiece(sq);
if (pc == 0 || (pc & 16) != side) continue;
int pieceType = pc & 15;
switch (pieceType) {
case Board.KING -> generateKingMoves(sq, side);
case Board.ADVISOR -> generateAdvisorMoves(sq, side);
case Board.BISHOP -> generateBishopMoves(sq, side);
case Board.KNIGHT -> generateKnightMoves(sq, side);
case Board.ROOK -> generateRookMoves(sq, side);
case Board.CANNON -> generateCannonMoves(sq, side);
case Board.PAWN -> generatePawnMoves(sq, side);
}
}
return moves;
}
private void generateKingMoves(int sq, int side) {
for (int d : KING_DELTA) {
int dst = sq + d;
if (inPalace(dst, side) && isValidTarget(dst, side)) {
moves.add(new Move(sq, dst));
}
}
// 王对王规则：若两王在同一列且中间无子，可直接将军
int oppKing = findKing(side == Board.RED ? Board.BLACK : Board.RED);
if (oppKing != -1 && Board.sqToCol(sq) == Board.sqToCol(oppKing)) {
boolean blocked = false;
int step = oppKing > sq ? 16 : -16;
for (int p = sq + step; p != oppKing; p += step) {
if (board.getPiece(p) != Board.EMPTY) { blocked = true; break; }
}
if (!blocked) moves.add(new Move(sq, oppKing));
}
}
private boolean inPalace(int sq, int side) {
int row = Board.sqToRow(sq), col = Board.sqToCol(sq);
if (col < 3 || col > 5) return false;
return side == Board.RED ? (row >= 7 && row <= 9) : (row >= 0 && row <= 2);
}
private void generateAdvisorMoves(int sq, int side) {
for (int d : ADVISOR_DELTA) {
int dst = sq + d;
if (inPalace(dst, side) && isValidTarget(dst, side)) {
moves.add(new Move(sq, dst));
}
}
}
private void generateBishopMoves(int sq, int side) {
for (int i = 0; i < 4; i++) {
int dst = sq + BISHOP_DELTA[i];
int eye = sq + BISHOP_EYE_DELTA[i];
if (inBishopHalf(dst, side) && board.getPiece(eye) == Board.EMPTY
&& isValidTarget(dst, side)) {
moves.add(new Move(sq, dst));
}
}
}
private boolean inBishopHalf(int sq, int side) {
int row = Board.sqToRow(sq), col = Board.sqToCol(sq);
if ((row + col) % 2 != 0) return false; // 象只能走同色格
return side == Board.RED ? (row >= 5 && row <= 9) : (row >= 0 && row <= 4);
}
private void generateKnightMoves(int sq, int side) {
for (int i = 0; i < 8; i++) {
int dst = sq + KNIGHT_DELTA[i];
int leg = sq + KNIGHT_LEG_DELTA[i];
if (board.getPiece(leg) == Board.EMPTY && isValidTarget(dst, side)) {
moves.add(new Move(sq, dst));
}
}
}
private void generateRookMoves(int sq, int side) {
for (int d : new int[]{-16, 16, -1, 1}) {
for (int dst = sq + d; board.getPiece(dst) != -1; dst += d) {
int target = board.getPiece(dst);
if (target == Board.EMPTY) {
moves.add(new Move(sq, dst));
} else {
if ((target & 16) != side) moves.add(new Move(sq, dst));
break;
}
}
}
}
private void generateCannonMoves(int sq, int side) {
for (int d : new int[]{-16, 16, -1, 1}) {
boolean overPiece = false;
for (int dst = sq + d; board.getPiece(dst) != -1; dst += d) {
int target = board.getPiece(dst);
if (!overPiece) {
if (target == Board.EMPTY) {
moves.add(new Move(sq, dst));
} else {
overPiece = true;
}
} else {
if (target != Board.EMPTY) {
if ((target & 16) != side) moves.add(new Move(sq, dst));
break;
}
}
}
}
}
private void generatePawnMoves(int sq, int side) {
int row = Board.sqToRow(sq);
int forward = side == Board.RED ? -16 : 16;
// 向前
int dst = sq + forward;
if (board.getPiece(dst) != -1 && isValidTarget(dst, side)) {
moves.add(new Move(sq, dst));
}
// 过河后可以左右移动
boolean crossed = side == Board.RED ? row <= 4 : row >= 5;
if (crossed) {
for (int d : new int[]{-1, 1}) {
dst = sq + d;
if (board.getPiece(dst) != -1 && isValidTarget(dst, side)) {
moves.add(new Move(sq, dst));
}
}
}
}
private boolean isValidTarget(int sq, int side) {
int pc = board.getPiece(sq);
return pc == Board.EMPTY || (pc & 16) != side;
}
private int findKing(int side) {
for (int sq = Board.coordToSq(0, 0); sq <= Board.coordToSq(9, 8); sq++) {
int pc = board.getPiece(sq);
if ((pc & 15) == Board.KING && (pc & 16) == side) return sq;
}
return -1;
}
/**
* 着法对象：包含源位置和目标位置
*/
public record Move(int from, int to) {}
}
三、评估函数：子力价值与位置加分
评估函数是 AI 的”眼睛”，决定搜索终点局面优劣。本文采用子力价值表加位置分的经典方案，对每种棋子在每个位置预设一个附加值。
/**
* 评估器：结合子力价值和位置分进行局面评分
* 分数为正表示红方优势，为负表示黑方优势
*/
public class Evaluator {
// 基础子力价值（兵/卒在不同行价值不同）
private static final int[] PIECE_VALUE = {
0, // EMPTY
10000, // KING
250, // ADVISOR
250, // BISHOP
400, // KNIGHT
900, // ROOK
450, // CANNON
100 // PAWN (基准值，实际按位置动态调整)
};
// 兵/卒的位置分表（红方视角，黑方需要镜像）
private static final int[][] PAWN_POSITION = new int[10][9];
// 马的位置分表
private static final int[][] KNIGHT_POSITION = new int[10][9];
// 车的位置分表
private static final int[][] ROOK_POSITION = new int[10][9];
// 炮的位置分表
private static final int[][] CANNON_POSITION = new int[10][9];
static {
initPawnTable();
initKnightTable();
initRookTable();
initCannonTable();
}
private static void initPawnTable() {
// 兵过河后价值提升，逼近对方老将位置分数更高
int[][] base = {
{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},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{10, 10, 15, 20, 20, 20, 15, 10, 10}, // 过河
{15, 20, 25, 30, 30, 30, 25, 20, 15},
{20, 30, 40, 50, 50, 50, 40, 30, 20},
{30, 40, 50, 60, 60, 60, 50, 40, 30},
{40, 50, 60, 70, 80, 70, 60, 50, 40}
};
for (int r = 0; r < 10; r++) System.arraycopy(base[r], 0, PAWN_POSITION[r], 0, 9);
}
private static void initKnightTable() {
int[][] base = {
{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},
{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},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0}
};
// 马在开阔位置更灵活，中心及河道位置价值更高
for (int r = 2; r <= 7; r++) {
for (int c = 1; c <= 7; c++) {
base[r][c] = 20;
}
}
for (int r = 0; r < 10; r++) System.arraycopy(base[r], 0, KNIGHT_POSITION[r], 0, 9);
}
private static void initRookTable() {
// 车在棋盘任何位置都强力，但在中线和横线交汇处更具控制力
for (int r = 0; r < 10; r++) {
for (int c = 0; c < 9; c++) {
ROOK_POSITION[r][c] = (c == 4 || r == 4 || r == 5) ? 15 : 5;
}
}
}
private static void initCannonTable() {
// 炮需要依托炮台，在阵地战中价值高，开局略低
for (int r = 0; r < 10; r++) {
for (int c = 0; c < 9; c++) {
CANNON_POSITION[r][c] = (r >= 2 && r <= 7) ? 10 : 5;
}
}
}
/**
* 评估当前局面得分
* @param board 当前棋盘
* @return 分数（红方为正，黑方为负）
*/
public int evaluate(Board board) {
int score = 0;
for (int sq = Board.coordToSq(0, 0); sq <= Board.coordToSq(9, 8); sq++) {
int pc = board.getPiece(sq);
if (pc == Board.EMPTY) continue;
int type = pc & 15;
int side = pc & 16;
int row = Board.sqToRow(sq);
int col = Board.sqToCol(sq);
int value = PIECE_VALUE[type];
int posValue = getPositionValue(type, row, col, side);
// 红方加分，黑方减分
if (side == Board.RED) {
score += value + posValue;
} else {
score -= value + posValue;
}
}
return score;
}
private int getPositionValue(int type, int row, int col, int side) {
// 黑方需要镜像行索引
int mappedRow = side == Board.RED ? row : 9 - row;
return switch (type) {
case Board.PAWN -> PAWN_POSITION[mappedRow][col];
case Board.KNIGHT -> KNIGHT_POSITION[mappedRow][col];
case Board.ROOK -> ROOK_POSITION[mappedRow][col];
case Board.CANNON -> CANNON_POSITION[mappedRow][col];
default -> 0;
};
}
}
四、Alpha-Beta 剪枝：极小极大搜索的加速利器
Alpha-Beta 剪枝是博弈树搜索的核心算法，在 Minimax 基础上维护 $\alpha$（己方已确认的最优下界）和 $\beta$（对方已确认的最优上界），当 $\alpha \geq \beta$ 时剪去不可影响决策的分支。
/**
* 搜索引擎：实现Alpha-Beta剪枝与迭代加深
*/
public class SearchEngine {
private final Board board;
private final Evaluator evaluator;
private final MoveGenerator moveGen;
private final TranspositionTable tt;
private int nodesSearched; // 统计搜索节点数
private int cutoffs; // 统计剪枝次数
private Move bestMove; // 当前最佳着法
private boolean timeUp; // 时间标志（用于软时限）
// 极大/极小值边界
private static final int INFINITY = 1000000;
private static final int MATE_VALUE = 900000;
public SearchEngine(Board board) {
this.board = board;
this.evaluator = new Evaluator();
this.moveGen = new MoveGenerator(board);
this.tt = new TranspositionTable();
}
/**
* 迭代加深搜索：逐层加深，既保证随时有合法着法，又利于置换表命中
* @param side 当前方
* @param maxDepth 最大搜索深度
* @return 当前最佳着法
*/
public Move iterativeDeepening(int side, int maxDepth) {
bestMove = null;
for (int depth = 2; depth <= maxDepth; depth++) {
nodesSearched = 0;
cutoffs = 0;
timeUp = false;
Move mv = alphaBetaRoot(side, depth);
if (mv != null) bestMove = mv;
System.out.printf("深度 %d: 节点=%d, 剪枝=%d, 推荐=%s%n",
depth, nodesSearched, cutoffs, mv);
}
return bestMove;
}
private Move alphaBetaRoot(int side, int depth) {
List<MoveGenerator.Move> moves = moveGen.generateMoves(side);
if (moves.isEmpty()) return null;
// 按历史启发排序，优先搜索可能引发剪枝的着法
moves.sort((a, b) -> historyHeuristic(b) - historyHeuristic(a));
int bestScore = -INFINITY;
Move best = null;
for (MoveGenerator.Move mv : moves) {
int captured = makeMove(mv);
int score = -alphaBeta(side == Board.RED ? Board.BLACK : Board.RED,
depth - 1, -INFINITY, INFINITY);
undoMove(mv, captured);
if (score > bestScore) {
bestScore = score;
best = mv;
}
}
return best;
}
/**
* Alpha-Beta剪枝核心递归函数
* @param side 当前行棋方
* @param depth 剩余搜索深度
* @param alpha 当前最优下界
* @param beta 当前最优上界
* @return 当前局面的评估分数
*/
private int alphaBeta(int side, int depth, int alpha, int beta) {
nodesSearched++;
// 1. 查置换表
long key = board.getZobristKey();
TTEntry entry = tt.probe(key);
if (entry != null && entry.depth >= depth) {
if (entry.flag == TTEntry.EXACT) return entry.score;
if (entry.flag == TTEntry.LOWER && entry.score >= beta) return entry.score;
if (entry.flag == TTEntry.UPPER && entry.score <= alpha) return entry.score;
}
// 2. 终止条件：深度为0或游戏结束
if (depth <= 0) return quiescenceSearch(side, alpha, beta);
List<MoveGenerator.Move> moves = moveGen.generateMoves(side);
if (moves.isEmpty()) {
// 无合法着法：若被将军则判负，否则和棋
return isInCheck(side) ? -(MATE_VALUE + depth) : 0;
}
// 3. 按历史启发排序（MVV-LVA + 杀手启发可进一步优化）
moves.sort((a, b) -> historyHeuristic(b) - historyHeuristic(a));
int bestScore = -INFINITY;
int flag = TTEntry.UPPER;
for (MoveGenerator.Move mv : moves) {
int captured = makeMove(mv);
int score = -alphaBeta(side == Board.RED ? Board.BLACK : Board.RED,
depth - 1, -beta, -alpha);
undoMove(mv, captured);
if (score > bestScore) {
bestScore = score;
if (score > alpha) {
alpha = score;
flag = TTEntry.EXACT;
if (depth == 2) bestMove = mv; // 更新根节点最佳着法
}
}
if (alpha >= beta) {
cutoffs++;
flag = TTEntry.LOWER;
updateHistoryHeuristic(mv, depth);
break; // Beta剪枝
}
}
// 4. 存入置换表
tt.store(key, depth, bestScore, flag, bestMove);
return bestScore;
}
/**
* 静态搜索（Quiescence Search）：在叶子节点只搜索吃子着法，避免水平线效应
*/
private int quiescenceSearch(int side, int alpha, int beta) {
int standPat = evaluator.evaluate(board);
if (standPat >= beta) return beta;
if (alpha < standPat) alpha = standPat;
// 只生成吃子着法
List<MoveGenerator.Move> captures = moveGen.generateMoves(side).stream()
.filter(mv -> board.getPiece(mv.to()) != Board.EMPTY)
.toList();
for (MoveGenerator.Move mv : captures) {
int captured = makeMove(mv);
int score = -quiescenceSearch(side == Board.RED ? Board.BLACK : Board.RED, -beta, -alpha);
undoMove(mv, captured);
if (score >= beta) return beta;
if (score > alpha) alpha = score;
}
return alpha;
}
private boolean isInCheck(int side) {
// 简化实现：检查对方是否能吃掉我方老将
int opp = side == Board.RED ? Board.BLACK : Board.RED;
List<MoveGenerator.Move> oppMoves = moveGen.generateMoves(opp);
int kingSq = findKing(side);
for (MoveGenerator.Move mv : oppMoves) {
if (mv.to() == kingSq) return true;
}
return false;
}
private int findKing(int side) {
for (int sq = Board.coordToSq(0, 0); sq <= Board.coordToSq(9, 8); sq++) {
int pc = board.getPiece(sq);
if ((pc & 15) == Board.KING && (pc & 16) == side) return sq;
}
return -1;
}
private int makeMove(MoveGenerator.Move mv) {
int captured = board.getPiece(mv.to());
board.setPiece(mv.to(), board.getPiece(mv.from()));
board.setPiece(mv.from(), Board.EMPTY);
board.updateZobrist(mv, captured);
return captured;
}
private void undoMove(MoveGenerator.Move mv, int captured) {
board.setPiece(mv.from(), board.getPiece(mv.to()));
board.setPiece(mv.to(), captured);
board.updateZobrist(mv, captured);
}
// 历史启发表：记录某着法引发剪枝的次数
private final int[][] history = new int[256][256];
private int historyHeuristic(MoveGenerator.Move mv) {
return history[mv.from()][mv.to()];
}
private void updateHistoryHeuristic(MoveGenerator.Move mv, int depth) {
history[mv.from()][mv.to()] += depth * depth;
}
public int getNodesSearched() { return nodesSearched; }
public int getCutoffs() { return cutoffs; }
}
五、Zobrist 哈希：高效的状态指纹与置换表
Zobrist 哈希为每个棋盘状态生成一个伪随机的 64 位指纹，支持 $O(1)$ 的增量更新。置换表（Transposition Table）利用该指纹缓存已搜索局面的结果，避免重复计算。
/**
* Zobrist哈希生成器：为每个(位置, 棋子)组合预分配随机数
*/
public class Zobrist {
// 256位置 * 32种棋子编码（含颜色） = 8192个随机数
private static final long[][] KEYS = new long[256][32];
private static final long SIDE_KEY; // 行棋方切换用的随机数
static {
Random rand = new Random(0x5D41402ABC4B2A76L); // 固定种子保证可复现
for (int sq = 0; sq < 256; sq++) {
for (int pc = 0; pc < 32; pc++) {
KEYS[sq][pc] = rand.nextLong();
}
}
SIDE_KEY = rand.nextLong();
}
public static long getKey(int sq, int pc) {
return KEYS[sq][pc];
}
public static long getSideKey() { return SIDE_KEY; }
}
/**
* 置换表条目：缓存搜索深度、分数、标志位和最佳着法
*/
public class TTEntry {
public static final int UPPER = 0, LOWER = 1, EXACT = 2;
public long key; // Zobrist哈希值
public int depth; // 搜索深度
public int score; // 评估分数
public int flag; // 节点类型（UPPER/LOWER/EXACT）
public Move bestMove; // 该节点最佳着法
public TTEntry(long key, int depth, int score, int flag, Move bestMove) {
this.key = key; this.depth = depth; this.score = score;
this.flag = flag; this.bestMove = bestMove;
}
}
/**
* 置换表：使用简单的线性探测哈希表
*/
public class TranspositionTable {
private static final int SIZE = 1 << 20; // 约100万条目
private final TTEntry[] table = new TTEntry[SIZE];
public TTEntry probe(long key) {
int idx = (int) (key & (SIZE - 1));
TTEntry e = table[idx];
return (e != null && e.key == key) ? e : null;
}
public void store(long key, int depth, int score, int flag, Move bestMove) {
int idx = (int) (key & (SIZE - 1));
TTEntry existing = table[idx];
// 替换策略：深度更深或同深度覆盖
if (existing == null || existing.depth <= depth) {
table[idx] = new TTEntry(key, depth, score, flag, bestMove);
}
}
}
六、完整运行入口与测试
/**
* 主程序：初始化棋盘并启动AI搜索
*/
public class ChineseChessAI {
public static void main(String[] args) {
Board board = new Board();
SearchEngine engine = new SearchEngine(board);
System.out.println("=== 中国象棋AI引擎启动 ===");
System.out.println("初始局面FEN: rnbakabnr/9/1c5c1/p1p1p1p1p/9/9/P1P1P1P1P/1C5C1/9/RNBAKABNR w");
// 红方先走，搜索深度4层（生产环境建议6-8层）
MoveGenerator.Move best = engine.iterativeDeepening(Board.RED, 4);
if (best != null) {
System.out.printf("\\n推荐着法: %c%d -> %c%d%n",
(char) ('a' + Board.sqToCol(best.from())),
9 - Board.sqToRow(best.from()),
(char) ('a' + Board.sqToCol(best.to())),
9 - Board.sqToRow(best.to()));
}
System.out.printf("总搜索节点: %d, 剪枝次数: %d%n",
engine.getNodesSearched(), engine.getCutoffs());
}
}
七、复杂度分析
| 模块 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 着法生成 | $O(n)$ | $O(1)$ | $n$ 为单步合法着法数，车炮扫描最坏约 17 种 |
| Alpha-Beta 搜索 | $O(b^{d/2})$ | $O(d)$ | 理想剪枝将分支因子 $b$ 的指数减半 |
| 置换表查询 | $O(1)$ | $O(SIZE)$ | $SIZE$ 取 $2^{20}$ 时约占用 56MB |
| 评估函数 | $O(1)$ | $O(1)$ | 固定遍历 90 个交叉点，常数级 |
八、总结
本文完整实现了一个基于 Java 的中国象棋 AI 引擎，核心算法要点如下：
- 一维数组 + 边界哨兵 的棋盘表示，将越界判断简化为单次数组访问。
- 预计算偏移量 的着法生成，使每种棋子的走法规则清晰可维护。
- 子力价值 + 位置分 的评估函数，为搜索终点提供可量化的局面优劣依据。
- Alpha-Beta 剪枝 将博弈树搜索效率从 $O(b^d)$ 提升到 $O(b^{d/2})$，配合迭代加深随时可用。
- Zobrist 哈希置换表 以 $O(1)$ 时间消除重复局面计算，是引擎强度跃升的关键。
读者可在此基础上继续引入 MVV-LVA 吃子排序、杀手启发、空着裁剪（Null Move Pruning） 等高级优化，进一步提升搜索深度与棋力。
