Untitled
unknown
plain_text
a year ago
13 kB
3
Indexable
Never
#pragma once #include <vector> #include <array> #include <bitset> #include <vector> #include <ctime> #include <cmath> #include <array> #include <bitset> #include <algorithm> #include <iostream> #include <fstream> #include <limits.h> #include <cstdlib> #include <fstream> using namespace std; //#include "../config.hpp" #define max(a,b) ((a>b)?a:b) #define min(a,b) ((a<b)?a:b) #define MINF -2147483647 #define INF 2147483647 #define SIZE 15 enum SPOT_STATE { EMPTY = 0, BLACK = 1, WHITE = 2 }; enum GAME_STATE { UNKNOWN, LOSE, DRAW, NONE }; struct Point { int x, y; Point() : Point(0, 0) {} Point(float x, float y) : x(x), y(y) {} bool operator==(const Point& rhs) const { return x == rhs.x && y == rhs.y; } bool operator!=(const Point& rhs) const { return !operator==(rhs); } Point operator+(const Point& rhs) const { return Point(x + rhs.x, y + rhs.y); } Point operator-(const Point& rhs) const { return Point(x - rhs.x, y - rhs.y); } }; //use bitset to build board typedef std::bitset<SIZE> Row; typedef std::array<Row, SIZE> Board_Min; typedef std::array<Board_Min, 3> Board; extern std::vector<Point> move_list; extern void move_list_init(); const int ROUND[8][2] = { {1,0}, {-1,0}, {0,1}, {0,-1}, {1,1}, {-1,1}, {1,-1}, {-1,-1}, }; class State{ private: Board board; int player; GAME_STATE res = UNKNOWN; void get_legal_actions(void); public: std::vector<Point> legal_actions; State(){}; State(Board board, int player); State* next_state(Point move); GAME_STATE check_res(); int eval(); }; #pragma once //#include "../state/state.hpp" template<class Iter> inline size_t argmax(Iter first, Iter last); class MiniMax{ public: static int eval(State *state, int depth); static Point get_move(State *state, int depth); }; #include <ctime> #include <cmath> //#include "minimax.hpp" template<class Iter> inline size_t argmax(Iter first, Iter last){ return std::distance(first, std::max_element(first, last)); } //Evaluate state with MiniMax int MiniMax::eval(State *state, int depth){ GAME_STATE now_res = state->check_res(); if(now_res == LOSE){ delete state; return MINF; } if(now_res==DRAW){ delete state; return 0; } if(depth==0){ int score = state->eval(); delete state; return score; } int best = MINF; for(auto move: state->legal_actions){ //negative max int score = -eval(state->next_state(move), depth-1); if (score>best) best = score; } delete state; return best; }; //Run MiniMax and get best move Point MiniMax::get_move(State *state, int depth){ Point best_action = Point(-1, -1); int best_score = MINF; for(Point move: state->legal_actions){ int score = -eval(state->next_state(move), depth-1); if(score>best_score){ best_action = move; best_score = score; } } return best_action; }; #include <vector> #include <array> #include <bitset> #include <algorithm> //#include "state.hpp" std::vector<Point> move_list; // get all the point on the board void move_list_init(){ for(int i=0; i<SIZE; ++i) for(int j=0; j<SIZE; ++j) move_list.push_back(Point(i,j)); } // check if 5 discs on a row // use a tircky method to check if n-disc on a row // first use bitset to store the board(empty, pl1, pl2) // // horizontally: xxxxx11111xxxxx >> 5 == xxxxxxxxxx11111 // // vertically: // xx1xxx1xxxxxxxx // xx1xxxxx1xxxxxx // xx1xxxxx1xxxxxx // xx1xxxxxxxxxxxx // xx1xxxxx1xxxxxx // & = xx1xxxxxxxxxxxx // // cross: // xx1xxxxxx xx1xxxxxx // xxx1xxxxx xxx1xxxxx // xxxx1xxxx -> xxxx1xxxx // xxxxx1xxx xxxxx1xxx // xxxxxx1xx xxxxxx1xx static bool check_5(Board_Min board){ for(int i=0; i<SIZE-4; i+=1){ if((board[i] & board[i+1] & board[i+2] & board[i+3] & board[i+4]).any()) return true; if((board[i] & (board[i+1]>>1) & (board[i+2]>>2) & (board[i+3]>>3) & (board[i+4]>>4)).any()) return true; if((board[i] & (board[i+1]<<1) & (board[i+2]<<2) & (board[i+3]<<3) & (board[i+4]<<4)).any()) return true; for(int j=0; j<SIZE; j+=1){ if(((board[j]>>i)&=0b11111) == 0b11111) return true; } } return false; } static bool check_4(Board_Min board, Board_Min avail){ for(int i=0; i<SIZE-4; i+=1){ if((avail[i] & board[i+1] & board[i+2] & board[i+3] & board[i+4]).any()) return true; if((board[i] & board[i+1] & board[i+2] & board[i+3] & avail[i+4]).any()) return true; if((avail[i] & (board[i+1]>>1) & (board[i+2]>>2) & (board[i+3]>>3) & (board[i+4]>>4)).any()) return true; if((board[i] & (board[i+1]>>1) & (board[i+2]>>2) & (board[i+3]>>3) & (avail[i+4]>>4)).any()) return true; if((avail[i] & (board[i+1]<<1) & (board[i+2]<<2) & (board[i+3]<<3) & (board[i+4]<<4)).any()) return true; if((board[i] & (board[i+1]<<1) & (board[i+2]<<2) & (board[i+3]<<3) & (avail[i+4]<<4)).any()) return true; for(int j=0; j<SIZE; j+=1){ if( ((board[j]>>i)&=0b11110) == 0b11110 && ((avail[j]>>i)&=0b00001) == 0b00001 )return true; if( ((board[j]>>i)&=0b01111) == 0b01111 && ((avail[j]>>i)&=0b10000) == 0b10000 )return true; } } return false; } static int count_4(Board_Min board, Board_Min avail){ int res = 0; for(int i=0; i<SIZE-4; i+=1){ res += ( avail[i] & board[i+1] & board[i+2] & board[i+3] & board[i+4] ).count(); res += ( board[i] & board[i+1] & board[i+2] & board[i+3] & avail[i+4] ).count(); res += (avail[i] & (board[i+1]>>1) & (board[i+2]>>2) & (board[i+3]>>3) & (board[i+4]>>4)).count(); res += (board[i] & (board[i+1]>>1) & (board[i+2]>>2) & (board[i+3]>>3) & (avail[i+4]>>4)).count(); res += (avail[i] & (board[i+1]<<1) & (board[i+2]<<2) & (board[i+3]<<3) & (board[i+4]<<4)).count(); res += (board[i] & (board[i+1]<<1) & (board[i+2]<<2) & (board[i+3]<<3) & (avail[i+4]<<4)).count(); for(int j=0; j<SIZE; j+=1){ res += ( ((board[j]>>i)&=0b11110) == 0b11110 && ((avail[j]>>i)&=0b00001) == 0b00001 ); res += ( ((board[j]>>i)&=0b01111) == 0b01111 && ((avail[j]>>i)&=0b10000) == 0b10000 ); } if(res>2) return res; } return res; } static int count_3_op(Board_Min board, Board_Min avail){ int res = 0; for(int i=0; i<SIZE-2; i+=1){ Row avail_check; Row avail_check_d; Row target; // vertically avail_check = avail_check_d = Row(0); target = board[i] & board[i+1] & board[i+2]; if(i>0 && i<SIZE-3) avail_check_d = avail[i-1] & avail[i+3]; if(i>1) avail_check |= avail[i-1] & avail[i-2]; if(i<SIZE-4) avail_check |= avail[i+3] & avail[i+4]; res += (avail_check & target).count(); res += (avail_check_d & target).count(); // cross l-up to r-bottom avail_check = avail_check_d = Row(0); target = board[i] & (board[i+1]>>1) & (board[i+2]>>2); if(i>0 && i<SIZE-3) avail_check_d = (avail[i-1]<<1) & (avail[i+3]>>3); if(i>1) avail_check |= (avail[i-1]<<1) & (avail[i-2]<<2); if(i<SIZE-4) avail_check |= (avail[i+3]>>3) & (avail[i+4]>>4); res += (avail_check & target).count(); res += (avail_check_d & target).count(); // cross r-up to l-bottom avail_check = avail_check_d = Row(0); target = board[i] & (board[i+1]<<1) & (board[i+2]<<2); if(i>0 && i<SIZE-3) avail_check_d = (avail[i-1]>>1) & (avail[i+3]<<3); if(i>1) avail_check |= (avail[i-1]>>1) & (avail[i-2]>>2); if(i<SIZE-4) avail_check |= (avail[i+3]<<3) & (avail[i+4]<<4); res += (avail_check & target).count(); res += (avail_check_d & target).count(); // horizontally for(int j=0; j<SIZE; j+=1){ bool avail_check = false, avail_check_d = false; bool target = (((board[j]>>i)&=0b111) == 0b111); if(i>0 && i<SIZE-3) avail_check_d = avail[j][SIZE-i]&&avail[j][SIZE-i-4]; if(i>1) avail_check |= avail[j][SIZE-i]&&avail[j][SIZE-i+1]; if(i<SIZE-4) avail_check |= avail[j][SIZE-i-4]&&avail[j][SIZE-i-5]; res += (avail_check & target); res += (avail_check_d & target); } } return res; } /* Declaration of State */ State::State(Board board, int player): board(board), player(player){ this->get_legal_actions(); }; //Get legal actions around the existed discs void State::get_legal_actions(void){ std::vector<Point> actions; Board_Min point; bool initial = true; // only use the point that around the disc on the board for(auto p: move_list){ if(board[0][p.x][p.y]==0){ initial = false; for(auto p_off: ROUND){ int x = p.x+p_off[0]; int y = p.y+p_off[1]; if(x<0 || y<0 || x>=SIZE || y>=SIZE || point[x][y] || board[0][x][y]==0) continue; actions.push_back(Point(x, y)); point[x][y] = 1; } } } // initial state(only use the central as legal action) if(actions.empty() && initial) actions.push_back(Point(SIZE/2, SIZE/2)); legal_actions = actions; }; //Get next state with a move State* State::next_state(Point move){ Board new_board = this->board; // place the disc new_board[this->player][move.x][move.y] = 1; new_board[0][move.x][move.y] = 0; // create next state State *next = new State(); next->board = new_board; next->player = 3-player; // get the legal actions for next state Board_Min point; std::vector<Point> actions; for(Point action:legal_actions){ if(action!=move){ actions.push_back(action); point[action.x][action.y] = 1; } } for(auto p_off: ROUND){ int x = move.x+p_off[0]; int y = move.y+p_off[1]; if(x<0 || y<0 || x>=SIZE || y>=SIZE || point[x][y] || board[0][x][y]==0) continue; actions.push_back(Point(x, y)); point[x][y] = 1; } next->legal_actions = actions; return next; } //Check if this game is and or not GAME_STATE State::check_res(){ if (this->res != UNKNOWN) return this->res; Board_Min next = board[3-this->player]; if (check_5(next)){ this->res = LOSE; }else if (this->legal_actions.empty()){ this->res = DRAW; }else{ this->res = NONE; } return this->res; } //The State-Value function of this state int State::eval(){ Board_Min self = board[this->player]; Board_Min avail = board[0]; if(check_5(self) || check_4(self, avail)) return 1000000; Board_Min opnt = board[3-this->player]; if(count_4(opnt, avail)>1) return -1000000; return count_3_op(self, avail)-count_3_op(opnt, avail); } State root; void read_board(std::ifstream& fin) { Board board; int player; fin >> player; for (int i = 0; i < SIZE; i++) { for (int j = 0; j < SIZE; j++) { board[0][i][j] = board[1][i][j] = board[2][i][j] = 0; int temp; fin >> temp; board[temp][i][j] = 1; } } root = State(board, player); } void write_valid_spot(std::ofstream& fout) { auto moves = root.legal_actions; for(auto move:moves){ if(root.next_state(move)->check_res() == LOSE){ fout << move.x << " " << move.y << std::endl; fout.flush(); return; } } if(moves.empty()) return; // Keep updating the output until getting killed. int depth = 1; while (true) { auto move = MiniMax::get_move(&root, depth); if(move.x != -1 && move.y != -1){ fout << move.x << " " << move.y << std::endl; fout.flush(); } depth += 1; } } int main(int, char** argv) { //srand(RANDOM_SEED); std::ifstream fin(argv[1]); std::ofstream fout(argv[2]); move_list_init(); read_board(fin); write_valid_spot(fout); fin.close(); fout.close(); return 0; }