// FiveGame.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<stdlib.h>
#include<stdio.h>
#include<ctype.h>
#include<string.h>
#include<windows.h>
#define SPACE 18
const int MAX = 8;
const char player_c = 'U';  //User
const char comp_c = 'C';	//Computer	
void print_space(int num);
void displayBoard(char board[][MAX]);
int valid_moves(char board[][MAX],bool moves[][MAX],char player);
void make_move(char board[][MAX],int row,int col,char player);
int best_move(char board[][MAX],bool moves[][MAX],char player);
int get_score(char board[][MAX],char player);
int best_move(char board[][MAX],bool moves[][MAX],char player);
void computer_move(char board[][MAX],bool moves[][MAX],char player);
int main()
{
	char again = 0;
	char begain = 0;
	char board[MAX][MAX] = {0};
	bool moves[MAX][MAX] = {false};
	int mid = MAX/2;
	int row = 0;
	int col = 0;
	int no_of_games = 0;
	int no_of_moves = 0;
	int invalid_moves = 0;
	int comp_score = 0;
	int user_score = 0;
	char y = 0;
	int x = 0;
	int yy = 0;
	bool next_player = true;
	printf("|*************************************************************|\n");
	printf("|****************************REVERSI**************************|\n");
	printf("|*You can go first on the first game ,then we will take turns*|\n");
	printf("|*You will be white-(%c) and I will be black-(%c)              *|\n",player_c,comp_c);
	printf("|*Select a square for your move by typing a digit for the row*|\n");
	printf("|*and a letter for the column with no space between          *|\n");
	printf("|*Good luck! Press EnterKey to start...                      *|\n");
	printf("|*************************************************************|\n");
	begain = getchar();
	do{
		next_player = !next_player;
		no_of_moves = 4;
		for(row = 0; row < MAX; row++)
		{
			for(col = 0; col < MAX; col++)
			{
				board[row][col] = ' ';
			}
		}
		//initial four counters
		board[mid-1][mid-1] = board[mid][mid] = player_c;
		board[mid-1][mid] = board[mid][mid-1] = comp_c;
		/* The game play loop */
		do{
			displayBoard(board);
			next_player = !next_player;
			if(next_player)		/* It is the player's turn */
			{
				if(valid_moves(board,moves,player_c))
				{
					for(;;)
					{
						printf("Enter your move(row column):");
						scanf_s("%d%c",&x,&y,1,1);
						yy = (towlower(y) - 'a');
						x--;
						if(x>=0 && yy>=0 && x<MAX && yy<MAX && moves[x][y])
						{
							make_move(board,x,yy,player_c);
							no_of_moves++;
							break;
						}
						else
						{
							printf("Not a valid move, try again.\n");
						}
					}
				}
				else if(++invalid_moves<2)
				{
					printf("\nYou have to pass, press (Y) return.\n");
					scanf_s(" %c",&again,1 );
				}
				else
				{
					printf("\nNeither of us can go,so the game is over.\n");
				}
				
			}
			else    /* It is the computer's turn */
			{
				if(valid_moves(board,moves,comp_c))
				{
					invalid_moves = 0;
					computer_move(board,moves,comp_c);
					no_of_moves++;
				}
				else
				{ 
					if(++invalid_moves<2)
					{
						printf("\n I have to pass, your go.\n");
					}
					else
					{
						printf("\nNeither of us can go,so the game is over.\n");
					}
				}
			}
			system("cls");
		}while(no_of_moves < MAX*MAX && invalid_moves < 2);
		/* Game is over */
	displayBoard(board);
	/* Get final score and display them */
	comp_score = user_score = 0;     /* Initial the score */
	for(row = 0; row < MAX; row++)
	{
		for(col = 0; col < MAX; col++)
		{
			comp_score += board[row][col] == comp_c;
			user_score += board[row][col] == player_c;
		}
	}
	printf("The final score is: \n");
	printf("Computer %d\nUser %d\n\n",comp_score,user_score);
	if(comp_score > user_score)
	{
		printf("Unfortunately， You are failed, Computer win....\n\n");
		printf("Don't lose confident. Failure is normal!\n\n");
	}
	else if(comp_score < user_score)
	{
		printf("Well done! You are so smart....\n");
	}
	else
	{
		printf("Saidly, No Winners...\n\n");
	}
	printf("Do you wanna again(y/n)？");
	scanf_s(" %c",&again,1);
	}while(towlower(again) == 'y');
	printf("\nGoodbye\n");
	system("pause");
	return 0;
}

