#include<bits/stdc++.h>
#define int long long
#define INF 9223372036854775807
#define TIE 9223372036854775806
#define REPLR(i) for(long long i=LEFT;i<RIGHT;i++)
using namespace std;

const int LIMIT = 10;
const int DEPTH = 3;

const int COMPUTER = 1;
const int PLAYER = 2;
const int EMPTY = 0;
const int BOARDER = 3;

const int SIZE = 15;
const int BOARDSIZE = SIZE + 15;
const int LEFT = 10, RIGHT = LEFT + SIZE;
const int CENTER = LEFT + RIGHT >> 1;

int board[BOARDSIZE][BOARDSIZE];

void initialize(){
    for(int i=0;i<BOARDSIZE;i++)
        for(int j=0;j<BOARDSIZE;j++)
            board[i][j]=BOARDER;
    REPLR(i) REPLR(j) board[i][j]=EMPTY;
}

void showBoard(){
    cout << "   ";
    REPLR(i) cout << setw(2) << char(i-LEFT+'A');
    cout << endl;
    REPLR(j){
        cout << setw(3) << j-LEFT+1 << ' ';
        REPLR(i){
            if(board[i][j] == EMPTY)
                cout << "- ";
            if(board[i][j] == COMPUTER)
                cout << "O ";
            if(board[i][j] == PLAYER)
                cout << "X ";
        }
        cout << endl;
    }
    cout << endl;
}

vector<int> countPattern(int x,int y,int dx,int dy){
    vector<int> cnt = {0,0,0,0};
    for(int i=0;i<5;i++){
        cnt[board[x+i*dx][y+i*dy]]++;
    }
    int maxlen = 0, len = 0;
    for(int i=0;i<5;i++){
        if(board[x+i*dx][y+i*dy] == COMPUTER)
            maxlen = max(maxlen, ++len);
        else len = 0;
    }
    cnt[COMPUTER] = maxlen;
    for(int i=0;i<5;i++){
        if(board[x+i*dx][y+i*dy] == PLAYER)
            maxlen = max(maxlen, ++len);
        else len = 0;
    }
    cnt[PLAYER] = maxlen;
    return cnt;
}

int evaluate(){
    vector<pair<int,int>> patterns = {{0,1},{1,0},{1,1},{1,-1}};
    int score = 0;
    int TIMES = 0;
    REPLR(i)
        REPLR(j)
            for(auto pattern: patterns){
                vector<int> cnt = countPattern(i,j,pattern.first,pattern.second);
                if(cnt[BOARDER] || cnt[EMPTY] == 5 || (cnt[PLAYER] && cnt[COMPUTER]))
                    continue;
                else TIMES++;
                if(!cnt[PLAYER]){
                    score += pow(50, 2*cnt[COMPUTER]-1);
                    if(cnt[COMPUTER] == 5) return INF;
                }
                else if(!cnt[COMPUTER]){
                    score -= pow(50, 2*cnt[PLAYER]);
                    if(cnt[PLAYER] == 5) return -INF;
                }
            }
    if(!TIMES) return TIE;
    return score + rand()%2500;
}

int playersTurn(){
    showBoard();
    char row;
    int col;
    do{
        cout << "INSERT THE LOCATION: ";
        cin >> row >> col;
        row = toupper(row);
        --col;
    }while( !('A' <= row && row < 'A'+SIZE && 0 <= col && col < SIZE
              && board[row-'A'+LEFT][col+LEFT] == EMPTY ) );
    board[row-'A'+LEFT][col+LEFT] = PLAYER;
    int result = evaluate();
    if(result == -INF) return PLAYER;
    else if(result == TIE) return BOARDER;
    return EMPTY;
}

pair<int,pair<int,int>> minimax(int depth,int alpha,int beta,bool ismaximizing){
    pair<int,int> moves = {0,0};
    int staticEval = evaluate();
    if(!depth || staticEval == INF || staticEval == -INF) return {staticEval,moves};
    if(staticEval == TIE) return {0,moves};

    if(ismaximizing){
        vector<pair<int,pair<int,int>>> scores;
        REPLR(i) REPLR(j) if(board[i][j] == EMPTY){
            board[i][j] = COMPUTER;
            int result = evaluate();
            scores.push_back({result,{i,j}});
            board[i][j] = EMPTY;
        }
        sort(scores.begin(),scores.end(),greater<pair<int,pair<int,int>>>());
        int maxEval = -INF;
        bool purn = false;
        int counter = 0;
        for(auto position: scores){
        if(++counter >= LIMIT) break;
        int i = position.second.first;
        int j = position.second.second;
            if(!purn && board[i][j] == EMPTY){
                board[i][j] = COMPUTER;
                int eval = minimax(depth-1, alpha, beta, false).first;
                if(eval > maxEval){
                    maxEval = max(maxEval, eval);
                    moves = {i,j};
                }
                alpha = max(alpha, eval);
                if(beta <= alpha) purn = true;
                board[i][j] = EMPTY;
            }
        }
        return {maxEval,moves};
    }
    else{
        vector<pair<int,pair<int,int>>> scores;
        REPLR(i) REPLR(j) if(board[i][j] == EMPTY){
            board[i][j] = PLAYER;
            int result = evaluate();
            scores.push_back({result,{i,j}});
            board[i][j] = EMPTY;
        }
        sort(scores.begin(),scores.end());
        int minEval = INF;
        bool purn = false;
        int counter = 0;
        for(auto position: scores){
        if(++counter >= LIMIT) break;
        int i = position.second.first;
        int j = position.second.second;
            if(!purn && board[i][j] == EMPTY){
                board[i][j] = PLAYER;
                int eval = minimax(depth-1, alpha, beta, false).first;
                if(eval < minEval){
                    minEval = min(minEval, eval);
                    moves = {i,j};
                }
                alpha = min(alpha, eval);
                if(beta <= alpha) purn = true;
                board[i][j] = EMPTY;
            }
        }
        return {minEval,moves};
    }
}

int computersTurn(){
    auto res = minimax(DEPTH, -INF, INF, false);
    int nextx = res.second.first;
    int nexty = res.second.second;
    board[nextx][nexty] = COMPUTER;
    system("cls");
    cout << "     COMPUTER: " << char(nextx-LEFT+'A') << nexty-LEFT+1 << endl << endl;
    int result = evaluate();
    if(result == INF) return COMPUTER;
    else if(result == TIE) return BOARDER;
    return EMPTY;
}

signed main(){
    srand(time(0));
    initialize();
    int winner = EMPTY;
    board[CENTER][CENTER] = COMPUTER;
    while(winner == EMPTY){
        winner = playersTurn();
        if(winner != EMPTY) break;
        winner = computersTurn();
    }
    system("cls");
    showBoard();
    cout << "WINNER: ";
    if(winner == PLAYER) cout << "PLAYER\n";
    if(winner == COMPUTER) cout << "COMPUTER\n";
    if(winner == BOARDER) cout << "TIE!\n";
}