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

以下是基于C++的alpha-beta剪枝算法五子棋代码示例：

#include <iostream>
#include <limits>
#include <vector>

using namespace std;

const int BOARD_SIZE = 15;
const int WIN_COUNT = 5;
const int HUMAN = 1;
const int COMPUTER = 2;

struct Position {
    int x;
    int y;
    Position(int x, int y) : x(x), y(y) {}
};

class Board {
public:
    Board() {
        board = new int*[BOARD_SIZE];
        for (int i = 0; i < BOARD_SIZE; i++) {
            board[i] = new int[BOARD_SIZE];
            for (int j = 0; j < BOARD_SIZE; j++) {
                board[i][j] = 0;
            }
        }
    }

    ~Board() {
        for (int i = 0; i < BOARD_SIZE; i++) {
            delete[] board[i];
        }
        delete[] board;
    }

    int get(int x, int y) const {
        return board[x][y];
    }

    void set(int x, int y, int value) {
        board[x][y] = value;
    }

    bool isFull() const {
        for (int i = 0; i < BOARD_SIZE; i++) {
            for (int j = 0; j < BOARD_SIZE; j++) {
                if (board[i][j] == 0) {
                    return false;
                }
            }
        }
        return true;
    }

    bool hasWon(int player) const {
        int count = 0;
        // Check rows
        for (int i = 0; i < BOARD_SIZE; i++) {
            count = 0;
            for (int j = 0; j < BOARD_SIZE; j++) {
                if (board[i][j] == player) {
                    count++;
                    if (count == WIN_COUNT) {
                        return true;
                    }
                } else {
                    count = 0;
                }
            }
        }
        // Check columns
        for (int j = 0; j < BOARD_SIZE; j++) {
            count = 0;
            for (int i = 0; i < BOARD_SIZE; i++) {
                if (board[i][j] == player) {
                    count++;
                    if (count == WIN_COUNT) {
                        return true;
                    }
                } else {
                    count = 0;
                }
            }
        }
        // Check diagonals
        for (int k = 0; k < BOARD_SIZE * 2 - 1; k++) {
            count = 0;
            for (int i = 0; i < BOARD_SIZE; i++) {
                int j = k - i;
                if (j >= 0 && j < BOARD_SIZE) {
                    if (board[i][j] == player) {
                        count++;
                        if (count == WIN_COUNT) {
                            return true;
                        }
                    } else {
                        count = 0;
                    }
                }
            }
        }
        // Check anti-diagonals
        for (int k = 0; k < BOARD_SIZE * 2 - 1; k++) {
            count = 0;
            for (int i = 0; i < BOARD_SIZE; i++) {
                int j = k - (BOARD_SIZE - 1 - i);
                if (j >= 0 && j < BOARD_SIZE) {
                    if (board[i][j] == player) {
                        count++;
                        if (count == WIN_COUNT) {
                            return true;
                        }
                    } else {
                        count = 0;
                    }
                }
            }
        }
        return false;
    }

    vector<Position> getEmptyPositions() const {
        vector<Position> emptyPositions;
        for (int i = 0; i < BOARD_SIZE; i++) {
            for (int j = 0; j < BOARD_SIZE; j++) {
                if (board[i][j] == 0) {
                    emptyPositions.push_back(Position(i, j));
                }
            }
        }
        return emptyPositions;
    }

private:
    int** board;
};

int score(const Board& board, int player) {
    if (board.hasWon(player)) {
        return numeric_limits<int>::max();
    } else if (board.hasWon(3 - player)) {
        return numeric_limits<int>::min();
    } else {
        return 0;
    }
}

int alphaBeta(const Board& board, int depth, int alpha, int beta, int player) {
    if (depth == 0 || board.isFull()) {
        return score(board, player);
    }
    if (player == COMPUTER) {
        int value = numeric_limits<int>::min();
        for (const auto& emptyPosition : board.getEmptyPositions()) {
            Board newBoard = board;
            newBoard.set(emptyPosition.x, emptyPosition.y, player);
            value = max(value, alphaBeta(newBoard, depth - 1, alpha, beta, 3 - player));
            alpha = max(alpha, value);
            if (alpha >= beta) {
                break;
            }
        }
        return value;
    } else { // player == HUMAN
        int value = numeric_limits<int>::max();
        for (const auto& emptyPosition : board.getEmptyPositions()) {
            Board newBoard = board;
            newBoard.set(emptyPosition.x, emptyPosition.y, player);
            value = min(value, alphaBeta(newBoard, depth - 1, alpha, beta, 3 - player));
            beta = min(beta, value);
            if (alpha >= beta) {
                break;
            }
        }
        return value;
    }
}

Position findBestMove(const Board& board, int depth, int player) {
    int alpha = numeric_limits<int>::min();
    int beta = numeric_limits<int>::max();
    int bestValue = numeric_limits<int>::min();
    Position bestMove(-1, -1);
    for (const auto& emptyPosition : board.getEmptyPositions()) {
        Board newBoard = board;
        newBoard.set(emptyPosition.x, emptyPosition.y, player);
        int value = alphaBeta(newBoard, depth - 1, alpha, beta, 3 - player);
        if (value > bestValue) {
            bestValue = value;
            bestMove = emptyPosition;
        }
    }
    return bestMove;
}

int main() {
    Board board;
    int player = HUMAN;
    while (!board.isFull() && !board.hasWon(HUMAN) && !board.hasWon(COMPUTER)) {
        if (player == HUMAN) {
            int x, y;
            cout << "Enter your move (x y): ";
            cin >> x >> y;
            while (board.get(x, y) != 0) {
                cout << "Invalid move. Please try again." << endl;
                cout << "Enter your move (x y): ";
                cin >> x >> y;
            }
            board.set(x, y, HUMAN);
            player = COMPUTER;
        } else { // player == COMPUTER
            int depth = 5; // You can adjust the search depth here
            Position bestMove = findBestMove(board, depth, COMPUTER);
            cout << "Computer's move: " << bestMove.x << " " << bestMove.y << endl;
            board.set(bestMove.x, bestMove.y, COMPUTER);
            player = HUMAN;
        }
        // Print the board
        for (int i = 0; i < BOARD_SIZE; i++) {
            for (int j = 0; j < BOARD_SIZE; j++) {
                cout << board.get(i, j) << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
    if (board.hasWon(HUMAN)) {
        cout << "You win!" << endl;
    } else if (board.hasWon(COMPUTER)) {
        cout << "Computer wins!" << endl;
    } else {
        cout << "Draw." << endl;
    }
    return 0;
}

这个代码实现了基本的alpha-beta剪枝算法，你可以根据自己的需求进行调整和拓展。