每日算法 — 使用java实现中国象棋：Alpha-Beta剪枝与Zobrist哈希置换表

引言：从楚河汉界到博弈树搜索

中国象棋是起源于中国古代的经典二人博弈游戏，棋盘由九道直线和十道横线交叉组成，中间以”楚河汉界”分隔。双方各持十六枚棋子，目标是将死对方的”将（帅）”。从算法视角看，中国象棋是一个完全信息零和博弈——双方对局面信息完全透明，一方所得即另一方所失。

本文将用Java实现一个具备基础AI能力的中国象棋程序，核心算法包括：
– Alpha-Beta剪枝：在Minimax搜索框架上剪除无效分支，将搜索效率提升数倍
– Zobrist哈希：为每个局面生成唯一哈希值，支撑置换表的高效查询
– 置换表（Transposition Table）：缓存已搜索局面的评估结果，避免重复计算

通过这三个技术的组合，AI可以在有限的搜索深度内做出高质量的着法决策。

棋盘表示与着法生成

棋盘编码

采用10×9的二维数组表示棋盘，用整数编码棋子类型：

正负号区分红黑双方，便于统一判断阵营。

着法生成规则

每种棋子有独特的走法规则：
– 将/帅：九宫格内横竖一格，且不能照面
– 仕/士：九宫格内斜走一格
– 相/象：走”田”字，不能过河，不能被”塞象眼”
– 马：走”日”字，不能被”蹩马腿”
– 车：横竖直线，无阻挡可任意距离
– 炮：移动同车，吃子需隔一个棋子（炮架）
– 兵/卒：过河前只能前进，过河后可横移或前进，不能后退

着法生成的效率直接影响搜索深度，需要精细实现。

评估函数设计

评估函数是AI的”棋感”来源，将局面转化为可量化的分数。正数表示红方优势，负数表示黑方优势。

棋子基础价值

位置价值表（Piece-Square Table）

除基础价值外，同一棋子在棋盘不同位置具有不同的战术价值。例如：
– 马：在棋盘中心灵活，在边线活动受限
– 炮：需要炮架才能发挥威力，初始位置价值中等，残局价值上升
– 兵/卒：过河后价值大幅提升，逼近九宫时威胁剧增

位置价值表通过预计算的二维数组实现，评估时直接查表相加。

附加评估项

• 灵活性：棋子可移动位置的数量
• 将军威胁：直接攻击对方将/帅的额外奖励
• 棋子协同：车炮配合、马后炮等经典杀法的模式检测

Alpha-Beta剪枝搜索

Minimax基础

在二人零和博弈中，红方选择使自己得分最大的着法，黑方选择使红方得分最小（即自己得分最大）的着法。Minimax递归地模拟这一过程：

max层（红方）: 选择子节点中的最大评估值
min层（黑方）: 选择子节点中的最小评估值

Alpha-Beta剪枝原理

Minimax需要遍历整棵博弈树，效率极低。Alpha-Beta剪枝利用已搜索信息跳过不可能影响最终结果的分支：

• Alpha：max层当前能保证的最小得分下限
• Beta：min层当前能保证的最大得分上限

当在某节点发现 alpha >= beta 时，说明该分支的后续搜索结果不可能被选中，可以直接返回。

剪枝效率：在着法排序良好的情况下，Alpha-Beta的搜索节点数约为Minimax的平方根级别，即同样时间内搜索深度可翻倍。

迭代加深（Iterative Deepening）

从深度1开始逐步加深搜索，每一层复用上一层的着法排序信息（历史启发），使浅层搜索结果指导深层的着法排序，大幅提升剪枝效率。

Zobrist哈希与置换表

为什么需要置换表

在搜索过程中，同一局面可能通过不同的着法序列到达（称为置换）。例如先走”炮二平五”再走”马八进七”，与先走”马八进七”再走”炮二平五”，可能到达相同局面。如果不做缓存，同一局面会被重复评估多次，造成巨大浪费。

Zobrist哈希原理

为每个（棋子类型, 棋盘位置）组合预生成一个64位随机数。局面的哈希值为所有 occupied 位置对应随机数的异或（XOR）结果。

