/* FORZA 4 - algoritmo DFS minimax */

#define SKILL 10
#define ROW 6
#define COLUMN 7


int board[ROW*COLUMN];
long int depth,skill;
unsigned long int nodes;

void display_board(void)
{
	long int i,j;
	printf("\n");
	for(j=0;j<ROW;j++)
	{
		for(i=0;i<COLUMN;i++)
		{
			if(board[i+j*COLUMN]==1) printf("X ");
			if(board[i+j*COLUMN]==-1) printf("O ");
			if(board[i+j*COLUMN]==0) printf(". ");
		}
		printf("\n");
	}
	for(i=0;i<(COLUMN*2)-1;i++) printf("-");
	printf("\n");
	for(i=0;i<COLUMN;i++) printf("%d ",i+1);
	printf("\n");
}


int checkwin(int player,int column,int lenght)
{
	long int j,r,l,i,height;
	lenght--;
	i = column;
	j = ROW-1;
	while(board[i+j*COLUMN]!=0) j--;
	j++;
	height = j;
	
	r = 0;
	l = 0;
	while(((++i)<COLUMN)&&(board[i+j*COLUMN]==player)) r++;
	i = column;
	while(((--i)>=0)&&(board[i+j*COLUMN]==player)) l++;
	if ((r+l)>=lenght) return 1;
	i = column;
	
	r = 0;
	while(((++j)<ROW)&&(board[i+j*COLUMN]==player)) r++;
	if (r>=lenght) return 1;
	j = height;
	
	r = 0;
	l = 0;
	while(((++i)<COLUMN)&&((++j)<ROW)&&(board[i+j*COLUMN]==player)) r++;
	i = column;
	j = height;
	while(((--i)>=0)&&((--j)>=0)&&(board[i+j*COLUMN]==player)) l++;
	if ((r+l)>=lenght) return 1;
	i = column;
	j = height;
	
	r = 0;
	l = 0;
	while(((++i)<COLUMN)&&((--j)>=0)&&(board[i+j*COLUMN]==player)) r++;
	i = column;
	j = height;
	while(((--i)>=0)&&((++j)<ROW)&&(board[i+j*COLUMN]==player)) l++;
	if ((r+l)>=lenght) return 1;
	
	return 0;
}

int extimated_value(int player)
{
	long int i,j,value,l;
	
	value = 0;
	for(l=2;l<4;l++)
	{
		for(i=0;i<COLUMN;i++)
		{
			if(checkwin(player,i,l)) value = value + l;
		}
	}
	
	return value;
}

int goodness(int player,int depth,int column,int trigger)
{
	long int max,i,value,j;
	max = -200;
	if (checkwin(-player,column,4)) return -128;
	if (depth==0) return 0;
	for(i=0;i<COLUMN;i++)
	{
		if(board[i]==0)
		{
			j = ROW-1;
			while(board[i+j*COLUMN]!=0) j--;
			board[i+j*COLUMN] = player;
			nodes++;
			value = -goodness(-player,depth-1,i,-max)/2;
			board[i+j*COLUMN] = 0;
			if (value>max) max = value;
			if (value>trigger) return max;
		}
	}
	return max;
}

int best_move(int player)
{
	long int i,j,max,value,best,same,trigger,old,att;
	long int res[COLUMN];
	max = -100;
	best = -1;
	for(i=0;i<COLUMN;i++)
	{
		if(board[i]==0)
		{
			nodes = 0;
			j = ROW-1;
			while((board[i+j*COLUMN]!=0)&&(j>=0)) j--;
			board[i+j*COLUMN] = player;
			value = -goodness(-player,skill,i,200);
			printf("\nmove %d goodness: %d   tree size for this move: %d nodes",i+1,value,nodes);
			res[i] = value;
			board[i+j*COLUMN] = 0;
			if (value>max)
			{
				max = value;
				best = i;
			}
		}
	}
	if(best==-1)
	{
		for(i=0;i<COLUMN;i++) if(board[i]==0) return i;
	}
	
	return best;
}




int main(void)
{
	int move,j,i,coins;
	coins = ROW*COLUMN;
	skill = SKILL-3;
	
	for(i=0;i<(ROW*COLUMN);i++) board[i] = 0;
	display_board();
	
	while(coins!=0)
	{
		if (coins==40) skill=SKILL-2; /* quick start */
		if (coins==36) skill=SKILL-1; /* improve skill level... */
		if (coins==34) skill=SKILL;   /* ...to maximum */
		do
		{
			printf("\nchoose column [1-%d]...",COLUMN);
			scanf("%d",&move);
			if(board[move-1]!=0) printf("\ncolumn is full");
		}
		while(board[move-1]!=0);
		move--;
		j = ROW-1;
		while((board[move+j*COLUMN]!=0)&&(j>=0)) j--;
		board[move+j*COLUMN] = 1;
		coins--;
		display_board();
		if(checkwin(1,move,4))
		{
			printf("\nYou win\n");
			return 1;
		}
		move = best_move(-1);
		
		j = ROW-1;
		while((board[move+j*COLUMN]!=0)&&(j>=0)) j--;
		board[move+j*COLUMN] = -1;
		display_board();
		printf("\nCPU move in %d",move+1);
		coins--;
		if(checkwin(-1,move,4))
		{
			display_board();
			printf("\nCPU wins\n");
			return 1;
		}
		printf("\n");

		
	}
	printf("\n");
	return 1;
}