Untitled

#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;
}