#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <memory.h>
#include <crtdbg.h>
#include "MfcKatsunariDoc.h"

//#define BOARD_SIZE 11
//#define PURE_BOARD_SIZE 9
//#define SPACE 0
//#define BLACK 1
//#define WHITE 2
#//define OB	  3

#define TRUE 1
#define FALSE 0
typedef int BOOL;

int Ban[BOARD_SIZE][BOARD_SIZE];
int Eval[BOARD_SIZE][BOARD_SIZE];
int ko_x,ko_y,ko_num;

static void ColorClear(int size);
//static int WhichColor(int x,int y,int BoardSize,int Ban[BOARD_SIZE][BOARD_SIZE]);
//static int Keisei(int Ban[BOARD_SIZE][BOARD_SIZE]);
/*int mcts(int *x, int *y, int Ban[BOARD_SIZE][BOARD_SIZE], int Eval[BOARD_SIZE][BOARD_SIZE], int color, int move);*/
int mcts(int* x, int* y, int pos_array[BOARD_SIZE*BOARD_SIZE], int color, int size, int ko_x , int ko_y, int playout, int komi);

#define BL_AREA 7
#define WH_AREA 8
#define BL_DEAD 17
#define WH_DEAD 18

//extern "C" void initAll();												// 全体の初期化
void initAll()
{
	//　実は、ここでsrandしても意味がないらしい。
	// というのは、initAllは思考の本体と別スレッドで動くからで、どうもスレッド毎にsrandしないといけないようだ。
	srand((unsigned)time(NULL));
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF|_CRTDBG_CHECK_ALWAYS_DF|_CRTDBG_LEAK_CHECK_DF);
}

// 既に盤上のこの位置をチェック済みかどうか。
int check[BOARD_SIZE][BOARD_SIZE];

// x,yの位置にあるcolor色の石を、隣接する石も含めて再帰的に取り除き、取り除いた石の数を返す
int DoRemoveRecursive(int x,int y,int color,int board[BOARD_SIZE][BOARD_SIZE],int size)
{
	int ret=0;
	if (check[y][x]) return 0;
	check[y][x]=1;
	if (y<1 || x<1 || x>size/*PURE_BOARD_SIZE*/||y>size/*PURE_BOARD_SIZE*/) return 0;
	if( board[y][x] == color ){
		if (x>1) {
			ret+=DoRemoveRecursive(x-1, y, color,board,size);
		}
		if (y>1) {
			ret+=DoRemoveRecursive(x, y-1, color,board,size);
		}
		if (x<size/*PURE_BOARD_SIZE*/) {
			ret+=DoRemoveRecursive(x+1, y, color,board,size);
		}
		if (y<size/*PURE_BOARD_SIZE*/) {
			ret+=DoRemoveRecursive(x, y+1, color,board,size);
		}
		board[y][x]=SPACE;
		ret++;
	}
	return ret;
}

// x,yの位置にあるcolor色の石の塊を取り除き、取り除いた石の数を返す
int DoRemove(int x,int y,int color,int board[BOARD_SIZE][BOARD_SIZE],int size)
{
	memset(check,0,sizeof(check));
	return DoRemoveRecursive(x,y,color,board,size);
}


// x,yの位置のcolor色の石が取れるかどうかを、隣接する石も含めて再帰的にチェックし、取れるかどうかを返す
int CheckRemoveRecursive(int x,int y,int color,int board[BOARD_SIZE][BOARD_SIZE], int size)
{
	if (check[y][x]) return TRUE;
	check[y][x]=1;
	if (y<1 || x<1 || x>size/*PURE_BOARD_SIZE*/||y>size/*PURE_BOARD_SIZE*/) return TRUE;
	if (board[y][x]==SPACE) return FALSE;
	if( board[y][x] == color ){
		if (x>1) {
			if (!CheckRemoveRecursive(x-1, y, color,board, size)) {
				return FALSE;
			}
		}
		if (y>1) {
			if (!CheckRemoveRecursive(x, y-1, color,board, size)) {
				return FALSE;
			}
		}
		if (x<PURE_BOARD_SIZE) {
			if (!CheckRemoveRecursive(x+1, y, color,board, size)) {
				return FALSE;
			}
		}
		if (y<PURE_BOARD_SIZE) {
			if (!CheckRemoveRecursive(x, y+1, color,board, size)) {
				return FALSE;
			}
		}
	}
	return TRUE;
}

// x,yの位置のcolor色の石の塊が取れるかどうかをチェックし、取れるかどうかを返す
int CheckRemove(int x,int y,int color,int board[BOARD_SIZE][BOARD_SIZE],int size)
{
	memset(check,0,sizeof(check));
	return CheckRemoveRecursive(x,y,color,board,size);
}

