每日算法 — 使用java实现六子棋：UCT蒙特卡洛树搜索与局面评估

引言

六子棋（Connect6）是由吴毅成教授于2005年提出的棋类游戏，规则简单却变化无穷：双方轮流落子，黑方第一手下一颗子，之后每手各下两颗子，先连成六子者获胜。相比五子棋，六子棋的平衡性更佳，不存在先手必胜的困局。本文将用Java实现一个带AI的六子棋程序，核心算法采用UCT（Upper Confidence Bound applied to Trees）蒙特卡洛树搜索，结合启发式局面评估函数，让AI具备与人类对弈的能力。

核心算法原理

1. 蒙特卡洛树搜索（MCTS）

MCTS是一种通过随机模拟来评估决策的搜索算法，包含四个阶段：

• 选择（Selection）：从根节点出发，使用UCT公式选择最优子节点，直到到达未完全展开的节点。
• 扩展（Expansion）：为选中的节点添加一个或多个子节点（模拟一步落子）。
• 模拟（Simulation）：从新节点出发，进行随机对弈直到终局，记录胜负结果。
• 回溯（Backpropagation）：将模拟结果沿路径反向更新各节点的胜率统计。

2. UCT公式

UCT公式平衡了”利用”（选择胜率高的节点）和”探索”（尝试访问次数少的节点）：

UCT = (winCount / visitCount) + C * sqrt(ln(parentVisitCount) / visitCount)

其中 C 为探索常数（通常取 sqrt(2)），第一项为平均胜率（利用），第二项鼓励探索未被充分访问的节点。

3. 局面评估函数

为了加速模拟收敛，在随机模拟阶段加入启发式评估：评估棋盘上所有五连、四连、三连的活棋数量，给予不同权重，引导模拟向有利方向发展。

Java完整实现

import java.util.*;

/**
 * 六子棋（Connect6）AI实现
 * 核心算法：UCT蒙特卡洛树搜索 + 启发式局面评估
 */
public class Connect6Game {

    private static final int BOARD_SIZE = 19;      // 棋盘大小
    private static final int WIN_COUNT = 6;        // 获胜连子数
    private static final int SIMULATION_COUNT = 3000; // 每步模拟次数
    private static final double EXPLORATION_C = 1.414; // UCT探索常数 sqrt(2)

    // 棋盘状态：0=空, 1=黑棋, 2=白棋
    private final int[][] board;
    private int currentPlayer; // 1=黑, 2=白
    private int moveCount;     // 总手数

    public Connect6Game() {
        this.board = new int[BOARD_SIZE][BOARD_SIZE];
        this.currentPlayer = 1;
        this.moveCount = 0;
    }

    /**
     * 复制棋盘状态（用于模拟）
     */
    public Connect6Game copy() {
        Connect6Game g = new Connect6Game();
        for (int i = 0; i < BOARD_SIZE; i++) {
            System.arraycopy(this.board[i], 0, g.board[i], 0, BOARD_SIZE);
        }
        g.currentPlayer = this.currentPlayer;
        g.moveCount = this.moveCount;
        return g;
    }

    /**
     * 获取当前玩家每手需落子数
     */
    public int stonesPerMove() {
        return (moveCount == 0 && currentPlayer == 1) ? 1 : 2;
    }

    /**
     * 执行落子
     */
    public boolean makeMove(int r1, int c1, int r2, int c2) {
        int stones = stonesPerMove();
        if (!isValid(r1, c1)) return false;
        board[r1][c1] = currentPlayer;
        if (stones == 2) {
            if (!isValid(r2, c2)) {
                board[r1][c1] = 0; // 回滚
                return false;
            }
            board[r2][c2] = currentPlayer;
        }
        currentPlayer = (currentPlayer == 1) ? 2 : 1;
        moveCount++;
        return true;
    }

    private boolean isValid(int r, int c) {
        return r >= 0 && r < BOARD_SIZE && c >= 0 && c < BOARD_SIZE && board[r][c] == 0;
    }

