# 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;
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();