char board[9] = {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '};

const int wins[8][3] = {
  {0, 1, 2}, {3, 4, 5}, {6, 7, 8},
  {0, 3, 6}, {1, 4, 7}, {2, 5, 8},
  {0, 4, 8}, {2, 4, 6}
};

void printBoard() {
  Serial.println();

  for (int i = 0; i < 9; i++) {
    Serial.print(" ");
    Serial.print(board[i] == ' ' ? char('1' + i) : board[i]);

    if (i % 3 != 2) {
      Serial.print(" |");
    } else if (i != 8) {
      Serial.println();
      Serial.println("---+---+---");
    }
  }

  Serial.println("\n");
}

bool hasWon(char player) {
  for (int i = 0; i < 8; i++) {
    if (board[wins[i][0]] == player &&
        board[wins[i][1]] == player &&
        board[wins[i][2]] == player) {
      return true;
    }
  }
  return false;
}

bool boardIsFull() {
  for (int i = 0; i < 9; i++) {
    if (board[i] == ' ') return false;
  }
  return true;
}

// Returns the empty square that completes a line for the given player.
// Returns -1 if there is no such move.
int findWinningMove(char player) {
  for (int i = 0; i < 8; i++) {
    int a = wins[i][0];
    int b = wins[i][1];
    int c = wins[i][2];

    if (board[a] == player && board[b] == player && board[c] == ' ') return c;
    if (board[a] == player && board[c] == player && board[b] == ' ') return b;
    if (board[b] == player && board[c] == player && board[a] == ' ') return a;
  }
  return -1;
}

int computerMove() {
  int move;

  // Take a winning move, if available.
  move = findWinningMove('O');
  if (move != -1) return move;

  // Block the human from winning.
  move = findWinningMove('X');
  if (move != -1) return move;

  // Take the center if it's free.
  if (board[4] == ' ') return 4;

  // Prefer an available corner.
  int corners[] = {0, 2, 6, 8};
  int availableCorners[4];
  int cornerCount = 0;

  for (int i = 0; i < 4; i++) {
    if (board[corners[i]] == ' ') {
      availableCorners[cornerCount++] = corners[i];
    }
  }

  if (cornerCount > 0) {
    return availableCorners[random(cornerCount)];
  }

  // Otherwise, choose any available square.
  int available[9];
  int count = 0;

  for (int i = 0; i < 9; i++) {
    if (board[i] == ' ') {
      available[count++] = i;
    }
  }

  return available[random(count)];
}

void setup() {
  Serial.begin(9600);
  randomSeed(analogRead(A0));

  Serial.println("Tic-Tac-Toe! You are X; the computer is O.");
  Serial.println("Enter a square number from 1 to 9.");
  printBoard();
}

void loop() {
  if (!Serial.available()) return;

  int move = Serial.parseInt();

  // Discard the rest of the input line.
  while (Serial.available()) {
    Serial.read();
  }

  if (move < 1 || move > 9 || board[move - 1] != ' ') {
    Serial.println("Invalid or occupied square. Choose an empty square from 1 to 9.");
    return;
  }

  // Human's move.
  board[move - 1] = 'X';
  printBoard();

  if (hasWon('X')) {
    Serial.println("You win!");
    while (true) {}
  }

  if (boardIsFull()) {
    Serial.println("It's a draw!");
    while (true) {}
  }

  // Computer's move.
  int computerSquare = computerMove();
  board[computerSquare] = 'O';

  Serial.print("Computer chose square ");
  Serial.println(computerSquare + 1);
  printBoard();

  if (hasWon('O')) {
    Serial.println("Computer wins!");
    while (true) {}
  }

  if (boardIsFull()) {
    Serial.println("It's a draw!");
    while (true) {}
  }

  Serial.println("Your turn. Enter a square number from 1 to 9:");
}