Tic Tac Toe game AI in C++

Question

I wrote a Tic Tac Toe game from scratch a couple days ago.

My AI doesn't always make the best moves, so I'd like some advice on how to improve it. I also hardcoded a move in a very specific situation to prevent it from losing, so I'd like some advice on that. I read about minimax, but I haven't learned algorithms yet, so I don't know how to implement (I will try to do a minimax Tic Tac Toe later).

Any other advice are welcome too!

main.cpp

#include <iostream>
#include <chrono>

#include "Board.h"

using namespace std;
using namespace std::chrono;

int main()
{
    cout << "~ Eric Li's Tic Tac Toe game C++ (April 17, 2016) ~" << endl;
    cout << "Would you like to play tic-tac-toe? (y/n) ";
    string answer;
    cin >> answer;

    while (answer == "y") {

        Board board;
        bool firstMoveRandom = true;
        string winner;

        while (!board.gameEnd() && !board.gameWinner(winner)) {

            cout << "Current board: " << endl;
            board.displayBoard();
            cout << "____________________" << endl;

            if (board.getTurn() == "u") {

                firstMoveRandom = false;

                cout << "Your turn" << endl;

                int x;
                int y;

                try {
                    cout << "Please enter x (0 to 2): ";
                    cin >> x;

                    cout << "Please enter y (0 to 2): ";
                    cin >> y;
                    if (y < 0 || y > 2 || x < 0 || x > 2) {
                        throw runtime_error("Error: must enter between 0 and 2");
                    }
                }
                catch (runtime_error& e) {
                    cout << e.what() << endl;
                }

                board.userPlay(x, y);
            }

            else if (board.getTurn() == "c") {
                if (firstMoveRandom) {
                    board.computerPlayRandom();
                    firstMoveRandom = false;
                }
                else {
                    high_resolution_clock::time_point t1 = high_resolution_clock::now();

                    board.computerPlay();

                    high_resolution_clock::time_point t2 = high_resolution_clock::now();
                    double duration = duration_cast<microseconds>( t2 - t1 ).count();
                    cout << duration/1000000 << " seconds" << endl;
                }
            }
        }

        if (winner.size() != 0) {
            cout << "The " << winner << " has won the game!" << endl;
        }

        else cout << "The game was a tie!" << endl;

        board.displayBoard();

        cout << "Would you like to play again? (y/n) ";
        cin >> answer;
    }

    return 0;
}

Board.cpp

#include "Board.h"

Board::Board()
{
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            board_[i][j] = " ";
        }
    }

    srand(time(0));
    if (rand()%2 == 0) {
        user_ = "X";
        computer_ = "O";
        turn_ = "u";
        uStart_ = true;
    }
    else {
        user_ = "O";
        computer_ = "X";
        turn_ = "c";
        uStart_ = false;
    }
}

Board::~Board()
{

}

string Board::getTurn()
{
    return turn_;
}

bool Board::userPlay(int x, int y)
{
    if (board_[y][x] == " ") {
        board_[y][x] = user_;
        turn_ = "c";
        return true;
    }
    return false;
}

bool Board::playMove(int x, int y)
{
    if (board_[y][x] == " ") {
        board_[y][x] = computer_;
        turn_ = "u";
        return true;
    }
    else {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board_[i][j] == " ") {
                    board_[i][j] = computer_;
                    turn_ = "u";
                    return true;
                }
            }
        }
    }
    return false;
}

void Board::computerPlayRandom()
{
    srand(time(0));
    int x = rand() % 3;
    int y = rand() % 3;

    if (rand() % 2 == 0) {
        playMove(x, y);
    }
    else {
        playMove(x, x);
    }
}

void Board::computerPlay()
{
    int computerState[3][3];
    readBoard(computerState);

    cout << "Computer State: " << endl;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cout << computerState[i][j] << " ";
        }
        cout << endl;
    }
    int x = 1;
    int y = 1;

    findBestMove(computerState, x, y);

    playMove(x, y);
}

