Question

In the C++ programming language write a program capable of playing Tic-Tac-Toe against the user. Your program should use OOP concepts in its design. You can use ASCII art to generate and display the 3x3 playing board. The program should randomly decide who goes first computer or user. Your program should know and inform the user if an illegal move was made (cell already occupied). The program should also announce if one of the players wins or if a draw is achieved. While it is desirable for your program to play a strong game, this is not an Artificial Intelligence course so if your program does not play at a world champion level you will not be penalized for it

Answer 1

#include <iostream>

#include <algorithm>

#include <vector>

#include <array>

using std::cout;

using std::cin;

using std::endl;

#define WIN 1000

#define DRAW 0

#define LOSS -1000

#define AI_MARKER 'O'

#define PLAYER_MARKER 'X'

#define EMPTY_SPACE '-'

#define START_DEPTH 0

// Print game state

void print_game_state(int state)

{

  if (WIN == state) { cout << "WIN" << endl; }

  else if (DRAW == state) { cout << "DRAW" << endl; }

  else if (LOSS == state) { cout << "LOSS" << endl; }

}

// All possible winning states

std::vector<std::vector<std::pair<int, int>>> winning_states

{

  // Every row

  { std::make_pair(0, 0), std::make_pair(0, 1), std::make_pair(0, 2) },

  { std::make_pair(1, 0), std::make_pair(1, 1), std::make_pair(1, 2) },

  { std::make_pair(2, 0), std::make_pair(2, 1), std::make_pair(2, 2) },

  // Every column

  { std::make_pair(0, 0), std::make_pair(1, 0), std::make_pair(2, 0) },

  { std::make_pair(0, 1), std::make_pair(1, 1), std::make_pair(2, 1) },

  { std::make_pair(0, 2), std::make_pair(1, 2), std::make_pair(2, 2) },

  // Every diagonal

  { std::make_pair(0, 0), std::make_pair(1, 1), std::make_pair(2, 2) },

  { std::make_pair(2, 0), std::make_pair(1, 1), std::make_pair(0, 2) }

};

// Print the current board state

void print_board(char board[3][3])

{

  cout << endl;

  cout << board[0][0] << " | " << board[0][1] << " | " << board[0][2] << endl;

  cout << "----------" << endl;

  cout << board[1][0] << " | " << board[1][1] << " | " << board[1][2] << endl;

  cout << "----------" << endl;

  cout << board[2][0] << " | " << board[2][1] << " | " << board[2][2] << endl << endl;

}

// Get all available legal moves (spaces that are not occupied)

std::vector<std::pair<int, int>> get_legal_moves(char board[3][3])

{

  std::vector<std::pair<int, int>> legal_moves;

  for (int i = 0; i < 3; i++)

  {

    for (int j = 0; j < 3; j++)

    {

      if (board[i][j] != AI_MARKER && board[i][j] != PLAYER_MARKER)

      {

        legal_moves.push_back(std::make_pair(i, j));

      }

    }

  }

  return legal_moves;

}

// Check if a position is occupied

bool position_occupied(char board[3][3], std::pair<int, int> pos)

{

  std::vector<std::pair<int, int>> legal_moves = get_legal_moves(board);

  for (int i = 0; i < legal_moves.size(); i++)

  {

    if (pos.first == legal_moves[i].first && pos.second == legal_moves[i].second)

    {

      return false;

    }

  }

  return true;

}

// Get all board positions occupied by the given marker

std::vector<std::pair<int, int>> get_occupied_positions(char board[3][3], char marker)

{

  std::vector<std::pair<int, int>> occupied_positions;

  for (int i = 0; i < 3; i++)

  {

    for (int j = 0; j < 3; j++)

    {

      if (marker == board[i][j])

      {

        occupied_positions.push_back(std::make_pair(i, j));

      }

    }

  }

  return occupied_positions;

}

// Check if the board is full

bool board_is_full(char board[3][3])

{

  std::vector<std::pair<int, int>> legal_moves = get_legal_moves(board);

  if (0 == legal_moves.size())

  {

    return true;

  }

  else

  {

    return false;

  }

}

// Check if the game has been won

bool game_is_won(std::vector<std::pair<int, int>> occupied_positions)

{

  bool game_won;

  for (int i = 0; i < winning_states.size(); i++)

  {

    game_won = true;

    std::vector<std::pair<int, int>> curr_win_state = winning_states[i];

    for (int j = 0; j < 3; j++)

    {

      if (!(std::find(std::begin(occupied_positions), std::end(occupied_positions), curr_win_state[j]) != std::end(occupied_positions)))

      {

        game_won = false;

        break;

      }

    }

    if (game_won)

    {

      break;

    }

  }

  return game_won;

}

