#pragma once
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cassert>
using namespace std;

int abss(int a) {
	if (a < 0) return -a;
	else return a;
}

long long getmin(int a, int b) {
	if (a < b) return a;
	else return b;
}

long long getmax(int a, int b) {
	if (a > b) return a;
	else return b;
}


//博弈树返回内容
struct node
{
	//阿尔法
	long long a;
	//贝塔
	long long b;
	//节点值
	long long point;
	node() {
		a = point = INT_MIN;
		b = INT_MAX;
	}
};

//棋盘大小
const int clen = 15;
class thinker {
private:
	//电脑棋子颜色
	const int AIcolor = 1;
	//玩家棋子颜色
	const int Player = 2;
	

	
	//棋盘
	int cboard[clen][clen];
	//越界判断
	bool yuejie(int x, int y)const;


	//五元组情况
	int state[3][clen][clen][4];
	//五元组不同情况的分数
	const long long cpoint[6] = { 0,0,2,1000,100000,INT_MAX };
	//更新五元组
	bool input(int x, int y, int who);
	bool remove(int x, int y);


	//不同情况的棋子排列
	int AIstate[6];
	int Manstate[6];
	//判断该五元组是否已经无效
	bool dead[clen][clen][4];
	//记录无效个数
	int deadnum = 0;

	//获得局面分数
	long long getpoint();
	

	//电脑落子位置
	int nx, ny;
	//搜索深度
	const int tdeep = 3;
	//递归过程
	node AIstep(int deep, const int rpoint, node root);
	node Manstep(int deep, const int rpoint, node root);
	//博弈树入口
	void think();


public:

	thinker() {
		memset(cboard, 0, sizeof(cboard));
		memset(state, 0, sizeof(state));
		memset(AIstate, 0, sizeof(AIstate));
		memset(Manstate, 0, sizeof(Manstate));
		memset(dead, false, sizeof(dead));
	}


	void clear() {
		memset(cboard, 0, sizeof(cboard));
		memset(state, 0, sizeof(state));
		memset(AIstate, 0, sizeof(AIstate));
		memset(Manstate, 0, sizeof(Manstate));
		memset(dead, false, sizeof(dead));
	}


	//用户输入
	void playerinp(int x, int y) {
		input(x,y, Player);
	}

	//获得电脑输入
	void getAIinp(int& x, int& y) {
		think();
		x = nx;
		y = ny;
		input(x, y, AIcolor);
	}


}AIplayer;


void thinker::think() {
	node top;
	top.a--;
	const long long root = getpoint();
	long long noww;
	for (int i = 0; i < clen; i++) {
		for (int j = 0; j < clen; j++) {
			if (input(i, j, AIcolor)) {
				noww = getpoint();
				if (noww != root) {
					node next = Manstep(tdeep, noww, top);
					if (top.a < next.point) {
						nx = i;
						ny = j;
						top.a = next.point;
						top.point = next.point;
					}
				}
				remove(i, j);
			}

		}
	}
}


node thinker::Manstep(int deep, const int rpoint, node root) {
	if (deep == 0) {
		root.point = rpoint;
		root.a = root.point;
		root.b = root.point;
		return root;
	}

	//游戏已经结束，一方获胜了
	if (rpoint == INT_MAX || rpoint == INT_MIN) {
		root.point = rpoint;
		root.a = root.point;
		root.b = root.point;
		return root;
	}


	//当前局面分
	long long tpoint;
	//操作者
	int op = Player;

	for (int i = 0; i < clen; i++) {
		for (int j = 0; j < clen; j++) {

			if (input(i, j, op)) {
				tpoint = getpoint();
				if (tpoint != rpoint) {
					node temp = AIstep(deep - 1, tpoint, root);
					int tempmin = getmin(tpoint, getmin(temp.a, temp.b));
					if (tempmin < root.b) {
						root.b = tempmin;
						root.point = tempmin;
					}
				}
				remove(i, j);
			}
			if (getpoint() != rpoint) {
				cout << "Manstep error:" << deep << " " << getpoint() << "\n";
				exit(100);
			}
			

			if (root.a >= root.b) break;
		}
		if (root.a >= root.b) break;
	}

	return root;
}


