Based on previous question i implemented most of suggestions. also, i have added Alpha-Beta pruning to minimize the calls. and making the game more generic to accept the board to be any value like 4×4 or 5×5 etc, every thing looks working fine for 3×3 board but it becomes so slow if i choose the board to be 4×4.
how can i improve it further?
#include <iostream> #include <iomanip> #include <algorithm> #include <limits> class Game { enum class Player { none = '-', human = 'X', computer = 'O' }; struct Move { unsigned x = 0; unsigned y = 0; }; static const unsigned DIM = 3; Player board[DIM][DIM]; unsigned remained; public: Game() : remained(DIM * DIM) { for (unsigned i = 0; i < DIM; i++) { for (unsigned j = 0; j < DIM; j++) { board[i][j] = Player::none; } } } void play() { unsigned turn = 0; bool exit = false; printBoard(); std::cout << "Enter your move in coordinate form[row, col]. ex: 02\n"; do { // human move if (turn == 0) { getHumanMove(); if (checkWin(Player::human)) { std::cout << "Human Wins\n"; exit = true; } } else { std::cout << "\nComputer Move: "; Move aimove = minimax(); std::cout << aimove.x << aimove.y << "\n"; board[aimove.x][aimove.y] = Player::computer; remained--; if (checkWin(Player::computer)) { std::cout << "Computer Wins\n"; exit = true; } } if (isTie()) { std::cout << "\n*** Tie ***\n"; exit = true; } turn ^= 1; printBoard(); } while (!exit); } private: void printBoard() { for (unsigned i = 0; i < DIM; i++) { std::cout << "\n|"; for (unsigned j = 0; j < DIM; j++) { std::cout << std::setw(3) << static_cast<char>(board[i][j]) << std::setw(3) << " |"; } } std::cout << "\n\n"; } bool isTie() { return remained == 0; } bool checkWin(Player player) { // check for row or column wins for (unsigned i = 0; i < DIM; ++i) { bool rowwin = true; bool colwin = true; for (unsigned j = 0; j < DIM; ++j) { rowwin &= board[i][j] == player; colwin &= board[j][i] == player; } if (colwin || rowwin) return true; } // check for diagonal wins bool diagwin = true; for (unsigned i = 0; i < DIM; ++i) diagwin &= board[i][i] == player; if (diagwin) return true; diagwin = true; for (unsigned i = 0; i < DIM; ++i) diagwin &= board[DIM - i - 1][i] == player; return diagwin; } Move minimax() { int score = std::numeric_limits<int>::max(); Move move; int level = 0; for (unsigned i = 0; i < DIM; i++) { for (unsigned j = 0; j < DIM; j++) { if (board[i][j] == Player::none) { board[i][j] = Player::computer; remained--; int temp = maxSearch(level, std::numeric_limits<int>::min(), std::numeric_limits<int>::max()); if (temp < score) { score = temp; move.x = i; move.y = j; } board[i][j] = Player::none; remained++; } } } return move; } int maxSearch(int level, int alpha, int beta) { if (checkWin(Player::human)) { return 10; } else if (checkWin(Player::computer)) { return -10; } else if (isTie()) { return 0; } int score = std::numeric_limits<int>::min(); for (unsigned i = 0; i < DIM; i++) { for (unsigned j = 0; j < DIM; j++) { if (board[i][j] == Player::none) { board[i][j] = Player::human; remained--; score = std::max(score, minSearch(level + 1, alpha, beta) - level); alpha = std::max(alpha, score); board[i][j] = Player::none; remained++; if (beta <= alpha) return alpha; } } } return score; } int minSearch(int level, int alpha, int beta) { if (checkWin(Player::human)) { return 10; } else if (checkWin(Player::computer)) { return -10; } else if (isTie()) { return 0; } int score = std::numeric_limits<int>::max(); for (unsigned i = 0; i < DIM; i++) { for (unsigned j = 0; j < DIM; j++) { if (board[i][j] == Player::none) { board[i][j] = Player::computer; remained--; score = std::min(score, maxSearch(level + 1, alpha, beta) + level); beta = std::min(beta, score); board[i][j] = Player::none; remained++; if (beta <= alpha) return beta; } } } return score; } void getHumanMove() { bool fail = true; unsigned x = -1, y = -1; do { std::cout << "Your Move: "; char c; std::cin >> c; x = c - '0'; std::cin >> c; y = c - '0'; fail = board[x][y] != Player::none; std::cin.clear(); std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); } while (fail); board[x][y] = Player::human; remained--; } }; int main() { Game tictactoe; tictactoe.play(); std::cin.ignore(); } 
