#include <stdio.h>
#include <alloc.h>
#include <string.h>
#include <process.h>

#define TRUE 1
#define FALSE 0
#define NUMBER_OF_LEVELS 9
#define DEBUG FALSE

struct answer {
  int value;
  int i_cord;
  int j_cord;
};

/* function prototypes */

struct answer ve(char [3][3], int, char);
int evaluate(char [3][3], char);
void disp_matrix(char [3][3]);
void get_player_move(char [3][3]);
void init_matrix(char [3][3]);
char check(char [3][3]);
void get_computer_move(char [3][3]);
int is_terminal(char [3][3]);
struct answer max(struct answer, struct answer);

/*********************************************************/

int main() {
  char board[3][3];
  char done = ' ';

  printf("This is the game of tic tac toe.\n");
  printf("You will be playing against the computer.\n");
  printf("The board coordinates are:\n");
  printf("1 1|1 2|1 3\n");
  printf("---|---|---\n");
  printf("2 1|2 2|2 3\n");
  printf("---|---|---\n");
  printf("3 1|3 2|3 3\n\n");

  init_matrix(board);  /* initialize the playing matrix */

  /* loop thru this mess until done */

  do {
	 get_player_move(board);     /* ask the user for a move */
	 done = check(board);        /* see if winner */
	 if(done != ' ') break;      /* winner!*/
	 get_computer_move(board);   /* get a computer move */
	 disp_matrix(board);         /* display the play matrix */
	 done = check(board);        /* see if winner */
  } while(done == ' ');

  if(done == 'X') printf("You won!\n");
	 else printf("I won!!!!\n");

  disp_matrix(board); /* show final play positions */

  return 0;
}

/**********************************************************/

int evaluate(char board[3][3], char player) {

  /* performs static board evaluation, returns the number of
	  rows, columns and diagionals remaining open for player
	  minus the number remaining open for the opponent
	  returns 9 for a wining position, and -9 for a losing
	  position.  Blanks rows are not checked for since these
	  end up being valued by both players and cancel each other
	  out. */

  static int XX_ = 'X' + 'X' + ' ';  /* 208 */
  static int X__ = 'X' + ' ' + ' ';  /* 152 */
  static int OO_ = 'O' + 'O' + ' ';  /* 190 */
  static int O__ = 'O' + ' ' + ' ';  /* 143 */
  static int XXX = 'X' + 'X' + 'X';  /* 264 */
  static int OOO = 'O' + 'O' + 'O';  /* 137 */

  int value_x = 0, value_o = 0;
  register int i, sum;

  /* check rows */

  for(i=0;i<3;i++) {
	 sum = board[i][0] + board[i][1] + board[i][2];
    if(sum == XX_ || sum == X__) value_x++;
	 if(sum == OO_ || sum == O__) value_o++;
	 if(sum == XXX)
		if(player == 'X') return 9;
        else return -9;
	 if(sum == OOO)
		if(player == 'O') return 9;
        else return -9;
  }

  /* check columns */

  for(i=0;i<3;i++) {
	 sum = board[0][i] + board[1][i] + board[2][i];
	 if(sum == XX_ || sum == X__) value_x++;
	 if(sum == OO_ || sum == O__) value_o++;
	 if(sum == XXX)
		if(player == 'X') return 9;
        else return -9;
	 if(sum == OOO)
		if(player == 'O') return 9;
        else return -9;
  }

  /* check diagonals */

  sum = board[0][0] + board[1][1] + board[2][2];
  if(sum == XX_ || sum == X__) value_x++;
  if(sum == OO_ || sum == O__) value_o++;
  if(sum == XXX)
    if(player == 'X') return 9;
      else return -9;
  if(sum == OOO)
    if(player == 'O') return 9;
      else return -9;


  sum = board[2][0] + board[1][1] + board[0][2];
  if(sum == XX_ || sum == X__) value_x++;
  if(sum == OO_ || sum == O__) value_o++;
  if(sum == XXX)
    if(player == 'X') return 9;
      else return -9;
  if(sum == OOO)
    if(player == 'O') return 9;
      else return -9;

  if(player == 'X') return value_x - value_o;
		else return value_o - value_x;
}

/*********************************************************/

