Untitled

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <array>
#include <vector>
#include <map>

enum SPOT_STATE {
    EMPTY = 0,
    BLACK = 1,
    WHITE = 2
};

int player;
const int SIZE = 15;
std::array<std::array<int, SIZE>, SIZE> board;
std::pair<int, int> decision;
std::map<std::pair<int, int>, bool> visited;
std::vector<std::pair<int, int> > moves;  

void read_board(std::ifstream& fin) {
    fin >> player;
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            fin >> board[i][j];
        }
    }
}

double value_function(bool left, int length, bool right) {
    if (!left && !right) return 0;
    if (length == 2) return ((!left || !right) ? 10 : 50);
    if (length == 3) return ((!left || !right) ? 200 : 500);
    if (length == 4) return ((!left || !right) ? 500 : 4800);
    return 6000;
}

double evaluate() {
    int rec[SIZE][SIZE][4][2] = {{{{0}}}}; // Horizontal, Diagonal Left, Vertical, Diagonal Right
    double result[2] = {0};
    for (int i=0; i<SIZE; i++) {
        for (int j=0; j<SIZE; j++) {
            if (board[i][j]) {
                rec[i][j][0][board[i][j]-1] = 1 + (j ? rec[i][j-1][0][board[i][j]-1] : 0);
                rec[i][j][1][board[i][j]-1] = 1 + ((i && j) ? rec[i-1][j-1][1][board[i][j]-1] : 0);
                rec[i][j][2][board[i][j]-1] = 1 + (i ? rec[i-1][j][2][board[i][j]-1] : 0);
                rec[i][j][3][board[i][j]-1] = 1 + ((i && j+1<SIZE) ? rec[i-1][j+1][3][board[i][j]-1] : 0);
            }
        }
    }
    int win = 0;
    for (int i=0; i<SIZE; i++) {
        for (int j=0; j<SIZE; j++) {
            if (board[i][j]) {
                if ((j+1 == SIZE || board[i][j+1] != board[i][j]) && rec[i][j][0][board[i][j]-1] >= 2) {
                    int lg = rec[i][j][0][board[i][j]-1];
                    bool left = (j-lg >= 0 && !board[i][j-lg]), right = (j+1 != SIZE && !board[i][j+1]);
                    result[board[i][j]-1] += value_function(left, lg, right);
                    if (lg == 5) win = board[i][j];
                }
                if ((i+1 == SIZE || j+1 == SIZE || board[i+1][j+1] != board[i][j]) && rec[i][j][1][board[i][j]-1] >= 2) {
                    int lg = rec[i][j][1][board[i][j]-1];
                    bool left = (i-lg >= 0 && j-lg >= 0 && !board[i-lg][j-lg]), right = (i+1 != SIZE && j+1 != SIZE && !board[i+1][j+1]);
                    result[board[i][j]-1] += value_function(left, lg, right);
                    if (lg == 5) win = board[i][j];
                }
                if ((i+1 == SIZE || board[i+1][j] != board[i][j]) && rec[i][j][2][board[i][j]-1] >= 2) {
                    int lg = rec[i][j][2][board[i][j]-1];
                    bool left = (i-lg >= 0 && !board[i-lg][j]), right = (i+1 != SIZE && !board[i+1][j]);
                    result[board[i][j]-1] += value_function(left, lg, right);
                    if (lg == 5) win = board[i][j];
                }
                if ((i+1 == SIZE || !j || board[i+1][j-1] != board[i][j]) && rec[i][j][3][board[i][j]-1] >= 2) {
                    int lg = rec[i][j][3][board[i][j]-1];
                    bool left = (i-lg >= 0 && j+lg < SIZE && !board[i-lg][j+lg]), right = (i+1 < SIZE && j-1 >= 0 && !board[i+1][j-1]);
                    result[board[i][j]-1] += value_function(left, lg, right);
                    if (lg == 5) win = board[i][j];
                }
            }
        }
    }
    if (win) result[win%2] = 0;
    return (player == 1 ? result[0] - result[1] : result[1] - result[0]);
}