char get_opponent_marker(char marker)

{

  char opponent_marker;

  if (marker == PLAYER_MARKER)

  {

    opponent_marker = AI_MARKER;

  }

  else

  {

    opponent_marker = PLAYER_MARKER;

  }

  return opponent_marker;

}

// Check if someone has won or lost

int get_board_state(char board[3][3], char marker)

{

  char opponent_marker = get_opponent_marker(marker);

  std::vector<std::pair<int, int>> occupied_positions = get_occupied_positions(board, marker);

  bool is_won = game_is_won(occupied_positions);

  if (is_won)

  {

    return WIN;

  }

  occupied_positions = get_occupied_positions(board, opponent_marker);

  bool is_lost = game_is_won(occupied_positions);

  if (is_lost)

  {

    return LOSS;

  }

  bool is_full = board_is_full(board);

  if (is_full)

  {

    return DRAW;

  }

  return DRAW;

}

// Apply the minimax game optimization algorithm

std::pair<int, std::pair<int, int>> minimax_optimization(char board[3][3], char marker, int depth, int alpha, int beta)

{

  // Initialize best move

  std::pair<int, int> best_move = std::make_pair(-1, -1);

  int best_score = (marker == AI_MARKER) ? LOSS : WIN;

  // If we hit a terminal state (leaf node), return the best score and move

  if (board_is_full(board) || DRAW != get_board_state(board, AI_MARKER))

  {

    best_score = get_board_state(board, AI_MARKER);

    return std::make_pair(best_score, best_move);

  }

  std::vector<std::pair<int, int>> legal_moves = get_legal_moves(board);

  for (int i = 0; i < legal_moves.size(); i++)

  {

    std::pair<int, int> curr_move = legal_moves[i];

    board[curr_move.first][curr_move.second] = marker;

    // Maximizing player's turn

    if (marker == AI_MARKER)

    {

      int score = minimax_optimization(board, PLAYER_MARKER, depth + 1, alpha, beta).first;

      // Get the best scoring move

      if (best_score < score)

      {

        best_score = score - depth * 10;

        best_move = curr_move;

        // Check if this branch's best move is worse than the best

        // option of a previously search branch. If it is, skip it

        alpha = std::max(alpha, best_score);

        board[curr_move.first][curr_move.second] = EMPTY_SPACE;

        if (beta <= alpha)

        {

          break;

        }

      }

    } // Minimizing opponent's turn

    else

    {

      int score = minimax_optimization(board, AI_MARKER, depth + 1, alpha, beta).first;

      if (best_score > score)

      {

        best_score = score + depth * 10;

        best_move = curr_move;

        // Check if this branch's best move is worse than the best

        // option of a previously search branch. If it is, skip it

        beta = std::min(beta, best_score);

        board[curr_move.first][curr_move.second] = EMPTY_SPACE;

        if (beta <= alpha)

        {

          break;

        }

      }

    }

    board[curr_move.first][curr_move.second] = EMPTY_SPACE; // Undo move

  }

  return std::make_pair(best_score, best_move);

}

// Check if the game is finished

bool game_is_done(char board[3][3])

{

  if (board_is_full(board))

  {

    return true;

  }

  if (DRAW != get_board_state(board, AI_MARKER))

  {

    return true;

  }

  return false;

}

int main()

{

  char board[3][3] = { EMPTY_SPACE };

  cout << "********************************\n\n\tTic Tac Toe AI\n\n********************************" << endl << endl;

  cout << "Player = X\t AI Computer = O" << endl << endl;

  print_board(board);

  while (!game_is_done(board))

  {

    int row, col;

    cout << "Row play: ";

    cin >> row;

    cout << "Col play: ";

    cin >> col;

    cout << endl << endl;

    if (position_occupied(board, std::make_pair(row, col)))

    {

      cout << "The position (" << row << ", " << col << ") is occupied. Try another one..." << endl;

      continue;

    }

    else

    {

      board[row][col] = PLAYER_MARKER;

    }

    std::pair<int, std::pair<int, int>> ai_move = minimax_optimization(board, AI_MARKER, START_DEPTH, LOSS, WIN);

    board[ai_move.second.first][ai_move.second.second] = AI_MARKER;

    print_board(board);

  }

  cout << "********** GAME OVER **********" << endl << endl;

  int player_state = get_board_state(board, PLAYER_MARKER);

  cout << "PLAYER "; print_game_state(player_state);

  return 0;

}