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

以下是基于alpha-beta剪枝算法实现的C++五子棋代码，供您参考：

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

using namespace std;

const int N = 15;

int board[N][N]; // 棋盘
int score[N][N]; // 每个位置的得分
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
int max_depth = 3; // 最大搜索深度
int best_x, best_y; // 记录最优落子位置

// 初始化棋盘
void init() {
    memset(board, 0, sizeof board);
    memset(score, 0, sizeof score);
    best_x = best_y = N / 2;
    board[N/2][N/2] = 1; // 中心落子
}

// 检查(x, y)是否越界
bool check(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < N;
}

// 判断是否有五子连珠
bool win(int x, int y) {
    for (int i = 0; i < 8; i++) {
        int cnt = 1;
        for (int j = 1; j <= 4; j++) {
            int nx = x + j * dx[i], ny = y + j * dy[i];
            if (check(nx, ny) && board[nx][ny] == board[x][y]) cnt ++;
            else break;
        }
        for (int j = 1; j <= 4; j++) {
            int nx = x - j * dx[i], ny = y - j * dy[i];
            if (check(nx, ny) && board[nx][ny] == board[x][y]) cnt ++;
            else break;
        }
        if (cnt >= 5) return true;
    }
    return false;
}

// 计算(x, y)的得分
int calc(int x, int y) {
    int res = 0;
    for (int i = 0; i < 8; i++) {
        int cnt = 0;
        bool flag1 = true, flag2 = true;
        for (int j = 1; j <= 4; j++) {
            int nx = x + j * dx[i], ny = y + j * dy[i];
            if (check(nx, ny)) {
                if (board[nx][ny] == 1) cnt ++;
                else if (board[nx][ny] == 2) {flag1 = false; break;}
            }
            else {flag1 = false; break;}
        }
        if (flag1) res += cnt * cnt;
        cnt = 0;
        for (int j = 1; j <= 4; j++) {
            int nx = x - j * dx[i], ny = y - j * dy[i];
            if (check(nx, ny)) {
                if (board[nx][ny] == 1) cnt ++;
                else if (board[nx][ny] == 2) {flag2 = false; break;}
            }
            else {flag2 = false; break;}
        }
        if (flag2) res += cnt * cnt;
    }
    return res;
}

// 计算每个位置的得分
void get_score() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (board[i][j] == 0) {
                score[i][j] = calc(i, j);
            }
        }
    }
}

// alpha-beta剪枝搜索
int dfs(int depth, int alpha, int beta) {
    if (depth == max_depth) return calc(best_x, best_y);
    vector<pair<int, int>> v;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (board[i][j] == 0) {
                v.push_back({i, j});
            }
        }
    }
    sort(v.begin(), v.end(), [](pair<int, int> a, pair<int, int> b) {
        return score[a.first][a.second] > score[b.first][b.second];
    });
    int res = -1e9;
    for (auto [x, y] : v) {
        board[x][y] = depth % 2 + 1;
        if (win(x, y)) { // 有必胜局面，直接返回
            board[x][y] = 0;
            return depth % 2 == 0 ? 1e9 : -1e9;
        }
        get_score();
        int t = dfs(depth + 1, alpha, beta);
        board[x][y] = 0;
        if (depth % 2 == 0) { // MAX节点
            if (t > res) {
                res = t;
                if (depth == 0) {
                    best_x = x;
                    best_y = y;
                }
            }
            alpha = max(alpha, t);
        }
        else { // MIN节点
            if (t < res) {
                res = t;
            }
            beta = min(beta, t);
        }
        if (alpha >= beta) break; // alpha剪枝或beta剪枝
    }
    return res;
}

int main() {
    init();
    get_score();
    dfs(0, -1e9, 1e9);
    cout << best_x << " " << best_y << endl;
    return 0;
}

在以上代码中，我们使用了alpha-beta剪枝算法进行搜索。搜索过程中，我们先计算每个位置的得分，然后按照得分从高到低对所有空位进行排序。在搜索时，我们依次枚举每个空位，对于每个空位，我们先尝试在该位置落子，然后计算该位置落子后的得分，然后进入下一层搜索。如果搜索到达了最大深度，我们就返回该位置的得分。如果该位置可以使当前玩家获胜，我们直接返回极大值或极小值。如果该位置不是必胜局面，我们继续搜索下一层。在搜索下一层时，我们需要将当前玩家交换为对手玩家，并更新alpha和beta。如果当前节点是MAX节点，则更新alpha，并进行alpha剪枝。如果当前节点是MIN节点，则更新beta，并进行beta剪枝。最后，我们返回当前节点的值。

由于五子棋的搜索空间非常庞大，因此我们需要设置一个最大搜索深度，以避免搜索时间过长。在以上代码中，我们设置了最大搜索深度为3。如果您的电脑性能较好，您可以适当增加最大搜索深度，以提高搜索质量。