Tic Tac Toe AI using AB pruning

game.cpp

/**
 * Tic Tac Toe using Minmax search with Alpha Beta Pruning.
 *
 * Author: Srishan Bhattarai
 *
 * Compile: g++ -g --std=c++11 ttt.cc -o ttt
 *
 * Follow the "get_ai_move" function to see the algorithm in action, rest of
 * the code is to get user input, render board into terminal, check for goal
 * states etc.
 */

#include <iostream>
#include <tuple>
#include <vector>

#define PAIR make_pair

using namespace std;

// bounds checked move typedef.
using Move = pair<int, int>;

// States the game can end up in.
enum Result {
  HumanWins,
  AiWins,
  Draw,
  Incomplete // <- if the game is still running, all other results except this
             // is a terminal state
};

// Board characters.
const char HUMAN = 'O';
const char AI = 'X';
const char EMPTY = '.';

// Scores for alpha beta pruning
const int AI_SCORE = 1000; // ai tries to maximize
const int DRAW_SCORE = 0;
const int HUMAN_SCORE = -1000; // human tries to minimize

// Current game state, 3x3, initially all empty.
vector<vector<char>> state(3, vector<char>(3, EMPTY));

// forward declaration.
Result eval_board_state(vector<vector<char>> = state);

// Prints the current game state (3x3 assumed)
void print_state() {
  cout << endl;
  cout << "  "
       << "   "
       << "0"
       << "   "
       << "1"
       << "   "
       << "2"
       << "   " << endl;
  cout << "0 "
       << " | " << state[0][0] << " | " << state[0][1] << " | " << state[0][2]
       << " | " << endl;
  cout << "   -------------" << endl;
  cout << "1 "
       << " | " << state[1][0] << " | " << state[1][1] << " | " << state[1][2]
       << " | " << endl;
  cout << "   -------------" << endl;
  cout << "2 "
       << " | " << state[2][0] << " | " << state[2][1] << " | " << state[2][2]
       << " | " << endl
       << endl;
}

// Checks if a piece can be placed at the coords specified by row and col.
bool is_valid_placement(const int row, const int col) {
  bool inBounds = row >= 0 && row <= 2 && col >= 0 && col <= 2;
  if (!inBounds)
    return false;

  // bounds ok. Check if occupied by someone else
  return state[row][col] == EMPTY;
}

// Gets valid input from the user on next move to make.
Move get_user_move() {
  while (true) {
    int row, col;
    cout << "Enter your move (e.g. 0 1): ";
    cin >> row >> col;

    if (!is_valid_placement(row, col)) {
      cout << "Slot occupied or out of bounds; try again!" << endl << endl;
      continue;
    }

    return PAIR(row, col);
  }

  // unreachable; but make compiler happy.
  return PAIR(-1, -1);
}

// Get a list of all possible moves.
vector<Move> possible_moves(vector<vector<char>> state) {
  vector<Move> moves;
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      if (state[i][j] == EMPTY)
        moves.push_back(PAIR(i, j));
    }
  }

  return moves;
}

// turn: Player to run the search for. At the top level, this will always be AI,
// but due to recursion this might end up being called for HUMAN too.
// alpha,beta: usual alpha beta pruning params.
// depth: Recursion depth, defaults to zero. this factors into the score we
// assign to any board state.
//
// Returns the best score for the search, and a pair indicating the best move.
pair<int, Move> alpha_beta_search(vector<vector<char>> curr_state, char turn,
                                  int alpha, int beta, int depth = 0) {
  Result r = eval_board_state(curr_state);

  /**
   * Base cases, leaf node cases reached where someone has won, or a draw has
   * been reached.
   */
  if (r == Result::HumanWins)
    return PAIR(HUMAN_SCORE, PAIR(-1, -1));
  else if (r == Result::AiWins)
    return PAIR(AI_SCORE, PAIR(-1, -1));
  else if (r == Result::Draw)
    return PAIR(DRAW_SCORE, PAIR(-1, -1));

  // A board state that does not have a winner is encountered! (aka
  // Result::Incomplete state)
  int ideal_score = turn == AI ? HUMAN_SCORE : AI_SCORE;

  // Get all possible moves
  vector<Move> pmoves = possible_moves(curr_state);
  Move bestMove = PAIR(-1, 1);
  for (auto pmove : pmoves) {
    // Simulate the possible move to happen, then recompute the score a/c to
    // minmax for the other player.
    curr_state[pmove.first][pmove.second] = turn;

    // If current turn is Ai, then compute Human's score for next turn,
    // otherwise it's humans turn so compute Ai score.
    int score = alpha_beta_search(curr_state, turn == AI ? HUMAN : AI, alpha,
                                  beta, depth + 1)
                    .first;

    // Maximizing.
    if (turn == AI) {
      if (ideal_score < score) {
        ideal_score = score - 10 * depth;
        bestMove = pmove;

        // compute new alpha
        alpha = max(alpha, ideal_score);

        // Undo the simulation.
        curr_state[pmove.first][pmove.second] = EMPTY;

        // Prune!
        if (beta <= alpha)
          break;
      }
    } else {
      if (ideal_score > score) {
        ideal_score = score + 10 * depth;
        bestMove = pmove;

        // compute new beta
        beta = min(beta, ideal_score);
        curr_state[pmove.first][pmove.second] = EMPTY;

        // prune!
        if (beta <= alpha)
          break;
      }
    }

    // Undo the simulation for cases where beta > alpha.
    curr_state[pmove.first][pmove.second] = EMPTY;
  }

  return std::make_pair(ideal_score, bestMove);
}

