每日算法 — 使用java实现围棋：蒙特卡洛树搜索与UCT算法

围棋起源于中国，拥有超过四千年的历史，被誉为人类智力游戏的巅峰。其19路棋盘带来的状态空间复杂度约为10^170，远超宇宙原子总数。正因如此，传统暴力搜索算法在围棋面前几乎束手无策。直到2016年AlphaGo凭借蒙特卡洛树搜索（MCTS）结合深度神经网络战胜世界冠军，MCTS才真正进入大众视野。本文将抛开神经网络部分，专注于用Java实现一套完整的MCTS引擎，让读者理解”仅凭随机模拟与统计”如何让AI下出具备职业水准的围棋。

一、MCTS核心思想：用统计代替搜索

MCTS（Monte Carlo Tree Search）的精髓在于不试图遍历所有可能，而是通过大量随机对局（称为playout或rollout）来统计每个落子点的胜率。它维护一棵搜索树，每个节点代表一个棋盘状态，每条边代表一次落子。算法在每轮迭代中执行四个步骤：

1. 选择（Selection）：从根节点出发，按照某种策略沿树向下走到一个尚未充分探索的节点。
2. 扩展（Expansion）：在该节点上添加一个或多个子节点（对应合法落子）。
3. 模拟（Simulation）：从新扩展的节点出发，随机落子直到终局，记录胜负。
4. 回传（Backpropagation）：将模拟结果沿路径向上更新所有祖先节点的统计量。

UCT（Upper Confidence Bound applied to Trees）公式负责”选择”步骤中的平衡：

UCT = (wi/ni) + c * sqrt(ln(Ni) / ni)

其中wi是节点i的累计收益，ni是节点i被访问次数，Ni是父节点被访问次数，c是探索常数。第一项鼓励”利用”高胜率分支，第二项鼓励”探索”访问次数少的分支。

二、棋盘表示与规则引擎

围棋规则复杂，核心在于”气”（liberty）的计算与”提子”（capture）。为了聚焦算法，本文实现9路棋盘（职业比赛为19路），但代码结构完全兼容扩展。

import java.util.*;

/**
 * 围棋棋盘与规则引擎
 * 使用一维数组表示二维棋盘，黑子=1，白子=-1，空=0
 */
public class GoBoard {
    public static final int EMPTY = 0;
    public static final int BLACK = 1;
    public static final int WHITE = -1;

    private final int size;       // 棋盘路数，如9
    private final int[] board;    // 一维棋盘，index = row * size + col
    private int currentPlayer;    // 当前落子方
    private int lastMove;         // 上一步落子位置（-1表示pass）
    private int consecutivePass;  // 连续pass次数，达到2次则终局

    // 记录历史局面，用于判断"打劫"（ko rule）
    private final Set<Long> historyHashes;

    public GoBoard(int size) {
        this.size = size;
        this.board = new int[size * size];
        this.currentPlayer = BLACK;
        this.lastMove = -1;
        this.consecutivePass = 0;
        this.historyHashes = new HashSet<>();
        this.historyHashes.add(zobristHash());
    }

    /** 深拷贝构造 */
    public GoBoard(GoBoard other) {
        this.size = other.size;
        this.board = other.board.clone();
        this.currentPlayer = other.currentPlayer;
        this.lastMove = other.lastMove;
        this.consecutivePass = other.consecutivePass;
        this.historyHashes = new HashSet<>(other.historyHashes);
    }

    public int getSize() { return size; }
    public int get(int row, int col) { return board[row * size + col]; }
    public int getCurrentPlayer() { return currentPlayer; }
    public boolean isGameOver() { return consecutivePass >= 2; }