void Board::readBoard(int boardState[3][3])
{
    // To calculate which square gives a potential fork for the AI
    bool boardStateHorizontal[3][3], boardStateVertical[3][3], boardStateDDiagonal[3][3], boardStateADiagonal[3][3];
    // To calculate which square gives a potential fork for the user
    bool bsh[3][3], bsv[3][3], bsdd[3][3], bsad[3][3];

    // Initializing the arrays of state
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board_[i][j] != " ") {
                boardState[i][j] = -1;
            }
            else {
                boardState[i][j] = 0;
            }
            boardStateHorizontal[i][j] = false;
            boardStateVertical[i][j] = false;
            boardStateDDiagonal[i][j] = false;
            boardStateADiagonal[i][j] = false;
            bsh[i][j] = false;
            bsv[i][j] = false;
            bsdd[i][j] = false;
            bsad[i][j] = false;
        }
    }

    // Hard-coded move for the specific situation where
    // X - -
    // - O -
    // - - X
    // The only right move is to avoid corners (AI is playing O)

    int boardSum = 0;
    cout << "Board State: " << endl;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cout << boardState[i][j] << " ";
            boardSum += boardState[i][j];
        }
        cout << endl;
    }

    if (boardSum == -3) {
        if ((board_[0][0] == board_[2][2] && board_[2][0] == board_[0][2]) 
            && board_[1][1] != " " && (board_[0][0] != " " || board_[2][0] != " ")) {
            boardState[0][1] += 1000000;
            boardState[2][1] += 1000000;
            boardState[1][0] += 1000000;
            boardState[1][2] += 1000000;
            return;
        }
    }


    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            // Computing Horizontal wins
            // If the square is empty and the other two squares in the same row are filled and the same; e.g. X X * where * is the square we're evaluating
            if (boardState[i][j % 3] != -1 && board_[i][(j + 1) % 3] != " " 
                && board_[i][(j + 1) % 3] == board_[i][(j + 2) % 3]) {
                // If they're filled by the computer
                if (board_[i][(j + 1) % 3] == computer_) {
                    boardState[i][j % 3] += 1000;
                }
                // If they're filled by the user
                else if (board_[i][(j + 1) % 3] == user_){
                    boardState[i][j % 3] += 100;
                }
            }

            // Computing Vertical wins
            // If the square is empty and the other two squares in the same column are filled and the same; e.g. see "Computing Horizontal wins"
            if (boardState[j % 3][i] != -1 && board_[(j + 1) % 3][i] != " " 
                && board_[(j + 1) % 3][i] == board_[(j + 2) % 3][i]) {
                // If they're filled by the computer
                if (board_[(j + 1) % 3][i] == computer_) {
                    boardState[j % 3][i] += 1000;
                }
                // If they're filled by the user
                else if (board_[(j + 1) % 3][i] == user_) {
                    boardState[j % 3][i] += 100;
                }
            }

            // Computing Horizontal points
            // If the square is empty and one of the other two squares is empty, but the other is filled; e.g. X - * where * is the square we're evaluating
            // A move that satisfies this condition forces the opponent to block
            if (boardState[i][j % 3] != -1 
                && (board_[i][(j + 1) % 3] == " " || board_[i][(j + 2) % 3] == " ") 
                && board_[i][(j + 1) % 3] != board_[i][(j + 2) % 3]) {
                // If it's filled by the computer
                if (board_[i][(j + 1) % 3] == computer_ || board_[i][(j + 2) % 3] == computer_) {
                    boardState[i][j % 3] += 10;
                    boardStateHorizontal[i][j % 3] = true;
                }
                // If it's filled by the user
                else if (board_[i][(j + 1) % 3] == user_ || board_[i][(j + 2) % 3] == user_) {
                    boardState[i][j % 3] += 10;
                    if (uStart_) {
                        bsh[i][j%3] = true;
                    }
                }
            }

            // Computing Vertical points
            // If the square is empty and one of the other two squares is empty, but the other is filled; e.g. see "Computing Horizontal points"
            // A move that satisfies this condition forces the opponent to block
            if (boardState[j % 3][i] != -1 
                && (board_[(j + 1) % 3][i] == " " || board_[(j + 2) % 3][i] == " ") 
                && board_[(j + 1) % 3][i] != board_[(j + 2) % 3][i]) {
                // If it's filled by the computer
                if (board_[(j + 1) % 3][i] == computer_ || board_[(j + 2) % 3][i] == computer_) {
                    boardState[j % 3][i] += 10;
                    boardStateVertical[j % 3][i] = true;
                }
                // If it's filled by the user
                else if (board_[(j + 1) % 3][i] == user_ || board_[(j + 2) % 3][i] == user_){
                    boardState[j % 3][i] += 10;
                    if (uStart_) {
                        bsv[j % 3][i] = true;
                    }
                }
            }

            // Horizontal potential
            // If the square is empty and the other two squares in the same row are empty; e.g. empty row
            if (boardState[i][j % 3] != -1 && board_[i][(j + 1) % 3] == " " 
                && " " == board_[i][(j + 2) % 3]) {
                boardState[i][j % 3] ++;
            }

            // Vertical potential
            // If the square is empty and the other two squares in the same column are empty; empty column
            if (boardState[j % 3][i] != -1 && board_[(j + 1) % 3][i] == " " 
                && " " == board_[(j + 2) % 3][i]) {
                boardState[j % 3][i] ++;
            }
        }

        // Descending diagonal wins
        // If the square is empty, and the other two squares on the descending diagonal are the same;
        // e.g. X - -
        //      - X - where * is the square we're evaluating
        //      - - *
        if (boardState[i % 3][i % 3] != -1 
            && board_[(i + 1) % 3][(i + 1) % 3] != " " 
            && board_[(i + 1) % 3][(i + 1) % 3] == board_[(i + 2) % 3][(i + 2) % 3]) {
            // If they're filled by the computer
            if (board_[(i + 1) % 3][(i + 1) % 3] == computer_) {
                boardState[i % 3][i % 3] += 1000;
            }
            // If they're filled by the user
            else if (board_[(i + 1) % 3][(i + 1) % 3] == user_) {
                boardState[i % 3][i % 3] += 100;
            }
        }

        // Ascending diagonal wins
        // If the square is empty, and the other two squares on the ascending diagonal are the same; e.g. see "Ascending Diagonal wins"
        if (boardState[(5 - i) % 3][i % 3] != -1 
            && board_[(4 - i) % 3][(i + 1) % 3] != " " 
            && board_[(4 - i) % 3][(i + 1) % 3] == board_[(3 - i) % 3][(i + 2) % 3]) {
            // If they're filled by the computer
            if (board_[(4 - i) % 3][(i + 1) % 3] == computer_) {
                boardState[(5 - i) % 3][i % 3] += 1000;
            }
            // If they're filled by the user
            else if (board_[(4 - i) % 3][(i + 1) % 3] == user_) {
                boardState[(5 - i) % 3][i % 3] += 100;
            }
        }

        // Descending diagonal points
        // If the square is empty and one of the other two squares is empty, but the other is filled;
        // e.g. X - -
        //      - - - where * is the square we're evaluating
        //      - - *
        if (boardState[i % 3][i % 3] != -1 
            && (board_[(i + 1) % 3][(i + 1) % 3] == " " || board_[(i + 2) % 3][(i + 2) % 3] == " ") 
            && board_[(i + 1) % 3][(i + 1) % 3] != board_[(i + 2) % 3][(i + 2) % 3]) {
            // If it's filled by the computer
            if (board_[(i + 1) % 3][(i + 1) % 3] == computer_ || board_[(i + 2) % 3][(i + 2) % 3] == computer_) {
                boardState[i % 3][i % 3] += 10;
                boardStateDDiagonal[i % 3][i % 3] = true;
            }
            // If it's filled by the user
            else if (board_[(i + 1) % 3][(i + 1) % 3] == user_ || board_[(i + 2) % 3][(i + 2) % 3] == user_){
                boardState[i % 3][i % 3] += 10;
                if (uStart_) {
                    bsdd[i % 3][i % 3] = true;
                }
            }
        }

        // Ascending diagonal points
        // If the square is empty and one of the other two squares is empty, but the other is filled
        if (boardState[(5 - i) % 3][i % 3] != -1 
            && (board_[(4 - i) % 3][(i + 1) % 3] == " " || board_[(3 - i) % 3][(i + 2) % 3] == " ")
            && board_[(4 - i) % 3][(i + 1) % 3] != board_[(3 - i) % 3][(i + 2) % 3]) {
            // If it's filled by the computer
            if (board_[(4 - i) % 3][(i + 1) % 3] == computer_ || board_[(3 - i) % 3][(i + 2) % 3] == computer_) {
                boardState[(5 - i) % 3][i % 3] += 10;
                boardStateADiagonal[(5 - i) % 3][i % 3] = true;
            }
            // If it's filled by the user
            else if (board_[(4 - i) % 3][(i + 1) % 3] == user_ || board_[(3 - i) % 3][(i + 2) % 3] == user_) {
                boardState[(5 - i) % 3][i % 3] += 10;
                if (uStart_) {
                    bsad[(5 - i) % 3][i % 3] = true;
                }
            }
        }

        /*// Descending diagonal potential
         // If the square is empty, and the other two squares on the descending diagonal are empty
         if (boardState[i % 3][i % 3] != -1 
             && board_[(i + 1) % 3][(i + 1) % 3] == " " 
             && " " == board_[(i + 2) % 3][(i + 2) % 3]) {
             boardState[i % 3][i % 3]++;
         }

         // Ascending diagonal potential
         // If the square is empty, and the other two squares on the ascending diagonal are empty
         if (boardState[(5 - i) % 3][i % 3] != -1 
             && board_[(4 - i) % 3][(i + 1) % 3] == " " && " " == board_[(3 - i) % 3][(i + 2) % 3]) {
             boardState[(5 - i) % 3][i % 3] ++;
         }*/
    }

    // Calculating forks
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            // If the square generates a fork for the AI, +30 points
            if (boardStateVertical[i][j]) {
                if (boardStateHorizontal[i][j]) {
                    boardState[i][j] += 30;
                }
                if (boardStateADiagonal[i][j]) {
                    boardState[i][j] += 30;
                }
                if (boardStateDDiagonal[i][j]) {
                    boardState[i][j] += 30;
                }
            }
            if (boardStateHorizontal[i][j]) {
                if (boardStateADiagonal[i][j]) {
                    boardState[i][j] += 30;
                }
                if (boardStateDDiagonal[i][j]) {
                    boardState[i][j] += 30;
                }
            }
            if (boardStateDDiagonal[i][j]) {
                if (boardStateADiagonal[i][j]) {
                    boardState[i][j] += 30;
                }
            }

            // If the square generates a fork for the user, +25 points
            // Better to create a fork first than to block a potential one from the user
            if (bsv[i][j]) {
                if (bsh[i][j]) {
                    boardState[i][j] += 25;
                }
                if (bsad[i][j]) {
                    boardState[i][j] += 25;
                }
                if (bsdd[i][j]) {
                    boardState[i][j] += 25;
                }
            }
            if (bsh[i][j]) {
                if (bsad[i][j]) {
                    boardState[i][j] += 25;
                }
                if (bsdd[i][j]) {
                    boardState[i][j] += 25;
                }
            }
            if (bsad[i][j]) {
                if (bsdd[i][j]) {
                    boardState[i][j] += 25;
                }
            }
        }
    }

}