Zobrist哈希的优势：
– 增量更新：移动一个棋子只需两次XOR操作（旧位置异或去掉，新位置异或加入）
– 极低碰撞率：64位哈希的碰撞概率可忽略不计
– 快速计算：每次着法后的哈希值可在O(1)时间更新

置换表结构

置换表以Zobrist哈希值为Key，存储以下信息：
– depth：搜索到该局面的深度
– score：评估分数
– flag： exact（精确值）、lower bound（下界）、upper bound（上界）
– bestMove：该局面下的最佳着法（用于着法排序）

当搜索某局面前先查置换表：若表项深度大于等于当前剩余深度，可直接返回缓存结果。

完整Java实现

import java.util.*;

/**
 * 中国象棋AI核心实现
 * 核心技术：Alpha-Beta剪枝 + Zobrist哈希 + 置换表
 */
public class ChineseChessAI {

    // ==================== 常量定义 ====================
    static final int EMPTY = 0;
    static final int R_KING = 1, R_ADVISOR = 2, R_BISHOP = 3, R_KNIGHT = 4;
    static final int R_ROOK = 5, R_CANNON = 6, R_PAWN = 7;
    static final int B_KING = -1, B_ADVISOR = -2, B_BISHOP = -3, B_KNIGHT = -4;
    static final int B_ROOK = -5, B_CANNON = -6, B_PAWN = -7;

    // 棋盘 10行 × 9列
    int[][] board = new int[10][9];

    // 棋子基础价值
    static final int[] PIECE_VALUE = {0, 10000, 120, 120, 270, 600, 285, 60,
                                       0, -10000, -120, -120, -270, -600, -285, -60};
    // 注意：索引需要配合实际编码调整，这里简化示意

    // Zobrist哈希随机数表
    long[][][] zobristTable = new long[14][10][9]; // 14种棋子状态 × 10行 × 9列
    long zobristKey = 0; // 当前局面哈希值
    long zobristSide;    // 轮次翻转哈希值

    // 置换表
    Map<Long, TransEntry> transTable = new HashMap<>();

    static class TransEntry {
        int depth;
        int score;
        int flag; // 0=exact, 1=lower, 2=upper
        Move bestMove;
    }

    static class Move {
        int fromRow, fromCol, toRow, toCol;
        int captured; // 被吃掉的棋子
        int score;    // 历史启发分数

        Move(int fr, int fc, int tr, int tc) {
            this.fromRow = fr; this.fromCol = fc;
            this.toRow = tr; this.toCol = tc;
        }
    }

    // 历史启发表：记录某着法在以往搜索中引发剪枝的次数
    int[][][][] historyTable = new int[10][9][10][9];

    // ==================== 初始化 ====================

    public ChineseChessAI() {
        initZobrist();
        initBoard();
    }

    /** 初始化Zobrist随机数表 */
    void initZobrist() {
        Random rand = new Random(0x5DEECE66DL); // 固定种子保证可复现
        for (int p = 0; p < 14; p++) {
            for (int r = 0; r < 10; r++) {
                for (int c = 0; c < 9; c++) {
                    zobristTable[p][r][c] = rand.nextLong();
                }
            }
        }
        zobristSide = rand.nextLong();
    }

    /** 初始化标准开局棋盘 */
    void initBoard() {
        int[][] init = {
            {-5,-4,-3,-2,-1,-2,-3,-4,-5}, // 黑车 马 象 士 将
            { 0, 0, 0, 0, 0, 0, 0, 0, 0},
            { 0,-6, 0, 0, 0, 0, 0,-6, 0}, // 黑炮
            {-7, 0,-7, 0,-7, 0,-7, 0,-7}, // 黑卒
            { 0, 0, 0, 0, 0, 0, 0, 0, 0},
            { 0, 0, 0, 0, 0, 0, 0, 0, 0},
            { 7, 0, 7, 0, 7, 0, 7, 0, 7}, // 红兵
            { 0, 6, 0, 0, 0, 0, 0, 6, 0}, // 红炮
            { 0, 0, 0, 0, 0, 0, 0, 0, 0},
            { 5, 4, 3, 2, 1, 2, 3, 4, 5}  // 红车 马 相 仕 帅
        };
        for (int r = 0; r < 10; r++) {
            System.arraycopy(init[r], 0, board[r], 0, 9);
        }
        computeZobristKey();
    }

