Simple Tic-Tac-Toe with Minimax Algorithm

Question

I have implemented AI to tictactoe game by using Minimax Algorithm. The game looks working okay and AI is intersecting the player moves to block him from winning the game.

I would like to know if I implemented the Minimax Algorithm correctly. if so, 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 int x = 0;
        unsigned int y = 0;
    };

    Player board[3][3];

public:
    Game() 
    {
        for (unsigned int i = 0; i < 3; i++)
        {
            for (unsigned int j = 0; j < 3; j++)
            {
                board[i][j] = Player::none;
            }
        }
    }

    void printBoard()
    {
        std::cout << "+-----------------+";
        for (unsigned int i = 0; i < 3; i++)
        {
            std::cout << "\n|";
            for (unsigned int j = 0; j < 3; j++)
            {
                std::cout << std::setw(3) << static_cast<char>(board[i][j]) << std::setw(3) << " |";
            }
        }
        std::cout << "\n+-----------------+\n";
    }

    bool isTie()
    {
        for (unsigned int i = 0; i < 3; i++)
        {
            if (board[i][0] == Player::none || board[i][1] == Player::none || board[i][2] == Player::none)
                return false;
        }
        return true;
    }

    bool checkWin(Player player)
    {
        for (unsigned int i = 0; i < 3; i++)
        {
            // Check horizontals
            if (board[i][0] == player && board[i][1] == player && board[i][2] == player)
                return true;

            // Check verticals
            if (board[0][i] == player && board[1][i] == player && board[2][i] == player)
                return true;
        }

        // Check diagonals
        if (board[0][0] == player && board[1][1] == player && board[2][2] == player)
            return true;

        if (board[0][2] == player && board[1][1] == player && board[2][0] == player)
            return true;

        return false;
    }

    Move minimax() 
    {
        int score = std::numeric_limits<int>::max();
        Move move;

        for (unsigned int i = 0; i < 3; i++)
        {
            for (unsigned int j = 0; j < 3; j++)
            {
                if (board[i][j] == Player::none)
                {
                    board[i][j] = Player::computer;

                    int temp = maxSearch();

                    if (temp < score)
                    {
                        score = temp;
                        move.x = i;
                        move.y = j;
                    }
                    board[i][j] = Player::none;
                }
            }
        }

        return move;
    }

    int maxSearch() 
    {
        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 int i = 0; i < 3; i++)
        {
            for (unsigned int j = 0; j < 3; j++)
            {
                if (board[i][j] == Player::none)
                {
                    board[i][j] = Player::human;
                    score = std::max(score, minSearch());
                    board[i][j] = Player::none;
                }
            }
        }

        return score;
    }

    int minSearch()
    {
        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 int i = 0; i < 3; i++)
        {
            for (unsigned int j = 0; j < 3; j++)
            {
                if (board[i][j] == Player::none)
                {
                    board[i][j] = Player::computer;
                    score = std::min(score, maxSearch());
                    board[i][j] = Player::none;
                }
            }
        }

        return score;
    }

    void getHumanMove()
    {
        bool fail = true;
        unsigned int 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;
    }

    void play()
    {
        unsigned int 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;

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

int main()
{
    Game tictactoe;
    tictactoe.play();
    std::cin.ignore();
}

Answer 1

Here are some things that may help you improve your code. First, yes, you implemented the minimax algorithm correctly, but there's an easy improvement you can make that I'll show later.

Avoid magic numbers

Although it's not too bad, the unnamed constant 3 could instead be made a named constant that indicates the size of the square board. By assigning this a name, one could easily adapt the game to 4x4, 5x5 or larger grids if desired.

Write generic rather than specific code

The checkWin code is correct, but I think it could be made better by making it generic rather than specific. That is, what the code seeks is whether all of the row or column or diagonal matches the passed player value. Rather than manually coding like this:

for (unsigned int i = 0; i < 3; i++)
{
    // Check horizontals
    if (board[i][0] == player && board[i][1] == player && board[i][2] == player)
        return true;

    // Check verticals
    if (board[0][i] == player && board[1][i] == player && board[2][i] == player)
        return true;
}

I'd probably code that portion like this:

for (unsigned i{0}; i < gridsize; ++i) {
    bool row{true};
    bool col{true};
    for (unsigned int j{0}; j < gridsize; ++j) {
        row &= board[i][j] == player;
        col &= board[j][i] == player;
    }
    if (row || col) {
        return true;
    }
}

Use const where practical

Many of the functions, including printBoard(), isTie(), and checkWin() do not alter the underlying object and therefore should be declared const.

Use appropriate data types

The turn variable is declared as an unsigned int but is probably more appropriately a bool because it's only 0 or 1. Alternatively, one could assign the current Player value types in an array and bounce back and forth between Player::human and Player::computer.

Consider improving the algorithm

If the human chooses 00, 22, and 12 in that order, we get this board:

+-----------------+
|  X  |  O  |  -  |
|  -  |  O  |  X  |
|  -  |  -  |  X  |
+-----------------+

The most logical move would be for the computer to place its O at 21, thus winning the game. But it doesn't with the current code. Instead, it puts its O in the upper right corner. Either move inevitably leads to a computer win, but why not choose the immediate win? One simple way to do that is to introduce the concept of tree level into the minimax routine. This changes the maxSearch and minSearch routines to accept an int level as a parameter. Then within maxSearch, where minSearch is called, one could write the line like this:

score = std::max(score, minSearch(level+1)-level);

Within minSearch, the call to maxSearch would be this:

score = std::min(score, maxSearch(level+1)+level);

This simply adjusts the scoring such that shorter trees have lower (more favorable) scores than longer ones.

Avoid doing extra work

Instead of iterating through all of the squares in isTie(), the program could instead simply keep a running total of available squares and isTie() would reduce to this:

bool isTie() const { return available == 0; }

Separate responsibilities

The Model-View-Controller design pattern is often useful for programs like this. Because the view in this case is essentially just printing the board to std::cout, we can simplify a bit and just have a model, the TicTacToe class, and a controller, the Game class. Doing so would make it much easier to make changes to the code such as porting it to use a GUI or adapting it to be playable remotely via a socket.