#include <iostream>

// class CBoard:
//    A class for the Tic-Tac-Toe board
//    Contains board spaces as private members, and public functions
//    for printing the board, filling spaces, etc.
class CBoard
{
   private:
      char space[9];   // should always be ' ', 'X' or 'O'
                       // 0|1|2
                       // 3|4|5
                       // 6|7|8
   public:
      CBoard();
      void print_board();
      int fill_space (int this_space, char this_tag);
      char get_space (int this_space);
      int report_win_alignment (char *winner);
      void clear_space (int clear_space)
         { space[clear_space-1] = ' '; }
};

// class CCompetitor:
//    An abstract base class with a pure virtual function select_space.
//    Classes that derive CCompetitor must implement select_space.
//    Human and computer player classes are derived from this class.
class CCompetitor
{
   protected:
      char tag;   // 'X' or 'O'
   public:
      virtual int select_space (CBoard *board) = 0;
      char get_tag()
         { return tag; }
};

// class CHuman:
//    A class that implements the select_space function for 
//    human players.
class CHuman: public CCompetitor
{
   public:
      CHuman (char new_tag) {tag = new_tag;}  // constructor
      int select_space (CBoard *board)
         {
            board->print_board();
            int space_chosen = 0, fill_result; 
            while (!space_chosen)
               {
                  cout << endl;
                  cout << "Choose an available space (1-9)" << endl;
                  cout << "1|2|3" << endl;
                  cout << "4|5|6" << endl;
                  cout << "7|8|9" << endl << endl;;
                  cin >> space_chosen;

                  fill_result = board->fill_space (space_chosen, tag);

                  if (fill_result < -1)
                     {
                        cerr << "Invalid choice" << endl;
                        space_chosen = 0;
                     }
               }

            if (fill_result > 0)
               // Last selection resulted in a win
               cout << "PLAYER " << tag << " WINS!" << endl;

            return fill_result;
         }
};

// class CBestMove:
//    A class used by a computer player to decide how to move.
//    Values are assigned to board spaces based on possible results.
class CBestMove
{
   public:
      int value;
      int space;
      CBestMove (int v)
         { value = v; space = -1; }
      CBestMove (int v, int s)
         { value = v; space = s; }
};

// class CComputer:
//    A class that implements the select_space function for 
//    computer players.
class CComputer: public CCompetitor
{
   private:
      CBestMove* choose_best_move (CBoard board, char my_tag);
   public:
      CComputer (char new_tag) {tag = new_tag;}   // constructor
      int select_space (CBoard *board)
         {
            int fill_result;
            CBoard working_board = *board;  // makes a copy of the board
                                            // to try different scenarios
            CBestMove *best_move = choose_best_move (working_board, tag);
            fill_result = board->fill_space (best_move->space, tag);
            delete best_move;

            if (fill_result > 0)
               // chosen move resulted in a win
               cout << "COMPUTER " << tag << " WINS!" << endl;
            return fill_result;
         }
};

