/* Tic tac toe game with minimax A.I.
 * by yetimach */
#include <stdio.h>
#include <stdlib.h>

#define FALSE 0
#define CPV_INT 1 // computer play value
#define HPV_INT 2  // human play value
#define OPEN_SQUARE 0

char xo[] = "0123456789"; // changes will always be made to xo and then xo_ints
// will be updated. 
// initialize ox_ints to OPEN_SQUARES
int xo_ints[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; // xo_ints will be used to check for positions, like evaluate
int evaluate = 0;
char hpv = 'X', cpv = 'O';     // human play value and computer play value
int main()
{              
	void clear();
	int game();
    while (game() != -1)  
		;
	clear();
	system("cowsay Have a nice day!");
	return 0;
}
void update_xo_ints(char *xo, int *xo_ints){
	for (int i = 1; i <= 9; i++){  
		if (xo[i] == cpv)
			xo_ints[i] = CPV_INT;
		else if (xo[i] == hpv)
			xo_ints[i] = HPV_INT;
		else
			xo_ints[i] = OPEN_SQUARE;
	}
}
void clear(){
	system("clear");
}

//take input from user
int read_play(){
	char play_char;
	play_char = getchar();
	int c;
	while ((c = getchar()) != '\n')
		;
	int play_int = play_char;
	play_int -= '0';
	if (play_int >= 1 && play_int <= 9 && (xo[play_int] != cpv && xo[play_int] != hpv))
		return play_int;
	else {  
		printf("\n\n\tInvalid entry. Try again: ");
		return -1;
	}
}
// implement read play above, read human play 
int read_hp(){
	int play;
	while ((play = read_play()) == -1)
		;
	return play;
}

void process_game(int evaluate){
	void remove_nums_from_xo(char*);
	void print_grid(char*);
	if (evaluate == CPV_INT){  
		remove_nums_from_xo(xo);
		clear();
		print_grid(xo);
		printf("\n\n\tThe computer wins.\n\n");
	}else if (evaluate == 3){  
		clear();
		print_grid(xo);
		printf("\n\n\tCat's game!\n\n");
	}
}

void print_grid(char *xo){
	int check_for_winner(int*);
	printf("\n\n\t   Tic Tac Toe");
	printf("\n\n\n\t     |     |     \n\t  %c  |  %c  |  %c  \n\t-----|-----|-----\n\t"
	"  %c  |  %c  |  %c  \n\t-----|-----|-----\n\t  %c  |  %c  |  %c  \n\t"
	"     |     |\n\n\n", xo[1], xo[2], xo[3], xo[4], xo[5], xo[6], 
	xo[7], xo[8], xo[9]);
}

void human_play(char *xo, int evaluate){
	if (evaluate != 0)  
		return;
	else{  
		printf("\n\n\tEnter the number of the\n\tsquare you want to play: ");
		int hp = read_hp();
		xo[hp] = hpv;
	}
}


// return 1 for computer win, 2 for human win, 3 for tie, 0 for unfinished
int check_for_winner(int *xo_ints){
	for (int i = 1; i <= 9; i +=3) {  
		if (xo_ints[i] != OPEN_SQUARE) {  
			if (xo_ints[i] == xo_ints[i+1] && xo_ints[i+1] == xo_ints[i+2])
				return xo_ints[i]; 
		}
	}
	for (int i = 1; i <= 3; i++){  
		if (xo_ints[i] != OPEN_SQUARE){  
			if (xo_ints[i] == xo_ints[i+3] && xo_ints[i+3] == xo_ints[i+6])
				return xo_ints[i];
		}
	}
	if (xo_ints[1] != OPEN_SQUARE){  
		if (xo_ints[1] == xo_ints[5] && xo_ints[5] == xo_ints[9])
				return xo_ints[1];
	}
	if (xo_ints[3] != OPEN_SQUARE){  
		if (xo_ints[3] == xo_ints[5] && xo_ints[5] == xo_ints[7])
				return xo_ints[3];
	}
	int tie = 1;
	for (int i = 1; i <= 9; i++){  
		if (xo_ints[i] == OPEN_SQUARE)  
			tie = 0;
	}
	if (tie)
		return 3;
	return 0;
}

void computer_play(char *xo, int evaluate){
	if (evaluate != 0){  
		return;
	}
	int find_best_move(int*);
	int cp = find_best_move(xo_ints);
	xo[cp] = cpv;
}


int game(){
	int go_again();
	int reset(char*, int*, int);
	while (evaluate == 0){
	clear();
	print_grid(xo);
	human_play(xo, evaluate);
	update_xo_ints(xo, xo_ints);
	evaluate = check_for_winner(xo_ints);
	computer_play(xo, evaluate);
	update_xo_ints(xo, xo_ints);
	evaluate = check_for_winner(xo_ints);
	}	
	process_game(evaluate);
	evaluate = reset(xo, xo_ints, evaluate);
	return go_again();
}

int max(int v1, int v2){
	return (v1 > v2) ? v1 : v2;
}

int min(int v1, int v2){
	return (v1 < v2) ? v1 : v2;
} 

int minimax( int *xo_ints, int depth, int is_max){
// check if finished
	int score = check_for_winner(xo_ints);
	if (score == CPV_INT)
		return score;
	if (score == HPV_INT)
		return -1;
	if (score == 3)
		return 0;
// maximize for computer
	if (is_max){
		int best = -1000;
		for (int i = 1; i < 10; i++){
			if (xo_ints[i] == OPEN_SQUARE){  
				xo_ints[i] = CPV_INT;
				best = max( best, minimax(xo_ints, depth+1, !is_max));
				xo_ints[i] = OPEN_SQUARE;
			}
		}
		return best;
	}else{
// minimize for human
		int best = 1000;
		for (int i = 1; i < 10; i++){
			if (xo_ints[i] == OPEN_SQUARE){
				xo_ints[i] = HPV_INT;
				best = min(best, minimax(xo_ints, depth+1, !is_max));
				xo_ints[i] = OPEN_SQUARE;
			}
		}
		return best;
	}
}
// impliment minimax to find best_move
int find_best_move(int *xo_ints){
	int best_val = -1000;
	int best_move = -1;
	for (int i = 1; i < 10; i++){
		if (xo_ints[i] == OPEN_SQUARE){
			xo_ints[i] = CPV_INT;
			int move_val = minimax(xo_ints, 0, FALSE);
			xo_ints[i] = OPEN_SQUARE;
			if (move_val > best_val){
				best_move = i;
				best_val = move_val;
			}
		}
	}
	return best_move;
}

int go_again(){
	printf("\n\n\tPlay again [y/n] ");
	char again = getchar();	
	char c;
	while((c = getchar()) != '\n')
		;
	return again == 'y' ? 0 : -1;
}

int reset(char *xo, int *xo_ints, int evaluate){
	for (int i = 1; i < 10; i++){
		xo[i] = i + '0';
		xo_ints[i] = OPEN_SQUARE;
	}
	return 0;
}
// to print out a neater board if the computer wins
void remove_nums_from_xo(char *xo){  
	for (int i = 1; i <= 9; i++)  
		if (xo[i] != cpv && xo[i] != hpv)
			xo[i] = ' ';
}