    /**
     * 落子主逻辑：放置棋子、计算气、提子、判断打劫
     * @return 是否落子成功（false表示非法落子）
     */
    public boolean placeStone(int row, int col) {
        if (row < 0 || row >= size || col < 0 || col >= size) return false;
        int idx = row * size + col;
        if (board[idx] != EMPTY) return false;

        // 尝试落子
        board[idx] = currentPlayer;

        // 检查是否提掉对方棋子
        List<Integer> capturedStones = new ArrayList<>();
        int opponent = -currentPlayer;
        for (int[] d : DIRECTIONS) {
            int nr = row + d[0], nc = col + d[1];
            if (inBounds(nr, nc) && get(nr, nc) == opponent) {
                Set<Integer> group = getConnectedGroup(nr, nc);
                if (countLiberties(group) == 0) {
                    capturedStones.addAll(group);
                }
            }
        }

        // 检查己方是否陷入无气状态（自杀手，除非同时提子）
        Set<Integer> selfGroup = getConnectedGroup(row, col);
        if (countLiberties(selfGroup) == 0 && capturedStones.isEmpty()) {
            board[idx] = EMPTY; // 恢复，自杀手非法
            return false;
        }

        // 执行提子
        for (int capIdx : capturedStones) {
            board[capIdx] = EMPTY;
        }

        // 打劫判断：落子后局面是否与历史上某局面完全相同
        long hash = zobristHash();
        if (historyHashes.contains(hash)) {
            // 恢复并拒绝
            board[idx] = EMPTY;
            for (int capIdx : capturedStones) {
                board[capIdx] = opponent;
            }
            return false;
        }

        historyHashes.add(hash);
        currentPlayer = opponent;
        lastMove = idx;
        consecutivePass = 0;
        return true;
    }

    /** Pass：当前方选择不落子 */
    public void pass() {
        currentPlayer = -currentPlayer;
        consecutivePass++;
        lastMove = -1;
    }

    /** 获取当前所有合法落子（包含pass） */
    public List<Integer> getLegalMoves() {
        List<Integer> moves = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            int r = i / size, c = i % size;
            GoBoard copy = new GoBoard(this);
            if (copy.placeStone(r, c)) {
                moves.add(i);
            }
        }
        // pass总是合法
        moves.add(-1);
        return moves;
    }

    /** 计算 Territory（领地），用于终局计分 */
    public double[] computeScore() {
        boolean[] visited = new boolean[board.length];
        double[] score = new double[2]; // 0=black, 1=white
        // 简单计分：棋子数 + 完全包围的空点数
        for (int i = 0; i < board.length; i++) {
            if (board[i] == BLACK) score[0]++;
            else if (board[i] == WHITE) score[1]++;
            else if (!visited[i]) {
                // BFS探索连通空区域，看被谁包围
                List<Integer> region = new ArrayList<>();
                Set<Integer> borders = new HashSet<>();
                Queue<Integer> q = new LinkedList<>();
                q.add(i);
                visited[i] = true;
                while (!q.isEmpty()) {
                    int cur = q.poll();
                    region.add(cur);
                    int r = cur / size, c = cur % size;
                    for (int[] d : DIRECTIONS) {
                        int nr = r + d[0], nc = c + d[1];
                        if (!inBounds(nr, nc)) continue;
                        int nidx = nr * size + nc;
                        if (board[nidx] == EMPTY && !visited[nidx]) {
                            visited[nidx] = true;
                            q.add(nidx);
                        } else if (board[nidx] != EMPTY) {
                            borders.add(board[nidx]);
                        }
                    }
                }
                // 如果空区域只与一种颜色相邻，算该颜色领地
                if (borders.size() == 1) {
                    int owner = borders.iterator().next();
                    if (owner == BLACK) score[0] += region.size();
                    else score[1] += region.size();
                }
            }
        }
        // 贴目（komi），白棋通常贴6.5目
        score[1] += 6.5;
        return score;
    }

    // ============ 辅助方法 ============

    private static final int[][] DIRECTIONS = {{-1,0},{1,0},{0,-1},{0,1}};

    private boolean inBounds(int r, int c) {
        return r >= 0 && r < size && c >= 0 && c < size;
    }

    /** 获取包含指定位置棋子的连通块 */
    private Set<Integer> getConnectedGroup(int row, int col) {
        int color = get(row, col);
        Set<Integer> group = new HashSet<>();
        Queue<Integer> q = new LinkedList<>();
        int start = row * size + col;
        q.add(start);
        group.add(start);
        while (!q.isEmpty()) {
            int cur = q.poll();
            int r = cur / size, c = cur % size;
            for (int[] d : DIRECTIONS) {
                int nr = r + d[0], nc = c + d[1];
                if (inBounds(nr, nc)) {
                    int nidx = nr * size + nc;
                    if (get(nr, nc) == color && !group.contains(nidx)) {
                        group.add(nidx);
                        q.add(nidx);
                    }
                }
            }
        }
        return group;
    }

    /** 计算连通块的气数 */
    private int countLiberties(Set<Integer> group) {
        Set<Integer> liberties = new HashSet<>();
        for (int idx : group) {
            int r = idx / size, c = idx % size;
            for (int[] d : DIRECTIONS) {
                int nr = r + d[0], nc = c + d[1];
                if (inBounds(nr, nc) && get(nr, nc) == EMPTY) {
                    liberties.add(nr * size + nc);
                }
            }
        }
        return liberties.size();
    }

    /** Zobrist哈希：快速生成局面指纹 */
    private long zobristHash() {
        long h = 0;
        // 使用固定种子生成确定性哈希（实际项目应预存随机表）
        for (int i = 0; i < board.length; i++) {
            if (board[i] != EMPTY) {
                h ^= zobristValue(i, board[i]);
            }
        }
        return h;
    }

    private long zobristValue(int pos, int color) {
        // 简单伪随机，实际应使用预计算的64位随机数表
        long base = 0x9E3779B97F4A7C15L;
        return base * (pos + 1) * (color == BLACK ? 1 : 3);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("  ");
        for (int c = 0; c < size; c++) sb.append((char)('A' + c)).append(" ");
        sb.append("\n");
        for (int r = 0; r < size; r++) {
            sb.append(r + 1).append(" ");
            for (int c = 0; c < size; c++) {
                int v = get(r, c);
                sb.append(v == BLACK ? "● " : v == WHITE ? "○ " : "+ ");
            }
            sb.append("\n");
        }
        return sb.toString();
    }
}

