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

以下是用 C++ 实现的 Alpha-Beta 剪枝五子棋算法：

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

using namespace std;

const int INF = 0x3f3f3f3f; // 定义正无穷

const int N = 15;

int n = 15; // 棋盘大小

int board[N][N]; // 棋盘

int dx[4] = {0, 1, 1, 1}; // 方向数组
int dy[4] = {1, 1, 0, -1};

// 判断当前位置是否越界
bool is_valid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n;
}

// 判断当前位置是否为空
bool is_empty(int x, int y) {
    return board[x][y] == 0;
}

// 判断当前位置是否为玩家棋子
bool is_player(int x, int y, int player) {
    return board[x][y] == player;
}

// 判断当前位置是否为电脑棋子
bool is_computer(int x, int y, int computer) {
    return board[x][y] == computer;
}

// 判断当前位置是否为边界
bool is_boundary(int x, int y) {
    return x == 0 || x == n - 1 || y == 0 || y == n - 1;
}

// 判断当前位置是否为角落
bool is_corner(int x, int y) {
    return (x == 0 && y == 0) || (x == 0 && y == n - 1) || (x == n - 1 && y == 0) || (x == n - 1 && y == n - 1);
}

// 判断当前位置是否为边缘
bool is_edge(int x, int y) {
    return is_boundary(x, y) && !is_corner(x, y);
}

// 判断当前位置是否可下
bool is_valid_move(int x, int y) {
    return is_valid(x, y) && is_empty(x, y);
}

// 判断当前位置是否能形成五子连珠
bool is_win(int x, int y, int player) {
    for (int i = 0; i < 4; i++) {
        int cnt = 1;
        int xx = x + dx[i], yy = y + dy[i];
        while (is_valid(xx, yy) && is_player(xx, yy, player)) {
            cnt++;
            xx += dx[i];
            yy += dy[i];
        }
        xx = x - dx[i], yy = y - dy[i];
        while (is_valid(xx, yy) && is_player(xx, yy, player)) {
            cnt++;
            xx -= dx[i];
            yy -= dy[i];
        }
        if (cnt >= 5) return true;
    }
    return false;
}

// 估价函数
int evaluate(int player, int computer) {
    int score = 0;
    // 统计电脑棋子在各个方向上的连子数
    int cnt[4] = {0, 0, 0, 0};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (is_computer(i, j, computer)) {
                for (int k = 0; k < 4; k++) {
                    int xx = i + dx[k], yy = j + dy[k];
                    while (is_valid(xx, yy) && is_computer(xx, yy, computer)) {
                        cnt[k]++;
                        xx += dx[k];
                        yy += dy[k];
                    }
                }
            }
        }
    }
    // 统计得分
    for (int i = 0; i < 4; i++) {
        if (cnt[i] == 1) score += 10;
        else if (cnt[i] == 2) score += 100;
        else if (cnt[i] == 3) score += 1000;
        else if (cnt[i] == 4) score += 10000;
    }
    // 统计玩家棋子在各个方向上的连子数
    memset(cnt, 0, sizeof cnt);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (is_player(i, j, player)) {
                for (int k = 0; k < 4; k++) {
                    int xx = i + dx[k], yy = j + dy[k];
                    while (is_valid(xx, yy) && is_player(xx, yy, player)) {
                        cnt[k]++;
                        xx += dx[k];
                        yy += dy[k];
                    }
                }
            }
        }
    }
    // 统计得分
    for (int i = 0; i < 4; i++) {
        if (cnt[i] == 1) score -= 10;
        else if (cnt[i] == 2) score -= 100;
        else if (cnt[i] == 3) score -= 1000;
        else if (cnt[i] == 4) score -= 10000;
    }
    return score;
}

// Alpha-Beta 剪枝搜索
int alpha_beta(int depth, int alpha, int beta, int player, int computer) {
    // 到达搜索深度，返回估价函数值
    if (depth == 0) {
        return evaluate(player, computer);
    }
    // 判断是否为电脑回合
    bool is_computer_turn = true;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (is_player(i, j, player) || is_computer(i, j, computer)) {
                is_computer_turn = false;
                break;
            }
        }
        if (!is_computer_turn) break;
    }
    // 电脑回合
    if (is_computer_turn) {
        int max_val = -INF;
        // 枚举所有可下的位置
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (is_valid_move(i, j)) {
                    board[i][j] = computer;
                    int val = alpha_beta(depth - 1, alpha, beta, player, computer);
                    board[i][j] = 0;
                    max_val = max(max_val, val);
                    alpha = max(alpha, val);
                    if (beta <= alpha) break; // Beta 剪枝
                }
            }
        }
        return max_val;
    }
    // 玩家回合
    else {
        int min_val = INF;
        // 枚举所有可下的位置
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (is_valid_move(i, j)) {
                    board[i][j] = player;
                    int val = alpha_beta(depth - 1, alpha, beta, player, computer);
                    board[i][j] = 0;
                    min_val = min(min_val, val);
                    beta = min(beta, val);
                    if (beta <= alpha) break; // Alpha 剪枝
                }
            }
        }
        return min_val;
    }
}

// 电脑下棋
void computer_move(int &x, int &y, int player, int computer) {
    int max_val = -INF;
    // 枚举所有可下的位置
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (is_valid_move(i, j)) {
                board[i][j] = computer;
                int val = alpha_beta(4, -INF, INF, player, computer); // 搜索深度为 4
                board[i][j] = 0;
                if (val > max_val) {
                    max_val = val;
                    x = i;
                    y = j;
                }
            }
        }
    }
    board[x][y] = computer;
}

// 显示棋盘
void display_board() {
    cout << "  ";
    for (int i = 0; i < n; i++) {
        cout << i + 1 << " ";
    }
    cout << endl;
    for (int i = 0; i < n; i++) {
        cout << i + 1 << " ";
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 0) cout << "+ ";
            else if (board[i][j] == 1) cout << "O ";
            else cout << "X ";
        }
        cout << endl;
    }
}

// 判断游戏是否结束
bool is_game_over(int player, int computer) {
    // 判断是否有五子连珠
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (is_win(i, j, player)) {
                cout << "You win!" << endl;
                return true;
            }
            if (is_win(i, j, computer)) {
                cout << "Computer win!" << endl;
                return true;
            }
        }
    }
    // 判断是否棋盘已满
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (is_empty(i, j)) return false;
        }
    }
    cout << "Draw!" << endl;
    return true;
}

int main() {
    int player = 1, computer = 2;
    memset(board, 0, sizeof board);
    display_board();
    while (true) {
        int x, y;
        cout << "Your move: ";
        cin >> x >> y;
        x--, y--;
        if (is_valid_move(x, y)) {
            board[x][y] = player;
            if (is_game_over(player, computer)) break;
            computer_move(x, y, player, computer);
            if (is_game_over(player, computer)) break;
            display_board();
        } else {
            cout << "Invalid move, please try again." << endl;
        }
    }
    return 0;
}

这里给出了一个简单的估价函数，具体的优化需要根据实际情况进行调整。搜索深度也可以根据实际情况进行调整。