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

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

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

const int BOARD_SIZE = 15;

enum class ChessType { NONE, BLACK, WHITE };

struct ChessBoard {
    ChessType board[BOARD_SIZE][BOARD_SIZE];
    ChessType current_player;
    int last_row, last_col;

    ChessBoard() {
        for (int i = 0; i < BOARD_SIZE; i++) {
            for (int j = 0; j < BOARD_SIZE; j++) {
                board[i][j] = ChessType::NONE;
            }
        }
        current_player = ChessType::BLACK;
        last_row = -1;
        last_col = -1;
    }

    void print() const {
        cout << "  ";
        for (int i = 0; i < BOARD_SIZE; i++) {
            cout << i << " ";
        }
        cout << endl;
        for (int i = 0; i < BOARD_SIZE; i++) {
            cout << i << " ";
            for (int j = 0; j < BOARD_SIZE; j++) {
                switch (board[i][j]) {
                    case ChessType::NONE:
                        cout << "+ ";
                        break;
                    case ChessType::BLACK:
                        cout << "X ";
                        break;
                    case ChessType::WHITE:
                        cout << "O ";
                        break;
                }
            }
            cout << endl;
        }
    }

    bool put(int row, int col) {
        if (row < 0 || row >= BOARD_SIZE || col < 0 || col >= BOARD_SIZE ||
            board[row][col] != ChessType::NONE) {
            return false;
        }
        board[row][col] = current_player;
        last_row = row;
        last_col = col;
        return true;
    }

    void undo() {
        board[last_row][last_col] = ChessType::NONE;
        last_row = -1;
        last_col = -1;
        current_player = (current_player == ChessType::BLACK) ? ChessType::WHITE : ChessType::BLACK;
    }

    bool is_win() const {
        if (last_row == -1 || last_col == -1) {
            return false;
        }
        const ChessType win_player = board[last_row][last_col];
        int count = 0;
        // 横向
        for (int i = max(last_col - 4, 0); i <= min(last_col + 4, BOARD_SIZE - 1); i++) {
            if (board[last_row][i] == win_player) {
                count++;
                if (count >= 5) {
                    return true;
                }
            } else {
                count = 0;
            }
        }
        count = 0;
        // 纵向
        for (int i = max(last_row - 4, 0); i <= min(last_row + 4, BOARD_SIZE - 1); i++) {
            if (board[i][last_col] == win_player) {
                count++;
                if (count >= 5) {
                    return true;
                }
            } else {
                count = 0;
            }
        }
        count = 0;
        // 斜向（左上到右下）
        for (int i = max(last_row - 4, 0), j = max(last_col - 4, 0); i <= min(last_row + 4, BOARD_SIZE - 1) && j <= min(last_col + 4, BOARD_SIZE - 1); i++, j++) {
            if (board[i][j] == win_player) {
                count++;
                if (count >= 5) {
                    return true;
                }
            } else {
                count = 0;
            }
        }
        count = 0;
        // 斜向（左下到右上）
        for (int i = min(last_row + 4, BOARD_SIZE - 1), j = max(last_col - 4, 0); i >= max(last_row - 4, 0) && j <= min(last_col + 4, BOARD_SIZE - 1); i--, j++) {
            if (board[i][j] == win_player) {
                count++;
                if (count >= 5) {
                    return true;
                }
            } else {
                count = 0;
            }
        }
        return false;
    }

    vector<pair<int, int>> get_possible_positions() const {
        vector<pair<int, int>> positions;
        for (int i = 0; i < BOARD_SIZE; i++) {
            for (int j = 0; j < BOARD_SIZE; j++) {
                if (board[i][j] == ChessType::NONE) {
                    positions.emplace_back(i, j);
                }
            }
        }
        return positions;
    }
};