void Board::findBestMove(int boardState[3][3], int& x, int& y)
{
    // Find the square that has the highest points on boardState[3][3]
    int bestScore = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (boardState[i][j] > bestScore) {
                bestScore = boardState[i][j];
                x = j;
                y = i;
            }
            // If two squares have the same points, randomize the choice
            else if (boardState[i][j] == bestScore && rand()%2) {
                bestScore = boardState[i][j];
                x = j;
                y = i;
            }
        }
    }
    // If the center is the best score, don't randomize
    if (boardState[1][1] == bestScore) {
        x = 1;
        y = 1;
    }
}

void Board::clearBoard()
{
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            board_[i][j] = " ";
        }
    }
}

void Board::displayBoard()
{
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cout << "" << board_[i][j];
            if (j < 2) {
                cout << "|";
            }
        }
        if (i < 2) {
            cout << endl << "-+-+-" << endl;
        }
        else {
            cout << endl;
        }
    }
}

bool Board::gameEnd()
{
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board_[i][j] == " ") {
                return false;
            }
        }
    }
    return true;
}

bool Board::gameWinner(string& winner)
{
    for (int i = 0; i < 3; i++) {

        // Horizontal
        // If the square is empty and the other two squares in the same row are empty
        if (board_[i][0] == board_[i][1] && board_[i][1] == board_[i][2] && board_[i][0] != " ") {
            if (board_[i][0] == computer_) {
                winner = "computer";
                return true;
            }
            else {
                winner = "user";
                return true;
            }
        }

        // Vertical
        // If the square is empty and the other two squares in the same column are empty
        if (board_[0][i] == board_[1][i] && board_[1][i] == board_[2][i] && board_[0][i] != " ") {
            if (board_[i % 3][i] == computer_) {
                winner = "computer";
                return true;
            }
            else {
                winner = "user";
                return true;
            }

        }
    }

    // Descending diagonal
    // If the square is empty, and the other two squares on the descending diagonal are empty
    if (board_[0][0] == board_[1][1] && board_[1][1] == board_[2][2] && board_[0][0] != " ") {
        if (board_[0][0] == computer_) {
            winner = "computer";
            return true;
        }
        else {
            winner = "user";
            return true;
        }
    }

    // Ascending diagonal
    // If the square is empty, and the other two squares on the ascending diagonal are empty
    if (board_[2][0] == board_[1][1] && board_[1][1] == board_[0][2] && board_[2][0] != " ") {
        if (board_[2][0] == computer_) {
            winner = "computer";
            return true;
        }
        else {
            winner = "user";
            return true;
        }
    }

    return false;
}

