#include <iostream>
#include <string>
using namespace std;

/********** Description of the game rules **********/

// Current game configuration
struct game_cfg {
  char board[9];
  bool x_to_move;
};

// Number of possible moves
const int num_moves = 9;

// What is winning?
struct {
  int line[3];
} lines[] = {
  { { 0, 1, 2 } },
  { { 3, 4, 5 } },
  { { 6, 7, 8 } },
  { { 0, 3, 6 } },
  { { 1, 4, 7 } },
  { { 2, 5, 8 } },
  { { 0, 4, 8 } },
  { { 2, 4, 6 } },
};

// 'X' is always the MAX player, seeking to maximize score
bool is_max_player(const game_cfg &cfg) {
  return cfg.x_to_move;
}

// Check whether game is ended.
// If the game is ended:
//   return true, score is set to 1, 0, -1 if 'X', nobody or 'O' wins.
// If the game is not ended:
//   return false.
bool game_ended(const game_cfg &cfg, int &score) {
  for (unsigned int i = 0; i < sizeof(lines)/sizeof(lines[0]); ++i) {
    char p = cfg.board[lines[i].line[0]];
    if (p != ' ' &&
	p == cfg.board[lines[i].line[1]] &&
	p == cfg.board[lines[i].line[2]]) {
      score = (p == 'X') ? 1 : -1;
      return true;
    }
  }
  for (int i = 0; i < 9; ++i)
    if (cfg.board[i] == ' ')
      return false;
  score = 0;
  return true;
}

// Check whether a move is valid, and if so make the move in a configuration
bool make_move(game_cfg &cfg, int move) {
  if (move < 0 || move > num_moves)
    return false;
  if (cfg.board[move] != ' ')
    return false;
  cfg.board[move] = cfg.x_to_move ? 'X' : 'O';
  cfg.x_to_move = !cfg.x_to_move;
  return true;
}

/********** Generic game engine **********/

// Return value of the best play at a particular time
// The best play itself is recorded in move
int minimax_value(const game_cfg &cfg, int &move) {
  int val;
  if (game_ended(cfg, val))
    return val;
  bool is_max = is_max_player(cfg);
  int best = 0;
  bool found_move = false;
  for (int i = 0; i < num_moves; ++i) {
    game_cfg new_cfg = cfg;
    if (!make_move(new_cfg, i))
      continue;
    int dummy;
    val = minimax_value(new_cfg, dummy);
    if (!found_move) {
      best = val;
      move = i;
      found_move = true;
    } else if (is_max) {
      if (val > best) {
	best = val;
	move = i;
      }
    } else {
      if (val < best) {
	best = val;
	move = i;
      }
    }
  }
  return best;
}

/********** Interface functions **********/

// A computer move
void make_comp_move(game_cfg &cfg) {
  int move;
  int val = minimax_value(cfg, move);
  make_move(cfg, move);
  if (val > 0)
    cout << "I'm winning now." << endl;
  else if (val < 0)
    cout << "I'm losing now." << endl;
}

// Print the current board
void print_board(const game_cfg &cfg) {
  for (int i = 0; i < 9; ++i) {
    if (cfg.board[i] == ' ')
      cout << i;
    else
      cout << cfg.board[i];
    if (i % 3 == 2)
      cout << endl;
    else
      cout << ' ';
  }
}

// Main function
int main() {
  game_cfg curr;
  for (int i = 0; i < 9; ++i)
    curr.board[i] = ' ';
  cout << "Move first? " << endl;
  char first;
  cin >> first;
  curr.x_to_move = !(first == 'y' || first == 'Y');
  int score;
  while (!game_ended(curr, score)) {
    print_board(curr);
    if (curr.x_to_move) {
      cout << "My Move\n";
      make_comp_move(curr);
    } else {
      for (;;) {
	int inp;
	cout << "Move: "; cin >> inp;
	if (make_move(curr, inp))
	  break;
	cout << "Invalid.  Please retry." << endl;
	cin.clear();
	string s;
	getline(cin, s);
      }
    }
  }
  if (score == 0)
    cout << "Draw!" << endl;
  else if (score > 0)
    cout << "I win!" << endl;
  else
    cout << "You win!" << endl;
  if (score == 0) {
  }
  print_board(curr);
}