C++ Minimax算法详解（从零实现井字棋AI）

实战：用C++实现井字棋Minimax AI

我们将分步骤构建一个完整的井字棋程序，包含以下功能：

1. 棋盘表示
2. 胜负判断
3. Minimax算法实现
4. 人机对战主循环

第1步：定义棋盘和基本结构

#include <iostream>#include <vector>#include <climits>using namespace std;// 棋盘大小const int BOARD_SIZE = 3;// 玩家标识const char PLAYER_X = 'X';const char PLAYER_O = 'O';const char EMPTY = ' ';// 棋盘用二维向量表示vector<vector<char>> board(BOARD_SIZE, vector<char>(BOARD_SIZE, EMPTY));

第2步：判断游戏状态（胜负/平局）

// 检查是否有玩家获胜bool checkWin(char player) {    // 检查行    for (int i = 0; i < BOARD_SIZE; i++) {        if (board[i][0] == player && board[i][1] == player && board[i][2] == player)            return true;    }        // 检查列    for (int j = 0; j < BOARD_SIZE; j++) {        if (board[0][j] == player && board[1][j] == player && board[2][j] == player)            return true;    }        // 检查对角线    if (board[0][0] == player && board[1][1] == player && board[2][2] == player)        return true;    if (board[0][2] == player && board[1][1] == player && board[2][0] == player)        return true;        return false;}// 检查是否平局bool isBoardFull() {    for (int i = 0; i < BOARD_SIZE; i++) {        for (int j = 0; j < BOARD_SIZE; j++) {            if (board[i][j] == EMPTY)                return false;        }    }    return true;}

第3步：实现Minimax核心算法

这是整个程序的关键部分。我们将为AI（假设是'O'）实现Minimax函数，返回最佳走法的评分。

// Minimax算法int minimax(bool isMaximizing) {    // 检查终止条件    if (checkWin(PLAYER_O)) return 1;   // AI赢    if (checkWin(PLAYER_X)) return -1;  // 玩家赢    if (isBoardFull()) return 0;     // 平局    if (isMaximizing) {        int bestScore = INT_MIN;        for (int i = 0; i < BOARD_SIZE; i++) {            for (int j = 0; j < BOARD_SIZE; j++) {                // 尝试一个空位                if (board[i][j] == EMPTY) {                    board[i][j] = PLAYER_O;                    int score = minimax(false);                    board[i][j] = EMPTY; // 回溯                    bestScore = max(score, bestScore);                }            }        }        return bestScore;    } else {        int bestScore = INT_MAX;        for (int i = 0; i < BOARD_SIZE; i++) {            for (int j = 0; j < BOARD_SIZE; j++) {                // 对手尝试一个空位                if (board[i][j] == EMPTY) {                    board[i][j] = PLAYER_X;                    int score = minimax(true);                    board[i][j] = EMPTY; // 回溯                    bestScore = min(score, bestScore);                }            }        }        return bestScore;    }}

第4步：让AI选择最佳走法

// AI执行最佳移动void aiMove() {    int bestScore = INT_MIN;    int bestRow = -1, bestCol = -1;    for (int i = 0; i < BOARD_SIZE; i++) {        for (int j = 0; j < BOARD_SIZE; j++) {            if (board[i][j] == EMPTY) {                board[i][j] = PLAYER_O;                int score = minimax(false);                board[i][j] = EMPTY;                if (score > bestScore) {                    bestScore = score;                    bestRow = i;                    bestCol = j;                }            }        }    }    if (bestRow != -1 && bestCol != -1) {        board[bestRow][bestCol] = PLAYER_O;        cout << "AI 落子于 (" << bestRow + 1 << ", " << bestCol + 1 << ")\n";    }}

第5步：主程序与人机对战

最后，我们编写主函数，实现人机轮流下棋的交互界面。

// 打印棋盘void printBoard() {    cout << "\n当前棋盘:\n";    for (int i = 0; i < BOARD_SIZE; i++) {        for (int j = 0; j < BOARD_SIZE; j++) {            cout << board[i][j];            if (j < BOARD_SIZE - 1) cout << " | ";        }        cout << endl;        if (i < BOARD_SIZE - 1) cout << "---------\n";    }    cout << endl;}int main() {    cout << "欢迎来到井字棋！你执 X，AI执 O。\n";    cout << "输入格式：行 列（例如：1 2 表示第一行第二列）\n";    while (true) {        printBoard();        // 玩家回合        int row, col;        cout << "请输入你的落子位置（行 列）: ";        cin >> row >> col;        row--; col--; // 转换为0索引        if (row < 0 || row >= BOARD_SIZE || col < 0 || col >= BOARD_SIZE || board[row][col] != EMPTY) {            cout << "无效位置，请重试！\n";            continue;        }        board[row][col] = PLAYER_X;        // 检查玩家是否获胜        if (checkWin(PLAYER_X)) {            printBoard();            cout << "恭喜你赢了！\n";            break;        }        if (isBoardFull()) {            printBoard();            cout << "平局！\n";            break;        }        // AI回合        aiMove();        if (checkWin(PLAYER_O)) {            printBoard();            cout << "AI获胜！\n";            break;        }        if (isBoardFull()) {            printBoard();            cout << "平局！\n";            break;        }    }    return 0;}

总结与进阶

通过本教程，你已经掌握了如何用C++ Minimax算法实现一个智能的井字棋AI。这个人工智能博弈算法虽然简单，但其思想可扩展到更复杂的游戏。

为了提升性能，你可以学习以下优化技术：

• Alpha-Beta剪枝：大幅减少搜索节点数量；
• 启发式评估函数：用于无法穷举的局面（如国际象棋）；
• 深度限制：避免在复杂游戏中递归过深。

无论你是想深入学习递归算法教程，还是希望构建自己的井字棋AI实现，Minimax都是一个绝佳的起点。动手试试吧，你会发现人工智能其实并不遥远！