// 自殺手になっていないかどうかチェックする
//int checkSuicide(int x,int y,int color,int board[BOARD_SIZE][BOARD_SIZE])
//{
//	board[y][x]=color;
//	if (CheckRemove(x,y,color,board)) {
		//自分の色の石の塊のダメおよび眼がないので自殺手かも知れない。
//		int opp=(color==WHITE)?BLACK:WHITE;
		// でも、隣接する相手の石が取れるなら自殺手ではない。
//		if ( (x>1 && board[y][x-1]==opp && CheckRemove(x-1,y,opp,board)) ) return FALSE;
//		if ( (y>1 && board[y-1][x]==opp && CheckRemove(x,y-1,opp,board)) ) return FALSE;
//		if ( (x<PURE_BOARD_SIZE && board[y][x+1]==opp && CheckRemove(x+1,y,opp,board))) return FALSE;
//		if ( (y<PURE_BOARD_SIZE && board[y+1][x]==opp && CheckRemove(x,y+1,opp,board))) return FALSE;
//		return TRUE;
//	}
//	return FALSE;
//}

// 位置x,yに、color色の石をmove手番目に置けるかどうかを返す
//int checkSetStoneGameBoard(int x,int y, int color, int move)
//{
//	int board[BOARD_SIZE][BOARD_SIZE];  /* 碁盤 */
//	int xx,yy;

//	for(yy=0;yy<BOARD_SIZE;yy++) {
//		for(xx=0;xx<BOARD_SIZE;xx++) {
//			board[yy][xx]=Ban[yy][xx];
//		}
//	}

	// 盤の外には置けない
//	if( x > PURE_BOARD_SIZE || x < 1 || y > PURE_BOARD_SIZE || y < 1 ){
//		return( FALSE );  /* FALSE=0 */
//	}
	// パス(x,yともに０)はいつでもOK。
//	if( (x == 0) || (y == 0) ){
		// パス
//		return( TRUE );
//	}
	//　何か既に置いてあったら置けない
//	if (Ban[y][x]!=SPACE) return FALSE;
	// コウのチェック：コウなら置けない
//	if (ko_x==x && ko_y==y && ko_num==move-1) return FALSE;
	// 自殺手のチェック：自殺手なら置けない
//	if (checkSuicide(x,y,color,board)) return FALSE;

//	return TRUE;
//}

//extern "C" int setStoneOnGameBoard(int x,int y,int color,int move);		// ユーザが指した手および自分の指した手を盤に置く
// 盤上の指定された位置x,yにcolor色の石を置く。
// 必要なら、それによって取られる石を取り除いたり、コウになっているかどうかのチェックもする。
int setStoneOnGameBoard(int x,int y,int color,int move,int size)
{
	int ret=0;
	int tmpBoard[BOARD_SIZE][BOARD_SIZE];
	// 敵の色
	int opp=(color==WHITE)?BLACK:WHITE;

	// 石は、ひとつだけ（隣接する同じ色の石がない）か？
	BOOL isSingleStone=TRUE;
	if (Ban[y-1][x]==color || Ban[y+1][x]==color || Ban[y][x+1]==color || Ban[y][x-1]==color) {
		isSingleStone=FALSE;
	}
	memcpy(tmpBoard,Ban,sizeof(Ban));

	// 石を置いてみる
	Ban[y][x]=color;

	// 置いたことによって、取り除かれる石がいくつあるか数えながら石を取り除く
	if (CheckRemove(x+1,y,opp,Ban,size)) {
		ret+=DoRemove(x+1,y,opp,Ban,size);
	}
	if (CheckRemove(x-1,y,opp,Ban,size)) {
		ret+=DoRemove(x-1,y,opp,Ban,size);
	}
	if (CheckRemove(x,y+1,opp,Ban,size)) {
		ret+=DoRemove(x,y+1,opp,Ban,size);
	}
	if (CheckRemove(x,y-1,opp,Ban,size)) {
		ret+=DoRemove(x,y-1,opp,Ban,size);
	}
	// 石が一つだけで、取った石の数が１つならば、コウ
	if (ret==1 && isSingleStone) {
		// コウの起きた手番
		ko_num=move;
		// どこを取った？取った位置ko_x,ko_yがコウで次の手番の着手禁止点になる。
		if (Ban[y][x+1]==SPACE && tmpBoard[y][x+1]!=SPACE) {
			ko_x=x+1;
			ko_y=y;
		}
		if (Ban[y][x-1]==SPACE && tmpBoard[y][x-1]!=SPACE) {
			ko_x=x-1;
			ko_y=y;
		}
		if (Ban[y+1][x]==SPACE && tmpBoard[y+1][x]!=SPACE) {
			ko_x=x;
			ko_y=y+1;
		}
		if (Ban[y-1][x]==SPACE && tmpBoard[y-1][x]!=SPACE) {
			ko_x=x;
			ko_y=y-1;
		}
	}
	// 一応、取った石の数を返しているが、UIの方でも処理しているので実は何でも良い
	return ret;
}