bool win_game(int x, int y) {

    // Vertical 5
    int now = 1, nx = x-1, ny = y;
    while (nx >= 0 && board[nx][ny] == board[x][y]) now++, nx--;
    nx = x+1;
    while (nx < SIZE && board[nx][ny] == board[x][y]) now++, nx++;
    if (now >= 5) return true;

    // Horizontal 5
    now = 1, nx = x, ny = y-1;
    while (ny >= 0 && board[nx][ny] == board[x][y]) now++, ny--;
    ny = y+1;
    while (ny < SIZE && board[nx][ny] == board[x][y]) now++, ny++;
    if (now >= 5) return true;

    // Diagonal Left 5
    now = 1, nx = x-1, ny = y-1;
    while (nx >= 0 && ny >= 0 && board[nx][ny] == board[x][y]) now++, nx--, ny--;
    nx = x+1, ny = y+1;
    while (nx < SIZE && ny < SIZE && board[nx][ny] == board[x][y]) now++, nx++, ny++;
    if (now >= 5) return true;

    // Diagonal Right 5
    now = 1, nx = x-1, ny = y+1;
    while (nx >= 0 && ny < SIZE && board[nx][ny] == board[x][y]) now++, nx--, ny++;
    nx = x+1, ny = y-1;
    while (nx < SIZE && ny >= 0 && board[nx][ny] == board[x][y]) now++, nx++, ny--;
    if (now >= 5) return true;

    return false;
}



double dfs(int depth, double alpha, double beta, bool maximize) {
    double value = (maximize ? -1e9 : 1e9);
    bool cutoff = false;
    int sz = moves.size();
    for (int i=0; i<sz; i++) {
        int x = moves[i].first, y = moves[i].second;
        if (board[x][y]) continue;
        board[x][y] = (maximize ? player : player%2+1);
        if (win_game(x, y)) depth = 0;
        for (int nx=std::max(0, x-1); nx<=std::min(SIZE-1, x+1); nx++) {
            for (int ny=std::max(0, y-1); ny<=std::min(SIZE-1, y+1); ny++) {
                if (!board[nx][ny] && !visited[{nx, ny}]) {
                    moves.push_back({nx, ny});
                    visited[{nx, ny}] = true;
                }
            }
        }
        if (maximize) {
            value = std::max(value, (!depth ? evaluate() : dfs(depth-1, alpha, beta, !maximize)));
            alpha = std::max(alpha, value);
            if (alpha >= beta) cutoff = true;
        } else {
            value = std::min(value, (!depth ? evaluate() : dfs(depth-1, alpha, beta, !maximize)));
            beta = std::min(beta, value);
            if (beta <= alpha) cutoff = true;
        }
        board[x][y] = 0;
        if (cutoff) break;
    }
    while (int(moves.size()) > sz) {
        visited[{moves[moves.size()-1].first, moves[moves.size()-1].second}] = false;
        moves.pop_back();
    }
    return value;
}

void alpha_beta(std::ofstream& fout) {

    visited.clear(), moves.clear();
    for (int i=0; i<SIZE; i++) {
        for (int j=0; j<SIZE; j++) {
            if (board[i][j]) {
                // Search range
                for (int nx=std::max(0, i-1); nx<=std::min(SIZE-1, i+1); nx++) {
                    for (int ny=std::max(0, j-1); ny<=std::min(SIZE-1, j+1); ny++) {
                        if (!board[nx][ny]) visited[{nx, ny}] = true;
                    }
                }
            }
        }
    }

    for (auto i: visited) moves.push_back(i.first);
    if (!moves.size()) moves.push_back({7, 7});

    // We win in one step
    for (auto p: moves) {
        int x = p.first, y = p.second;
        board[x][y] = player;
        if (win_game(x, y)) {
            decision = {x, y};
            return;
        }
        board[x][y] = 0;
    }
    
    // They win in one step
    for (auto p: moves) {
        int x = p.first, y = p.second;
        board[x][y] = player%2+1;
        if (win_game(x, y)) {
            decision = {x, y};
            return;
        }
        board[x][y] = 0;
    }

    // Tree search
    double value = -1e9, tmp;
    int sz = moves.size();
    for (int i=0; i<sz; i++) {
        int x = moves[i].first, y = moves[i].second;
        board[x][y] = player;
        tmp = dfs(2, -1e9, 1e9, false);
        if (tmp >= value) {
            value = tmp;
            decision = {x, y};
            fout << x << " " << y << std::endl;
        }
        board[x][y] = 0;
    }
}

void write_valid_spot(std::ofstream& fout) {
    alpha_beta(fout);
    fout << decision.first << " " << decision.second << std::endl;
    fout.flush();
}

int main(int, char** argv) {
    std::srand(time(0));
    std::ifstream fin(argv[1]);
    std::ofstream fout(argv[2]);
    read_board(fin);
    write_valid_spot(fout);
    fin.close();
    fout.close();
    return 0;
}