三、MCTS树节点设计

每个树节点需要存储：棋盘状态引用、父节点、子节点列表、该节点代表的行动、访问次数、累计收益。为节省内存，棋盘状态采用即时拷贝策略——仅在扩展时深拷贝，树中节点只保存必要的路径信息。

/**
 * MCTS树节点
 */
public class MCTSNode {
    private final GoBoard board;      // 该节点对应的局面（深拷贝）
    private final MCTSNode parent;    // 父节点
    private final int move;           // 从父节点到达本节点的落子（-1表示pass）
    private final List<MCTSNode> children;
    private final List<Integer> untriedMoves; // 尚未扩展的落子

    private int visitCount;           // 访问次数
    private double winScore;          // 累计收益（从当前节点视角）

    public MCTSNode(GoBoard board, MCTSNode parent, int move) {
        this.board = new GoBoard(board);
        this.parent = parent;
        this.move = move;
        this.children = new ArrayList<>();
        this.untriedMoves = new ArrayList<>(board.getLegalMoves());
        // 移除pass，通常只在特定阶段考虑pass
        this.untriedMoves.remove(Integer.valueOf(-1));
        this.visitCount = 0;
        this.winScore = 0.0;
    }

    /** 是否还有未尝试的落子 */
    public boolean hasUntriedMoves() {
        return !untriedMoves.isEmpty();
    }

    /** 随机选择一个未尝试的落子并移除 */
    public int selectUntriedMove(Random rnd) {
        int idx = rnd.nextInt(untriedMoves.size());
        return untriedMoves.remove(idx);
    }

    /** 根据UCT值选择最佳子节点 */
    public MCTSNode selectBestChild(double explorationConstant) {
        MCTSNode best = null;
        double bestValue = Double.NEGATIVE_INFINITY;
        for (MCTSNode child : children) {
            double uct = (child.winScore / child.visitCount)
                + explorationConstant * Math.sqrt(Math.log(this.visitCount) / child.visitCount);
            if (uct > bestValue) {
                bestValue = uct;
                best = child;
            }
        }
        return best;
    }

    /** 添加子节点 */
    public MCTSNode addChild(int move, GoBoard boardState) {
        MCTSNode child = new MCTSNode(boardState, this, move);
        children.add(child);
        return child;
    }

    /** 回传模拟结果 */
    public void backpropagate(double result) {
        this.visitCount++;
        this.winScore += result;
        if (parent != null) {
            // 结果对父节点来说是相反的（零和博弈）
            parent.backpropagate(1.0 - result);
        }
    }

    /** 获取访问次数最多的子节点（用于最终决策） */
    public MCTSNode getMostVisitedChild() {
        MCTSNode best = null;
        int maxVisits = -1;
        for (MCTSNode child : children) {
            if (child.visitCount > maxVisits) {
                maxVisits = child.visitCount;
                best = child;
            }
        }
        return best;
    }

