Untitled
unknown
c_cpp
2 years ago
8.1 kB
6
Indexable
#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; }
Editor is loading...