引言

AI 是棋类游戏的灵魂。轻棋局内置了象棋和五子棋两个 AI 引擎，同时支持接入外部引擎（Pikafish、Piskvork、KataGo）。本篇深入讲解 AI 的核心算法、优化技巧和工程实现。

---

1. 象棋 AI：Negamax + Alpha-Beta 剪枝

核心算法

象棋 AI 使用经典的 Negamax 搜索框架，配合 Alpha-Beta 剪枝：

public class MinimaxAI {
    private int negamax(Board board, int depth, int alpha, int beta, PieceColor color) {
        // 终止条件
        if (depth == 0 || board.isGameOver()) {
            return evaluate(board, color);
        }
        
        List<Move> moves = board.generateMoves(color);
        int bestScore = Integer.MIN_VALUE;
        
        for (Move move : moves) {
            board.makeMove(move);
            int score = -negamax(board, depth - 1, -beta, -alpha, color.opposite());
            board.undoMove(move);
            
            if (score > bestScore) {
                bestScore = score;
            }
            if (score > alpha) {
                alpha = score;
            }
            if (alpha >= beta) {
                break;  // Beta 剪枝
            }
        }
        
        return bestScore;
    }
}

Negamax 的优势：只需要写一个搜索函数，通过颜色翻转实现双方搜索，代码量减半。

迭代加深

不直接搜索固定深度，而是从深度 1 开始逐步加深：

public Move findBestMove(Board board, PieceColor aiColor) {
    Move bestMove = null;
    
    for (int depth = 1; depth <= maxDepth; depth++) {
        Move candidate = searchRoot(board, depth, aiColor);
        if (candidate != null) {
            bestMove = candidate;
        }
    }
    
    return bestMove;
}

好处：

1. 时间可控 — 可以在任意深度中断，返回当前最优解
2. 走法排序 — 上一轮的结果可以用于下一轮的走法排序，提高剪枝效率
3. 渐进式增强 — 浅层搜索快速给出候选，深层搜索精确验证

评估函数

棋盘评估是 AI 的核心：

private int evaluate(Board board, PieceColor color) {
    int score = 0;
    
    // 子力价值
    for (int row = 0; row < Board.ROWS; row++) {
        for (int col = 0; col < Board.COLS; col++) {
            Piece piece = board.getPiece(row, col);
            if (piece != null) {
                int value = getPieceValue(piece);
                if (piece.getColor() == color) {
                    score += value;
                } else {
                    score -= value;
                }
            }
        }
    }
    
    // 位置价值（棋子在不同位置的价值不同）
    score += positionalBonus(board, color);
    
    // 机动性（可走步数）
    score += mobilityBonus(board, color);
    
    return score;
}

子力价值参考表：

棋子	基础价值	说明
车	1000	最强攻击子
马	500	灵活但受限于蹩马腿
炮	500	远程攻击，需要炮架
士/仕	200	防守核心
象/相	200	防守，不能过河
兵/卒	100-200	过河后价值翻倍

---

2. 高级优化技术

置换表（Transposition Table）

用 Zobrist 哈希记录已搜索过的局面，避免重复计算：

private Map<Long, TranspositionEntry> transpositionTable = new HashMap<>();

public int probe(Board board, int depth, int alpha, int beta) {
    long hash = board.getZobristHash();
    TranspositionEntry entry = transpositionTable.get(hash);
    
    if (entry != null && entry.depth >= depth) {
        if (entry.flag == EXACT) {
            return entry.score;
        } else if (entry.flag == LOWER_BOUND && entry.score > alpha) {
            alpha = entry.score;
        } else if (entry.flag == UPPER_BOUND && entry.score < beta) {
            beta = entry.score;
        }
        
        if (alpha >= beta) {
            return entry.score;
        }
    }
    
    return UNKNOWN;
}

Zobrist 哈希的优势：增量更新。走棋时只需 XOR 操作，无需重新计算整个棋盘的哈希。

public class Zobrist {
    private static long[][][] keys;  // [row][col][pieceType]
    
    public static long compute(Board board) {
        long hash = 0;
        for (int row = 0; row < Board.ROWS; row++) {
            for (int col = 0; col < Board.COLS; col++) {
                Piece piece = board.getPiece(row, col);
                if (piece != null) {
                    hash ^= keys[row][col][piece.getType().ordinal()];
                }
            }
        }
        return hash;
    }
    
    // 增量更新：走棋后 XOR 掉起点和终点的棋子
    public static long update(long hash, int fromRow, int fromCol, 
                               int toRow, int toCol, Piece piece) {
        hash ^= keys[fromRow][fromCol][piece.getType().ordinal()];
        hash ^= keys[toRow][toCol][piece.getType().ordinal()];
        return hash;
    }
}

