α-β剪枝实现井字棋游戏 c++

以下是使用C++实现井字棋游戏的α-β剪枝算法的示例代码：

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

using namespace std;

const int BOARD_SIZE = 3;
const int MAX_DEPTH = 9;

enum class Player { None, Human, Computer };

struct Move {
    int row;
    int col;
};

struct Board {
    vector<vector<Player>> cells;

    Board() {
        cells.resize(BOARD_SIZE, vector<Player>(BOARD_SIZE, Player::None));
    }

    bool is_full() const {
        for (int row = 0; row < BOARD_SIZE; ++row) {
            for (int col = 0; col < BOARD_SIZE; ++col) {
                if (cells[row][col] == Player::None) {
                    return false;
                }
            }
        }
        return true;
    }

    bool is_winner(Player player) const {
        // Check rows
        for (int row = 0; row < BOARD_SIZE; ++row) {
            bool win = true;
            for (int col = 0; col < BOARD_SIZE; ++col) {
                if (cells[row][col] != player) {
                    win = false;
                    break;
                }
            }
            if (win) {
                return true;
            }
        }

        // Check columns
        for (int col = 0; col < BOARD_SIZE; ++col) {
            bool win = true;
            for (int row = 0; row < BOARD_SIZE; ++row) {
                if (cells[row][col] != player) {
                    win = false;
                    break;
                }
            }
            if (win) {
                return true;
            }
        }

        // Check diagonals
        bool win = true;
        for (int i = 0; i < BOARD_SIZE; ++i) {
            if (cells[i][i] != player) {
                win = false;
                break;
            }
        }
        if (win) {
            return true;
        }

        win = true;
        for (int i = 0; i < BOARD_SIZE; ++i) {
            if (cells[i][BOARD_SIZE - i - 1] != player) {
                win = false;
                break;
            }
        }
        if (win) {
            return true;
        }

        return false;
    }

    vector<Move> get_moves() const {
        vector<Move> moves;
        for (int row = 0; row < BOARD_SIZE; ++row) {
            for (int col = 0; col < BOARD_SIZE; ++col) {
                if (cells[row][col] == Player::None) {
                    moves.push_back({row, col});
                }
            }
        }
        return moves;
    }

    void make_move(const Move& move, Player player) {
        cells[move.row][move.col] = player;
    }

    void undo_move(const Move& move) {
        cells[move.row][move.col] = Player::None;
    }

    void print() const {
        for (int row = 0; row < BOARD_SIZE; ++row) {
            for (int col = 0; col < BOARD_SIZE; ++col) {
                switch (cells[row][col]) {
                    case Player::None:
                        cout << "-";
                        break;
                    case Player::Human:
                        cout << "X";
                        break;
                    case Player::Computer:
                        cout << "O";
                        break;
                }
                if (col < BOARD_SIZE - 1) {
                    cout << "|";
                }
            }
            cout << endl;
            if (row < BOARD_SIZE - 1) {
                cout << "-----" << endl;
            }
        }
    }
};

int evaluate(const Board& board) {
    if (board.is_winner(Player::Computer)) {
        return 1;
    } else if (board.is_winner(Player::Human)) {
        return -1;
    } else {
        return 0;
    }
}

int alpha_beta_pruning(Board& board, int depth, int alpha, int beta, bool maximizing_player) {
    if (depth == MAX_DEPTH || board.is_full()) {
        return evaluate(board);
    }

    if (maximizing_player) {
        int max_eval = -1000;
        for (const auto& move : board.get_moves()) {
            board.make_move(move, Player::Computer);
            int eval = alpha_beta_pruning(board, depth + 1, alpha, beta, false);
            board.undo_move(move);
            max_eval = max(max_eval, eval);
            alpha = max(alpha, eval);
            if (beta <= alpha) {
                break;
            }
        }
        return max_eval;
    } else {
        int min_eval = 1000;
        for (const auto& move : board.get_moves()) {
            board.make_move(move, Player::Human);
            int eval = alpha_beta_pruning(board, depth + 1, alpha, beta, true);
            board.undo_move(move);
            min_eval = min(min_eval, eval);
            beta = min(beta, eval);
            if (beta <= alpha) {
                break;
            }
        }
        return min_eval;
    }
}

Move get_best_move(const Board& board) {
    int max_eval = -1000;
    Move best_move;
    for (const auto& move : board.get_moves()) {
        Board new_board = board;
        new_board.make_move(move, Player::Computer);
        int eval = alpha_beta_pruning(new_board, 0, -1000, 1000, false);
        if (eval > max_eval) {
            max_eval = eval;
            best_move = move;
        }
    }
    return best_move;
}

int main() {
    Board board;
    Player current_player = Player::Human;

    // Randomly select first player
    if (rand() % 2 == 0) {
        current_player = Player::Computer;
        Move move = {rand() % BOARD_SIZE, rand() % BOARD_SIZE};
        board.make_move(move, current_player);
        board.print();
    }

    while (!board.is_full() && !board.is_winner(Player::Human) && !board.is_winner(Player::Computer)) {
        if (current_player == Player::Human) {
            int row, col;
            cout << "Enter row and column (0-indexed): ";
            cin >> row >> col;
            Move move = {row, col};
            if (board.cells[row][col] == Player::None) {
                board.make_move(move, current_player);
                current_player = Player::Computer;
            } else {
                cout << "Invalid move!" << endl;
            }
        } else {
            Move move = get_best_move(board);
            board.make_move(move, current_player);
            current_player = Player::Human;
            cout << "Computer's move:" << endl;
        }
        board.print();
    }

    if (board.is_winner(Player::Human)) {
        cout << "You win!" << endl;
    } else if (board.is_winner(Player::Computer)) {
        cout << "Computer wins!" << endl;
    } else {
        cout << "Tie!" << endl;
    }

    return 0;
}