    public GoBoard getBoard() { return board; }
    public MCTSNode getParent() { return parent; }
    public int getMove() { return move; }
    public int getVisitCount() { return visitCount; }
    public List<MCTSNode> getChildren() { return children; }
}

四、MCTS引擎主循环

引擎执行固定时长的迭代搜索，每次迭代包含选择、扩展、模拟、回传四个阶段。模拟阶段采用完全随机落子策略——这是MCTS最朴素的形态，虽然棋力有限，但代码简洁且能完整展示算法流程。

/**
 * MCTS围棋AI引擎
 */
public class MCTSEngine {
    private final int boardSize;
    private final double explorationConstant; // UCT常数c，通常sqrt(2)
    private final Random random;

    public MCTSEngine(int boardSize) {
        this(boardSize, Math.sqrt(2));
    }

    public MCTSEngine(int boardSize, double explorationConstant) {
        this.boardSize = boardSize;
        this.explorationConstant = explorationConstant;
        this.random = new Random();
    }

    /**
     * 搜索最佳落子
     * @param board 当前局面
     * @param timeLimitMs 思考时间限制（毫秒）
     * @return 最佳落子位置（-1表示pass）
     */
    public int searchBestMove(GoBoard board, long timeLimitMs) {
        long startTime = System.currentTimeMillis();
        MCTSNode root = new MCTSNode(board, null, -1);

        int iterations = 0;
        while (System.currentTimeMillis() - startTime < timeLimitMs) {
            // 阶段1：选择
            MCTSNode node = select(root);

            // 阶段2：扩展
            if (!node.getBoard().isGameOver() && node.hasUntriedMoves()) {
                int move = node.selectUntriedMove(random);
                GoBoard nextBoard = new GoBoard(node.getBoard());
                if (move == -1) {
                    nextBoard.pass();
                } else {
                    nextBoard.placeStone(move / boardSize, move % boardSize);
                }
                node = node.addChild(move, nextBoard);
            }

            // 阶段3：模拟
            double result = simulate(node.getBoard());

            // 阶段4：回传
            // result是模拟终局时当前 node's board 的下一手方的胜率
            // 需要转换为从root视角的结果
            node.backpropagate(result);

            iterations++;
        }

        System.out.println("MCTS完成迭代次数: " + iterations);

        MCTSNode bestChild = root.getMostVisitedChild();
        if (bestChild == null) {
            return -1; // pass
        }
        return bestChild.getMove();
    }

    /** 选择阶段：从根节点沿UCT最优路径走到叶子 */
    private MCTSNode select(MCTSNode node) {
        while (!node.getBoard().isGameOver() && !node.hasUntriedMoves() && !node.getChildren().isEmpty()) {
            node = node.selectBestChild(explorationConstant);
        }
        return node;
    }

    /**
     * 模拟阶段：随机落子直到终局，返回结果
     * @return 从模拟开始时轮到的一方视角的胜率（1=胜, 0=负, 0.5=和）
     */
    private double simulate(GoBoard board) {
        GoBoard simBoard = new GoBoard(board);
        int simPlayer = simBoard.getCurrentPlayer();

        // 随机落子直到终局（连续pass或达到步数上限）
        int maxSteps = boardSize * boardSize * 2;
        int steps = 0;
        while (!simBoard.isGameOver() && steps < maxSteps) {
            List<Integer> moves = simBoard.getLegalMoves();
            if (moves.isEmpty() || (moves.size() == 1 && moves.get(0) == -1)) {
                simBoard.pass();
            } else {
                // 90%概率随机落子，10%概率pass（避免无意义填充）
                int move;
                if (random.nextDouble() < 0.9 && moves.size() > 1) {
                    List<Integer> nonPass = new ArrayList<>(moves);
                    nonPass.remove(Integer.valueOf(-1));
                    move = nonPass.get(random.nextInt(nonPass.size()));
                    simBoard.placeStone(move / boardSize, move % boardSize);
                } else {
                    simBoard.pass();
                }
            }
            steps++;
        }

        // 计分
        double[] score = simBoard.computeScore();
        // score[0]=black, score[1]=white
        // 判断simPlayer是否获胜
        if (simPlayer == GoBoard.BLACK) {
            return score[0] > score[1] ? 1.0 : score[0] < score[1] ? 0.0 : 0.5;
        } else {
            return score[1] > score[0] ? 1.0 : score[1] < score[0] ? 0.0 : 0.5;
        }
    }
}

