每日算法 — 使用java实现四子棋：Minimax博弈树与位运算优化

四子棋（Connect Four）是一款经典的双人策略棋类游戏，规则简洁却蕴含深刻的博弈论思想：两名玩家轮流在7列6行的竖立棋盘上落子，棋子受重力影响落入每列最低空位，先将四枚同色棋子在横、竖、斜任一方向连成一线者获胜。本文将用Java实现一个带AI的四子棋对战程序，核心亮点在于使用64位位运算压缩棋盘状态，并结合Minimax博弈树与Alpha-Beta剪枝让AI拥有人类高手级别的决策能力。

位运算棋盘表示

传统实现多用二维数组 int[6][7] 存储棋盘，每次检测胜负需要遍历四个方向。而四子棋的棋盘仅有42个格子，完全可以压缩进一个64位长整型（long）中。John Tromp提出的经典位棋盘方案将每列用9位表示（6个格子 + 3位填充），7列共63位，恰好落入一个 long 的范围内。

具体编码方式为：对每一列，从底部开始，用连续的位表示每个格子。额外在每列顶部设置一个”哨兵位”，用于快速判断该列是否已满。 player’s 棋盘与一个”掩码”（mask）配合使用：掩码记录所有已落子的位置，player’s 棋盘记录当前玩家落子的位置。

这种表示法的巨大优势在于：胜负检测可以通过位运算在常数时间内完成。若某玩家在某列落子后，只需将其棋盘与该方向预先构造的位掩码进行移位与按位与操作，即可判断是否在任意方向形成四连。

Minimax与Alpha-Beta剪枝

Minimax算法是二人零和博弈的标准解法。AI假设对手也会采取最优策略，递归评估每种走法的极小极大值。四子棋的分支因子最高为7（7列可选），深度为10时已有千万级节点，纯Minimax不可行。

Alpha-Beta剪枝通过维护两个阈值 α（己方至少能得到的分数）和 β（对方至多能让己方得到的分数），剪掉大量不影响最终决策的分支。在走法排序良好的情况下，剪枝效率极高。

本文还引入迭代加深策略：从浅层开始逐层加深搜索，既能在时间受限时给出合理决策，又能利用前一深度的结果优化走法排序，进一步提升剪枝率。

估值函数设计

对于无法搜索到终局的中间状态，需要估值函数量化局面优劣。本文采用基于”棋型计数”的评估策略：统计双方在横、竖、斜方向上所有长度为4的滑动窗口中，活三（3子连珠且两端开放）、眠三、活二等棋型的数量，按权重累加得分。AI选择最大化己方得分与 minimized 对手得分的差值。

完整Java实现

import java.util.*;

/**
 * 四子棋（Connect Four）AI对战程序
 * 核心：位运算棋盘 + Minimax + Alpha-Beta剪枝 + 迭代加深
 */
public class ConnectFourAI {

    // 棋盘常量：7列 x 6行，每列占9位（6格 + 3位顶部间隔），共63位
    private static final int WIDTH = 7;
    private static final int HEIGHT = 6;
    private static final int COLUMN_BITS = HEIGHT + 1; // 每列9位
    private static final long BOTTOM_MASK = bottomMask();
    private static final long TOP_MASK = topMask();

    // 方向位移量：水平、垂直、主对角线、副对角线
    private static final int[] DIRECTIONS = {1, COLUMN_BITS, COLUMN_BITS - 1, COLUMN_BITS + 1};

    // 当前对局状态：分别记录两位玩家的棋盘位图
    private long[] bitboards = new long[2];
    // 掩码记录所有已占用的格子（两位玩家棋盘按位或）
    private long mask = 0L;
    private int moves = 0; // 已走步数

    /**
     * 构造底部掩码：每列最底部一位为1
     */
    private static long bottomMask() {
        long m = 0L;
        for (int col = 0; col < WIDTH; col++) {
            m |= 1L << (col * COLUMN_BITS);
        }
        return m;
    }

    /**
     * 构造顶部掩码：每列最顶部（哨兵位）为1，用于判断列满
     */
    private static long topMask() {
        long m = 0L;
        for (int col = 0; col < WIDTH; col++) {
            m |= 1L << ((col + 1) * COLUMN_BITS - 1);
        }
        return m;
    }

    /**
     * 获取某列的列掩码（该列所有格子位）
     */
    private static long columnMask(int col) {
        return ((1L << HEIGHT) - 1) << (col * COLUMN_BITS);
    }

