C++alphabeta剪枝算法五子棋

C++实现Alpha-Beta剪枝算法的五子棋代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 15; // 棋盘大小
const int INF = 9999999; // 无穷大

int board[N][N]; // 棋盘
int player; // 玩家
int computer; // AI
int depth = 3; // 搜索深度

// 初始化棋盘
void init_board() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            board[i][j] = 0;
        }
    }
}

// 打印棋盘
void print_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] == player) {
                cout << "O ";
            } else if (board[i][j] == computer) {
                cout << "X ";
            } else {
                cout << "+ ";
            }
        }
        cout << endl;
    }
}

// 判断游戏是否结束
bool game_over(int p) {
    // 横向判断
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= N - 5; j++) {
            if (board[i][j] == p && board[i][j + 1] == p && board[i][j + 2] == p && board[i][j + 3] == p && board[i][j + 4] == p) {
                return true;
            }
        }
    }
    // 纵向判断
    for (int i = 0; i <= N - 5; i++) {
        for (int j = 0; j < N; j++) {
            if (board[i][j] == p && board[i + 1][j] == p && board[i + 2][j] == p && board[i + 3][j] == p && board[i + 4][j] == p) {
                return true;
            }
        }
    }
    // 斜向判断
    for (int i = 0; i <= N - 5; i++) {
        for (int j = 0; j <= N - 5; j++) {
            if (board[i][j] == p && board[i + 1][j + 1] == p && board[i + 2][j + 2] == p && board[i + 3][j + 3] == p && board[i + 4][j + 4] == p) {
                return true;
            }
        }
    }
    // 反斜向判断
    for (int i = 0; i <= N - 5; i++) {
        for (int j = 4; j < N; j++) {
            if (board[i][j] == p && board[i + 1][j - 1] == p && board[i + 2][j - 2] == p && board[i + 3][j - 3] == p && board[i + 4][j - 4] == p) {
                return true;
            }
        }
    }
    return false;
}

// 评估函数
int evaluate(int p) {
    int score = 0;
    // 横向评估
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= N - 5; j++) {
            int cnt = 0;
            for (int k = 0; k < 5; k++) {
                if (board[i][j + k] == p) {
                    cnt++;
                } else if (board[i][j + k] != 0) {
                    cnt = 0;
                    break;
                }
            }
            score += cnt * cnt;
        }
    }
    // 纵向评估
    for (int i = 0; i <= N - 5; i++) {
        for (int j = 0; j < N; j++) {
            int cnt = 0;
            for (int k = 0; k < 5; k++) {
                if (board[i + k][j] == p) {
                    cnt++;
                } else if (board[i + k][j] != 0) {
                    cnt = 0;
                    break;
                }
            }
            score += cnt * cnt;
        }
    }
    // 斜向评估
    for (int i = 0; i <= N - 5; i++) {
        for (int j = 0; j <= N - 5; j++) {
            int cnt = 0;
            for (int k = 0; k < 5; k++) {
                if (board[i + k][j + k] == p) {
                    cnt++;
                } else if (board[i + k][j + k] != 0) {
                    cnt = 0;
                    break;
                }
            }
            score += cnt * cnt;
        }
    }
    // 反斜向评估
    for (int i = 0; i <= N - 5; i++) {
        for (int j = 4; j < N; j++) {
            int cnt = 0;
            for (int k = 0; k < 5; k++) {
                if (board[i + k][j - k] == p) {
                    cnt++;
                } else if (board[i + k][j - k] != 0) {
                    cnt = 0;
                    break;
                }
            }
            score += cnt * cnt;
        }
    }
    return score;
}

// Alpha-Beta剪枝搜索
int alphabeta_search(int depth, int alpha, int beta, int p) {
    if (depth == 0 || game_over(player) || game_over(computer)) {
        return evaluate(computer) - evaluate(player);
    }
    vector<pair<int, int>> moves;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (board[i][j] == 0) {
                moves.push_back(make_pair(i, j));
            }
        }
    }
    if (p == computer) {
        int value = -INF;
        for (auto move : moves) {
            int i = move.first, j = move.second;
            board[i][j] = p;
            value = max(value, alphabeta_search(depth - 1, alpha, beta, player));
            board[i][j] = 0;
            alpha = max(alpha, value);
            if (beta <= alpha) {
                break;
            }
        }
        return value;
    } else {
        int value = INF;
        for (auto move : moves) {
            int i = move.first, j = move.second;
            board[i][j] = p;
            value = min(value, alphabeta_search(depth - 1, alpha, beta, computer));
            board[i][j] = 0;
            beta = min(beta, value);
            if (beta <= alpha) {
                break;
            }
        }
        return value;
    }
}

// AI下棋
void computer_move() {
    int value = -INF;
    vector<pair<int, int>> moves;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (board[i][j] == 0) {
                board[i][j] = computer;
                int tmp = alphabeta_search(depth - 1, -INF, INF, player);
                board[i][j] = 0;
                if (tmp > value) {
                    value = tmp;
                    moves.clear();
                    moves.push_back(make_pair(i, j));
                } else if (tmp == value) {
                    moves.push_back(make_pair(i, j));
                }
            }
        }
    }
    int idx = rand() % moves.size();
    int i = moves[idx].first, j = moves[idx].second;
    board[i][j] = computer;
    cout << "AI下棋: (" << i + 1 << "," << j + 1 << ")" << endl;
}

int main() {
    init_board();
    cout << "请选择先手(1:玩家 2:AI): ";
    cin >> player;
    if (player == 1) {
        computer = 2;
    } else {
        computer = 1;
        computer_move();
        print_board();
    }
    while (true) {
        int x, y;
        cout << "请输入落子位置(x,y): ";
        cin >> x >> y;
        if (x < 1 || x > N || y < 1 || y > N || board[x - 1][y - 1] != 0) {
            cout << "无效落子，请重新输入!" << endl;
            continue;
        }
        board[x - 1][y - 1] = player;
        if (game_over(player)) {
            cout << "你赢了!" << endl;
            break;
        }
        if (game_over(computer)) {
            cout << "AI赢了!" << endl;
            break;
        }
        computer_move();
        print_board();
        if (game_over(player)) {
            cout << "你赢了!" << endl;
            break;
        }
        if (game_over(computer)) {
            cout << "AI赢了!" << endl;
            break;
        }
    }
    return 0;
}

这里使用了Alpha-Beta剪枝算法进行搜索，评估函数使用了一种简单的方式，即计算连续的空位个数的平方。可以根据需要进行更改。