    /** 从零计算当前局面的Zobrist哈希值 */
    void computeZobristKey() {
        zobristKey = 0;
        for (int r = 0; r < 10; r++) {
            for (int c = 0; c < 9; c++) {
                int p = board[r][c];
                if (p != EMPTY) {
                    int idx = pieceToIndex(p);
                    zobristKey ^= zobristTable[idx][r][c];
                }
            }
        }
    }

    /** 棋子编码转Zobrist表索引：红1~7->0~6, 黑-1~-7->7~13 */
    int pieceToIndex(int p) {
        return p > 0 ? p - 1 : 7 + (-p) - 1;
    }

    /** 移动棋子后增量更新Zobrist哈希 */
    void updateZobrist(int fromR, int fromC, int toR, int toC, int movedPiece, int capturedPiece) {
        // 移走原位置
        zobristKey ^= zobristTable[pieceToIndex(movedPiece)][fromR][fromC];
        // 放入新位置
        zobristKey ^= zobristTable[pieceToIndex(movedPiece)][toR][toC];
        // 如果有吃子，移除被吃棋子
        if (capturedPiece != EMPTY) {
            zobristKey ^= zobristTable[pieceToIndex(capturedPiece)][toR][toC];
        }
        // 切换轮次
        zobristKey ^= zobristSide;
    }

    // ==================== 着法生成 ====================

    /** 生成指定阵营的所有合法着法 */
    List<Move> generateMoves(boolean redTurn) {
        List<Move> moves = new ArrayList<>();
        for (int r = 0; r < 10; r++) {
            for (int c = 0; c < 9; c++) {
                int p = board[r][c];
                if (p == EMPTY) continue;
                if (redTurn && p < 0) continue;
                if (!redTurn && p > 0) continue;
                generatePieceMoves(r, c, p, moves);
            }
        }
        return moves;
    }

    void generatePieceMoves(int r, int c, int p, List<Move> moves) {
        int absP = Math.abs(p);
        switch (absP) {
            case 1: generateKingMoves(r, c, p, moves); break;
            case 2: generateAdvisorMoves(r, c, p, moves); break;
            case 3: generateBishopMoves(r, c, p, moves); break;
            case 4: generateKnightMoves(r, c, p, moves); break;
            case 5: generateRookMoves(r, c, p, moves); break;
            case 6: generateCannonMoves(r, c, p, moves); break;
            case 7: generatePawnMoves(r, c, p, moves); break;
        }
    }