    /**
     * 在指定列落子，返回是否成功
     */
    public boolean play(int col) {
        if (col < 0 || col >= WIDTH) return false;
        long move = (mask & columnMask(col)) + (1L << (col * COLUMN_BITS));
        if ((move & TOP_MASK) != 0) return false; // 列已满
        bitboards[moves & 1] ^= move; // 当前玩家落子
        mask |= move;
        moves++;
        return true;
    }

    /**
     * 撤销最近一步（用于搜索回溯）
     */
    public void undo() {
        moves--;
        long move = mask ^ (mask - BOTTOM_MASK);
        mask &= ~move;
        bitboards[moves & 1] ^= move;
    }

    /**
     * 判断当前玩家（上一位落子者）是否获胜
     * 核心：位运算常数时间检测四连
     */
    public boolean isWin() {
        long bb = bitboards[(moves - 1) & 1];
        // 对四个方向分别检测
        for (int dir : DIRECTIONS) {
            long m = bb & (bb >> dir);
            if ((m & (m >> (2 * dir))) != 0) return true;
        }
        return false;
    }

    /**
     * 判断是否为平局
     */
    public boolean isDraw() {
        return moves == WIDTH * HEIGHT;
    }

    /**
     * 获取当前可走的所有列（中间优先启发式排序）
     */
    public List<Integer> getValidMoves() {
        List<Integer> moves = new ArrayList<>();
        int[] order = {3, 2, 4, 1, 5, 0, 6}; // 中间列优先，增强剪枝效率
        for (int col : order) {
            if ((mask & TOP_MASK & columnMask(col)) == 0) {
                moves.add(col);
            }
        }
        return moves;
    }

    /**
     * 估值函数：基于棋型统计的局面评估
     */
    public int evaluate(int player) {
        int score = 0;
        long myBoard = bitboards[player];
        long oppBoard = bitboards[1 - player];

        // 扫描所有四格窗口进行棋型评分
        for (int r = 0; r < HEIGHT; r++) {
            for (int c = 0; c <= WIDTH - 4; c++) {
                score += scoreWindow(myBoard, oppBoard, r, c, 1, 0); // 水平
            }
        }
        for (int r = 0; r <= HEIGHT - 4; r++) {
            for (int c = 0; c < WIDTH; c++) {
                score += scoreWindow(myBoard, oppBoard, r, c, 0, 1); // 垂直
            }
        }
        for (int r = 0; r <= HEIGHT - 4; r++) {
            for (int c = 0; c <= WIDTH - 4; c++) {
                score += scoreWindow(myBoard, oppBoard, r, c, 1, 1);   // 主对角
                score += scoreWindow(myBoard, oppBoard, r, c + 3, 1, -1); // 副对角
            }
        }
        return score;
    }

    /**
     * 评估一个四格窗口的得分
     */
    private int scoreWindow(long my, long opp, int r, int c, int dc, int dr) {
        int myCount = 0, oppCount = 0;
        for (int i = 0; i < 4; i++) {
            int pos = (r + i * dr) + (c + i * dc) * COLUMN_BITS;
            long bit = 1L << pos;
            if ((my & bit) != 0) myCount++;
            else if ((opp & bit) != 0) oppCount++;
        }
        if (myCount > 0 && oppCount > 0) return 0; // 双方混合，无威胁
        if (oppCount == 4) return -100000; // 对手已四连（不应出现，已被终局检测拦截）
        if (myCount == 4) return 100000;
        // 威胁权重：活三 > 眠三 > 活二
        int[] weights = {0, 10, 100, 1000};
        if (oppCount == 0) return weights[myCount];
        return -weights[oppCount];
    }

    // ------------------- AI 搜索核心 -------------------

    private int searchDepth = 8;
    private int evaluatedNodes = 0;

    /**
     * AI选择最佳落子（Minimax + Alpha-Beta + 迭代加深）
     */
    public int findBestMove(int aiPlayer) {
        int bestCol = -1;
        int currentPlayer = moves & 1;
        if (currentPlayer != aiPlayer) return -1;

        evaluatedNodes = 0;
        long startTime = System.currentTimeMillis();

        // 迭代加深：从浅层到深层逐步搜索
        for (int depth = 1; depth <= searchDepth; depth++) {
            int[] result = minimax(depth, Integer.MIN_VALUE + 1, Integer.MAX_VALUE - 1, true, aiPlayer);
            if (result[0] != Integer.MIN_VALUE) {
                bestCol = result[1];
            }
            long elapsed = System.currentTimeMillis() - startTime;
            if (elapsed > 2000) break; // 时间上限2秒
        }
        System.out.println("AI搜索节点数: " + evaluatedNodes);
        return bestCol;
    }

