/*
 * Noughts and Crosses
 * (aka Tic-Tac-Toe)
 * © 2002 Richard Heathfield
 * All rights reserved
 *
 * Permission is granted to copy and modify this file,
 * provided the whole of this copyright notice remains
 * intact, and provided any modifications are clearly
 * marked as such. In other words, don't pretend you
 * wrote my bits, and don't pretend I wrote your bits.
 * :-)
 *
 * Richard Heathfield may be contacted at
 * binary@eton.powernet.co.uk
 */

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

#include <assert.h>

/* A noughts-and-crosses board can be thought of as a bitmap,
 * with each square representing one bit. We can define the
 * values of the squares, then, as successive powers of 2,
 * with an empty square having a value of 0.
 */

#define SPACE           0
#define TOP_LEFT        1
#define TOP_CENTRE      2
#define TOP_RIGHT       4
#define CENTRE_LEFT     8
#define CENTRE_CENTRE  16
#define CENTRE_RIGHT   32
#define BOTTOM_LEFT    64
#define BOTTOM_CENTRE 128
#define BOTTOM_RIGHT  256

/* To analyse a position, we simply add (or OR) together the
 * values of all the squares occupied by a particular
 * player. Now, there are eight winning lines, which can
 * be represented by the following OR operations.
 */

#define TOP_ROW    (TOP_LEFT    | TOP_CENTRE    | TOP_RIGHT)
#define CENTRE_ROW (CENTRE_LEFT | CENTRE_CENTRE | CENTRE_RIGHT)
#define BOTTOM_ROW (BOTTOM_LEFT | BOTTOM_CENTRE | BOTTOM_RIGHT)

#define LEFT_COL   (TOP_LEFT    | CENTRE_LEFT   | BOTTOM_LEFT)
#define CENTRE_COL (TOP_CENTRE  | CENTRE_CENTRE | BOTTOM_CENTRE)
#define RIGHT_COL  (TOP_RIGHT   | CENTRE_RIGHT  | BOTTOM_RIGHT)

#define TLBR_DIAG  (TOP_LEFT    | CENTRE_CENTRE | BOTTOM_RIGHT)
#define BLTR_DIAG  (BOTTOM_LEFT | CENTRE_CENTRE | TOP_RIGHT)

/* To determine whether a player has a win, we can just
 * AND his score with each of these winning lines in turn.
 * If any of them is equal to the value of the winning
 * line after ANDing, then that player has a win. Clearly
 * we must do this in strict move-history order! Otherwise,
 * we could end up with two winners in one game, which
 * wouldn't do at all.
 */


/* Let's start off with a banner */
void ShowBanner(void)
{
  char *msg[] =
  {
    "",
    " ***********************",
    " *                     *",
    " * NOUGHTS AND CROSSES *",
    " *                     *",
    " * a.k.a. Tic-Tac-Toe  *",
    " *                     *",
    " ***********************",
    "",
    ""
  };
  size_t n = sizeof msg / sizeof msg[0];
  size_t i = 0;
  while(i < n)
  {
    printf("%s\n", msg[i++]);
  }
}

/* YesNo() asks a question that can be answered yes or no, and
 * returns 0 if the first character of the answer is y or Y. If any
 * other character is used, the function returns 1. In the event of
 * the user bombing out by signalling end-of-input, *stop is set to 1.
 */
int YesNo(const char *prompt, int *stop)
{
  int rc = 1; /* 0 = yes, 1 = no */
  char answer[8] = {0};
  int dummy = printf("%s\n", prompt);
  char *result = fgets(answer, sizeof answer, stdin);
  if(result != NULL)
  {
    if(toupper((unsigned char)answer[0]) == 'Y')
    {
      rc = 0;
    }
  }
  else
  {
    *stop = 1;
  }
  return rc;
}

/* ScoreGame() returns 0 if the board does not
 * currently contain a win. Otherwise, it returns
 * the turn number on which the win occurred.
 * A result of 4 or 6 or 8 therefore indicates a
 * win for the first player, whereas a result
 * of 5 or 7 indicates a win for the second player.
 */
