oai.cpp

java game uploading now

	//check bottom-left
	if ((x>1) && (y<=5) && (board[x-1][y+1]==-who)){
		for (i=2;((x-i)>=0) && ((y+i)<8); i++){
			if (board[x-i][y+i]== who)
				return TRUE;
			else if (board[x-i][y+i] == EMPTY)
				break;
		}
	}

	//check left
	if ((x>1) && (board[x-1][y]==-who)){
		for (i=x-2; i>=0; i--){
			if (board[i][y]== who)
				return TRUE;
			else if (board[i][y] == EMPTY)
				break;
		}
	}

	//check left-upper
	if ((x>1) && (y>1) && (board[x-1][y-1]==-who)){
		for (i=2;((x-i)>=0) && ((y-i)>=0); i++){
			if (board[x-i][y-i]== who)
				return TRUE;
			else if (board[x-i][y-i] == EMPTY)
				break;
		}
	}
	return FALSE;
}

//NegaMax search
int COAI::search(int alpha, int beta, int search_depth)
{
	if (search_depth==0)	//evaluate board if reach leaf
		return stat_eval();
	move_st move_struct;
	set_up_legal_moves(&move_struct, to_play);

	if (!move_struct.no_legal_moves){	//no moves to play
		move_st move_struct2;
		set_up_legal_moves(&move_struct2, -to_play);

		if (move_struct2.no_legal_moves==0){	//game ends
			int i2 = disk_difference(to_play);
			e_count++;
			if (i2>0) return WIN+i2;
			else if (i2<0) return LOSE+i2;
			else return DRAW;
		}
		else{	//skip turn
			to_play = -to_play;
			int e2 = -search(-beta, -alpha, search_depth-1);
			to_play = -to_play;
			return e2;
		}
	}

	//order the moves for best pruning
	int move_order[40] = { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39};
	if ((!move_order_search) && (search_depth>=4) && (ordermove))
			order_moves(&move_struct, move_order);

	int best = START_ALPHA;
	int e;	//evaluate value
	for (int i = 0; i<move_struct.no_legal_moves; i++){
		play_move(&move_struct, move_order[i]);
		to_play = -to_play;
		e = -search(-beta, -alpha, search_depth-1);
		to_play = -to_play;
		undo_move(&move_struct, move_order[i]);

		if (e>best){
			best = e;
			if (best > alpha){
				alpha = best;
				if (alpha >= beta) return alpha;
			}
		}
	}
	return best;
}

//NegaScout search (turtle)
int COAI::search2(int alpha, int beta, int search_depth)
{
	if (search_depth==0)	//evaluate board if reach leaf
		return stat_eval();
	move_st move_struct;
	set_up_legal_moves(&move_struct, to_play);

	if (!move_struct.no_legal_moves){
		move_st move_struct2;
		set_up_legal_moves(&move_struct2, -to_play);
		if (move_struct2.no_legal_moves==0){	//game ends
			e_count++;
			int i2 = disk_difference(to_play);
			if (i2>0) return WIN+i2;
			else if (i2<0) return LOSE+i2;
			else return DRAW;
		}
		else{	//skip turn
			to_play = -to_play;
			int e2 = -search2(-beta, -alpha, search_depth-1);
			to_play = -to_play;
			return e2;
		}
	}

	//order the moves for best pruning
	int move_order[40] = { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39};
	if ((!move_order_search) && (search_depth>=4) && (ordermove))
		order_moves(&move_struct, move_order);

	play_move(&move_struct, move_order[0]);
	to_play = -to_play;
	int e = -search2(-beta, -alpha, search_depth-1);
	to_play = -to_play;
	undo_move(&move_struct, move_order[0]);

	int v;
	for (int i = 1; i<move_struct.no_legal_moves; i++){

		if (e>alpha){
			alpha = e;
			if (alpha>=beta) return alpha;	//cut-off
		}

		play_move(&move_struct, move_order[i]);
		to_play = -to_play;
		v = -search2(-alpha-1, -alpha, search_depth-1);	//null window search
		to_play = -to_play;
		undo_move(&move_struct, move_order[i]);

		if (v>alpha && v<beta){		//re-search
			play_move(&move_struct, move_order[i]);
			to_play = -to_play;
			v = -search2(-beta, -v, search_depth-1);	//null window search
			to_play = -to_play;
			undo_move(&move_struct, move_order[i]);
		}

		if (v>e) e=v;
	}

	return e;
}