    /**
     * 检查指定位置是否形成六连
     */
    public boolean checkWinAt(int r, int c) {
        int player = board[r][c];
        if (player == 0) return false;

        int[][] dirs = {{0,1}, {1,0}, {1,1}, {1,-1}};
        for (int[] d : dirs) {
            int count = 1;
            // 正向搜索
            for (int i = 1; i < WIN_COUNT; i++) {
                int nr = r + d[0] * i, nc = c + d[1] * i;
                if (nr < 0 || nr >= BOARD_SIZE || nc < 0 || nc >= BOARD_SIZE || board[nr][nc] != player) break;
                count++;
            }
            // 反向搜索
            for (int i = 1; i < WIN_COUNT; i++) {
                int nr = r - d[0] * i, nc = c - d[1] * i;
                if (nr < 0 || nr >= BOARD_SIZE || nc < 0 || nc >= BOARD_SIZE || board[nr][nc] != player) break;
                count++;
            }
            if (count >= WIN_COUNT) return true;
        }
        return false;
    }

    /**
     * 检查当前棋盘是否有玩家获胜
     */
    public int checkWinner() {
        for (int r = 0; r < BOARD_SIZE; r++) {
            for (int c = 0; c < BOARD_SIZE; c++) {
                if (board[r][c] != 0 && checkWinAt(r, c)) {
                    return board[r][c];
                }
            }
        }
        return 0;
    }

    /**
     * 获取所有合法落子位置（只考虑已有棋子附近，缩小搜索空间）
     */
    public List<int[]> getCandidateMoves() {
        Set<String> candidates = new LinkedHashSet<>();
        boolean hasStone = false;
        for (int r = 0; r < BOARD_SIZE; r++) {
            for (int c = 0; c < BOARD_SIZE; c++) {
                if (board[r][c] != 0) {
                    hasStone = true;
                    // 已有棋子周围2格范围内
                    for (int dr = -2; dr <= 2; dr++) {
                        for (int dc = -2; dc <= 2; dc++) {
                            int nr = r + dr, nc = c + dc;
                            if (isValid(nr, nc)) {
                                candidates.add(nr + "," + nc);
                            }
                        }
                    }
                }
            }
        }
        if (!hasStone) {
            // 第一手落中心
            candidates.add((BOARD_SIZE/2) + "," + (BOARD_SIZE/2));
        }
        List<int[]> moves = new ArrayList<>();
        for (String s : candidates) {
            String[] parts = s.split(",");
            moves.add(new int[]{Integer.parseInt(parts[0]), Integer.parseInt(parts[1])});
        }
        return moves;
    }

    /**
     * 核心算法1：启发式局面评估
     * 评估当前局面对指定玩家的有利程度
     */
    public double evaluate(int player) {
        double score = 0;
        int opponent = (player == 1) ? 2 : 1;

        int[][] dirs = {{0,1}, {1,0}, {1,1}, {1,-1}};
        for (int r = 0; r < BOARD_SIZE; r++) {
            for (int c = 0; c < BOARD_SIZE; c++) {
                for (int[] d : dirs) {
                    score += evaluateLine(r, c, d[0], d[1], player);
                    score -= evaluateLine(r, c, d[0], d[1], opponent) * 0.9;
                }
            }
        }
        return score;
    }

    /**
     * 评估一条直线上的连子价值
     */
    private double evaluateLine(int r, int c, int dr, int dc, int player) {
        int count = 0, blocked = 0;
        for (int i = 0; i < WIN_COUNT; i++) {
            int nr = r + dr * i, nc = c + dc * i;
            if (nr < 0 || nr >= BOARD_SIZE || nc < 0 || nc >= BOARD_SIZE) {
                blocked++;
                break;
            }
            if (board[nr][nc] == player) {
                count++;
            } else if (board[nr][nc] != 0) {
                blocked++;
                break;
            }
        }
        // 权重：活五 > 活四 > 冲四 > 活三 > 其他
        if (count >= 5) return 100000;
        if (count == 4 && blocked == 0) return 10000;
        if (count == 4 && blocked == 1) return 1000;
        if (count == 3 && blocked == 0) return 1000;
        if (count == 3 && blocked == 1) return 100;
        if (count == 2 && blocked == 0) return 100;
        return count * 10;
    }