五、主程序与对局演示

以下主程序启动一局人机对弈，人类执黑先行，AI执白后行，每步AI思考1秒。

import java.util.Scanner;

public class GoGameDemo {
    public static void main(String[] args) {
        int size = 9; // 9路棋盘，适合快速演示
        GoBoard board = new GoBoard(size);
        MCTSEngine engine = new MCTSEngine(size);
        Scanner scanner = new Scanner(System.in);

        System.out.println("=== 围棋MCTS AI演示 ===");
        System.out.println("棋盘大小: " + size + "x" + size);
        System.out.println("输入格式: 行 列，例如 '3 4' 表示第3行第4列");
        System.out.println("输入 'pass' 表示停一手，输入 'quit' 退出\n");

        while (!board.isGameOver()) {
            System.out.println(board);
            int current = board.getCurrentPlayer();
            System.out.println(current == GoBoard.BLACK ? "黑棋(●)行棋" : "白棋(○)行棋");

            if (current == GoBoard.BLACK) {
                // 人类落子
                System.out.print("你的落子: ");
                String input = scanner.nextLine().trim();
                if (input.equalsIgnoreCase("quit")) break;
                if (input.equalsIgnoreCase("pass")) {
                    board.pass();
                    continue;
                }
                String[] parts = input.split("\\s+");
                if (parts.length != 2) {
                    System.out.println("输入格式错误，请重试");
                    continue;
                }
                try {
                    int row = Integer.parseInt(parts[0]) - 1; // 1-based输入
                    int col = Integer.parseInt(parts[1]) - 1;
                    if (!board.placeStone(row, col)) {
                        System.out.println("非法落子，请重试");
                    }
                } catch (NumberFormatException e) {
                    System.out.println("请输入数字");
                }
            } else {
                // AI落子
                System.out.println("AI思考中...");
                long start = System.currentTimeMillis();
                int move = engine.searchBestMove(board, 1000); // 思考1秒
                long elapsed = System.currentTimeMillis() - start;

                if (move == -1) {
                    System.out.println("AI选择pass (思考用时" + elapsed + "ms)");
                    board.pass();
                } else {
                    int row = move / size + 1;
                    int col = move % size + 1;
                    System.out.println("AI落子: " + row + " " + col + " (思考用时" + elapsed + "ms)");
                    board.placeStone(move / size, move % size);
                }
            }
        }

        System.out.println("\n=== 对局结束 ===");
        System.out.println(board);
        double[] score = board.computeScore();
        System.out.printf("最终比分 — 黑棋: %.1f, 白棋: %.1f (含贴目6.5)\n", score[0], score[1]);
        if (score[0] > score[1]) System.out.println("黑棋胜!");
        else if (score[1] > score[0]) System.out.println("白棋胜!");
        else System.out.println("和棋!");

        scanner.close();
    }
}

六、算法优化方向

本文实现的MCTS是最基础的”纯随机模拟”版本，在实际竞赛级引擎中还需要以下增强：

其中RAVE是最容易实现的改进：当一次模拟经过节点A并访问了落子X，即使X不是在A处下的，也可以为A的子节点中对应X的节点提供一次”虚拟访问”统计，从而在树还很稀疏时加速价值估计收敛。

七、复杂度分析

• 时间复杂度：每轮迭代为O(d + s)，其中d为树深度（通常<50），s为模拟步数（上限O(n²)，n为路数）。设总迭代次数为N，则总时间为O(N·(d + n²))。9路棋盘在1秒内可完成约5000-10000次迭代。
• 空间复杂度：搜索树节点数上限为O(N)，每个节点存储棋盘拷贝O(n²)，总空间O(N·n²)。实际中因剪枝和哈希去重远低于此上限。
• UCT收敛性：当迭代次数N→∞时，UCT保证以概率1选择最优行动（Kocsis & Szepesvári, 2006）。

八、总结

蒙特卡洛树搜索的美妙之处在于它将”随机”与”统计”结合，用大量廉价模拟替代昂贵的精确搜索。虽然本文的纯随机版本棋力有限，但它完整展示了MCTS的四阶段框架，读者在此基础上叠加RAVE、领域知识或神经网络即可构建出具备实战水平的围棋AI。这套思想不仅适用于围棋，同样适用于象棋、扑克、星际争霸等任何信息完备或不完备的博弈场景，是当代游戏AI的基石算法之一。