// CBestMove* choose_best_move (CBoard board, char consider_tag)
//    board: a copy of the hypothetical working tic-tac-toe board
//    my_tag: the next player (X|O) to make a move in this scenario
CBestMove* CComputer::choose_best_move (CBoard board, char my_tag)
{
   char opp_tag;
   CBestMove *opp_reply;
   int evaluate_board;
   int best_space = 5;  // default best space is the middle
   int value;
   char winning_tag;

   // Assign scores to various outcomes for the computer player
   const int I_LOSE  = 0;
   const int DRAW    = 1;
   const int UNCLEAR = 2;
   const int I_WIN   = 3;

   evaluate_board = board.report_win_alignment (&winning_tag);

   if (evaluate_board != 0)
      // result is not unclear
      {
          if (evaluate_board == -1)
             {
                // last scenario resulted in a draw
                return new CBestMove (DRAW);
             }
          if (evaluate_board > 0)
             {
                if (winning_tag == tag)
                   {
                      // last scenario resulted in a computer victory
                      return new CBestMove (I_WIN);
                   }
                if (winning_tag != tag)
                   {
                      // scenario was victory for the computer's opponent
                      return new CBestMove (I_LOSE);
                   }
             }
      }

   if (tag == my_tag)
      {
         // consider the next hypothetical move by the computer
         value = I_LOSE;
         switch (my_tag)
            {
               case 'X':
                  opp_tag = 'O';
                  break;
               default:
                  opp_tag = 'X';
                  break;
            }
      }
   else
      {
         // consider the next hypothetical move by the computer's opponent
         value = I_WIN;
         opp_tag = tag;
      }

   // Create hypothetical situations by filling each space one-by-one 
   for (int i = 0; i <= 9; i++)
      {
         // Should always give preference to middle space; try it first
         if (i == 5) i++;
         if (i == 0) i = 5;

         // Check to see if this space is taken already
         if (board.get_space(i) == ' ')
            {
               board.fill_space (i, my_tag);
               opp_reply = choose_best_move (board, opp_tag);
               board.clear_space (i);

               // The computer will pick the best move for itself;
               // Assume opponent will pick the worst move for computer
               if ((my_tag == tag && opp_reply->value > value) ||
                   (opp_tag == tag && opp_reply->value < value))
                  {
                     // This move is the best option found so far
                     value = opp_reply->value;
                     best_space = i;
                  }
               delete opp_reply;
            }
         if (i == 5) 
            // Now consider spaces other than the middle
            i = 0;
      }
   return new CBestMove (value, best_space);
}

// CBoard constructor: initialize board spaces to ' '
CBoard::CBoard ()
{
   for (int i = 0; i <= 9; i++)
      space[i] = ' ';
}

void CBoard::print_board ()
{
   // print stars around tags that were part of a winning move
   char win_stars[9];
   for (int i = 0; i <= 8; i++)
      win_stars[i] = ' ';
   switch (report_win_alignment(NULL))
      {
         // horizontal winners:
         case 1:
            win_stars[0] = '*';
            win_stars[1] = '*';
            win_stars[2] = '*';
            break;
         case 2:
            win_stars[3] = '*';
            win_stars[4] = '*';
            win_stars[5] = '*';
            break;
         case 3:
            win_stars[6] = '*';
            win_stars[7] = '*';
            win_stars[8] = '*';
            break;
         // vertical winners:
         case 4:
            win_stars[0] = '*';
            win_stars[3] = '*';
            win_stars[6] = '*';
            break;
         case 5:
            win_stars[1] = '*';
            win_stars[4] = '*';
            win_stars[7] = '*';
            break;
         case 6:
            win_stars[2] = '*';
            win_stars[5] = '*';
            win_stars[8] = '*';
            break;
         // diagonal winners:
         case 7:
            win_stars[0] = '*';
            win_stars[4] = '*';
            win_stars[8] = '*';
            break;
         case 8:
            win_stars[2] = '*';
            win_stars[4] = '*';
            win_stars[6] = '*';
            break;
         case 0:  // no winner yet
         case -1: // draw
         default:
            break;
      }

   for (int row = 0; row <= 2; row++)
      {
         for (int col = 0; col <= 2; col++)
            {
               // Surround tag with stars or spaces
               for (int star = 1; star <= 3; star++)
                  cout << win_stars[col+(row*3)];
               if (col < 2)
                  cout << "|";
            }
         cout << endl;
         for (int col = 0; col <= 2; col++)
            {
               // Print board space tag ('X', 'O', ' ')
               cout << win_stars[col+(row*3)] << space[col+(row*3)] << 
                       win_stars[col+(row*3)] ;
               if (col < 2)
                  cout << "|" ;
            }
         cout << endl;
         for (int col = 0; col <= 2; col++)
            {
               // Surround tag with stars or spaces
               for (int star = 1; star <= 3; star++)
                  cout << win_stars[col+(row*3)];
               if (col < 2)
                  cout << "|";
            }
         cout << endl;
         if (row < 2)
            cout << "---+---+---" << endl;
      }
}