int ScoreGame(int *MoveHistory)
{
  int result = 0;
  int i = 0;
  unsigned long FirstPlayer = 0;
  unsigned long SecondPlayer = 0;

  for(i = 0; 0 == result && i < 9; i++)
  {
    if(i % 2 == 0)
    {
      FirstPlayer |= MoveHistory[i];
      if(((FirstPlayer & TOP_ROW)    == TOP_ROW)    ||
         ((FirstPlayer & CENTRE_ROW) == CENTRE_ROW) ||
         ((FirstPlayer & BOTTOM_ROW) == BOTTOM_ROW) ||
         ((FirstPlayer & LEFT_COL)   == LEFT_COL)   ||
         ((FirstPlayer & CENTRE_COL) == CENTRE_COL) ||
         ((FirstPlayer & RIGHT_COL)  == RIGHT_COL)  ||
         ((FirstPlayer & TLBR_DIAG)  == TLBR_DIAG)  ||
         ((FirstPlayer & BLTR_DIAG)  == BLTR_DIAG))
      {
        result = i;
      }
    }
    else
    {
      SecondPlayer |= MoveHistory[i];
      if(((SecondPlayer & TOP_ROW)    == TOP_ROW)    ||
         ((SecondPlayer & CENTRE_ROW) == CENTRE_ROW) ||
         ((SecondPlayer & BOTTOM_ROW) == BOTTOM_ROW) ||
         ((SecondPlayer & LEFT_COL)   == LEFT_COL)   ||
         ((SecondPlayer & CENTRE_COL) == CENTRE_COL) ||
         ((SecondPlayer & RIGHT_COL)  == RIGHT_COL)  ||
         ((SecondPlayer & TLBR_DIAG)  == TLBR_DIAG)  ||
         ((SecondPlayer & BLTR_DIAG)  == BLTR_DIAG))
      {
        result = i;
      }
    }
  }

  return result;
}


/* A legal move is one which has not yet been made. */
int GetLegalMoves(int *LegalMoves, int *MoveHistory)
{
  int i = 0;
  int j = 0;

  unsigned long MovesAlreadyMade = 0;
  unsigned long ThisMove = 0;

  for(i = 0; i < 9; i++)
  {
    MovesAlreadyMade |= MoveHistory[i];
    LegalMoves[i] = 0;
  }

  for(i = 0, j = 0; i < 9; i++)
  {
    ThisMove = 1 << i;
    if((ThisMove & MovesAlreadyMade) != ThisMove)
    {
      LegalMoves[j] = ThisMove;
      ++j;
    }
  }

  return j; /* number of legal moves */
}

int GetPlayerMove(int *MoveHistory, int *stop)
{
  int LegalMoveArray[9] = {0};
  int LegalMoves = GetLegalMoves(LegalMoveArray, MoveHistory);
  int Move = 0;
  int done = 0;

  char Answer[8] = {0};
  char *result = NULL;

  char LegalResponses[10] = {0};

  int i = 0;

  while(i < LegalMoves)
  {
    switch(LegalMoveArray[i])
    {
      case 0:
        break;
      case TOP_LEFT:
        LegalResponses[i] = 'A';
        break;
      case TOP_CENTRE:
        LegalResponses[i] = 'B';
        break;
      case TOP_RIGHT:
        LegalResponses[i] = 'C';
        break;
      case CENTRE_LEFT:
        LegalResponses[i] = 'D';
        break;
      case CENTRE_CENTRE:
        LegalResponses[i] = 'E';
        break;
      case CENTRE_RIGHT:
        LegalResponses[i] = 'F';
        break;
      case BOTTOM_LEFT:
        LegalResponses[i] = 'G';
        break;
      case BOTTOM_CENTRE:
        LegalResponses[i] = 'H';
        break;
      case BOTTOM_RIGHT:
        LegalResponses[i] = 'I';
        break;
      default:
        printf("Illegal legal move! :-%%\n");
        assert(0);
        break;
    }

    ++i;
  }

  printf("Where do you want to move?\n");

  do
  {
    result = fgets(Answer, sizeof Answer, stdin);
    if(result != NULL)
    {
      int firstchar = toupper((unsigned char)Answer[0]);
      char *legit = strchr(LegalResponses, firstchar);

      if(legit != NULL)
      {
        Move = legit - LegalResponses;
        done = 1;
      }
      else
      {
        printf("Sorry, you must choose from %s\n", LegalResponses);
        printf("Please re-try.\n");
      }
    }
    else
    {
      *stop = 1;
    }
  } while(!*stop && !done);

  return LegalMoveArray[Move];
}