    /**
     * Minimax + Alpha-Beta 递归搜索
     * @return int[]{分数, 最佳列}
     */
    private int[] minimax(int depth, int alpha, int beta, boolean isMaximizing, int aiPlayer) {
        evaluatedNodes++;

        // 终局检测
        if (moves > 0 && isWin()) {
            int winner = (moves - 1) & 1;
            return new int[]{winner == aiPlayer ? 1000000 + depth : -1000000 - depth, -1};
        }
        if (isDraw()) return new int[]{0, -1};
        if (depth == 0) {
            int currentPlayer = moves & 1;
            int score = (currentPlayer == aiPlayer) ? evaluate(aiPlayer) : -evaluate(1 - aiPlayer);
            return new int[]{score, -1};
        }

        List<Integer> validMoves = getValidMoves();
        if (validMoves.isEmpty()) return new int[]{0, -1};

        int bestCol = validMoves.get(0);

        if (isMaximizing) {
            int maxEval = Integer.MIN_VALUE;
            for (int col : validMoves) {
                play(col);
                int eval = minimax(depth - 1, alpha, beta, false, aiPlayer)[0];
                undo();
                if (eval > maxEval) {
                    maxEval = eval;
                    bestCol = col;
                }
                alpha = Math.max(alpha, eval);
                if (beta <= alpha) break; // Beta剪枝
            }
            return new int[]{maxEval, bestCol};
        } else {
            int minEval = Integer.MAX_VALUE;
            for (int col : validMoves) {
                play(col);
                int eval = minimax(depth - 1, alpha, beta, true, aiPlayer)[0];
                undo();
                if (eval < minEval) {
                    minEval = eval;
                    bestCol = col;
                }
                beta = Math.min(beta, eval);
                if (beta <= alpha) break; // Alpha剪枝
            }
            return new int[]{minEval, bestCol};
        }
    }

    // ------------------- 控制台对战入口 -------------------

    public static void main(String[] args) {
        ConnectFourAI game = new ConnectFourAI();
        Scanner scanner = new Scanner(System.in);
        int humanPlayer = 0; // 人类先手
        int aiPlayer = 1;

        System.out.println("===== 四子棋对战（人类 vs AI） =====");
        System.out.println("列号：0 1 2 3 4 5 6");
        printBoard(game);

        while (true) {
            int current = game.moves & 1;
            if (current == humanPlayer) {
                System.out.print("请输入落子列号(0-6): ");
                int col = scanner.nextInt();
                if (!game.play(col)) {
                    System.out.println("非法落子，请重试！");
                    continue;
                }
            } else {
                System.out.println("AI思考中...");
                int col = game.findBestMove(aiPlayer);
                if (col < 0) break;
                game.play(col);
                System.out.println("AI落子列: " + col);
            }

            printBoard(game);

            if (game.isWin()) {
                String winner = ((game.moves - 1) & 1) == humanPlayer ? "人类" : "AI";
                System.out.println(winner + "获胜！");
                break;
            }
            if (game.isDraw()) {
                System.out.println("平局！");
                break;
            }
        }
        scanner.close();
    }

    /**
     * 控制台打印当前棋盘
     */
    private static void printBoard(ConnectFourAI game) {
        char[] symbols = {'X', 'O'};
        for (int r = HEIGHT - 1; r >= 0; r--) {
            for (int c = 0; c < WIDTH; c++) {
                int pos = r + c * COLUMN_BITS;
                long bit = 1L << pos;
                char ch = '.';
                if ((game.bitboards[0] & bit) != 0) ch = symbols[0];
                else if ((game.bitboards[1] & bit) != 0) ch = symbols[1];
                System.out.print(ch + " ");
            }
            System.out.println();
        }
        System.out.println("0 1 2 3 4 5 6");
        System.out.println();
    }
}

复杂度分析

总结与拓展

本文通过四子棋这一经典游戏，展示了位运算在棋盘状态压缩中的强大威力：原本需要二维数组和多重循环的操作，被简化为几次位运算，不仅代码优雅，运行效率也提升了一个数量级。结合Minimax与Alpha-Beta剪枝，AI在普通消费级电脑上即可达到10层以上的搜索深度，展现出接近人类高手的棋力。

读者可以在此基础上继续拓展：引入置换表（Transposition Table）缓存已评估的局面，采用MTD(f) 或 Negascout 等更先进的搜索框架，甚至训练神经网络替代手工估值函数，探索四子棋的更多算法可能。