// Gets the next Ai move.
pair<int, Move> get_ai_move() {
  return alpha_beta_search(state, AI, HUMAN_SCORE, AI_SCORE);
}

// Checks if state is a terminal state. Works with current state by default.
Result eval_board_state(vector<vector<char>> state) {
  // horizontal sequences that can win.
  vector<vector<Move>> horizontals = {
      vector<Move>{PAIR(0, 0), PAIR(0, 1), PAIR(0, 2)},
      vector<Move>{PAIR(1, 0), PAIR(1, 1), PAIR(1, 2)},
      vector<Move>{PAIR(2, 0), PAIR(2, 1), PAIR(2, 2)}};

  // vertical sequences that can win.
  vector<vector<Move>> verticals = {
      vector<Move>{PAIR(0, 0), PAIR(1, 0), PAIR(2, 0)},
      vector<Move>{PAIR(0, 1), PAIR(1, 1), PAIR(2, 1)},
      vector<Move>{PAIR(0, 2), PAIR(1, 2), PAIR(2, 2)}};

  // diagonal sequences that can win.
  vector<vector<Move>> diagonals = {
      vector<Move>{PAIR(0, 0), PAIR(1, 1), PAIR(2, 2)},
      vector<Move>{PAIR(2, 0), PAIR(1, 1), PAIR(0, 2)}};

  // Is atleast one state empty? Helps determine a draw state.
  bool contains_empty = false;

  // Can win horizontally, vertically or diagonally.
  vector<vector<vector<Move>>> winning_seqs = {horizontals, verticals,
                                               diagonals};
  for (auto ws : winning_seqs) {
    for (auto seq : ws) {
      auto m1 = seq[0];
      auto m2 = seq[1];
      auto m3 = seq[2];

      // Values at each position.
      char m1v = state[m1.first][m1.second];
      char m2v = state[m2.first][m2.second];
      char m3v = state[m3.first][m3.second];

      // if all equal, someone has maybe won if they are not all empty.
      if (m1v == m2v && m2v == m3v) {
        if (m1v == HUMAN)
          return Result::HumanWins;
        else if (m1v == AI)
          return Result::AiWins;
      }

      // if not, check if any of them was empty.
      if (m1v == EMPTY || m2v == EMPTY || m3v == EMPTY) {
        contains_empty = true;
      }
    }
  }

  // Went through all sequences, no winner!
  // If we saw an empty space somewhere, it means there are more moves to make.
  // Otherwise, all slots are full and there is no winner which is a draw.
  if (!contains_empty) {
    return Result::Draw;
  }

  return Result::Incomplete;
}

int main(int _argc, char **_argv) {
  print_state();

  Result board_state = Result::Incomplete;
  while (true) {
    // Move human.
    auto hmove = get_user_move();
    state[hmove.first][hmove.second] = HUMAN;

    // Has a terminal state been reached with this human move?
    board_state = eval_board_state();
    if (board_state != Result::Incomplete) {
      print_state();
      break;
    }

    // Move Ai
    auto next = get_ai_move();
    Move amove = next.second;
    state[amove.first][amove.second] = AI;
    cout << "Ai moved: (" << amove.first << ", " << amove.second << ")" << endl;

    // Re-render
    print_state();

    // Has a terminal state been reached with this Ai move?
    board_state = eval_board_state();
    if (board_state != Result::Incomplete)
      break;
  }

  // Print result.
  switch (board_state) {
  case Result::HumanWins:
    cout << "Human has won! But, this should not have been possible :(" << endl;
    break;
  case Result::AiWins:
    cout << "Ai has won, sorry human!" << endl;
    break;
  case Result::Draw:
    cout << "Game has ended in a draw!" << endl;
    break;
  case Result::Incomplete:
    cout << "There is a bug in the code; game should never end in an "
            "incomplete state"
         << endl;
  }

  return 0;
}