struct answer ve ( char brd[3][3],
			          int looklevel,
			          char player ) {
  int i, j, value, move_count;
  struct answer ans, new_move;
  int moves[2][9]; /* stores indexes of possible moves */
  char board[3][3], ch;

  /* if current board it terminal or levels = 0 then return */

  if((looklevel == 0) || (is_terminal(brd) == TRUE)) {
	 ans.value = evaluate(brd, player);
	 return ans;
  }

  looklevel--; /* decrement the level we are at */

  /* find the possible moves from current board */

  move_count = 0;
  for (i=0; i < 3; ++i) {
	 for (j=0; j < 3; ++j) {
		if (brd[i][j] == ' ') {
		  moves[0][move_count] = i;
		  moves[1][move_count] = j;
		  move_count++;
      }
	 }
  }

  /* copy the input board to a local variable */

  for (i=0; i < 3; ++i)
    for (j=0; j < 3; ++j) 
		board[i][j] = brd[i][j];

  /* traverse the first subtree */

  /* make the move on the board */

  board[moves[0][0]][moves[1][0]] = player;

  if(player == 'X') player = 'O'; else player = 'X';
  ans = ve(board, looklevel, player);
  if(player == 'X') player = 'O'; else player = 'X';
  ans.i_cord = moves[0][0];
  ans.j_cord = moves[1][0];
  ans.value = -ans.value;

  /* undo the move on the board */

  board[moves[0][0]][moves[1][0]] = ' ';

  /* traverse the remaining subtrees */

  for(i = 1; i < move_count; i++) {

    /* make the move on the board */

    board[moves[0][i]][moves[1][i]] = player;

    if(player == 'X') player = 'O'; else player = 'X';
	 new_move = ve(board, looklevel, player);
	 if(player == 'X') player = 'O'; else player = 'X';
	 new_move.i_cord = moves[0][i];
	 new_move.j_cord = moves[1][i];
	 new_move.value = - new_move.value;
	 ans = max(ans, new_move);

    /* undo the move on the board */

    board[moves[0][i]][moves[1][i]] = ' ';

  }

  return ans;

} /* end nextmove */

/*******************************************************/

struct answer max(struct answer x, struct answer y) {
  if(x.value > y.value) return x;
	 else return y;
}

/*******************************************************/

int is_terminal(char board[3][3]) {
/* check to see if board is terminal */
  int i, j;
  for (i=0; i < 3; ++i) {
	 for (j=0; j < 3; ++j) {
      if(board[i][j] == ' ') return FALSE;
	 }
  }
  return TRUE;	  
}


/**********************************************************/

/* Display the matrix on the screen. */

void disp_matrix(char matrix[3][3]) {
  int i;

  for(i=0;i<3;i++) {
	 printf(" %c | %c | %c\n",
	   matrix[i][0],matrix[i][1],matrix[i][2]);
    if(i < 2) printf("---|---|---\n");
  }
} /* end disp_matrix */

/********************************************************/

/* Get a player's move. */

void get_player_move(char matrix[3][3]) {

  int x, y;

  for(;;) {
    printf("Enter coordinates for your X (row column): ");
    scanf("%d%d",&x,&y);
	 if((x > 0) && (x < 4) && (y > 0) && (y < 4)) break;
    printf("\nIllegal coordinate(s) entered, try again\n");
  }

  x--; y--;

  if(matrix[x][y] != ' ') {
    printf("Invalid move, try again.\n");
    get_player_move(matrix);
  }
  else matrix[x][y] = 'X';
} /* end get_player_move */

/********************************************************/

/* initialize the matrix to blanks */

void init_matrix(char matrix[3][3]) {
  int i, j;

  /* initialize the board */

  for (i=0; i < 3; ++i)
    for (j=0; j < 3; ++j) 
      matrix[i][j] = ' '; 
}  /* end init_matrix */

/********************************************************/

/* See if there is a winner. */
/* returns 'X' if X is a winner,
   returns 'O' if O is a winner,
   returns ' ' if no winner yet */

char check(char m[3][3]) {

  int i,j;

  /* check rows */

  for(i=0;i<3;i++) {
	 if(m[i][0] == m[i][1] &&
		 m[i][1] == m[i][2] &&
		 m[i][0] != ' ') return m[i][0];
  }

  /* check columns */

  for(i=0;i<3;i++) {
	 if(m[0][i] == m[1][i] &&
		 m[1][i] == m[2][i] &&
		 m[0][i] != ' ') return m[0][i];
  }

  /* check diagionals */

	 if(m[0][0] == m[1][1] &&
		 m[1][1] == m[2][2] &&
		 m[0][0] != ' ') return m[0][0];

	 if(m[2][0] == m[1][1] &&
		 m[1][1] == m[0][2] &&
		 m[0][2] != ' ') return m[0][2];

  /* check for cats game */

  while(TRUE) {
    for (i=0; i < 3; ++i)
      for (j=0; j < 3; ++j) 
        if(m[i][j] == ' ') goto out_of_here; 

	 printf("cats game\n");
	 disp_matrix(m); /* show final play positions */
    exit(0);
  }
  
  out_of_here: return ' ';
} /* end check */

/*****************************************************/

void get_computer_move(char brd[3][3]) {

  /* get the computer move from nextmove */

  int looklevel = NUMBER_OF_LEVELS;
  char player = 'O';
  struct answer move;

  move = ve(brd, looklevel, player );

  brd[move.i_cord][move.j_cord] = player;


} /* end get_computer_move */

/*******************************************************/