人机大战超级井字棋

#include <iostream>
#include <vector>
#include <tuple>
#include <limits>
#include <algorithm>

using namespace std;

class UltimateBoard {
public:
    struct SmallBoard {
        char cells[3][3];
        bool is_won;
        char winner;

        SmallBoard() : is_won(false), winner('.') {
            for(int i=0; i<3; i++)
                for(int j=0; j<3; j++)
                    cells[i][j] = '.';
        }
    };

    SmallBoard boards[3][3];
    int current_board_row;
    int current_board_col;
    char current_player;
    bool game_over;
    char ultimate_winner;

    UltimateBoard() : current_board_row(-1), current_board_col(-1),
                     current_player('X'), game_over(false), ultimate_winner('.') {}

    UltimateBoard(const UltimateBoard& other) {
        for(int i=0; i<3; i++)
            for(int j=0; j<3; j++)
                boards[i][j] = other.boards[i][j];
        
        current_board_row = other.current_board_row;
        current_board_col = other.current_board_col;
        current_player = other.current_player;
        game_over = other.game_over;
        ultimate_winner = other.ultimate_winner;
    }

    bool is_small_board_full(const SmallBoard& sb) const {
        for(int i=0; i<3; i++)
            for(int j=0; j<3; j++)
                if(sb.cells[i][j] == '.') return false;
        return true;
    }

    bool check_small_win(SmallBoard& sb, char player) {
        // Check rows
        for(int i=0; i<3; i++)
            if(sb.cells[i][0] == player && sb.cells[i][1] == player && sb.cells[i][2] == player)
                return true;

        // Check columns
        for(int j=0; j<3; j++)
            if(sb.cells[0][j] == player && sb.cells[1][j] == player && sb.cells[2][j] == player)
                return true;

        // Check diagonals
        if(sb.cells[0][0] == player && sb.cells[1][1] == player && sb.cells[2][2] == player)
            return true;
        if(sb.cells[0][2] == player && sb.cells[1][1] == player && sb.cells[2][0] == player)
            return true;

        return false;
    }

    void check_ultimate_win() {
        // Check rows
        for(int i=0; i<3; i++)
            if(boards[i][0].winner != '.' && boards[i][0].winner == boards[i][1].winner && 
               boards[i][1].winner == boards[i][2].winner) {
                game_over = true;
                ultimate_winner = boards[i][0].winner;
                return;
            }

        // Check columns
        for(int j=0; j<3; j++)
            if(boards[0][j].winner != '.' && boards[0][j].winner == boards[1][j].winner && 
               boards[1][j].winner == boards[2][j].winner) {
                game_over = true;
                ultimate_winner = boards[0][j].winner;
                return;
            }

        // Check diagonals
        if(boards[0][0].winner != '.' && boards[0][0].winner == boards[1][1].winner && 
           boards[1][1].winner == boards[2][2].winner) {
            game_over = true;
            ultimate_winner = boards[0][0].winner;
            return;
        }

        if(boards[0][2].winner != '.' && boards[0][2].winner == boards[1][1].winner && 
           boards[1][1].winner == boards[2][0].winner) {
            game_over = true;
            ultimate_winner = boards[0][2].winner;
            return;
        }

        // Check for full board
        bool all_full = true;
        for(int i=0; i<3; i++)
            for(int j=0; j<3; j++)
                if(!is_small_board_full(boards[i][j]) && !boards[i][j].is_won)
                    all_full = false;

        if(all_full) {
            game_over = true;
            ultimate_winner = '.';
        }
    }

    bool make_move(int board_row, int board_col, int cell_row, int cell_col) {
        if(game_over) return false;

        // Check if we're supposed to be in a specific board
        if(current_board_row != -1 && (board_row != current_board_row || board_col != current_board_col))
            return false;

        SmallBoard& target_board = boards[board_row][board_col];
        if(target_board.is_won || target_board.cells[cell_row][cell_col] != '.')
            return false;

        // Make the move
        target_board.cells[cell_row][cell_col] = current_player;

        // Check small board win
        if(check_small_win(target_board, current_player)) {
            target_board.is_won = true;
            target_board.winner = current_player;
        }

        // Update next target board
        current_board_row = cell_row;
        current_board_col = cell_col;

        // If next target board is already won or full, reset to any board
        if(boards[current_board_row][current_board_col].is_won || 
           is_small_board_full(boards[current_board_row][current_board_col])) {
            current_board_row = -1;
            current_board_col = -1;
        }

        // Check ultimate win
        check_ultimate_win();

        // Switch players
        current_player = (current_player == 'X') ? 'O' : 'X';
        return true;
    }

