#include <stdio.h>
#include <stdlib.h>


struct gnode {

      struct gnode * child [8];
      int value;
      int best_move;
}


char check();
void init_root(struct gnode *);
void init_matrix();
void get_player_move(void);
void get_computer_move(struct gnode *);
void disp_matrix(void);
void get_input(void);
void validate_game(void);


struct gnode * gn_root;


int end = 1;
int avail_moves = 0;
char matrix[3][3];
int moves [9];
int move = 1;






int main() {



//for move, 0 means player turn, 1 means comp turn


	system("clear");

        init_matrix();
	init_root(gn_root);
	print("This is a game of Tic Tac Toe.\n You will be playing against the computer.\n");
	disp_board();
        while (end) {
         
		get_input();

	}

}


 void get_input()

 {

	 switch(move) {

		 case 0 :
                      get_player_move();
		      break;

		 case 1 :     
                      get_computer_move(gn_root);
		      break;

		 default:
		      break;

	 }

 }


void init_root(struct gnode * gn ) {

  gn = (struct gnode *) malloc(sizeof(struct gnode));
  gn->best_move = moves[0];
  gn->value = 0;
  move = 1; 
  
}

void init_matrix ()
{
	int i,j;

	for (i = 0; i < 3; i++){ 
              for (j=0; j < 3; j++) {
		      matrix[i][j] = ' ';
	      }
	}
}


void disp_matrix(void) {

	printf("%c|%c|%c\n",matrix[0][0],matrix[0,1],matrix[0,2]);
        printf("%c|%c|%c\n",matrix[1][0],matrix[1,1],matrix[1,2]);
        printf("%c|%c|%c\n",matrix[2][0],matrix[2,1],matrix[2,2]);

}


void get_player_move() {

 int x;
 int y;
 char buf [5];
 char i = 'X'; // X for player, O for cpu

 printf("Enter X,Y coordinates for your move:");
 sscanf(buf,"%u,%u",&x,&y);

  if ( (x < 0 && x > 2) && ( y < 0 && y > 2) ) {

                printf("Invalid coordinates. Please use coordintes between 0 and 2 for X or Y.");
		
		}

    matrix[x][y] = i;
    validate_game();
    disp_matrix();
    move = 1;


    }


 void get_computer_move( struct gnode * gns) {
    
   
   
   int i,j;
   int Min = 0, Max = 0;
   int t = 0;
  
 struct gnode * gn = gns;
   validate_game();

   for(i=0;i<3;i++) {

	  for(j=0;j<3;j++) {

             if (matrix[i][j] = ' ') {
		     t++;
		     moves[avail_moves] = t;
		     avail_moves++;

	     }


	  }
  }

 
 for (i = 0; i < avail_moves; i++)
      {
        gn->child[i] = (struct gnode *) malloc(sizeof(struct gnode));
        gn->child[i]->value = 0;
      }

  
     gn->best_move = moves[0];
     Max = gn->child[0]->value;
     Min = gn->child[0]->value;

     
     move = !(move);

     if (move) {
         
       for (i = 1; i < avail_moves;i++)
       {
	       if (gn->child[i]->value > Max)
	       {
		       Max = gn->child[i]->value;
		       gn->best_move = moves[i];
		       if (Max == 1); break;
	       }

	      }

       gn->value = Max;
     }
     else
     {
     
      for (i = 1; i < avail_moves; i++)
	    if( gn->child[i]->value < Min) {
		  
		    Min = gn->child[i]->value;
		    gn->child[i]->best_move = moves[i];
		    if (Min == -1) break;
	    }
      gn->value = Min;

     }


     for (i=0; i < avail_moves;i++) {

	     free(gn->child[i]);

     }

 }




 void validate_game ()

{

  char i;
 if(!avail_moves) end = 0;

 if (( i = check()) == 'X')
 {
	 printf("YOU WIN!");
         end = 0;
 
 }


 else if ((i = check()) == 'O') {

	 printf("YOU LOSE!");
	 end = 0;
 }

 else return;
}


 char check() {

  int i;

  for(i=0; i<3; i++)  /* check rows */
    if(matrix[i][0]==matrix[i][1] &&
       matrix[i][0]==matrix[i][2]) return matrix[i][0];

  for(i=0; i<3; i++)  /* check columns */
    if(matrix[0][i]==matrix[1][i] &&
       matrix[0][i]==matrix[2][i]) return matrix[0][i];

  /* test diagonals */
  if(matrix[0][0]==matrix[1][1] &&
     matrix[1][1]==matrix[2][2])
       return matrix[0][0];

  if(matrix[0][2]==matrix[1][1] &&
     matrix[1][1]==matrix[2][0])
       return matrix[0][2];

  return ' ';


 }