/* The move history is in terms of bitmaps, but sometimes
 * we need to know the board position pertaining to a given
 * bitmap. Here's a function to give us that information.
 */
int BitmapToPosition(int bitmap)
{
  int pos = 0;

  while(bitmap > 1)
  {
    bitmap >>= 1;
    ++pos;
  }

  return pos;
}

/* Such intelligence as the game has is rooted in this function, which
 * is a fairly straight recursive trawl through the remaining lines of
 * play. Regrettably, this doesn't always give us the best strategy!
 */
void SearchForBestMove(int *Moves,
                       size_t n,
                       size_t unchanged,
                       long *Score,
                       size_t HowFarIntoGame,
                       int WhichPlayerAmI)
{
  size_t outer = 0;
  size_t inner = 0;
  int temp = 0;

  if(unchanged < n)
  {
    for(outer = unchanged; outer < n; outer++)
    {
      temp = Moves[outer];
      for(inner = outer; inner > unchanged; inner--)
      {
        Moves[inner] = Moves[inner - 1];
      }
      Moves[unchanged] = temp;
      SearchForBestMove(Moves,
                        n,
                        unchanged + 1,
                        Score,
                        HowFarIntoGame,
                        WhichPlayerAmI);

      for(inner = unchanged; inner < outer; inner++)
      {
        Moves[inner] = Moves[inner + 1];
      }
      Moves[outer] = temp;
    }
  }
  else
  {
    int Result = ScoreGame(Moves);
    if(0 == Result)
    {
      /* draw - do nothing */
    }
    else if((Result % 2) == WhichPlayerAmI)
    {
      Score[BitmapToPosition(Moves[HowFarIntoGame])] += 9 - Result;
    }
    else
    {
      Score[BitmapToPosition(Moves[HowFarIntoGame])] -= 9 - Result;
    }
  }
}

int GetComputerMove(int *MoveHistory, int WhoAmI, int Nobbled)
{
  int LegalMoveArray[9] = {0};
  int LegalMoves = GetLegalMoves(LegalMoveArray, MoveHistory);
  long Scores[9] = {0};

  int BoardCopy[9] = {0};
  size_t MovesSoFar = 0;
  int i = 0;
  int Move = 0;
  int BestMove = 0;
  int BestScore = 0;
  int ScoresOffset = 0;

  if(Nobbled)
  {
    Move = LegalMoveArray[rand() % LegalMoves];
  }
  else
  {
    /* Copy the move history into a safe place */
    while(MoveHistory[MovesSoFar] != 0 && MovesSoFar < 9)
    {
      BoardCopy[MovesSoFar] = MoveHistory[MovesSoFar];
      MovesSoFar++;
    }

    /* Append the remaining legal moves to the safe copy */
    i = MovesSoFar;
    while(i < 9)
    {
      BoardCopy[i] = LegalMoveArray[i - MovesSoFar];
      i++;
    }

    SearchForBestMove(BoardCopy, 9, MovesSoFar, Scores, MovesSoFar, WhoAmI);

    BestMove = 0;
    BestScore = Scores[BitmapToPosition(LegalMoveArray[BestMove])];

    for(i = 1; i < LegalMoves; i++)
    {
      ScoresOffset = BitmapToPosition(LegalMoveArray[i]);

      if(Scores[ScoresOffset] > BestScore)
      {
        BestMove = i;
        BestScore = Scores[BitmapToPosition(LegalMoveArray[BestMove])];
      }
    }

    Move = LegalMoveArray[BestMove];
  }

  return Move;
}


void ClearBoard(int *MoveHistory)
{
  int i = 0;
  while(i < 9)
  {
    MoveHistory[i++] = 0;
  }
}

/* DisplayBoard() displ... well! Anyway, SymbolSet
 * must be a pointer to a string beginning with
 * either "OX" or "XO". The first of the two symbols
 * is used for Player 1.
 */