void print_space(int num)
{
	for(int i=0; i<num; i++)
		printf(" ");
}

void displayBoard(char board[][MAX]){
	char col_label = 'a';
	int row = 0;
	print_space(SPACE+2);
	//diaplay the col
	for(int col = 0; col<MAX; col++)
	{	
		printf("   %c ",col_label+col);
	}
	printf("\n");
	//display the row
	for(int row = 0; row<MAX; row++)
	{
		//display the top line for the current row
		print_space(SPACE);
		printf("  +");
		for(int col=0; col<MAX; col++)
		{
			printf("----+");
		}
		printf("\n");
		print_space(SPACE);
		printf("%2d|",row+1);
		//print_space(SPACE);
		//display the counters in the current row
		for(int col=0; col<MAX; col++)
		{
			printf(" %c  |", board[row][col]);
		}
		printf("\n");	
	}
	//display the bottom line
	print_space(SPACE);
	printf("  +");
	for(int col=0; col<MAX; col++)
	{
		printf("----+");	
	}
	printf("\n");
}

int valid_moves(char board[][MAX],bool moves[][MAX],char player)
{
	int rowdelta = 0;		/* Row increment around a square */
	int coldelta = 0;		/* col increment around a square */
	int x = 0;				/* row index when searching */
	int y = 0;				/* col index when searching */
	int num_of_moves = 0;	/* Number of valid moves */
	/* Set the opponnent */
	char opponent = (player == player_c)?comp_c : player_c;
	/* Initial the moves array to false */
	for(int row = 0; row<MAX; row++)
	{
		for(int col = 0; col<MAX; col++)
		{
			moves[row][col] = false;
		}
	}
	/* Find squares for valid moves */
	/* A valid move must be on a blank square and must enclose */
	/* at least one opponent square between two player squares */
	for(int row = 0; row<MAX; row++)
	{
		for(int col = 0; col<MAX; col++)
		{
			if(board[row][col] != ' ')	/* if it is not a blank square ,so go to the next*/
			{
				continue;
			}
			/* Check all the squares around the blank square for the opponents counter */			
			for(rowdelta = -1; rowdelta<= 1;rowdelta++)
			{
				for(coldelta = -1; coldelta<= 1; coldelta++)
				{
					/* Don't check outside the array and the current square */
					if(row+rowdelta<0||col+coldelta<0||row+rowdelta>=MAX||col+coldelta>=MAX
						||(rowdelta==0&&coldelta==0))
					{
						continue;
					}
					/* Now check the square*/
					if(board[row+rowdelta][col+coldelta] == opponent)
					{
						/* If we find the opponent, move in the delta direction */
						/* over opponent counters searching for a player counter */
						/* move to the opponent square*/
						x = row + rowdelta;
						y = col + coldelta;
						/* Look for a player square in the delta direction */
						for(; ; )
						{
							/* Go to next square in the delta direction */
							x += rowdelta;
							y += coldelta;
							/* If we outside the array, so give up */
							if(x < 0 || x >= MAX || y < 0 || y >= MAX)
							{
								break;
							}
							/* If we find a blank square, also give up */
							if(board[x][y] == ' ')
							{
								break;
							}
							/* If the square has a player counter, then we have a valid move */
							if(board[x][y] == player)
							{
								moves[row][col] = true;		/* Mark as valid */
								num_of_moves ++;			/* Increment the valid moves */
								break;						/* Go check another square */
							}
						}
					}
				}
			}
		}
	}
	return num_of_moves; /* Return the number of moves player can go*/
}
/* Player makes move */
void make_move(char board[][MAX],int row,int col,char player)
{
	int rowdelta = 0;
	int coldelta = 0;
	int x = 0;
	int y = 0;
	char opponent = (player == player_c)? comp_c : player_c;
	board[row][col] = player;
	/* Check all the squares around the blank square for the opponents counter */			
	for(rowdelta = -1; rowdelta<= 1;rowdelta++)
	{
		for(coldelta = -1; coldelta<= 1; coldelta++)
		{
			/* Don't check outside the array and the current square */
			if(row+rowdelta<0||col+coldelta<0||row+rowdelta>MAX||col+coldelta>MAX
				||(rowdelta==0&&coldelta==0))
			{
				continue;
			}
			/* Now check the square*/
			if(board[row+rowdelta][col+coldelta] == opponent)
			{
				/* If we find the opponent, move in the delta direction */
				/* over opponent counters searching for a player counter */
				/* move to the opponent square*/
				x = row + rowdelta;
				y = col + coldelta;
				/* Look for a player square in the delta direction */
				for(; ; )
				{
					/* Go to next square in the delta direction */
					x += rowdelta;
					y += coldelta;
					/* If we outside the array, so give up */
					if(x < 0 || x >= MAX || y < 0 || y >= MAX)
					{
						break;
					}
					/* If we find a blank square, also give up */
					if(board[x][y] == ' ')
					{
						break;
					}
					/* If the square has a player counter, then we have a valid move */
					if(board[x][y] == player)
					{
						while(board[x-=rowdelta][y-=coldelta] == opponent)
						{
							board[x][y] = player;	/* Just replace it */			
						}
						break;					   /* Go check another square */	
					}
				}
			}
		}
	}
}