// Fill specified space with specified tag;
// Return win code in case the move won the game
int CBoard::fill_space (int this_space, char this_tag)
{
   if (this_space < 1 || this_space > 9)
      {
         cerr << "In CBoard::fill_space: input parameter must be
                  between 1 and 9, passed " << this_space << endl;
         return -100;
      }

   if (space[this_space - 1] != ' ')
      {
         cerr << "That space is not empty" << endl;
         return -100;
      }

   space[this_space - 1] = this_tag;

   return report_win_alignment(NULL);
}

char CBoard::get_space (int this_space)
{
   if (this_space < 1 || this_space > 9)
      {
         cerr << "In CBoard::get_space: input parameter must be
                  between 1 and 9" << endl;
         return '\0';
      }
   return space[this_space - 1];
}

// Report if we have a winner, draw, or nothing
int CBoard::report_win_alignment (char *winner)
{
   // Check for possible wins by looking for matching characters
   // cases 1-3: horizontals
   for (int i = 0; i <= 2; i++)
      {
         if (space[(i*3)+0] != ' ' &&
             space[(i*3)+1] != ' ' &&
             space[(i*3)+2] != ' ')
             if (space[(i*3)+0] == space[(i*3)+1] &&
                 space[(i*3)+1] == space[(i*3)+2])
                {
                   if (winner)
                      *winner = space[i*3];
                   return (i + 1);
                }
      }

   // cases 4-6: verticals
   for (int i = 0; i <= 2; i++)
      {
         if (space[0+i] != ' ' &&
             space[3+i] != ' ' &&
             space[6+i] != ' ')
            if (space[0+i] == space[3+i] &&
                space[3+i] ==  space[6+i])
               {
                  if (winner)
                     *winner = space[0+i];
                  return (i + 4);
               }
      }

   // cases 7-8: diagonals
   if (space[0] != ' ' && space[4] != ' ' && space[8] != ' ')
      if (space[0] == space[4] && space[4] == space[8])
         {
            if (winner)
               *winner = space[0];
            return 7;
         }
   if (space[2] != ' ' && space[4] != ' ' && space[6] != ' ')
      if (space[2] == space[4] && space[4] == space[6])
         {
            if (winner)
               *winner = space[2];
            return 8;
         }

   // case (-1): draw; if no draw, return 0
   for (int i = 0; i <= 8; i++)
      {
         if (space[i] == ' ')
            return 0;
      }
   return -1;
}


int main ()
{
   CCompetitor *cX, *cO;
   char Xselection, Oselection;

start_game:
   cout << "Select player X: (H)uman, (C)omputer" << endl;
   cin >> Xselection;

   switch (Xselection)
      {
         case 'H':
         case 'h':
            // Competitor X is a human
            cX = new CHuman ('X');
            break;
         case 'C':
         case 'c':
            // Competitor X is a computer
            cX = new CComputer ('X');
            break;
         default:
            cerr << "Must select (H)uman or (C)omputer" << endl;
            return -1;
      }

   cout << "Select player O: (H)uman, (C)omputer" << endl;
   cin >> Oselection;

   switch (Oselection)
      {
         case 'H':
         case 'h':
            // Competitor O is a human
            cO = new CHuman ('O');
            break;
         case 'C':
         case 'c':
            // Competitor O is a computer
            cO = new CComputer ('O');
            break;
         default:
            cerr << "Must select (H)uman or (C)omputer" << endl;
            return -1;
      }

   CBoard board;

   int win_code = 0;

   // Keep playing until we get a winner or a draw
   while (win_code == 0)
      {
          // X's turn
          win_code = cX->select_space (&board);

          if (win_code != 0)
             break;

          // O's turn
          win_code = cO->select_space (&board);
      }

   board.print_board();
   if (win_code == -1)
      {
         cout << "DRAW" << endl;
      }

   cout << "GAME OVER" << endl;

   delete cX;
   delete cO;

   char again;
   cout << "Play again (Y/N)?" << endl;
   cin >> again;
   if (again == 'y' || again == 'Y')
      goto start_game;

   return 0;
}