void DisplayBoard(int *MoveHistory, char* SymbolSet)
{
  char Display[3][3] =
  {
    "ABC",
    "DEF",
    "GHI"
  };
  int i = 0;

  for(i = 0; i < 9; i++)
  {
    switch(MoveHistory[i])
    {
      case 0:
        break;
      case TOP_LEFT:
        Display[0][0] = SymbolSet[i % 2];
        break;
      case TOP_CENTRE:
        Display[0][1] = SymbolSet[i % 2];
        break;
      case TOP_RIGHT:
        Display[0][2] = SymbolSet[i % 2];
        break;
      case CENTRE_LEFT:
        Display[1][0] = SymbolSet[i % 2];
        break;
      case CENTRE_CENTRE:
        Display[1][1] = SymbolSet[i % 2];
        break;
      case CENTRE_RIGHT:
        Display[1][2] = SymbolSet[i % 2];
        break;
      case BOTTOM_LEFT:
        Display[2][0] = SymbolSet[i % 2];
        break;
      case BOTTOM_CENTRE:
        Display[2][1] = SymbolSet[i % 2];
        break;
      case BOTTOM_RIGHT:
        Display[2][2] = SymbolSet[i % 2];
        break;
      default:
        printf("ERROR! Move %d is illegal.\n", MoveHistory[i]);
        assert(0); /* program bug! */
        break;
    }
  }

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

  return;
}

int main(void)
{
  int done = 0; /* Player has had enough */
  int stop = 0; /* EOF detected */
  int PlayerTurn = 0;
  int PlayerSymbol = 0;
  int GameOver = 0;
  int Turn = 0;
  int Move = 0;
  char Player1IsNoughts[] = "OX";
  char Player2IsNoughts[] = "XO";
  char *Symbols = NULL;
  int Winner = 0;

  /* Set Nobbled to 1 if you want to turn off what little intelligence
   * the game has. If Nobbled is set, the game will play (pseudo)randomly.
   */
  int Nobbled = 0;

  int MoveHistory[9] = {0};

  ShowBanner();

  do
  {
    PlayerTurn = YesNo("Do you want to go first?", &stop);

    if(!stop)
    {
      PlayerSymbol = YesNo("Do you want to be Noughts (Y/N)?", &stop);
    }
    if(!stop)
    {
      GameOver = 0;
      Turn = 0;
      ClearBoard(MoveHistory);

      if(0 == PlayerTurn)
      {
        if(0 == PlayerSymbol)
        {
          Symbols = Player1IsNoughts;
        }
        else
        {
          Symbols = Player2IsNoughts;
        }
      }
      else
      {
        if(0 == PlayerSymbol)
        {
          Symbols = Player2IsNoughts;
        }
        else
        {
          Symbols = Player1IsNoughts;
        }
      }

      while(!GameOver)
      {
        printf("TURN %d\n", Turn);

        DisplayBoard(MoveHistory, Symbols);

        if(Turn % 2 == PlayerTurn)
        {
          Move = GetPlayerMove(MoveHistory, &stop);
        }
        else
        {
          Move = GetComputerMove(MoveHistory, !PlayerTurn, Nobbled);
        }

        if(!stop)
        {
          MoveHistory[Turn] = Move;
        }

        Winner = ScoreGame(MoveHistory);

        if(stop || 8 == Turn || Winner != 0)
        {
          GameOver = 1;
        }

        ++Turn;
      }
      DisplayBoard(MoveHistory, Symbols);
      printf("\nGame Over:");
      if(0 == Winner)
      {
        printf(" Draw.\n");
      }
      else if(Winner % 2 == PlayerTurn)
      {
        printf("Human player wins!\n");
      }
      else
      {
        printf("Computer wins.\n");
      }
    }

    if(!stop)
    {
      done = YesNo("Do you want to play again? (Y/N)", &stop);
    }
  } while(!stop && !done);

  if(stop)
  {
    fprintf(stderr, "Unexpected end of file. Actually, I did\n");
    fprintf(stderr, "kind of half-expect it, didn't I? :-)\n");
  }

  return 0;
}