//*****************************
// Filename: ai.cpp
// Author: Aaron Rogers
// Updated: 09/07/02
// Purpose: Tic Tac Toe game AI
//*****************************

#include "ai.h"
#include "stdlib.h"


//**********************************
// Function: ai_move()
// Purpose: Determines the AI's move
//**********************************
u8 ai_move(TICTACTOE *ttt, u8 skill)
{
	// Make sure there is an open spot or there's a problem
	if (ttt->gos() == 0) return 9;

	// Variables
	u8 turn = ttt->gt(); // Stores the current turn
	u8 the_spot; // The spot that will be returned

	// Some of the following moves are only made depending 
	// on the AI's skill level

	// Is there a winning move
	if ((skill == 3 ) || (skill == 4) || (skill == 5)) {
		the_spot = move_to_win(ttt, turn);
		if (the_spot != 9) return the_spot;
	}

	// Is there a blocking move
	if ((skill == 2 ) || (skill == 3 ) || (skill == 4) || (skill == 5)) {
		the_spot = move_to_block(ttt, turn);
		if (the_spot != 9) return the_spot;
	}

	// Is there a good move to make
	if (skill == 5) {
		the_spot = move_to_good(ttt, turn);
		if (the_spot != 9) return the_spot;
	}
	
	// Is a corner open
	if ((skill == 4) || (skill == 5)) {
		the_spot = move_to_corner(ttt);
		if (the_spot != 9) return the_spot;
	}

	// Is the center open
	if ((skill == 4) || (skill == 5)) {
		the_spot = move_to_center(ttt);
		if (the_spot != 9) return the_spot;
	}

	// Pick a random spot
	the_spot = move_to_open(ttt);
	if (the_spot != 9) return the_spot;

	return 9; // This should never happen
}


//*********************************
// Function: move_to_win()
// Purpose: Is there a winning move
//*********************************
u8 move_to_win(TICTACTOE *ttt, u8 turn)
{	
	// Check each spot to see if there is a way to win
	for (u8 i = 0; i < 9; ++i) {
		if (ttt->who(i) == 0 && (win_move(ttt, i, turn) != 9)) return i;
	}

	return 9;
}  // End of move_to_win()


//**********************************
// Function: move_to_block()
// Purpose: Is there a blocking move
//**********************************
u8 move_to_block(TICTACTOE *ttt, u8 turn)
{
	// Basically we are calling win_move() 
	// pretending to be the other player.  

	// Change turn because we want to block the win
	turn = other_turn(turn);
	
	// Check each spot to see if there is a way to win
	for (u8 i = 0; i < 9; ++i) {
		if (ttt->who(i) == 0 && (win_move(ttt, i, turn) != 9)) return i;
	}

	return 9;
}  // End of move_to_block()


//****************************
// Function: move_to_good()
// Purpose: Picks a smart move
//****************************
u8 move_to_good(TICTACTOE *ttt, u8 turn)
{
	// Change turn 
	turn = other_turn(turn);

	// Open squares
	u8 os = ttt->gos();

	// The other player has made one move
	if (os == 8) {
		// Check to see if the center is open
		// Same as move_to_center()
		if (ttt->who(4) == 0) return 4;
	}

	if (os == 6) {
		// Check if opponent picked opposite corners
		// If so, randomly pick a middle outside spot that forces
		// the opponent to block an AI win instead of setting one up
		if ((ttt->who(0) == turn) && (ttt->who(8) == turn) || 
			(ttt->who(2) == turn) && (ttt->who(6) == turn)) {
			u8 rand_num = rand()%4;
			// *** return ((rand_num * 2) + 1); ***
			switch (rand_num) {
			case 0:
				if(ttt->who(1) == 0) return 1;
				break;
			case 1:
				if(ttt->who(1) == 0) return 3;
				break;
			case 2:
				if(ttt->who(1) == 0) return 5;
				break;
			case 3:
				if(ttt->who(1) == 0) return 7;
				break;
			default:
				if(ttt->who(1) == 0) return 1;
				break;
			}
		}

		// Check for two sides, at most one of which is a corner
		// If so, randomly pick a middle outside spot that forces
		// the opponent to block an AI win instead of setting one up
		if (((ttt->who(1) == turn) && (ttt->who(3) == turn)) || 
			((ttt->who(1) == turn) && (ttt->who(6) == turn)) || 
			((ttt->who(2) == turn) && (ttt->who(3) == turn))) {
			if (ttt->who(0) == 0) return 0;
		}
		if (((ttt->who(1) == turn) && (ttt->who(5) == turn)) || 
			((ttt->who(1) == turn) && (ttt->who(8) == turn)) ||
			((ttt->who(0) == turn) && (ttt->who(5) == turn))) {
			if (ttt->who(2) == 0) return 2;
		}
		if (((ttt->who(0) == turn) && (ttt->who(7) == turn)) || 
			((ttt->who(3) == turn) && (ttt->who(7) == turn)) || 
			((ttt->who(3) == turn) && (ttt->who(8) == turn))) {
			if (ttt->who(6) == 0) return 6;
		}
		if (((ttt->who(2) == turn) && (ttt->who(7) == turn)) || 
			((ttt->who(5) == turn) && (ttt->who(6) == turn)) ||
			((ttt->who(5) == turn) && (ttt->who(7) == turn))) {
			if (ttt->who(8) == 0) return 8;
		}

		// *** don't know why these bugs are happening ***
		// *** the computer often takes spot[1]        ***
		if ((ttt->who(0) == turn) && (ttt->who(4) == turn)) return 2;
		if ((ttt->who(2) == turn) && (ttt->who(4) == turn)) return 8;
		if ((ttt->who(6) == turn) && (ttt->who(4) == turn)) return 0;
		if ((ttt->who(8) == turn) && (ttt->who(4) == turn)) return 6;
		
	}

	return 9;
} // End of move_to_good()