Board.h

#ifndef Board_h
#define Board_h

#include <stdio.h>
#include <string>
#include <iostream>

using namespace std;

class Board {
public:
    Board();
    ~Board();

    string getTurn();

    bool userPlay(int x, int y);
    bool playMove(int x, int y);

    void computerPlayRandom();
    void computerPlay();

    void readBoard(int boardState[3][3]);
    void findBestMove(int boardState[3][3], int& x, int& y);

    void clearBoard();
    void displayBoard();

    bool gameEnd();
    bool gameWinner(string& winner);

private:
    string board_[3][3];
    string user_;
    string computer_;
    string turn_;
    bool uStart_;
};

#endif /* Board_hpp */

Answer 1

Optimal strategy

One of the comments on this answer points to http://xkcd.com/832/ which gives the complete optimal strategy for Tic-Tac_Toe.

This is not to say that it wouldn't be a good programming exercise to implement a Minimax solution. But it isn't necessary.

using namespace std

using namespace std;

Why is “using namespace std;” considered bad practice?

Note that it is especially bad practice to put a using namespace in a .h file, as those may be included by other files that did not intend to use std.

I personally find it easier to read std::string than figure out that string is supposed to be std::string. Another reason to avoid this habit.

do/while

    cin >> answer;

    while (answer == "y") {

and to finish the loop

        cin >> answer;
    }

