Simple Tic-Tac-Toe with Minimax Algorithm - follow up

Question

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();
}

• coderodde: Can you add a sample game with all the user input? I have difficulties in proceeding after the "Enter your move in coordinate form[row, col]. ex: 02" message.
• MORTAL: @coderodde make sure DIM is equal 3 and just type the user input as 02 or 22 or 00
• coderodde: As a side note to anyone compiling and running on Xcode; start the program from the command line instead. For some reason Xcode could not print the boards.
• Jakob Lovern: Have you considered that it's so slow because your depth is exponentially larger?
• MORTAL: @JakobLovern ... yes.... it solves the performance issue if i limit the depth to 6.

Answer 1

Looks good! Runs without any warnings on clang trunk with C++17, so good job on that +1 :).

But I still have some suggestions you could incorporate.

1. If you odr-use Game::DIM (ignoring that all caps names are ugly IMO) then you will have a ill-formed, no diagnostics required program, which is pretty bad. Make it constexpr instead, because as of C++17, static const data members of classes are implicitly inline, and so doesn't suffer from the same problem.

   Or you could provide a definition.

2. Mark functions that do not throw noexcept, if you compile with exceptions.

3. Mark classes that shouldn't be inherited from with final.

4. Use pre-increment if you don't care about returning the previous value.

5. Instead of the do while loop and exit in Game::play, you can use an infinite loop and break out when needed.

6. Don't abuse integers as booleans please. turn really should be renamed to something like isHumanTurn and should be a boolean.

7. For a single character, use single quotes. That will avoid a call to std::strlen, even if the compiler will optimize it away anyways :).

8. In Game::play, if either the player or the computer plays, then remaining is going to get decremented. It's clear in the else branch of the computer, but for the player it's hidden in Game::getHumanMove. I suggest moving it out there and putting --remained; at the end of the branch.

9. In conjunction with the previous point, I'd suggest making Game::getHumanMove really just get the move that the human chose. That way, it does the same thing as Game::minimax, which is the computer's move, and then in Game::play actually set the board position to the appropriate value.

10. You seem to use std::numeric_limits<int> a lot. Maybe consider using an alias or define the constants yourself.

11. Sometimes you use braces for single statements in if conditions (line 206) and sometimes not (line 227). Be consistent please! :)

12. Use ranged for loops! So that instead of writing board[i][j] you'll use something like square. Maybe you'll find a better name than me.

13. You're still using magic numbers ;). Why is Game::maxSearch returning 10, -10 and 0? It's clear but maybe you'd like to define those constants somewhere. Maybe a static thread_local?

14. For DIM == 4, the game runs really slowly because of all the nested loops and the recursion everywhere, but you probably already know that. My algorithmic theory is not that great, so I can't help you on that, sorry...