//extern "C" void clearGameBoard();										// 盤をクリアする
void clearGameBoard(int boardSize)
{
	int x,y;
	ko_x=ko_y=ko_num=0;
	for(y=0;y<boardSize;y++) {
		for(x=0;x<boardSize;x++) {
			if (x==0||y==0||x==boardSize-1||y==boardSize-1) {
				Ban[y][x]=OB;
			} else {
				Ban[y][x]=SPACE;
			}
		}
	}
}

//extern "C" void setHandicapStoneGameBoard(int Handicap);				// 盤に、置石をする
void setHandicapStoneGameBoard(int Handicap) {
	switch(Handicap) {
		case 9:
			Ban[ 4][ 4]=BLACK;
			Ban[ 4][10]=BLACK;
			Ban[ 4][16]=BLACK;
			Ban[10][ 4]=BLACK;
			Ban[10][10]=BLACK;
			Ban[10][16]=BLACK;
			Ban[16][ 4]=BLACK;
			Ban[16][10]=BLACK;
			Ban[16][16]=BLACK;
			break;
		case 8:
			Ban[ 4][ 4]=BLACK;
			Ban[ 4][10]=BLACK;
			Ban[ 4][16]=BLACK;
			Ban[10][ 4]=BLACK;
			Ban[10][16]=BLACK;
			Ban[16][ 4]=BLACK;
			Ban[16][10]=BLACK;
			Ban[16][16]=BLACK;
			break;
		case 7:
			Ban[ 4][ 4]=BLACK;
			Ban[ 4][16]=BLACK;
			Ban[10][ 4]=BLACK;
			Ban[10][10]=BLACK;
			Ban[10][16]=BLACK;
			Ban[16][ 4]=BLACK;
			Ban[16][16]=BLACK;
			break;
		case 6:
			Ban[ 4][ 4]=BLACK;
			Ban[ 4][16]=BLACK;
			Ban[10][ 4]=BLACK;
			Ban[10][16]=BLACK;
			Ban[16][ 4]=BLACK;
			Ban[16][16]=BLACK;
			break;
		case 5:
			Ban[ 4][ 4]=BLACK;
			Ban[ 4][16]=BLACK;
			Ban[10][10]=BLACK;
			Ban[16][ 4]=BLACK;
			Ban[16][16]=BLACK;
			break;
		case 4:
			Ban[ 4][ 4]=BLACK;
			Ban[ 4][16]=BLACK;
			Ban[16][ 4]=BLACK;
			Ban[16][16]=BLACK;
			break;
		case 3:
			Ban[ 4][16]=BLACK;
			Ban[16][ 4]=BLACK;
			Ban[16][16]=BLACK;
			break;
		case 2:
			Ban[ 4][16]=BLACK;
			Ban[16][ 4]=BLACK;
			break;
		default:
			break;
	}
}

// 眼形をつぶさないようにチェックする。
int checkMetubushi(int x,int y,int color)
{
	int tmpBoard[BOARD_SIZE][BOARD_SIZE];
	memcpy(tmpBoard,Ban,sizeof(Ban));

	// 盤外をあらわす数値は"3"なので、WHITEと論理積を取っても、BLACKと論理積を取っても、
	// WHITEまたはBLACKになる。
	if ((tmpBoard[y-1][x] & color) && (tmpBoard[y+1][x] & color) && (tmpBoard[y][x-1] & color) && (tmpBoard[y][x+1] & color)) {
		// 周囲に４つの石または壁がある：眼潰しの可能性あり。
		if((tmpBoard[y-1][x-1]&color) + (tmpBoard[y-1][x+1]&color) +(tmpBoard[y+1][x-1]&color) + (tmpBoard[y+1][x+1]&color) >= color*3) {
			// さらに斜め方向に３つ以上「石があるか、または盤外」ならば眼形。
			return TRUE;
		}
	}
	return FALSE;
}

