/* Tic Tac Toe Demonstration Program, C compilable.                  */
/*                                                                   */
/* Created March 18, 1999, for use with Computer Science 101 at USC. */
/* Version 1.08. Last edited March 20, 1999.                         */
/* Copyright 1999 by Rick Wagner, all rights reserved.               */

#include <stdio.h>
#include <stdlib.h>   /* For malloc(), free(), and exit(). */
#include <conio.h>    /* For getch(). */

/* Node in the tic tac toe game tree: */
typedef struct node
{
  int iMetric;
  int iComputerMove;
  int iBestMove;
  struct node* gnChild[9];
  char cConfig[9];
} GameNode;

/* Function prototypes: */
void about();
void play(GameNode* gnGameRoot, char cChoice);
void drawBoard(char* board);
void constructGameNodeChildren(GameNode* gnNode, int n);
void destroyGameNodeChildren(GameNode* gnNode, int n);
int getHumanMove(char* board);
void makeComputerMove(GameNode* gnGameRoot, char* cBoardConfig);
void computerMove(GameNode* gn);
int getAvailableMoves(GameNode* gnNode, int* iAvailable);
int evaluation(char* board);

void main()
{
  int i = 0;
  char cChoice = 0;
  GameNode* gnGameRoot;

  /* Tell about the program: */
  about();

    /* Construct the game root GameNode: */
  gnGameRoot = malloc(sizeof(GameNode));

  while (1)                          /* Loop forever. */
  {
    /* Set the game root GameNode initial configuration: */
    for (i = 0; i < 9; i++)
    {
      gnGameRoot->cConfig[i] = '-';  /* Hyphen represents empty square. */
    }

    printf("\nWhom do you want to have the first move, human or computer?\n\n");
    printf("  h. Human goes first.\n");
    printf("  c. Computer goes first.\n\n");
    printf("Enter your selection: ");
    scanf("%c", &cChoice);
    fflush(stdin);

    /* Initiate play: */
    play(gnGameRoot, cChoice);

    printf("\nPlay again? (y/n) ");
    scanf("%c", &cChoice);
    fflush(stdin);
    if(cChoice != 'y') exit(0);
  }
}

void about()
{
  puts("               Tic Tac Toe Demonstration Program, C compilable.");
  puts("");
  puts("       Created March 18, 1999, for use with Computer Science 101 at USC.");
  puts("                  Version 1.08. Last edited March 20, 1999.");
  puts("              Copyright 1999 by Rick Wagner, all rights reserved.");
  puts("");
}

/* Allocate memory for the n children of a game node: */
void constructGameNodeChildren(GameNode* gnNode, int n)
{
  int i = 0;

  for (i = 0; i < n; i++)
  {
    gnNode->gnChild[i] = malloc(sizeof(GameNode));
  }
}

/* Free up the memory of no-longer-needed game node children. */
void destroyGameNodeChildren(GameNode* gnNode, int n)
{
  int i = 0;

  for (i = 0; i < n; i++)
  {
    free(gnNode->gnChild[i]);
  }
}

/* Play one game of tic tac toe. Human is X and goes first by default. */
void play(GameNode* gnGameRoot, char cFirstPlayer)
{
  int i = 0;
  int iCount = 0;               /* Number of moves can't exceed 9 */
  int iPlay = 1;                /* Play as long as this flag is true */
  int iStatus = 0;
  char cBoardConfig[9];         /* The Xs and Os played. */

  /* Make a copy of the initial game configuration (all hyphens). */
  for (i = 0; i < 9; i++)
  {
    cBoardConfig[i] = gnGameRoot->cConfig[i];
  }
  if (cFirstPlayer == 'c')
  {
    drawBoard(cBoardConfig);
    printf("The computer is thinking about his first move.");
  }
  while (iPlay)
  {
    if (iCount % 2 == 0)
    {
      if (cFirstPlayer == 'c')
      {
        makeComputerMove(gnGameRoot,  cBoardConfig);
      }
      else
      {
        drawBoard(cBoardConfig);
        cBoardConfig[getHumanMove(cBoardConfig)] = 'X';
      }
    }
    else
    {
      if (cFirstPlayer == 'c')
      {
        drawBoard(cBoardConfig);
        cBoardConfig[getHumanMove(cBoardConfig)] = 'X';
      }
      else
      {
        makeComputerMove(gnGameRoot,  cBoardConfig);
      }
    }
    iCount++;
    if (iCount > 8) iPlay = 0;
    iStatus = evaluation(cBoardConfig);          /* Check for three in a row. */
    if (iStatus != 0) iPlay = 0;;
  }
  drawBoard(cBoardConfig);
  if (iStatus == -1)
  {
    printf("\n\nGame over, the human player won.\n");
  }
  else
  {
    if (iStatus == 1)
    {
      printf("\n\nGame over, the computer player won.\n");
    }
    else
    {
      printf("\n\nGame over, draw.\n");
    }
  }
}