    void generateKingMoves(int r, int c, int p, List<Move> moves) {
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        boolean red = p > 0;
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (inKingPalace(nr, nc, red) && canMove(r, c, nr, nc, p)) {
                moves.add(new Move(r, c, nr, nc));
            }
        }
        // 照面检测：同列无阻挡可飞将
        int enemyKingRow = -1;
        for (int i = 0; i < 10; i++) {
            int tp = board[i][c];
            if (tp != EMPTY && Math.abs(tp) == 1 && tp * p < 0) {
                enemyKingRow = i; break;
            }
        }
        if (enemyKingRow != -1) {
            boolean blocked = false;
            int minR = Math.min(r, enemyKingRow);
            int maxR = Math.max(r, enemyKingRow);
            for (int i = minR + 1; i < maxR; i++) {
                if (board[i][c] != EMPTY) { blocked = true; break; }
            }
            if (!blocked) {
                moves.add(new Move(r, c, enemyKingRow, c));
            }
        }
    }

    boolean inKingPalace(int r, int c, boolean red) {
        if (c < 3 || c > 5) return false;
        return red ? (r >= 7 && r <= 9) : (r >= 0 && r <= 2);
    }

    void generateAdvisorMoves(int r, int c, int p, List<Move> moves) {
        int[][] dirs = {{-1,-1},{-1,1},{1,-1},{1,1}};
        boolean red = p > 0;
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (inKingPalace(nr, nc, red) && canMove(r, c, nr, nc, p)) {
                moves.add(new Move(r, c, nr, nc));
            }
        }
    }

    void generateBishopMoves(int r, int c, int p, List<Move> moves) {
        int[][] dirs = {{-2,-2},{-2,2},{2,-2},{2,2}};
        boolean red = p > 0;
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            int er = r + d[0]/2, ec = c + d[1]/2; // 象眼位置
            if (nr < 0 || nr > 9 || nc < 0 || nc > 8) continue;
            if (red && nr < 5) continue; // 红相不能过河
            if (!red && nr > 4) continue; // 黑象不能过河
            if (board[er][ec] != EMPTY) continue; // 塞象眼
            if (canMove(r, c, nr, nc, p)) moves.add(new Move(r, c, nr, nc));
        }
    }

    void generateKnightMoves(int r, int c, int p, List<Move> moves) {
        int[][] offsets = {{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
        int[][] legs = {{-1,0},{-1,0},{0,-1},{0,1},{0,-1},{0,1},{1,0},{1,0}}; // 马腿方向
        for (int i = 0; i < offsets.length; i++) {
            int nr = r + offsets[i][0], nc = c + offsets[i][1];
            int lr = r + legs[i][0], lc = c + legs[i][1];
            if (nr < 0 || nr > 9 || nc < 0 || nc > 8) continue;
            if (board[lr][lc] != EMPTY) continue; // 蹩马腿
            if (canMove(r, c, nr, nc, p)) moves.add(new Move(r, c, nr, nc));
        }
    }

    void generateRookMoves(int r, int c, int p, List<Move> moves) {
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        for (int[] d : dirs) {
            for (int step = 1; step < 10; step++) {
                int nr = r + d[0]*step, nc = c + d[1]*step;
                if (nr < 0 || nr > 9 || nc < 0 || nc > 8) break;
                if (board[nr][nc] != EMPTY) {
                    if (board[nr][nc] * p < 0) moves.add(new Move(r, c, nr, nc));
                    break;
                }
                moves.add(new Move(r, c, nr, nc));
            }
        }
    }

    void generateCannonMoves(int r, int c, int p, List<Move> moves) {
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        for (int[] d : dirs) {
            boolean overPiece = false;
            for (int step = 1; step < 10; step++) {
                int nr = r + d[0]*step, nc = c + d[1]*step;
                if (nr < 0 || nr > 9 || nc < 0 || nc > 8) break;
                if (!overPiece) {
                    if (board[nr][nc] == EMPTY) {
                        moves.add(new Move(r, c, nr, nc));
                    } else {
                        overPiece = true; // 遇到第一个炮架
                    }
                } else {
                    if (board[nr][nc] != EMPTY) {
                        if (board[nr][nc] * p < 0) moves.add(new Move(r, c, nr, nc));
                        break;
                    }
                }
            }
        }
    }

    void generatePawnMoves(int r, int c, int p, List<Move> moves) {
        boolean red = p > 0;
        int forward = red ? -1 : 1; // 红方向上行，黑方向下行
        int[][] dirs;
        if (red) {
            dirs = (r <= 4) ? new int[][]{{-1,0},{0,-1},{0,1}} : new int[][]{{-1,0}};
        } else {
            dirs = (r >= 5) ? new int[][]{{1,0},{0,-1},{0,1}} : new int[][]{{1,0}};
        }
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr < 0 || nr > 9 || nc < 0 || nc > 8) continue;
            if (canMove(r, c, nr, nc, p)) moves.add(new Move(r, c, nr, nc));
        }
    }

    /** 检查目标位置是否可被己方棋子移动（不越界、不吃己方） */
    boolean canMove(int fr, int fc, int tr, int tc, int p) {
        if (tr < 0 || tr > 9 || tc < 0 || tc > 8) return false;
        int target = board[tr][tc];
        return target == EMPTY || target * p < 0;
    }

    // ==================== 评估函数 ====================

    /** 静态局面评估：正值红优，负值黑优 */
    int evaluate() {
        int score = 0;
        for (int r = 0; r < 10; r++) {
            for (int c = 0; c < 9; c++) {
                int p = board[r][c];
                if (p == EMPTY) continue;
                int val = getPieceValue(p, r, c);
                score += (p > 0) ? val : -val;
            }
        }
        return score;
    }

    int getPieceValue(int p, int r, int c) {
        int absP = Math.abs(p);
        int base = 0;
        switch (absP) {
            case 1: base = 10000; break;
            case 2: base = 120; break;
            case 3: base = 120; break;
            case 4: base = 270; break;
            case 5: base = 600; break;
            case 6: base = 285; break;
            case 7: base = pawnValue(r, p > 0); break;
        }
        // 加上位置价值（简化版：中心位置加分）
        int posBonus = positionBonus(absP, r, c, p > 0);
        return base + posBonus;
    }

    int pawnValue(int r, boolean red) {
        if (red) {
            if (r <= 4) return 100; // 过河逼近九宫
            if (r <= 6) return 60;  // 刚过河
            return 30; // 未过河
        } else {
            if (r >= 5) return 100;
            if (r >= 3) return 60;
            return 30;
        }
    }

    int positionBonus(int absP, int r, int c, boolean red) {
        int rr = red ? r : 9 - r; // 红黑对称，红方视角
        switch (absP) {
            case 4: // 马：中心灵活
                return (5 - Math.abs(rr - 5)) * 3 + (4 - Math.abs(c - 4)) * 2;
            case 5: // 车：横竖畅通
                return 10;
            case 6: // 炮：需要机动
                return (5 - Math.abs(rr - 5)) * 2;
            case 7: // 兵：位置越前越好
                return red ? (9 - rr) * 5 : rr * 5;
            default:
                return 0;
        }
    }

    // ==================== Alpha-Beta搜索 ====================

    int nodesSearched = 0;
    int cacheHits = 0;

    /** 带置换表的Alpha-Beta搜索 */
    int alphaBeta(int depth, int alpha, int beta, boolean redTurn) {
        nodesSearched++;

        // 1. 查置换表
        TransEntry entry = transTable.get(zobristKey);
        if (entry != null && entry.depth >= depth) {
            cacheHits++;
            if (entry.flag == 0) return entry.score;
            if (entry.flag == 1 && entry.score >= beta) return entry.score;
            if (entry.flag == 2 && entry.score <= alpha) return entry.score;
        }

        // 2. 到达叶子节点，静态评估
        if (depth <= 0) {
            return quiescenceSearch(alpha, beta, redTurn, 0);
        }

        // 3. 生成并排序着法
        List<Move> moves = generateMoves(redTurn);
        if (moves.isEmpty()) {
            // 无合法着法：被将死或困毙
            return redTurn ? -30000 + depth : 30000 - depth;
        }

        // 着法排序：置换表着法 > 吃子着法（MVV-LVA）> 历史启发
        Move hashMove = (entry != null) ? entry.bestMove : null;
        sortMoves(moves, hashMove);

        int bestScore = redTurn ? Integer.MIN_VALUE : Integer.MAX_VALUE;
        Move bestMove = null;
        int oldAlpha = alpha, oldBeta = beta;

        for (Move m : moves) {
            makeMove(m);
            int score = alphaBeta(depth - 1, alpha, beta, !redTurn);
            undoMove(m);

            if (redTurn) {
                if (score > bestScore) {
                    bestScore = score;
                    bestMove = m;
                }
                alpha = Math.max(alpha, score);
                if (alpha >= beta) {
                    historyTable[m.fromRow][m.fromCol][m.toRow][m.toCol] += depth * depth;
                    break;
                }
            } else {
                if (score < bestScore) {
                    bestScore = score;
                    bestMove = m;
                }
                beta = Math.min(beta, score);
                if (beta <= alpha) {
                    historyTable[m.fromRow][m.fromCol][m.toRow][m.toCol] += depth * depth;
                    break;
                }
            }
        }

        // 4. 存入置换表
        TransEntry newEntry = new TransEntry();
        newEntry.depth = depth;
        newEntry.score = bestScore;
        newEntry.bestMove = bestMove;
        if (bestScore <= oldAlpha) newEntry.flag = 2; // upper bound
        else if (bestScore >= oldBeta) newEntry.flag = 1; // lower bound
        else newEntry.flag = 0; // exact
        transTable.put(zobristKey, newEntry);

        return bestScore;
    }

    /** 静态搜索（Quiescence Search）：只搜索吃子着法直到局面平静 */
    int quiescenceSearch(int alpha, int beta, boolean redTurn, int qDepth) {
        int standPat = evaluate();
        if (redTurn) {
            if (standPat >= beta) return beta;
            alpha = Math.max(alpha, standPat);
        } else {
            if (standPat <= alpha) return alpha;
            beta = Math.min(beta, standPat);
        }
        if (qDepth >= 6) return standPat;

        List<Move> captures = generateCaptures(redTurn);
        sortMoves(captures, null);

        for (Move m : captures) {
            makeMove(m);
            int score = quiescenceSearch(alpha, beta, !redTurn, qDepth + 1);
            undoMove(m);

            if (redTurn) {
                alpha = Math.max(alpha, score);
                if (alpha >= beta) return beta;
            } else {
                beta = Math.min(beta, score);
                if (beta <= alpha) return alpha;
            }
        }
        return redTurn ? alpha : beta;
    }

    List<Move> generateCaptures(boolean redTurn) {
        List<Move> all = generateMoves(redTurn);
        List<Move> caps = new ArrayList<>();
        for (Move m : all) {
            if (m.captured != EMPTY) caps.add(m);
        }
        return caps;
    }

    /** 着法排序：优先探索更可能引发剪枝的着法 */
    void sortMoves(List<Move> moves, Move hashMove) {
        for (Move m : moves) {
            if (hashMatch(m, hashMove)) {
                m.score = 1000000;
            } else if (m.captured != EMPTY) {
                // MVV-LVA：吃高价值棋子优先，同价值时 mover 价值低者优先
                m.score = 900000 + Math.abs(m.captured) * 100 - Math.abs(board[m.fromRow][m.fromCol]);
            } else {
                m.score = historyTable[m.fromRow][m.fromCol][m.toRow][m.toCol];
            }
        }
        moves.sort((a, b) -> b.score - a.score);
    }

    boolean hashMatch(Move a, Move b) {
        if (a == null || b == null) return false;
        return a.fromRow == b.fromRow && a.fromCol == b.fromCol
            && a.toRow == b.toRow && a.toCol == b.toCol;
    }

    // ==================== 局面操作 ====================

    void makeMove(Move m) {
        m.captured = board[m.toRow][m.toCol];
        int piece = board[m.fromRow][m.fromCol];
        updateZobrist(m.fromRow, m.fromCol, m.toRow, m.toCol, piece, m.captured);
        board[m.toRow][m.toCol] = piece;
        board[m.fromRow][m.fromCol] = EMPTY;
    }

    void undoMove(Move m) {
        int piece = board[m.toRow][m.toCol];
        updateZobrist(m.toRow, m.toCol, m.fromRow, m.fromCol, piece, m.captured);
        board[m.fromRow][m.fromCol] = piece;
        board[m.toRow][m.toCol] = m.captured;
    }

    // ==================== 迭代加深与主入口 ====================

    /** 查找当前局面下的最佳着法 */
    Move findBestMove(boolean redTurn, int maxDepth) {
        Move bestMove = null;
        int bestScore = redTurn ? Integer.MIN_VALUE : Integer.MAX_VALUE;
        nodesSearched = 0;
        cacheHits = 0;

        long startTime = System.currentTimeMillis();

        for (int depth = 1; depth <= maxDepth; depth++) {
            List<Move> moves = generateMoves(redTurn);
            if (moves.isEmpty()) break;
            Move hashMove = (transTable.get(zobristKey) != null) ? transTable.get(zobristKey).bestMove : null;
            sortMoves(moves, hashMove);

            int currentBest = redTurn ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            Move currentMove = null;

            for (Move m : moves) {
                makeMove(m);
                int score = alphaBeta(depth - 1, Integer.MIN_VALUE, Integer.MAX_VALUE, !redTurn);
                undoMove(m);

                if (redTurn) {
                    if (score > currentBest) { currentBest = score; currentMove = m; }
                } else {
                    if (score < currentBest) { currentBest = score; currentMove = m; }
                }
            }

            bestMove = currentMove;
            bestScore = currentBest;
            long elapsed = System.currentTimeMillis() - startTime;
            System.out.printf("深度 %d 完成: 最佳着法 (%d,%d)->(%d,%d), 评估值=%d, 搜索节点=%d, 置换表命中=%d, 用时=%dms%n",
                depth, bestMove.fromRow, bestMove.fromCol, bestMove.toRow, bestMove.toCol,
                bestScore, nodesSearched, cacheHits, elapsed);

            if (elapsed > 5000) break; // 超时保护：超过5秒停止加深
        }

        return bestMove;
    }

    /** 打印当前棋盘 */
    void printBoard() {
        String[] symbols = {".","帅","仕","相","马","车","炮","兵","将","士","象","马","车","炮","卒"};
        System.out.println("  0 1 2 3 4 5 6 7 8");
        for (int r = 0; r < 10; r++) {
            System.out.print(r + " ");
            for (int c = 0; c < 9; c++) {
                int p = board[r][c];
                if (p == 0) System.out.print(". ");
                else if (p > 0) System.out.print(symbols[p] + " ");
                else System.out.print(symbols[7 - p] + " ");
            }
            System.out.println();
        }
    }

    // ==================== 主程序 ====================

    public static void main(String[] args) {
        ChineseChessAI ai = new ChineseChessAI();

        System.out.println("=== 中国象棋AI — 初始局面 ===");
        ai.printBoard();

        // 红方先行，搜索深度4层
        System.out.println("\n=== 红方AI思考中（深度1~4）===");
        Move best = ai.findBestMove(true, 4);

        System.out.println("\n=== 最终选择着法 ===");
        System.out.printf("红方走: (%d,%d) -> (%d,%d)%n",
            best.fromRow, best.fromCol, best.toRow, best.toCol);

        ai.makeMove(best);
        System.out.println("\n=== 走完一步后局面 ===");
        ai.printBoard();

        // 黑方回应
        System.out.println("\n=== 黑方AI思考中 ===");
        Move blackBest = ai.findBestMove(false, 4);
        System.out.printf("黑方走: (%d,%d) -> (%d,%d)%n",
            blackBest.fromRow, blackBest.fromCol, blackBest.toRow, blackBest.toCol);
    }
}