node thinker::AIstep(int deep, const int rpoint, node root) {
	if (deep == 0) {
		root.point = rpoint;
		root.a = root.point;
		root.b = root.point;
		return root;
	}

	//游戏已经结束，一方获胜了
	if (rpoint == INT_MAX || rpoint == INT_MIN) {
		root.point = rpoint;
		root.a = root.point;
		root.b = root.point;
		return root;
	}


	//当前局面分
	long long tpoint;
	//操作者
	int op = AIcolor;

	for (int i = 0; i < clen; i++) {
		for (int j = 0; j < clen; j++) {
			if (input(i, j, op)) {
				tpoint = getpoint();
				if (tpoint != rpoint) {
					node temp = Manstep(deep - 1, tpoint, root);
					int tempmax = getmax(tpoint, getmax(temp.a, temp.b));
					if (tempmax > root.a) {
						root.a = tempmax;
						root.point = tempmax;
					}
				}
				remove(i, j);
			}
			if (getpoint() != rpoint) {
				cout << "AIstep error:\n";
				exit(120);
			}

			if (root.a >= root.b) break;
		}
		if (root.a >= root.b) break;
	}

	return root;
}



bool thinker::yuejie(int x, int y)const
{
	if (x < 0 || x>=clen || y < 0 || y>=clen) return true;
	return false;
}




