C语言Minimax算法实战指南（从零实现井字棋AI）

什么是Minimax算法？

Minimax（极小极大）算法是一种递归实现Minimax的搜索策略。它的基本思想是：

• Max玩家（通常是AI）希望最大化自己的得分；
• Min玩家（人类对手）希望最小化AI的得分；
• 算法通过构建一棵“博弈树”，遍历所有可能的走法，最终选择最优路径。

在井字棋中，我们可以为每个终局状态赋值：AI赢 = +10，人类赢 = -10，平局 = 0。Minimax会回溯这些值，决定当前最佳落子位置。

步骤一：定义棋盘和基础函数

首先，我们用一个3x3的二维数组表示棋盘：

#include <stdio.h>#include <limits.h>#define BOARD_SIZE 3#define PLAYER 'X'   // 人类玩家#define AI 'O'      // AI玩家char board[BOARD_SIZE][BOARD_SIZE];void initBoard() {    for (int i = 0; i < BOARD_SIZE; i++)        for (int j = 0; j < BOARD_SIZE; j++)            board[i][j] = ' ';}void printBoard() {    for (int i = 0; i < BOARD_SIZE; i++) {        for (int j = 0; j < BOARD_SIZE; j++) {            printf("%c", board[i][j]);            if (j < BOARD_SIZE - 1) printf(" | ");        }        printf("\n");        if (i < BOARD_SIZE - 1) printf("---------\n");    }}

步骤二：判断游戏状态

我们需要一个函数来检查是否有玩家获胜或是否平局：

int evaluate() {    // 检查行    for (int row = 0; row < BOARD_SIZE; row++) {        if (board[row][0] == board[row][1] &&            board[row][1] == board[row][2]) {            if (board[row][0] == AI) return +10;            else if (board[row][0] == PLAYER) return -10;        }    }    // 检查列    for (int col = 0; col < BOARD_SIZE; col++) {        if (board[0][col] == board[1][col] &&            board[1][col] == board[2][col]) {            if (board[0][col] == AI) return +10;            else if (board[0][col] == PLAYER) return -10;        }    }    // 检查对角线    if (board[0][0] == board[1][1] && board[1][1] == board[2][2]) {        if (board[0][0] == AI) return +10;        else if (board[0][0] == PLAYER) return -10;    }    if (board[0][2] == board[1][1] && board[1][1] == board[2][0]) {        if (board[0][2] == AI) return +10;        else if (board[0][2] == PLAYER) return -10;    }    return 0; // 无人获胜}int isMovesLeft() {    for (int i = 0; i < BOARD_SIZE; i++)        for (int j = 0; j < BOARD_SIZE; j++)            if (board[i][j] == ' ') return 1;    return 0;}

步骤三：核心——Minimax递归函数

这是整个AI的大脑！它会递归地探索每一步的可能结果：

int minimax(int depth, int isMax) {    int score = evaluate();    // 如果AI赢了    if (score == 10) return score - depth;    // 如果人类赢了    if (score == -10) return score + depth;    // 如果没有空格了（平局）    if (!isMovesLeft()) return 0;    // Max玩家（AI）回合    if (isMax) {        int best = INT_MIN;        for (int i = 0; i < BOARD_SIZE; i++) {            for (int j = 0; j < BOARD_SIZE; j++) {                // 如果格子为空                if (board[i][j] == ' ') {                    board[i][j] = AI;                    best = best > minimax(depth + 1, 0) ? best : minimax(depth + 1, 0);                    board[i][j] = ' '; // 回溯                }            }        }        return best;    }    // Min玩家（人类）回合    else {        int best = INT_MAX;        for (int i = 0; i < BOARD_SIZE; i++) {            for (int j = 0; j < BOARD_SIZE; j++) {                if (board[i][j] == ' ') {                    board[i][j] = PLAYER;                    best = best < minimax(depth + 1, 1) ? best : minimax(depth + 1, 1);                    board[i][j] = ' ';                }            }        }        return best;    }}

步骤四：让AI选择最佳落子

void findBestMove() {    int bestVal = 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] == ' ') {                board[i][j] = AI;                int moveVal = minimax(0, 0);                board[i][j] = ' ';                if (moveVal > bestVal) {                    bestRow = i;                    bestCol = j;                    bestVal = moveVal;                }            }        }    }    board[bestRow][bestCol] = AI;    printf("AI 落子于 (%d, %d)\n", bestRow + 1, bestCol + 1);}

完整运行与测试

将上述代码整合后，你就可以和AI对战井字棋了！这个实现展示了如何通过井字棋AI来理解Minimax的完整流程。虽然对于复杂游戏（如国际象棋）需要优化（例如Alpha-Beta剪枝），但本例足以帮助初学者掌握核心思想。

通过本教程，你不仅学会了C语言Minimax算法的编写，还掌握了递归实现Minimax的关键技巧。下一步可以尝试加入难度选择、图形界面，或扩展到其他棋类游戏！