算法复杂度分析

其中 b 为平均分支因子（中国象棋约30~50），d 为搜索深度。置换表在重复局面多的残局中可将节点数再减少30%~70%。

扩展与优化方向

1. 开局库：将经典开局序列预存入哈希表，前10~15回合直接查表，避免搜索盲区
2. 历史启发与杀手启发：记录引发剪枝频率高的着法，在后续搜索中优先尝试
3. 空着裁剪（Null Move Pruning）：在己方明显优势时尝试”停一手”，若仍无法被超越则大幅剪枝
4. 多线程并行搜索：使用Work-Stealing算法在多个CPU核心间分配搜索任务
5. 神经网络评估：用深度学习替代手工评估函数，如AlphaZero的ResNet策略-价值网络

总结

本文完整实现了中国象棋AI的核心决策系统，关键要点如下：
– 棋盘表示：10×9二维数组配合正负编码，简洁高效
– 着法生成：按棋子类型分别实现走法规则，注意象眼、马腿、炮架等特殊约束
– Alpha-Beta剪枝：在Minimax基础上通过维护alpha/beta区间剪除无效分支
– Zobrist哈希：利用异或增量更新实现O(1)局面哈希，碰撞率极低
– 置换表：缓存已搜索局面的结果，避免重复计算，是提升深度的关键

理解这套方法后，你可以将其应用于其他完全信息博弈（如国际象棋、围棋简化版），也可以尝试引入神经网络评估函数，向现代博弈AI更进一步。

思考题

1. 如果将搜索深度从4层提升到6层，在实际对局中AI水平会有怎样的变化？为什么现实中不无限加深？
2. Zobrist哈希使用64位随机数，如果改成32位，碰撞概率会有多大变化？对AI决策有什么影响？
3. 如何在现有框架中加入将军延伸（Check Extension），当搜索到己方被将军时强制加深一层？这会怎样改变战术决策质量？