Consider

    do {

Everything in between could stay the same.

        std::cin >> answer;
    } while (answer == "y" || answer == "Y");

This will start playing without asking but will ask before subsequent runs. You save duplicating the cin code.

Also I checked for an uppercase Y, which seems a reasonable input.

Don't use try/catch as a control structure

                try {
                    cout << "Please enter x (0 to 2): ";
                    cin >> x;

                    cout << "Please enter y (0 to 2): ";
                    cin >> y;
                    if (y < 0 || y > 2 || x < 0 || x > 2) {
                        throw runtime_error("Error: must enter between 0 and 2");
                    }
                }
                catch (runtime_error& e) {
                    cout << e.what() << endl;
                }

You could just say

                std::cout << "Please enter x (0 to 2): ";
                std::cin >> x;

                std::cout << "Please enter y (0 to 2): ";
                std::cin >> y;
                if (y < 0 || y > 2 || x < 0 || x > 2) {
                    std::cout << "Error: must enter between 0 and 2" << std::endl;
                    continue;
                }

Then you wouldn't have to go through the extra work of declaring the try block and catching the exception.

I also added the continue since otherwise it calls board.userPlay with invalid values.

Keep it together

            }

            else if (board.getTurn() == "c") {

Please don't separate a } from its else. Personally I prefer them all on the same line, but if you do want to do it this way, please always write it

            }
            else if (board.getTurn() == "c") {

That way it's easy to see that the two go together. The compiler won't care, but human readers will find this easier to follow.

Also please don't put comments in there.

Avoid the single statement forms of control structures

        if (winner.size() != 0) {
            cout << "The " << winner << " has won the game!" << endl;
        }

        else cout << "The game was a tie!" << endl;

It's safer and easier to follow to just always use the block form.

        if (winner.size() == 0) {
            std::cout << "The game was a tie!" << std::endl;
        }
        else {
            std::cout << "The " << winner << " has won the game!" << std::endl;
        }

I also find the else logic easier if it is a positive statement in the if.