历史启发（History Heuristic）

记录导致剪枝的走法，在后续搜索中优先尝试：

private int[][][] historyTable = new int[Board.ROWS][Board.COLS][Board.ROWS * Board.COLS];

public void updateHistory(Move move, int depth) {
    historyTable[move.fromRow][move.fromCol][move.toRow * Board.COLS + move.toCol] 
        += depth * depth;  // 深度越大，优先级越高
}

public int getHistoryScore(Move move) {
    return historyTable[move.fromRow][move.fromCol][move.toRow * Board.COLS + move.toCol];
}

杀手着法（Killer Moves）

记录每个搜索深度的两个"杀手着法"（导致剪枝的走法）：

private Move[][] killerMoves = new Move[maxDepth][2];

public void recordKiller(Move move, int depth) {
    if (killerMoves[depth][0] == null || 
        killerMoves[depth][0].equals(move)) {
        return;
    }
    killerMoves[depth][1] = killerMoves[depth][0];
    killerMoves[depth][0] = move;
}

走法排序

搜索前对走法排序，提高剪枝效率：

private List<Move> orderMoves(Board board, List<Move> moves, int depth) {
    return moves.stream()
        .sorted((a, b) -> {
            int scoreA = moveScore(a, depth);
            int scoreB = moveScore(b, depth);
            return scoreB - scoreA;  // 降序
        })
        .collect(Collectors.toList());
}

private int moveScore(Move move, int depth) {
    int score = 0;
    
    // 吃子优先（MVV-LVA）
    if (move.isCapture()) {
        score += 10000 + captureValue(move);
    }
    
    // 杀手着法
    if (isKiller(move, depth)) {
        score += 5000;
    }
    
    // 历史启发
    score += getHistoryScore(move);
    
    return score;
}

空着剪枝（Null Move Pruning）

如果当前局面即使不走棋（空着）也能获得好分数，则跳过搜索：

if (!inCheck && depth >= 3 && !isNullMove) {
    board.makeNullMove();
    int score = -negamax(board, depth - 3, -beta, -beta + 1, color.opposite(), true);
    board.undoNullMove();
    
    if (score >= beta) {
        return beta;  // 空着剪枝成功
    }
}

静态搜索（Quiescence Search）

在搜索叶子节点时，继续搜索吃子着法，避免「水平线效应」：

private int quiescence(Board board, int alpha, int beta, PieceColor color) {
    int standPat = evaluate(board, color);
    
    if (standPat >= beta) return beta;
    if (standPat > alpha) alpha = standPat;
    
    List<Move> captures = board.generateCaptures(color);
    for (Move move : captures) {
        board.makeMove(move);
        int score = -quiescence(board, -beta, -alpha, color.opposite());
        board.undoMove(move);
        
        if (score >= beta) return beta;
        if (score > alpha) alpha = score;
    }
    
    return alpha;
}

---

3. 难度分级

AI 支持四个难度级别，通过搜索深度和时间预算控制：

public enum Difficulty {
    EASY(2, 500),      // 2层，500ms
    MEDIUM(4, 2000),   // 4层，2秒
    HARD(6, 5000),     // 6层，5秒
    EXPERT(8, 10000);  // 8层，10秒
    
    final int maxDepth;
    final long timeBudgetMs;
}

实际搜索深度会根据局面复杂度动态调整：

int effectiveDepth = difficulty.maxDepth;
if (board.isEndgame()) {
    effectiveDepth += 2;  // 残局阶段加深搜索
}
if (board.isInCheck()) {
    effectiveDepth += 1;  // 被将军时加深
}

---

4. 五子棋 AI

五子棋 AI 的设计与象棋有显著不同：

候选点生成

不搜索所有空位，只搜索已有棋子的邻域：

public List<int[]> generateCandidates(GomokuBoard board) {
    Set<int[]> candidates = new HashSet<>();
    int range = 2;  // 搜索范围：已有棋子周围2格
    
    for (int row = 0; row < SIZE; row++) {
        for (int col = 0; col < SIZE; col++) {
            if (board.getStone(row, col) != EMPTY) {
                // 收集周围的空位
                for (int dr = -range; dr <= range; dr++) {
                    for (int dc = -range; dc <= range; dc++) {
                        int r = row + dr, c = col + dc;
                        if (r >= 0 && r < SIZE && c >= 0 && c < SIZE 
                            && board.getStone(r, c) == EMPTY) {
                            candidates.add(new int[]{r, c});
                        }
                    }
                }
            }
        }
    }
    
    return new ArrayList<>(candidates);
}

战术优先

在搜索前，先做快速战术检查：