int evaluate(const ChessBoard& board, ChessType player) {
    int score = 0;
    int count = 0;
    // 横向
    for (int i = 0; i < BOARD_SIZE; i++) {
        for (int j = 0; j < BOARD_SIZE; j++) {
            if (board.board[i][j] == player) {
                count++;
            } else {
                score += count * count;
                count = 0;
            }
        }
        score += count * count;
        count = 0;
    }
    // 纵向
    for (int j = 0; j < BOARD_SIZE; j++) {
        for (int i = 0; i < BOARD_SIZE; i++) {
            if (board.board[i][j] == player) {
                count++;
            } else {
                score += count * count;
                count = 0;
            }
        }
        score += count * count;
        count = 0;
    }
    // 斜向（左上到右下）
    for (int k = 0; k < BOARD_SIZE; k++) {
        for (int i = max(k - 4, 0), j = max(k - 4, 0); i <= min(k + 4, BOARD_SIZE - 1) && j <= min(k + 4, BOARD_SIZE - 1); i++, j++) {
            if (board.board[i][j] == player) {
                count++;
            } else {
                score += count * count;
                count = 0;
            }
        }
        score += count * count;
        count = 0;
    }
    // 斜向（左下到右上）
    for (int k = 0; k < BOARD_SIZE; k++) {
        for (int i = min(k + 4, BOARD_SIZE - 1), j = max(k - 4, 0); i >= max(k - 4, 0) && j <= min(k + 4, BOARD_SIZE - 1); i--, j++) {
            if (board.board[i][j] == player) {
                count++;
            } else {
                score += count * count;
                count = 0;
            }
        }
        score += count * count;
        count = 0;
    }
    return score;
}

int alphabeta(const ChessBoard& board, int depth, int alpha, int beta, bool maximizing_player) {
    if (depth == 0 || board.is_win()) {
        return evaluate(board, ChessType::BLACK) - evaluate(board, ChessType::WHITE);
    }
    if (maximizing_player) {
        int max_score = INT_MIN;
        for (auto position : board.get_possible_positions()) {
            ChessBoard new_board = board;
            new_board.current_player = ChessType::BLACK;
            new_board.put(position.first, position.second);
            int score = alphabeta(new_board, depth - 1, alpha, beta, false);
            max_score = max(max_score, score);
            alpha = max(alpha, score);
            if (beta <= alpha) {
                break;
            }
        }
        return max_score;
    } else {
        int min_score = INT_MAX;
        for (auto position : board.get_possible_positions()) {
            ChessBoard new_board = board;
            new_board.current_player = ChessType::WHITE;
            new_board.put(position.first, position.second);
            int score = alphabeta(new_board, depth - 1, alpha, beta, true);
            min_score = min(min_score, score);
            beta = min(beta, score);
            if (beta <= alpha) {
                break;
            }
        }
        return min_score;
    }
}

pair<int, int> alphabeta_search(const ChessBoard& board, int depth) {
    pair<int, int> best_position(-1, -1);
    int best_score = INT_MIN;
    for (auto position : board.get_possible_positions()) {
        ChessBoard new_board = board;
        new_board.current_player = ChessType::BLACK;
        new_board.put(position.first, position.second);
        int score = alphabeta(new_board, depth, INT_MIN, INT_MAX, false);
        if (score > best_score) {
            best_score = score;
            best_position = position;
        }
    }
    return best_position;
}

int main() {
    ChessBoard board;
    board.print();
    while (!board.is_win()) {
        if (board.current_player == ChessType::BLACK) {
            int row, col;
            cout << "Please input the row and col: ";
            cin >> row >> col;
            while (!board.put(row, col)) {
                cout << "Invalid position, please input again: ";
                cin >> row >> col;
            }
        } else {
            pair<int, int> position = alphabeta_search(board, 4);
            cout << "The AI put at (" << position.first << ", " << position.second << ")" << endl;
            board.put(position.first, position.second);
        }
        board.print();
    }
    cout << "Game over!" << endl;
    return 0;
}

这个示例实现了五子棋游戏的基本逻辑和alphabeta剪枝算法。其中，evaluate函数用于评估当前局面的得分，alphabeta函数用于搜索最佳下法，alphabeta_search函数用于搜索整个搜索树并返回最佳下法。在主函数中，玩家可以通过命令行输入他们的下法，而AI则使用alphabeta剪枝算法搜索最佳下法。