int COAI::stat_eval()
{
	e_count++;
	int sum, sum1=0, sum2=0, sum3=0, sum4=0;
	int mob1,mob2,pmob1,pmob2;

	mobility(to_play, mob1, pmob1);
	mobility(-to_play, mob2, pmob2);
	sum1 = disk_difference(to_play);	//disk-difference
	if (!mob1 && !mob2){
		if (sum1>0) return WIN + sum1;
		else if(sum1<0) return LOSE + sum1;
		else return DRAW;
	}

	sum2 = corner(to_play);		//edge table
	sum3 = mob1 - mob2;			//mobility
	sum4 = pmob1 - pmob2;		//potential mobility
	sum = sum1 + upndown()*sum2 + raising()*sum3 + falling()*sum4;	//total evaluation

	return sum;
}

BOOL COAI::move(int who, int &score, int &x, int &y, int &time, int &nodes)
{
	move_st move_struct;
	e_count = 0;
	DWORD timenow = GetTickCount();

	move_order_search = FALSE;

	total_disks = disks_count();
	int depth_this_time = (total_disks>64-eg_empty)?60:depth;
	set_up_legal_moves(&move_struct, to_play);

	if (move_struct.no_legal_moves == 0){	//no moves to play
		x=y=-1;	//no move
		move_st move_struct2;
		set_up_legal_moves(&move_struct2, -to_play); //check opponents moves
		
		if (move_struct2.no_legal_moves ==0)	//game end
			score = END;
		else
			score = SKIP;	//just a pass from our side
		return FALSE;
	}
	else if (move_struct.no_legal_moves == 1){	//only one move available, make such move
		x = move_struct.disk_turned[0][0].x;
		y = move_struct.disk_turned[0][0].y;
		time = GetTickCount() - timenow;
		score = nodes = 0;
		return TRUE;
	}

	score = START_ALPHA;

#ifdef _DEBUG
	int sb[8][8]={0};
#endif

	int e;
	for(int i=0; i <move_struct.no_legal_moves; i++){
		play_move(&move_struct, i);
		to_play = -to_play;

		if (!searchmethod)
			e = -search(START_ALPHA, START_BETA, depth_this_time-1);
		else
			e = -search2(START_ALPHA, START_BETA, depth_this_time-1);
		to_play = -to_play;
		undo_move(&move_struct, i);

#ifdef _DEBUG
		sb[move_struct.disk_turned[i][0].x][move_struct.disk_turned[i][0].y] = e;
#endif
		if (e>score){
			score = e;
			x = move_struct.disk_turned[i][0].x;
			y = move_struct.disk_turned[i][0].y;
		}
	}

	time = GetTickCount() - timenow;
	nodes = e_count;

#ifdef _DEBUG
	CString de, de2;
	for (int y1=0; y1<8;y1++){
		de2.Format("%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n", sb[0][y1], sb[1][y1], sb[2][y1], sb[3][y1], sb[4][y1], sb[5][y1], sb[6][y1], sb[7][y1]);
		de+=de2;
	}
	de2.Format("CPU [%c%d]:%d",x+'A', y+1, score);
	de+=de2;
	::MessageBox(NULL,de,"Map",MB_OK);
#endif
	return TRUE;
	
}