    vector<tuple<int, int, int, int>> get_legal_moves() const {
        vector<tuple<int, int, int, int>> moves;

        // Get target boards
        vector<pair<int, int>> target_boards;
        if(current_board_row == -1) {
            // All boards that are not won and not full
            for(int i=0; i<3; i++)
                for(int j=0; j<3; j++)
                    if(!boards[i][j].is_won && !is_small_board_full(boards[i][j]))
                        target_boards.emplace_back(i, j);
        } else {
            if(!boards[current_board_row][current_board_col].is_won && 
               !is_small_board_full(boards[current_board_row][current_board_col])) {
                target_boards.emplace_back(current_board_row, current_board_col);
            } else {
                // If target board is invalid, any available board
                for(int i=0; i<3; i++)
                    for(int j=0; j<3; j++)
                        if(!boards[i][j].is_won && !is_small_board_full(boards[i][j]))
                            target_boards.emplace_back(i, j);
            }
        }

        // Collect all legal moves
        for(auto& tb : target_boards) {
            int br = tb.first, bc = tb.second;
            for(int cr=0; cr<3; cr++)
                for(int cc=0; cc<3; cc++)
                    if(boards[br][bc].cells[cr][cc] == '.')
                        moves.emplace_back(br, bc, cr, cc);
        }

        return moves;
    }

    void print_board() const {
        cout << "Current player: " << current_player << endl;
        for(int big_row=0; big_row<3; big_row++) {
            for(int small_row=0; small_row<3; small_row++) {
                for(int big_col=0; big_col<3; big_col++) {
                    const SmallBoard& sb = boards[big_row][big_col];
                    cout << " ";
                    for(int small_col=0; small_col<3; small_col++) {
                        cout << sb.cells[small_row][small_col];
                        if(small_col < 2) cout << " ";
                    }
                    cout << " ";
                    if(big_col < 2) cout << " ";
                }
                cout << endl;
            }
            if(big_row < 2) {
                cout << endl;
            }
        }
    }
};

class AI {
    int max_depth;

public:
    AI(int depth) : max_depth(depth) {}

    tuple<int, int, int, int> get_best_move(const UltimateBoard& board) {
        int best_value = numeric_limits<int>::min();
        tuple<int, int, int, int> best_move = make_tuple(-1, -1, -1, -1);
        
        for(auto move : board.get_legal_moves()) {
            UltimateBoard new_board(board);
            int br, bc, cr, cc;
            tie(br, bc, cr, cc) = move;
            new_board.make_move(br, bc, cr, cc);
            
            int value = minimax(new_board, max_depth-1, false, 
                               numeric_limits<int>::min(), numeric_limits<int>::max());
            
            if(value > best_value) {
                best_value = value;
                best_move = move;
            }
        }
        return best_move;
    }

private:
    int evaluate(const UltimateBoard& board) {
        int score = 0;
        
        // Evaluate small board wins
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                if(board.boards[i][j].winner == 'O') score += 100;
                else if(board.boards[i][j].winner == 'X') score -= 100;
            }
        }

        // Ultimate win check
        if(board.ultimate_winner == 'O') return 1000;
        if(board.ultimate_winner == 'X') return -1000;
        
        return score;
    }

    int minimax(UltimateBoard& board, int depth, bool maximizing, int alpha, int beta) {
        if(depth == 0 || board.game_over)
            return evaluate(board);

        auto moves = board.get_legal_moves();
        if(maximizing) {
            int max_eval = numeric_limits<int>::min();
            for(auto& move : moves) {
                UltimateBoard new_board(board);
                int br, bc, cr, cc;
                tie(br, bc, cr, cc) = move;
                new_board.make_move(br, bc, cr, cc);
                
                int eval = minimax(new_board, depth-1, false, alpha, beta);
                max_eval = max(max_eval, eval);
                alpha = max(alpha, eval);
                if(beta <= alpha)
                    break;
            }
            return max_eval;
        } else {
            int min_eval = numeric_limits<int>::max();
            for(auto& move : moves) {
                UltimateBoard new_board(board);
                int br, bc, cr, cc;
                tie(br, bc, cr, cc) = move;
                new_board.make_move(br, bc, cr, cc);
                
                int eval = minimax(new_board, depth-1, true, alpha, beta);
                min_eval = min(min_eval, eval);
                beta = min(beta, eval);
                if(beta <= alpha)
                    break;
            }
            return min_eval;
        }
    }
};

int main() {
    UltimateBoard game;
    AI ai(3); // Search depth of 3

    while(!game.game_over) {
        game.print_board();
        
        if(game.current_player == 'X') {
            int br, bc, cr, cc;
            cout << "Enter move (big_row big_col cell_row cell_col): ";
            cin >> br >> bc >> cr >> cc;
            
            if(!game.make_move(br, bc, cr, cc))
                cout << "Invalid move!" << endl;
        } else {
            auto move = ai.get_best_move(game);
            int br, bc, cr, cc;
            tie(br, bc, cr, cc) = move;
            game.make_move(br, bc, cr, cc);
            cout << "AI played at (" << br << "," << bc << ") (" << cr << "," << cc << ")" << endl;
        }
    }

    game.print_board();
    if(game.ultimate_winner != '.')
        cout << "Player " << game.ultimate_winner << " wins!" << endl;
    else
        cout << "It's a draw!" << endl;

    return 0;
}