// 自分の地かどうかチェックする
//int checkMyJi(int x,int y,int color)
//{
//	int tmpBoard[BOARD_SIZE][BOARD_SIZE];
//	memcpy(tmpBoard,Ban,sizeof(Ban));
	
	// 最初に、この関数を呼んで、地の形を認識させる
//	Keisei(tmpBoard);
	// 次に、x,yの位置がどちらの色の地（または中立）か判定する。
//	if (WhichColor(x,y,PURE_BOARD_SIZE,tmpBoard)==color) {
//		return TRUE;
//	}
//	return FALSE;
//}

//extern "C" char *selectNextMove(int *x,int *y,int *eval,int color,int move,int kind);	// 現在の盤を見て次の一手を返す
char *selectNextMove(int *x,int *y,int *eval,int color,int move/*,int kind*/,int ko_x_in, int ko_y_in, int ko_move, int size, int playout, int komi)
{
	int xx,yy;
//	int retx,rety;
//	int val;
	int r;
	int pos_array[BOARD_SIZE*BOARD_SIZE];

	if (ko_move==move-1) {
		ko_x = ko_x_in;
		ko_y = ko_y_in;
	}else{
		ko_x = 0;
		ko_y = 0;
	}
	//　ここで乱数のシードを初期化する。
	/*srand((unsigned)time(NULL));*/
	// checkMyJiのための初期化
	/*ColorClear();*/
	// ルール上新たに石を置けないところは-1,自分の地になっているか、眼形をつぶしてしまうところは-1000
	// それ以外ならランダムな数値を入れる
	/*for(yy=1;yy<=PURE_BOARD_SIZE;yy++) {
		for(xx=1;xx<=PURE_BOARD_SIZE;xx++) {
			if (checkSetStoneGameBoard(xx,yy,color,move)) {
				if (checkMetubushi(xx,yy,color) || checkMyJi(xx,yy,color)) {
					Eval[yy][xx]=-1000;
				} else {
					Eval[yy][xx]=rand()%256;
				}
			} else  {
				Eval[yy][xx]=-1;
			}
		}
	}*/
	//　上記だけではランダムになりきらないので、さらに乱数を適当に加える
	/*for(r=0;r<50;r++) {
		yy=(rand()%PURE_BOARD_SIZE)+1;
		xx=(rand()%PURE_BOARD_SIZE)+1;
		// でもやはり眼は潰さない。
		if (checkMetubushi(xx,yy,color)) continue;
		// 相手の地には加点しない
		if (checkMyJi(xx,yy,color==BLACK?WHITE:BLACK)) continue;
		// 打てる場所かどうかチェックして、
		if (checkSetStoneGameBoard(xx,yy,color,move)) {
			Eval[yy][xx]+=rand()%256;
		}
	}*/
	// モンテカルロ木探索
	/*mcts(x, y, Ban, Eval, color, move);*/
	/* 入力位置情報変換 */
	r = 0;
	for(yy=0;yy<size+2/*BOARD_SIZE*/;yy++){
		for(xx=0;xx<size+2/*BOARD_SIZE*/;xx++, r++){
			if(Ban[yy][xx] == WHITE) pos_array[r] = -1;
			else                     pos_array[r] = Ban[yy][xx];
		}
	}
	mcts(x, y, &pos_array[0], color, size/*PURE_BOARD_SIZE*/, ko_x, ko_y, playout, komi);

	// 乱数で決めた最大の評価になった位置を返す
	/*	for(yy=1;yy<=PURE_BOARD_SIZE;yy++) {
	val=-1;
	rety=0;
	retx=0;
		for(xx=1;xx<=PURE_BOARD_SIZE;xx++) {
			if (Eval[yy][xx]>val) {
				val=Eval[yy][xx];
				rety=yy;
				retx=xx;
			}
		}
	}
	*x=retx;
	*y=rety;}*/
//	*eval=val;
	*eval = 0;
	return "らんだむ";	// 返り値は、選んだ根拠。らんだむに選んでいるので"らんだむ"。
}
					 

//extern "C" int copyEvaluation(int buf[][BOARD_SIZE]);					// selextNextMoveの後、盤上の各指し手の評価値を返す
void copyEvaluation(int buf[BOARD_SIZE][BOARD_SIZE], int size)
{
	int x,y;
	for(y=0;y<size/*BOARD_SIZE*/;y++) {
		for(x=0;x<size/*BOARD_SIZE*/;x++) {
			if (x==0||y==0||x==size/*BOARD_SIZE*/-1||y==size/*BOARD_SIZE*/-1) {
				buf[y][x]=0;
			} else {
				buf[y][x]=Eval[y][x];
			}
		}
	}
}

