srishanbhattarai · April 28, 2020 02:42 · Apr 28, 2020 · Apr 28, 2020 · Apr 28, 2020 · Apr 28, 2020
diff --git a/game.cpp b/game.cpp
@@ -49,12 +49,25 @@ 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 << "  "
+       << "   "
+       << "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 << "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
+  cout << "2 "
+       << " | " << state[2][0] << " | " << state[2][1] << " | " << state[2][2]
+       << " | " << endl
        << endl;
 }
 
@@ -136,7 +149,8 @@ pair<int, Move> alpha_beta_search(vector<vector<char>> curr_state, char 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)
+    int score = alpha_beta_search(curr_state, turn == AI ? HUMAN : AI, alpha,
+                                  beta, depth + 1)
                     .first;
 
     // Maximizing.
@@ -292,4 +306,4 @@ int main(int _argc, char **_argv) {
   }
 
   return 0;
-}
+}
diff --git a/game.cpp b/game.cpp
@@ -58,9 +58,6 @@ void print_state() {
        << endl;
 }
 
-// Alpha beta search
-int search() { return 0; }
-
 // 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;

diff --git a/game.cpp b/game.cpp
@@ -3,12 +3,13 @@
  *
  * 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 <cstdlib>
 #include <iostream>
 #include <tuple>
 #include <vector>

diff --git a/game.cpp b/game.cpp
@@ -0,0 +1,297 @@
+/**
+ * Tic Tac Toe using Minmax search with Alpha Beta Pruning.
+ *
+ * Author: Srishan Bhattarai
+ *
+ * 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 <cstdlib>
+#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;
+}
+
+// Alpha beta search
+int search() { return 0; }
+
+// 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;
+}
No results found