int get_score(char board[][MAX],char player)
{
	int score = 0;
	char opponent = (player == player_c) ? comp_c : player_c;
	/* Check for all board squares */
	for(int row = 0; row < MAX; row++)
		for(int col = 0; col < MAX; col++)
		{
			score -= board[row][col] == opponent; /* Decrement for the opponent*/
			score += board[row][col] == player ; /* Increment for the player */
		}
		return score;
}

int best_move(char board[][MAX],bool moves[][MAX],char player)
{
	char opponent = (player == player_c) ? comp_c : player_c;
	char new_board[MAX][MAX] = {0};
	int score = 0;
	int new_score = 0;
	/* Check all the valid moves for the best */
	for(int row = 0; row < MAX; row++)
	{
		for(int col = 0; col < MAX; col++)
		{
			if(!moves[row][col])		/* ignore the unvaild moves */
			{
				continue;
			}
			memcpy(new_board,board,sizeof(new_board)); /* Copy the board to the new_board */
			/* Make move on the board copy */
			make_move(new_board,row,col,player);
			/* Get score for the move */
			new_score = get_score(new_board,player);
			if(new_score > score)
			{
				score = new_score;
			}
		}	
	}
	return score;
}

void computer_move(char board[][MAX],bool moves[][MAX],char player)
{
	int best_row = 0;
	int best_col = 0;
	int new_score = 0;
	int score = 100;
	char temp_board[MAX][MAX];
	bool temp_moves[MAX][MAX];
	char opponent = (player == player_c) ? comp_c : player_c;
	for(int row = 0; row < MAX; row++)
	{
		for(int col = 0; col < MAX; col++)
		{
			if(!moves[row][col])
			{
				continue;
			}
			memcpy(temp_board,board,sizeof(temp_board));
			make_move(temp_board,row,col,player);
			valid_moves(temp_board,temp_moves,opponent);
			new_score = best_move(temp_board,temp_moves,opponent);
			if(new_score < score)
			{
				score = new_score;
				best_row = row;
				best_col = col;
			}
		}		
	}
	make_move(board,best_row,best_col,player);
	//printf("Computer move: row-%d  col-%d",best_row,best_col);	
}