int Color[BOARD_SIZE][BOARD_SIZE];
int InCheck[BOARD_SIZE][BOARD_SIZE];

// 形勢判断（どちらの地か）を見極めるためのワークエリアをクリアする
static void ColorClear(int size) {
	int x,y;
	for(y=0;y<=size/*PURE_BOARD_SIZE*/+1;y++) {
		for(x=0;x<=size/*PURE_BOARD_SIZE*/+1;x++) {
			if (x==0 || y==0 ||y==size/*PURE_BOARD_SIZE*/+1 || x==size/*PURE_BOARD_SIZE*/+1) {
				Color[y][x]=0;
				InCheck[y][x]=-1;
		} else {
				InCheck[y][x]=0;
				Color[y][x]=0;
			}
		}
	}
}

// 形勢判断後、x,yの位置がどちらの色の地かを返す
static int WhichColor(int x,int y,int BoardSize,int tBan[BOARD_SIZE][BOARD_SIZE]) {
	int m1,m2,m3,m4;
	if (InCheck[y][x]==-1) return 0;
	if (InCheck[y][x]) return InCheck[y][x];
	if (Color[y][x]!=0) return Color[y][x];
	if (tBan[y][x]==BLACK || tBan[y][x]==5) {
		Color[y][x]=BLACK;
		return BLACK;
	}
	if (tBan[y][x]==WHITE || tBan[y][x]==6) {
		Color[y][x]=WHITE;
		return WHITE;
	}
	// 空白地帯に、どちらの色の石が接しているか、または両方の石が接しているのか。
	InCheck[y][x]=-1;
	m4=WhichColor(x,y-1,BoardSize,Ban);
	if (m4!=0) InCheck[y][x]=m4;
	m3=WhichColor(x-1,y,BoardSize,Ban);
	if (m3!=0) InCheck[y][x]=m3|m4;
	m1=WhichColor(x+1,y,BoardSize,Ban);
	if (m1!=0) InCheck[y][x]=m1|m3|m4;
	m2=WhichColor(x,y+1,BoardSize,Ban);
	Color[y][x]=(m1|m2|m3|m4)&3;
	if (Color[y][x]==0) Color[y][x]=3;

	InCheck[y][x]=0;
	return Color[y][x];
}

static int Keisei(int tBan[BOARD_SIZE][BOARD_SIZE], int size)
{
	int x,y;
	int keisei=0;
	ColorClear(size);
	// Color[y][x]に、どちらの地なのかを入れる。
	for(y=1;y<=size/*PURE_BOARD_SIZE*/;y++){
		for(x=1;x<=size/*PURE_BOARD_SIZE*/;x++) {
			Color[y][x]=WhichColor(x,y,size/*PURE_BOARD_SIZE*/,Ban);
		}
	}

	// 盤面認識にユーザインタフェースで求めている数値に置き換える。
	for(x=1;x<=size/*PURE_BOARD_SIZE*/;x++) {
		for(y=1;y<=size/*PURE_BOARD_SIZE*/;y++){
			if ((tBan[y][x]==BLACK||tBan[y][x]==5) && Color[y][x]==BLACK) {
				tBan[y][x]=BLACK;	//黒の石
			}
			if ((tBan[y][x]==WHITE||tBan[y][x]==6||tBan[y][x]==18) && Color[y][x]==BLACK) {
				tBan[y][x]=18;	//黒の地、白の死に石
				keisei+=1/*2*/;
			}
			if (tBan[y][x]==SPACE || tBan[y][x]==7 || tBan[y][x]==8) {
				if (Color[y][x]==3||Color[y][x]==0) {
					tBan[y][x]=0;
				} else {
					tBan[y][x]=Color[y][x]+6;
					if (Color[y][x]==BLACK) {
						keisei++;
					} else {
						keisei--;
					}
				}
			}
			if ((tBan[y][x]==WHITE||tBan[y][x]==6) && Color[y][x]==WHITE) {
				tBan[y][x]=WHITE;	//白の石
			}
			if ((tBan[y][x]==BLACK||tBan[y][x]==5||tBan[y][x]==17) && Color[y][x]==WHITE) {
				tBan[y][x]=17;	//白の地、黒の死に石
				keisei-=1/*2*/;
			}
		}
	}
	return keisei;
}


//extern "C" int copyStatus(int buf[][BOARD_SIZE]);						// 現在の盤面認識を返す
int copyStatus(int buf[BOARD_SIZE][BOARD_SIZE], int size)
{
	memcpy(buf,Ban,sizeof(Ban));
	return Keisei(buf, size);
}