// 1. 立即胜利
int[] winMove = findWinningMove(board, aiColor);
if (winMove != null) return winMove;

// 2. 立即防守（对手有四连）
int[] blockMove = findBlockingMove(board, humanColor);
if (blockMove != null) return blockMove;

// 3. 正常搜索
return alphaBetaSearch(board, depth);

禁手规则

黑方有禁手限制，防止先手必胜：

public boolean isForbidden(int row, int col, GomokuStone color) {
    if (color != BLACK) return false;
    
    // 长连禁手（超过5子）
    if (isOverline(row, col, color)) return true;
    
    // 四四禁手（同时形成两个活四）
    if (isDoubleFour(row, col, color)) return true;
    
    // 三三禁手（同时形成两个活三）
    if (isDoubleThree(row, col, color)) return true;
    
    return false;
}

---

5. 引擎抽象设计

接口定义

三种棋类各有独立的引擎接口：

// 象棋引擎接口
public interface XiangqiEngine {
    Move findBestMove(Board board, PieceColor aiColor, Difficulty difficulty);
    String getEngineId();
    String getEngineText();
}

// 五子棋引擎接口
public interface GomokuEngine {
    GomokuMove findBestMove(GomokuBoard board, GomokuStone aiColor);
    String getEngineId();
    String getEngineText();
}

// 围棋引擎接口
public interface GoEngine {
    GoEngineMove findBestMove(GoBoard board, GoStone aiColor);
    String getEngineId();
    String getEngineText();
}

引擎实现层次

XiangqiEngine (接口)
├── BuiltinXiangqiEngine    — 内置 Minimax AI
├── ConfigurableXiangqiEngine — 可配置外部引擎
└── PikafishUciEngine       — Pikafish UCI 适配器

ConfigurableXiangqiEngine 通过外部进程通信，支持 UCI 协议的引擎：

public class ConfigurableXiangqiEngine implements XiangqiEngine {
    private Process engineProcess;
    private BufferedWriter stdin;
    private BufferedReader stdout;
    
    public Move findBestMove(Board board, PieceColor aiColor, Difficulty difficulty) {
        // 1. 发送 UCI 位置信息
        stdin.write("position fen " + FenCodec.encode(board));
        stdin.write("go movetime " + difficulty.timeBudgetMs);
        
        // 2. 读取引擎返回的最佳着法
        String bestMove = readLine();  // "bestmove e2e4"
        return parseMove(bestMove);
    }
}

围棋外部引擎

围棋 AI 复杂度最高，采用独立进程 + HTTP 通信：

public class ConfigurableGoEngine implements GoEngine {
    private final String engineUrl;  // XQ_GO_ENGINE_URL
    
    public GoEngineMove findBestMove(GoBoard board, GoStone aiColor) {
        // 通过 HTTP 调用外部围棋引擎服务
        String response = httpClient.post(engineUrl + "/suggest", 
            Map.of("board", board.toSgf(), "color", aiColor.name()));
        return parseResponse(response);
    }
}

---

6. 残局练习系统

数据格式

残局数据存储在 endgames.json 中：

{
  "id": "eg-001",
  "name": "马后炮",
  "fen": "rnbakab1r/9/1c5c1/p3p1p2/9/6P2/P3P3P/1C4NC1/9/RNBAKAB2 w",
  "difficulty": "MEDIUM",
  "solution": ["h9g7", "h8f9", "g7e8"],
  "description": "经典马后炮杀法"
}

练习流程

1. 用户选择残局 → 创建练习对局
2. Board 加载 FEN → 清空棋盘并摆放残局
3. 用户走棋 → 验证是否符合解法
4. AI 自动应招 → 按预设解法走棋
5. 完成 → 记录到 learn_progress 表

---

7. 性能基准

在普通 PC 上的测试结果：

搜索深度	考虑节点数	耗时	棋力评估
2 层	~1,000	<50ms	初学者
4 层	~50,000	~500ms	中级
6 层	~500,000	~3s	高级
8 层	~5,000,000	~10s	业余高手

加上置换表和历史启发后，搜索效率提升约 3-5 倍。

---

小结

象棋 AI 的核心优化路径：

1. Alpha-Beta 剪枝 — 基础优化，剪掉无需搜索的分支
2. 迭代加深 — 时间可控，走法排序更高效
3. 置换表 — 记忆化搜索，避免重复计算
4. 走法排序 — 吃子优先、杀手着法、历史启发
5. 空着剪枝 — 快速判断是否值得搜索
6. 静态搜索 — 解决水平线效应

这些技术组合使用，可以让一个简单的 Minimax 搜索在普通硬件上达到相当强的棋力。

---

上一篇：（二）后端核心架构
下一篇：（四）前端 SPA 实战