BOOL COAI::is_legal2(int who, int x, int y, BOOL &pmob)
{
	if (board[x][y]){
		pmob = FALSE;
		return FALSE;
	}

	pmob = FALSE;

	int i;
	//check up
	if ((y>=2) && (board[x][y-1]==-who)){
		for (i=y-2; i>=0; i--){
			if (board[x][i]== who)
				return TRUE;
			else if(board[x][i]==EMPTY){
				pmob = TRUE;
				break;
			}
		}
	}

	//check up-right
	if ((x<=5) && (y>=2) && (board[x+1][y-1]==-who)){
		for (i=2; ((x+i)<8) && ((y-i)>=0); i++){
			if (board[x+i][y-i]== who)
				return TRUE;
			else if (board[x+i][y-i] == EMPTY){
				pmob = TRUE;
				break;
			}
		}
	}

	//check right
	if ((x<=5) && (board[x+1][y]==-who)){
		for (i=x+2; i<8; i++){
			if (board[i][y]== who)
				return TRUE;
			else if (board[i][y] == EMPTY){
				pmob = TRUE;
				break;
			}
		}
	}

	//check bottom-right
	if ((x<=5) && (y<=5) && (board[x+1][y+1]==-who)){
		for (i=2;((x+i)<8) && ((y+i)<8); i++){
			if (board[x+i][y+i]== who)
				return TRUE;
			else if (board[x+i][y+i] == EMPTY){
				pmob = TRUE;
				break;
			}
		}
	}

	//check bottom
	if ((y<=5) && (board[x][y+1]==-who)){
		for (i=y+2; i<8; i++){
			if (board[x][i] == who)
				return TRUE;
			else if (board[x][i] == EMPTY){
				pmob = TRUE;
				break;
			}
		}
	}

	//check bottom-left
	if ((x>1) && (y<=5) && (board[x-1][y+1]==-who)){
		for (i=2;((x-i)>=0) && ((y+i)<8); i++){
			if (board[x-i][y+i]== who)
				return TRUE;
			else if (board[x-i][y+i] == EMPTY){
				pmob = TRUE;
				break;
			}
		}
	}

	//check left
	if ((x>1) && (board[x-1][y]==-who)){
		for (i=x-2; i>=0; i--){
			if (board[i][y]== who)
				return TRUE;
			else if (board[i][y] == EMPTY){
				pmob = TRUE;
				break;
			}
		}
	}

	//check left-upper
	if ((x>1) && (y>1) && (board[x-1][y-1]==-who)){
		for (i=2;((x-i)>=0) && ((y-i)>=0); i++){
			if (board[x-i][y-i]== who)
				return TRUE;
			else if (board[x-i][y-i] == EMPTY){
				pmob = TRUE;
				break;
			}
		}
	}
	return FALSE;
}

void COAI::mobility(int who, int &mob, int &pmob)
{

	BOOL bmob;
	mob = pmob = 0;
	for (int i=0; i<8;i++)
		for (int j=0;j<8;j++){
			if (is_legal2(who,i,j,bmob))
				mob++;
			else if (bmob)
				pmob++;
		}
}

int COAI::disks_count()
{
	int re_val = 0;
	for (int i=0; i<8;i++)
		for (int j=0;j<8;j++)
			if (board[i][j])
				re_val++;
	return re_val;
}

void COAI::disks_count(int &bcount, int &wcount)
{
	bcount=wcount=0;
	for (int i=0; i<8;i++)
		for (int j=0;j<8;j++)
			if (board[i][j]==BLACK)
				bcount++;
			else if (board[i][j]==WHITE)
				wcount++;

}

//setup new board
void COAI::new_board()
{
	for (int i=0; i<8;i++)
		for (int j=0;j<8;j++)
			board[i][j] = EMPTY;
	board[3][3] = board[4][4] = WHITE;
	board[4][3] = board[3][4] = BLACK;

}

BOOL COAI::anyvalidmove(int who)
{
	for (int i=0;i<8;i++)
		for (int j=0;j<8;j++)
			if (is_legal(who,i,j))
				return TRUE;
	return FALSE;
}


int COAI::pmobility(int who)
{
	int to_return=0;
	for (int i=0;i<8;i++)
		for(int j=0;j<8;j++){
			if (board[i][j]==EMPTY){
				if (i>0) to_return += ((board[i-1][j]==-who)?1:0);
				if (i<7) to_return += ((board[i+1][j]==-who)?1:0);
				if (j>0) to_return += ((board[i][j-1]==-who)?1:0);
				if (j<7) to_return += ((board[i][j+1]==-who)?1:0);
				if (i>0 && j>0) to_return += ((board[i-1][j-1]==-who)?1:0);
				if (i>0 && j<7) to_return += ((board[i-1][j+1]==-who)?1:0);
				if (i<7 && j>0) to_return += ((board[i+1][j-1]==-who)?1:0);
				if (i<7 && j<7) to_return += ((board[i+1][j+1]==-who)?1:0);
			}
		}
	return to_return;
}

int COAI::upndown()
{
	if (total_disks<20)
		return(1 + (int)(total_disks*0.2 + 0.5));
	else
		return(1 + (int)(61-total_disks*0.2 + 0.5));

}

int COAI::raising()
{
	return (4 + (int)(total_disks*0.1 + 0.5));
}

int COAI::falling()
{
	return (7 - (int)(total_disks*0.1 + 0.5));
}