    /**
     * MCTS树节点
     */
    static class MCTSNode {
        Connect6Game state;
        MCTSNode parent;
        List<MCTSNode> children = new ArrayList<>();
        List<int[]> untriedMoves;
        int[][] move; // 导致该节点的落子 [(r1,c1),(r2,c2)]
        int visitCount = 0;
        double winScore = 0;
        int player; // 该节点对应玩家

        MCTSNode(Connect6Game state, MCTSNode parent, int[][] move) {
            this.state = state;
            this.parent = parent;
            this.move = move;
            this.player = state.currentPlayer;
            this.untriedMoves = state.getCandidateMoves();
        }

        /**
         * 核心算法2：UCT选择
         */
        MCTSNode selectChild() {
            MCTSNode best = null;
            double bestValue = Double.NEGATIVE_INFINITY;
            for (MCTSNode child : children) {
                double uct;
                if (child.visitCount == 0) {
                    uct = Double.POSITIVE_INFINITY;
                } else {
                    double exploitation = child.winScore / child.visitCount;
                    double exploration = EXPLORATION_C * Math.sqrt(Math.log(this.visitCount) / child.visitCount);
                    uct = exploitation + exploration;
                }
                if (uct > bestValue) {
                    bestValue = uct;
                    best = child;
                }
            }
            return best;
        }
    }

    /**
     * 核心算法3：执行一次MCTS搜索迭代
     */
    private MCTSNode mctsIteration(MCTSNode root) {
        MCTSNode node = root;

        // 1. 选择：使用UCT选择最优子节点
        while (node.untriedMoves.isEmpty() && !node.children.isEmpty()) {
            node = node.selectChild();
        }

        // 2. 扩展：添加新子节点
        if (!node.untriedMoves.isEmpty()) {
            int idx = (int) (Math.random() * node.untriedMoves.size());
            int[] move1 = node.untriedMoves.remove(idx);
            int[][] movePair = new int[][]{move1, move1}; // 简化：两次落同一位置附近

            Connect6Game newState = node.state.copy();
            int stones = newState.stonesPerMove();
            if (stones == 1) {
                newState.makeMove(move1[0], move1[1], -1, -1);
            } else {
                // 找第二个落子点
                List<int[]> candidates = newState.getCandidateMoves();
                int[] move2 = candidates.isEmpty() ? move1 : candidates.get(0);
                newState.makeMove(move1[0], move1[1], move2[0], move2[1]);
            }
            MCTSNode child = new MCTSNode(newState, node, movePair);
            node.children.add(child);
            node = child;
        }

        // 3. 模拟：随机对弈到终局
        Connect6Game simState = node.state.copy();
        int winner = simState.checkWinner();
        int simDepth = 0;
        while (winner == 0 && simDepth < 50) {
            List<int[]> moves = simState.getCandidateMoves();
            if (moves.size() < simState.stonesPerMove()) break;

            // 启发式：30%概率选择评估最高的走法，70%随机
            int[] m1, m2;
            if (Math.random() < 0.3 && moves.size() >= 2) {
                moves.sort((a, b) -> {
                    Connect6Game t1 = simState.copy();
                    t1.makeMove(a[0], a[1], moves.get(0)[0], moves.get(0)[1]);
                    Connect6Game t2 = simState.copy();
                    t2.makeMove(b[0], b[1], moves.get(0)[0], moves.get(0)[1]);
                    return Double.compare(t2.evaluate(simState.currentPlayer),
                                          t1.evaluate(simState.currentPlayer));
                });
                m1 = moves.get(0);
                m2 = moves.size() > 1 ? moves.get(1) : m1;
            } else {
                m1 = moves.get((int)(Math.random() * moves.size()));
                m2 = moves.get((int)(Math.random() * moves.size()));
            }

            if (simState.stonesPerMove() == 1) {
                simState.makeMove(m1[0], m1[1], -1, -1);
            } else {
                simState.makeMove(m1[0], m1[1], m2[0], m2[1]);
            }
            winner = simState.checkWinner();
            simDepth++;
        }

        // 4. 回溯：更新路径上的统计
        int rootPlayer = root.state.currentPlayer;
        while (node != null) {
            node.visitCount++;
            if (winner == rootPlayer) {
                node.winScore += 1;
            } else if (winner == 0) {
                node.winScore += 0.5; // 和棋
            }
            node = node.parent;
        }
        return root;
    }