//********************************
// Function: move_to_corner()
// Purpose: Is there a corner open
//********************************
u8 move_to_corner(TICTACTOE *ttt)
{
	u8 rand_num = rand()%4; // *** the bug may be here ***
	switch (rand_num) {
	case 0:
		if(ttt->who(0) == 0) return 0;
		break;
	case 1:
		if(ttt->who(2) == 0) return 2;
		break;
	case 2:
		if(ttt->who(6) == 0) return 6;
		break;
	case 3:
		if(ttt->who(8) == 0) return 8;
		break;
	default: // Should never happen
		if(ttt->who(0) == 0) return 0;
		break;
	}

	return 9;
}  // End of move_to_corner()


//****************************
// Function: move_to_center()
// Purpose: Is the center open
//****************************
u8 move_to_center(TICTACTOE *ttt)
{
	if (ttt->who(4) == 0) return 4;

	return 9;
}  // End of move_to_center()


//************************************
// Function: move_to_open()
// Purpose: Move to a random open spot
//************************************
u8 move_to_open(TICTACTOE *ttt)
{
	for (int i = 0; i < 9; ++i) {
		u8 rand_num = rand()%8;
		if (ttt->who(rand_num) == 0) { // open spot
			return rand_num;
		}
	}
			
	return 9;
}  // End of move_to_open()


//******************************************
// Function: win_move()
// Purpose: Checks whether the three squares 
//          passed are a winning combination
//******************************************
u8 win_move(TICTACTOE *ttt, u8 x, u8 turn)
{
	if (x == 0 && ((turn == ttt->who(1)) && (turn == ttt->who(2)))) return x;
	if (x == 0 && ((turn == ttt->who(3)) && (turn == ttt->who(6)))) return x;
	if (x == 0 && ((turn == ttt->who(4)) && (turn == ttt->who(8)))) return x;
	if (x == 1 && ((turn == ttt->who(0)) && (turn == ttt->who(2)))) return x;
	if (x == 1 && ((turn == ttt->who(4)) && (turn == ttt->who(7)))) return x;
	if (x == 2 && ((turn == ttt->who(0)) && (turn == ttt->who(1)))) return x;
	if (x == 2 && ((turn == ttt->who(4)) && (turn == ttt->who(6)))) return x;
	if (x == 2 && ((turn == ttt->who(5)) && (turn == ttt->who(8)))) return x;
	if (x == 3 && ((turn == ttt->who(0)) && (turn == ttt->who(6)))) return x;
	if (x == 3 && ((turn == ttt->who(4)) && (turn == ttt->who(5)))) return x;
	if (x == 4 && ((turn == ttt->who(0)) && (turn == ttt->who(8)))) return x;
	if (x == 4 && ((turn == ttt->who(1)) && (turn == ttt->who(7)))) return x;
	if (x == 4 && ((turn == ttt->who(2)) && (turn == ttt->who(6)))) return x;
	if (x == 4 && ((turn == ttt->who(3)) && (turn == ttt->who(5)))) return x;
	if (x == 5 && ((turn == ttt->who(2)) && (turn == ttt->who(8)))) return x;
	if (x == 5 && ((turn == ttt->who(3)) && (turn == ttt->who(4)))) return x;
	if (x == 6 && ((turn == ttt->who(0)) && (turn == ttt->who(3)))) return x;
	if (x == 6 && ((turn == ttt->who(2)) && (turn == ttt->who(4)))) return x;
	if (x == 6 && ((turn == ttt->who(7)) && (turn == ttt->who(8)))) return x;
	if (x == 7 && ((turn == ttt->who(1)) && (turn == ttt->who(4)))) return x;
	if (x == 7 && ((turn == ttt->who(6)) && (turn == ttt->who(8)))) return x;
	if (x == 8 && ((turn == ttt->who(0)) && (turn == ttt->who(4)))) return x;
	if (x == 8 && ((turn == ttt->who(2)) && (turn == ttt->who(5)))) return x;
	if (x == 8 && ((turn == ttt->who(6)) && (turn == ttt->who(7)))) return x;

	return 9;
} // End of win_move()


//********************************************
// Function: other_turn()
// Purpose: Returns the other player's turn ID
//********************************************
u8 other_turn(u8 turn)
{
	// Change turn because we want to block the win
	if (turn == 1) {
		turn = 2;
	} else if (turn == 2) {
		turn = 1;
	}

	return turn;
} // End of other_turn()