用c++实现alphabeta剪枝算法五子棋

以下是使用C++实现alphabeta剪枝算法的五子棋代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 15;

int board[N][N];
int player; // 当前玩家，0表示黑子，1表示白子
int max_depth; // 最大搜索深度

// 检查是否有五子连珠
bool check_win(int x, int y) {
    int dx[4] = {0, 1, 1, 1}; // 方向数组
    int dy[4] = {1, 1, 0, -1};
    for (int i = 0; i < 4; i++) {
        int cnt = 1;
        int nx = x + dx[i], ny = y + dy[i];
        while (nx >= 0 && nx < N && ny >= 0 && ny < N && board[nx][ny] == board[x][y]) {
            cnt++;
            nx += dx[i], ny += dy[i];
        }
        nx = x - dx[i], ny = y - dy[i];
        while (nx >= 0 && nx < N && ny >= 0 && ny < N && board[nx][ny] == board[x][y]) {
            cnt++;
            nx -= dx[i], ny -= dy[i];
        }
        if (cnt >= 5) return true;
    }
    return false;
}

// 计算当前局面分数
int evaluate() {
    int sc = 0;
    int dx[4] = {0, 1, 1, 1}; // 方向数组
    int dy[4] = {1, 1, 0, -1};
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (board[i][j] == player) {
                // 统计横向、纵向、斜向的得分
                for (int k = 0; k < 4; k++) {
                    int cnt = 1;
                    int nx = i + dx[k], ny = j + dy[k];
                    while (nx >= 0 && nx < N && ny >= 0 && ny < N && board[nx][ny] == board[i][j]) {
                        cnt++;
                        nx += dx[k], ny += dy[k];
                    }
                    nx = i - dx[k], ny = j - dy[k];
                    while (nx >= 0 && nx < N && ny >= 0 && ny < N && board[nx][ny] == board[i][j]) {
                        cnt++;
                        nx -= dx[k], ny -= dy[k];
                    }
                    if (cnt >= 5) return INT_MAX; // 如果有五子连珠，返回最大值
                    if (cnt == 4) sc += 10000; // 活四
                    else if (cnt == 3) sc += 1000; // 活三
                    else if (cnt == 2) sc += 100; // 活二
                    else if (cnt == 1) sc += 10; // 活一
                }
            }
        }
    }
    return sc;
}

// alpha-beta剪枝搜索
int alpha_beta_search(int depth, int alpha, int beta) {
    if (depth == max_depth || check_win(N - 1, N - 1) || check_win(N - 1, 0) || check_win(0, N - 1) || check_win(0, 0)) {
        // 如果达到最大深度或有一方胜利，返回当前局面分数
        return evaluate();
    }
    vector<pair<int, int>> moves; // 存储所有可行的落子位置
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (board[i][j] == -1) {
                moves.emplace_back(i, j);
            }
        }
    }
    if (moves.empty()) return 0; // 棋盘已满，返回0
    if (player == 0) { // 如果当前是黑子
        int v = INT_MIN;
        for (auto move : moves) {
            int x = move.first, y = move.second;
            board[x][y] = player;
            player = 1 - player; // 切换到白子
            v = max(v, alpha_beta_search(depth + 1, alpha, beta));
            board[x][y] = -1;
            player = 1 - player; // 切换回黑子
            alpha = max(alpha, v);
            if (beta <= alpha) break; // beta剪枝
        }
        return v;
    } else { // 如果当前是白子
        int v = INT_MAX;
        for (auto move : moves) {
            int x = move.first, y = move.second;
            board[x][y] = player;
            player = 1 - player; // 切换到黑子
            v = min(v, alpha_beta_search(depth + 1, alpha, beta));
            board[x][y] = -1;
            player = 1 - player; // 切换回白子
            beta = min(beta, v);
            if (beta <= alpha) break; // alpha剪枝
        }
        return v;
    }
}

int main() {
    // 初始化棋盘
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            board[i][j] = -1;
        }
    }
    // 玩家先手，黑子为玩家，白子为AI
    player = 0;
    cout << "请输入最大搜索深度：" << endl;
    cin >> max_depth;
    while (true) {
        int x, y;
        cout << "请输入落子位置(x, y)：" << endl;
        cin >> x >> y;
        if (board[x][y] != -1) {
            cout << "该位置已有棋子，请重新输入！" << endl;
            continue;
        }
        board[x][y] = player;
        if (check_win(x, y)) {
            cout << "恭喜你获胜了！" << endl;
            break;
        }
        player = 1 - player; // 切换到AI
        int best_score = INT_MIN;
        int best_x = -1, best_y = -1;
        vector<pair<int, int>> moves;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] == -1) {
                    moves.emplace_back(i, j);
                }
            }
        }
        for (auto move : moves) {
            int x = move.first, y = move.second;
            board[x][y] = player;
            player = 1 - player; // 切换到玩家
            int score = alpha_beta_search(0, INT_MIN, INT_MAX);
            board[x][y] = -1;
            player = 1 - player; // 切换回AI
            if (score > best_score) {
                best_score = score;
                best_x = x, best_y = y;
            }
        }
        cout << "AI在(" << best_x << ", " << best_y << ")处落子，当前局面评分为：" << best_score << endl;
        board[best_x][best_y] = player;
        if (check_win(best_x, best_y)) {
            cout << "很遗憾，你输了！" << endl;
            break;
        }
        player = 1 - player; // 切换回玩家
    }
    return 0;
}

在这个实现中，我们使用了alpha-beta剪枝算法来优化搜索过程，这样可以大大减少搜索时间。我们还实现了计算当前局面分数的函数，用于评估当前局面的好坏程度。在每次AI落子时，我们使用alpha-beta剪枝算法搜索出最好的落子位置，然后进行落子。如果AI或玩家获胜，则游戏结束。