    /**
     * AI选择最佳落子
     */
    public int[][] aiMove() {
        MCTSNode root = new MCTSNode(this.copy(), null, null);

        for (int i = 0; i < SIMULATION_COUNT; i++) {
            mctsIteration(root);
        }

        // 选择访问次数最多的子节点（最稳定）
        MCTSNode best = null;
        int bestVisits = -1;
        for (MCTSNode child : root.children) {
            if (child.visitCount > bestVisits) {
                bestVisits = child.visitCount;
                best = child;
            }
        }

        if (best == null) {
            List<int[]> moves = getCandidateMoves();
            return new int[][]{moves.get(0), moves.get(0)};
        }
        return best.move;
    }

    /**
     * 打印棋盘
     */
    public void printBoard() {
        System.out.print("   ");
        for (int c = 0; c < BOARD_SIZE; c++) {
            System.out.printf(" %c", 'A' + c);
        }
        System.out.println();
        for (int r = 0; r < BOARD_SIZE; r++) {
            System.out.printf("%2d ", r + 1);
            for (int c = 0; c < BOARD_SIZE; c++) {
                if (board[r][c] == 0) System.out.print("· ");
                else if (board[r][c] == 1) System.out.print("● ");
                else System.out.print("○ ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Connect6Game game = new Connect6Game();
        Scanner scanner = new Scanner(System.in);

        System.out.println("=== 六子棋（Connect6）===");
        System.out.println("● = 黑棋, ○ = 白棋");
        System.out.println("输入格式：row col（如：10 10），AI为白棋（○）");

        while (true) {
            game.printBoard();
            int winner = game.checkWinner();
            if (winner != 0) {
                System.out.println((winner == 1 ? "黑棋" : "白棋") + "获胜！");
                break;
            }

            if (game.currentPlayer == 1) {
                // 玩家回合
                int stones = game.stonesPerMove();
                System.out.println("黑棋落子，需下 " + stones + " 颗");
                for (int s = 0; s < stones; s++) {
                    System.out.print("输入行列（如 10 10）：");
                    int r = scanner.nextInt() - 1;
                    int c = scanner.nextInt() - 1;
                    if (!game.makeMove(r, c, -1, -1)) {
                        System.out.println("非法落子！");
                        s--;
                    }
                }
            } else {
                // AI回合
                System.out.println("白棋（AI）思考中...");
                int[][] move = game.aiMove();
                System.out.printf("AI落子：(%d,%d) (%d,%d)%n",
                        move[0][0]+1, move[0][1]+1, move[1][0]+1, move[1][1]+1);
                game.makeMove(move[0][0], move[0][1], move[1][0], move[1][1]);
            }
        }
        scanner.close();
    }
}

算法复杂度分析

总结

本文通过Java实现了一个带AI的六子棋程序，核心采用UCT蒙特卡洛树搜索：

1. MCTS四阶段循环：选择→扩展→模拟→回溯，通过大量随机模拟逼近最优策略。
2. UCT公式：平衡利用与探索，确保搜索既关注高胜率分支，又不遗漏潜在好棋。
3. 启发式评估：通过连子模式识别（活五、活四、活三等）引导模拟向有利方向发展，显著提升AI强度。

MCTS的优势在于无需领域知识即可工作，通过自我对弈不断提升。这种思想已广泛应用于AlphaGo、围棋AI和各类博弈游戏中，是当代游戏AI的基石算法之一。