/* Draw the game board as characters on the screen. */
void drawBoard(char* board)
{
  int i = 0;

  printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n"); /* Get some vertical white space. */
  for (i = 0; i < 9; i++)
  {
    if (i % 3 == 0) printf("  ");             /* Left edge padding. */
    printf(" %c ", board[i]);                 /* Print the board character. */
    if ((i + 1) % 3 == 0) printf("\n\n");     /* Skip a line. */
  }
  printf("\n\n\n");
}

/* Get the human's move. */
int getHumanMove(char* board)
{
  int r = 0;
  int i = 0;
  int iNumAvailableMoves = 0;
  int iAvailable[9];
  int iNotCorrect = 1;

  for (i = 0; i < 9; i++)
  {
    if (board[i] == '-')
    {
      iAvailable[iNumAvailableMoves] = i;
      iNumAvailableMoves++;
    }
  }
  printf("Which square? (");
  for (i = 0; i < iNumAvailableMoves - 1; i++)
  {
    printf("%d, ", iAvailable[i] + 1);
  }
  printf("%d) ", iAvailable[iNumAvailableMoves - 1] + 1);
  while (iNotCorrect)
  {
    scanf("%d", &r);
    fflush(stdin);
    for (i = 0; i < iNumAvailableMoves; i++)
    {
      if ((r - 1) == iAvailable[i])
      {
        iNotCorrect = 0;
        break;
      }
    }
    if (iNotCorrect) /* Don't let the human input an unavailable move. */
    {
      printf("\nThat move is not available. Try again. ");
    }
  }
  return r - 1;      /* Translate from human's one-based index to zero-based index. */
}

void makeComputerMove(GameNode* gnGameRoot, char* cBoardConfig)
{
  int i = 0;
  int iNumAvailableMoves = 0;
  int iAvailable[9];

  /* Copy the board configuration to the root GameNode */
  for (i = 0; i < 9; i++)
  {
    gnGameRoot->cConfig[i] = cBoardConfig[i];
  }
  iNumAvailableMoves = getAvailableMoves(gnGameRoot, iAvailable);
  gnGameRoot->iBestMove = iAvailable[0];     /* Initialize the best move. */
  gnGameRoot->iMetric = 0;
  gnGameRoot->iComputerMove = 1;             /* It's the computer's turn to move. */

  /* Start the recursive search: */
  computerMove(gnGameRoot);

  cBoardConfig[gnGameRoot->iBestMove] = 'O'; /* Mark an O for the computer's move. */
}

