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 4x4 or 5x5 etc, every thing looks working fine for 3x3 board but it becomes so slow if i choose the board to be 4x4.
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();
}