bool thinker::input(int x, int y, int who) {
	if (cboard[x][y] != 0) {
		return false;
	}
	cboard[x][y] = who;


	int other = who % 2 + 1;

	for (int i = 0; i < 5; i++) {
		if (!yuejie(x - i, y)) {
			//如果该点在该方向上没有被标记为死点 并且 该点在该方向上有对方的棋子
			if (!dead[x - i][y][0] && state[other][x - i][y][0] != 0) {
				//标记为死点
				dead[x - i][y][0] = true;
				deadnum++;

				//维护计分数组， 将对方的记录清除
				if (other == AIcolor) {
					AIstate[state[other][x - i][y][0]]--;
				}
				else {
					Manstate[state[other][x - i][y][0]]--;
				}

				//更新五元组状态
				state[who][x - i][y][0]++;
			}
			else if (!dead[x - i][y][0]) {
				//不是死点，维护计分数组，将自己的记录清除
				if (who == AIcolor) {
					AIstate[state[who][x - i][y][0]]--;
				}
				else {
					Manstate[state[who][x - i][y][0]]--;
				}
				//更新五元组状态
				state[who][x - i][y][0]++;
				//维护计分数组，添加记录
				if (who == AIcolor) {
					AIstate[state[who][x - i][y][0]]++;
				}
				else {
					Manstate[state[who][x - i][y][0]]++;
				}
			}
			else {
				//更新五元组状态
				state[who][x - i][y][0]++;
			}
		
		}
		if (!yuejie(x, y - i)) {

			//如果该点在该方向上没有被标记为死点 并且 该点在该方向上有对方的棋子
			if (!dead[x][y - i][1] && state[other][x][y - i][1] != 0) {
				//标记为死点
				dead[x][y - i][1] = true;
				deadnum++;
				//维护计分数组， 将对方的记录清除
				if (other == AIcolor) {
					AIstate[state[other][x][y - i][1]]--;
				}
				else {
					Manstate[state[other][x][y - i][1]]--;
				}
				//更新五元组状态
				state[who][x][y - i][1]++;
			}
			else if (!dead[x][y - i][1]) {
				//不是死点，维护计分数组，将自己的记录清除
				if (who == AIcolor) {
					AIstate[state[who][x][y - i][1]]--;
				}
				else {
					Manstate[state[who][x][y - i][1]]--;
				}
				//更新五元组状态
				state[who][x][y - i][1]++;
				//维护计分数组，添加记录
				if (who == AIcolor) {
					AIstate[state[who][x][y - i][1]]++;
				}
				else {
					Manstate[state[who][x][y - i][1]]++;
				}
			}
			else {
				//更新五元组状态
				state[who][x][y - i][1]++;
			}
		}
		if (!yuejie(x - i, y - i)) {
			//如果该点在该方向上没有被标记为死点 并且 该点在该方向上有对方的棋子
			if (!dead[x - i][y - i][2] && state[other][x - i][y - i][2] != 0) {
				//标记为死点
				dead[x - i][y - i][2] = true;
				deadnum++;
				//维护计分数组， 将对方的记录清除
				if (other == AIcolor) {
					AIstate[state[other][x - i][y - i][2]]--;
				}
				else {
					Manstate[state[other][x - i][y - i][2]]--;
				}
				//更新五元组状态
				state[who][x - i][y - i][2]++;
			}
			else if (!dead[x - i][y - i][2]) {
				//不是死点，维护计分数组，将自己的记录清除
				if (who == AIcolor) {
					AIstate[state[who][x - i][y - i][2]]--;
				}
				else {
					Manstate[state[who][x - i][y - i][2]]--;
				}
				//更新五元组状态
				state[who][x - i][y - i][2]++;
				//维护计分数组，添加记录
				if (who == AIcolor) {
					AIstate[state[who][x - i][y - i][2]]++;
				}
				else {
					Manstate[state[who][x - i][y - i][2]]++;
				}
			}
			else {
				//更新五元组状态
				state[who][x - i][y - i][2]++;
			}
		}
		if (!yuejie(x - i, y + i)) {
			//如果该点在该方向上没有被标记为死点 并且 该点在该方向上有对方的棋子
			if (!dead[x - i][y + i][3] && state[other][x - i][y + i][3] != 0) {
				//标记为死点
				dead[x - i][y + i][3] = true;
				deadnum++;
				//维护计分数组， 将对方的记录清除
				if (other == AIcolor) {
					AIstate[state[other][x - i][y + i][3]]--;
				}
				else {
					Manstate[state[other][x - i][y + i][3]]--;
				}
				//更新五元组状态
				state[who][x - i][y + i][3]++;
			}
			else if (!dead[x - i][y + i][3]) {
				//不是死点，维护计分数组，将自己的记录清除
				if (who == AIcolor) {
					AIstate[state[who][x - i][y + i][3]]--;
				}
				else {
					Manstate[state[who][x - i][y + i][3]]--;
				}
				//更新五元组状态
				state[who][x - i][y + i][3]++;
				//维护计分数组，添加记录
				if (who == AIcolor) {
					AIstate[state[who][x - i][y + i][3]]++;
				}
				else {
					Manstate[state[who][x - i][y + i][3]]++;
				}
			}
			else {
				//更新五元组状态
				state[who][x - i][y + i][3]++;
			}
		}
	}
	return true;
}