/* The classic min-max algorithm. */
void computerMove(GameNode* gn)
{
  int i = 0;
  int j = 0;
  int iStatus = 0;             /* Game metric semaphore: 1 is computer won, -1 is human won. */
  int iNumAvailableMoves = 0;  /* Number of available moves (= branching factor). */
  int iAvailable[9];           /* Available move indices. */
  int iMin = 0;
  int iMax = 0;

  iNumAvailableMoves = getAvailableMoves(gn, iAvailable);

  /* See if the game is over */
  iStatus = evaluation(gn->cConfig);

  if (iStatus != 0 || iNumAvailableMoves == 0)           
  {
    /* Game is over, bottom of tree (at a leaf). Carry the outcome back up. */
    gn->iMetric = iStatus;
  }
  else 
  {
    /* Game is not over, keep recursion going... */
    /* Construct my children: */
    constructGameNodeChildren(gn, iNumAvailableMoves);   /* One child to try each available move. */

    /* Spawn by recursion: */
    for (i = 0; i < iNumAvailableMoves; i++)
    {
      /* Toggle the computer move flag: */
      gn->gnChild[i]->iComputerMove = !(gn->iComputerMove);
      gn->gnChild[i]->iMetric = 0;

      /* Copy the child initial board configuration from the parent: */
      for (j = 0; j < 9; j++)
      {
        gn->gnChild[i]->cConfig[j] = gn->cConfig[j];
      }
      /* Each child makes a different available move: */
      if (gn->iComputerMove)
      {
        gn->gnChild[i]->cConfig[iAvailable[i]] = 'O';
      }
      else
      {
        gn->gnChild[i]->cConfig[iAvailable[i]] = 'X';
      }
      /* Recursion */
      computerMove(gn->gnChild[i]);
    }
    /* All recursion is complete now. Initialize the default best move */
    gn->iBestMove = iAvailable[0];
    iMax = gn->gnChild[0]->iMetric;
    iMin = gn->gnChild[0]->iMetric;

    /* Maximize on the computer's move, minimize on the human's move. */
    if (gn->iComputerMove)
    {
      /* It's the computer's move, search the children for the best outcome (1). */
      for (i = 1; i < iNumAvailableMoves; i++)
      {
        if (gn->gnChild[i]->iMetric > iMax)
        {
          iMax = gn->gnChild[i]->iMetric;
          gn->iBestMove = iAvailable[i];
          if (iMax == 1) break;
        }
      }
      gn->iMetric = iMax;
    }
    else
    {
      /* It's the human's move, search the children for the worst outcome (-1). */
      for (i = 1; i < iNumAvailableMoves; i++)
      {
        if (gn->gnChild[i]->iMetric < iMin)
        {
          iMin = gn->gnChild[i]->iMetric;
          gn->iBestMove = iAvailable[i];
          if (iMin == -1) break;
        }
      }
      gn->iMetric = iMin;
    }

    /* Recursion is complete and we've gathered the information: destroy the children. */
    destroyGameNodeChildren(gn, iNumAvailableMoves);
  }
}

int getAvailableMoves(GameNode* gnNode, int* iAvailable)
{
  /* The hyphen indicates an empty position. */
  int iNumAvailable = 0;
  int i = 0;

  for (i = 0; i < 9; i++)
  {
    if (gnNode->cConfig[i] == '-')
    {
      iAvailable[iNumAvailable] = i;
      iNumAvailable++;
    }
  }
  return iNumAvailable;
}

/* Return 1 for computer victory, -1 for human victory, 0 for neither. */
int evaluation(char* board)
{
  /* The game is over if there are three in a row: */
  int i = 0;

  for (i = 0; i < 3; i++)
  {
    /* Check for rows: */
    if (board[i * 3 + 0] == 'X' && board[i * 3 + 1] == 'X'  && board[i * 3 + 2] == 'X')
    {
      /* We have a row of Xs and the human wins. */
      return -1;
    }
    if (board[i * 3 + 0] == 'O' && board[i * 3 + 1] == 'O'  && board[i * 3 + 2] == 'O')
    {
      /* We have a row of Os and the computer wins. */
      return 1;
    }

    /* Check for columns: */
    if (board[0 + i] == 'X' && board[3 + i] == 'X'  && board[6 + i] == 'X')
    {
      /* We have a column of Xs and the human wins. */
      return -1;
    }
    if (board[0 + i] == 'O' && board[3 + i] == 'O'  && board[6 + i] == 'O')
    {
      /* We have a column of Os and the computer wins. */
      return 1;
    }
  }

  /* Check for diagonals: */
  if (board[0] == 'X' && board[4] == 'X'  && board[8] == 'X')
  {
    /* We have a diagonal of Xs and the human wins. */
    return -1;
  }
  if (board[2] == 'X' && board[4] == 'X'  && board[6] == 'X')
  {
    /* We have a diagonal of Xs and the human wins. */
    return -1;
  }
  if (board[0] == 'O' && board[4] == 'O'  && board[8] == 'O')
  {
    /* We have a diagonal of Os and the computer wins. */
    return 1;
  }
  if (board[2] == 'O' && board[4] == 'O'  && board[6] == 'O')
  {
    /* We have a diagonal of Os and the computer wins. */
    return 1;
  }

  return 0;
}