bool thinker::remove(int x, int y){
	if (cboard[x][y] == 0) {
		exit(1);
		return false;
	}
	int who = cboard[x][y];
	int other = who % 2 + 1;
	cboard[x][y] = 0;
	for (int i = 0; i < 5; i++) {
		if (!yuejie(x - i, y)) {
			if (!dead[x - i][y][0]) {
				//不是死点，维护计分数组，将自己的记录清除
				if (who == AIcolor) {
					AIstate[state[who][x - i][y][0]]--;
				}
				else {
					Manstate[state[who][x - i][y][0]]--;
				}
				//更新五元组状态
				state[who][x - i][y][0]--;
				//维护计分数组，添加记录
				if (who == AIcolor) {
					AIstate[state[who][x - i][y][0]]++;
				}
				else {
					Manstate[state[who][x - i][y][0]]++;
				}
			}
			else {
				//更新五元组状态
				state[who][x - i][y][0]--;
				//检查死点是否解除
				if (state[who][x - i][y][0] == 0) {
					//解除死点
					dead[x - i][y][0] = 0;
					deadnum--;
					if (other == AIcolor) {
						AIstate[state[other][x - i][y][0]]++;
					}
					else {
						Manstate[state[other][x - i][y][0]]++;
					}

				}

			}
		}
		if (!yuejie(x, y - i)) {
			if (!dead[x][y - i][1]) {
				//不是死点，维护计分数组，将自己的记录清除
				if (who == AIcolor) {
					AIstate[state[who][x][y - i][1]]--;
				}
				else {
					Manstate[state[who][x][y - i][1]]--;
				}
				//更新五元组状态
				state[who][x][y - i][1]--;
				//维护计分数组，添加记录
				if (who == AIcolor) {
					AIstate[state[who][x][y - i][1]]++;
				}
				else {
					Manstate[state[who][x][y - i][1]]++;
				}
			}
			else {

				//更新五元组状态
				state[who][x][y - i][1]--;
				//检查死点是否解除
				if (state[who][x][y - i][1] == 0) {
					//解除死点
					dead[x][y - i][1] = 0;
					deadnum--;
					if (other == AIcolor) {
						AIstate[state[other][x][y - i][1]]++;
					}
					else {
						Manstate[state[other][x][y - i][1]]++;
					}
				}

			}
		}
		if (!yuejie(x - i, y - i)) {

			if (!dead[x - i][y - i][2]) {
				//不是死点，维护计分数组，将自己的记录清除
				if (who == AIcolor) {
					AIstate[state[who][x - i][y - i][2]]--;
				}
				else {
					Manstate[state[who][x - i][y - i][2]]--;
				}
				//更新五元组状态
				state[who][x - i][y - i][2]--;
				//维护计分数组，添加记录
				if (who == AIcolor) {
					AIstate[state[who][x - i][y - i][2]]++;
				}
				else {
					Manstate[state[who][x - i][y - i][2]]++;
				}
			}
			else {
				state[who][x - i][y - i][2]--;
				//检查死点是否解除
				if (state[who][x - i][y - i][2] == 0) {
					//解除死点
					dead[x - i][y - i][2] = 0;
					deadnum--;
					if (other == AIcolor) {
						AIstate[state[other][x - i][y - i][2]]++;
					}
					else {
						Manstate[state[other][x - i][y - i][2]]++;
					}
				}
			}

		}
		if (!yuejie(x - i, y + i)) {

			if (!dead[x - i][y + i][3]) {
				//不是死点，维护计分数组，将自己的记录清除
				if (who == AIcolor) {
					AIstate[state[who][x - i][y + i][3]]--;
				}
				else {
					Manstate[state[who][x - i][y + i][3]]--;
				}
				//更新五元组状态
				state[who][x - i][y + i][3]--;
				//维护计分数组，添加记录
				if (who == AIcolor) {
					AIstate[state[who][x - i][y + i][3]]++;
				}
				else {
					Manstate[state[who][x - i][y + i][3]]++;
				}
			}
			else {
				state[who][x - i][y + i][3]--;
				//检查死点是否解除
				if (state[who][x - i][y + i][3] == 0) {
					//解除死点
					dead[x - i][y + i][3] = 0;
					deadnum--;
					if (other == AIcolor) {
						AIstate[state[other][x - i][y + i][3]]++;
					}
					else {
						Manstate[state[other][x - i][y + i][3]]++;
					}
				}
				
			}
		}
	}
	return true;
}

long long thinker::getpoint() {
	long long point = 0;

	if (AIstate[5] != 0) {
		return INT_MAX;
	}

	if (Manstate[5] != 0) {
		return INT_MIN;
	}

	for (int i = 0; i < 6; i++) {
		point += AIstate[i] * cpoint[i] * 0.95;
		point -= Manstate[i] * cpoint[i];
	}
	
	point += deadnum;
	return point;
}