An unbeatable Tic-Tac-Toe game using exhaustive enumeration of all cases

Question

I am a beginner programmer and I've been trying to complete an unbeatable tic-tac-toe program, my code is below. The program itself works, but it seems rather inefficient, as I literally have to type out every case of possible victory or defeat. Any suggestions on how to make the code more efficient, or general suggestions, are appreciated! Everything is in one 500 line program.

#include <iostream>
using namespace std;

const short SIZE = 3;

class Board
{
    private:
        char square[SIZE][SIZE], aiMark, userMark;
    public:
        Board();
        void instructions();
        void showBoard();
        //Gets user pre-approved user move.  
        void userMove(short n, short n2)
        {square[n][n2] = userMark;}
        bool checker(short n, short n2);
        void computerMove(short n);
        bool win();
        bool lose();
        bool full();
        void clear();
};

//The constructor initializes each space (square) to a blank space and the markers to x and o.
Board::Board()
{
    userMark = 'x', aiMark = 'o';
    for(short i = 0; i < SIZE; i++){
        for(short j = 0; j < SIZE; j++){
            square[i][j] = ' ';
        }
    }
}

//Outlines the basic instructions and coordinate system.
void Board::instructions(){
    cout<<"This is a Tic Tac Toe progam. All of the standard rules of Tic Tac Toe apply (i.e. three in a row is a victory).\n"
        <<"A player may make a move by inputting the coordinance of the point they would like "
        <<"to mark (ex. type \"0 0\" for the first space).\nAn outline of the table "
        <<"and coordinacnes are below:\n"
        <<"\n0 0 | 0 1 | 0 2\n"
        <<"----|-----|----\n"
        <<"1 0 | 1 1 | 1 2\n"
        <<"----|-----|----\n"
        <<"2 0 | 2 1 | 2 2\n\n";

    cout<<"Player 1 will make the first move, followed by Player 2, until the game ends. "
        <<"You are the x's, while the computer is the o's.\n";

    cout<<"Press enter when you are ready to continue. ";
    cin.get();
}

//Shows the current state of the board.
void Board::showBoard()
{
    cout<<square[0][0]<<"  | "<<square[0][1]<<" | "<<square[0][2]<<endl
        <<"---|---|---"<<endl
        <<square[1][0]<<"  | "<<square[1][1]<<" | "<<square[1][2]<<endl
        <<"---|---|---"<<endl
        <<square[2][0]<<"  | "<<square[2][1]<<" | "<<square[2][2]<<endl;
}

//Checks to see if either the computer or user is making a move that has already been made.
bool Board::checker(short n, short n2)
{
    if(square[n][n2] == aiMark || square[n][n2] == userMark){
        return false;
    } else {
        return true;
    }
}

//A random assignment is made, then based on game type (i.e. if user is Player 1) a
//specialized move is selected, then if any cases of imminent defeat or victory are detected
//it responds accordingly.
void Board::computerMove(short n)
{
    if(win()){
        cout<<"You have won!\n";
        return;
    }

    if(full()){
        cout<<"You have tied the computer!\n";
        return;
    }

    short r, r2, r3;

    double seed;
    seed = time(0);
    srand(seed);
    r = 0 + rand() % 3;
    r2 = 0 + rand() % 3;

    //Starts off with a random move assignment in the event that no cases fit.
    while(!checker(r, r2)){
        r = 0 + rand() % 3;
        r2 = 0 + rand() % 3;
    }

    switch(n){
        //This code is employs strategies reserved specifically for when the computer moves second.
        case 1:
            if(checker(1,1) && (square[0][0] == userMark || square[0][2] == userMark || square[2][0] == userMark || square[2][2] == userMark)){
                //If the user begins in a corner AI moves to the center.
                r = 1, r2 = 1;
            } else if (square[1][1] == aiMark){
                //After AI moves to the center AI attempts to occupy an edge.
                if(checker(0,1)){
                    r = 0, r2 = 1;
                } else if (checker(1,0)){
                    r = 1, r2 = 0;
                } else if (checker(1,2)){
                    r = 1, r2 = 2;
                } else if (checker(2,1)){
                    r = 2, r2 = 1;
                }
            } else if (square[1][1] == userMark){
                //If the user begins in the center the AI moves to a corner.
                if(checker(0,0)){
                    r = 0, r2 = 0;
                } else if (checker(0,2)){
                    r = 0, r2 = 2;
                } else if (checker(2,0)){
                    r = 2, r2 = 0;
                } else if (checker(2,2)){
                    r = 2, r2 = 2;
                }
            } else if (square[0][1] == userMark || square[1][0] == userMark || square[1][2] == userMark || square[2][1] == userMark){
                //If the user starts on the side the AI moves to the center.
                r=1, r2=1;
            }
            break;

        //This code is employs strategies reserved specifically for when the computer moves first.
        case 2:
            if (checker(0,0) && checker(0,2) && checker(2,0) && checker(2,2)){
                //Makes sure that the computer starts in a corner.
                r3 = 0 + rand() % 4;

                if(r3 == 0){
                    r = 0, r2 = 0;
                } else if (r3 == 1){
                    r = 0, r2 = 2;
                } else if (r3 == 2){
                    r = 2, r2 = 0;
                } else if (r3 == 3){
                    r = 2, r2 = 2;
                }
            } else if (square[1][1] == userMark){
                //If the user moves to the center AI moves to the opposite corner.
                if(square[0][0] == aiMark && checker(2,2)){
                    r = 2, r2 = 2;
                } else if (square[0][2] == aiMark && checker(2,0)){
                    r = 2, r2 = 0;
                } else if (square[2][0] == aiMark && checker(0,2)){
                    r = 0, r2 = 2;
                } else if (square[2][2] == aiMark && checker(0,0)){
                    r = 0, r2 = 0;
                }
            } else if (square[1][1] != userMark){
                //If the user does not move to the center AI moves to another corner which ensures a win.
                if(checker(0,0)){
                    r = 0, r2 = 0;
                } else if (checker(0,2)){
                    r = 0, r2 = 2;
                } else if (checker(2,0)){
                    r = 2, r2 = 0;
                } else if (checker(2,2)){
                    r = 2, r2 = 2;
                }
            }

            break;
    }

    //CODE FOR CHECKING IMMINENT USER VICTORY BEGINS HERE.

    //Checks diagonals.
    if(square[2][0] == userMark && square[1][1] == userMark && square[0][2] == ' '){
        r = 0, r2 = 2;
    } else if (square[2][0] == ' ' && square[1][1] == userMark && square[0][2] == userMark){
        r = 2, r2 = 0;
    } else if (square[0][0] == ' ' && square[1][1] == userMark && square[2][2] == userMark){
        r = 0, r2 = 0;
    } else if (square[0][0] == userMark && square[1][1] == userMark && square[2][2] == ' '){
        r = 2, r2 = 2;
    } else if (square[0][0] == userMark && square[1][1] == ' ' && square[2][2] == userMark){
        r = 1, r2 = 1;
    } else if (square[2][0] == userMark && square[1][1] == ' ' && square[0][2] == userMark){
        r = 1, r2 = 1;
    }

    //Checks all vertical possibilities.
    if(square[0][0] == userMark && square[1][0] == userMark && square[2][0] == ' '){
        r = 2, r2 = 0;
    } else if (square[0][0] == userMark && square[1][0] == ' ' && square[2][0] == userMark){
        r = 1, r2 = 0;
    } else if (square[0][0] == ' ' && square[1][0] == userMark && square[2][0] == userMark){
        r = 0, r2 = 0;
    } else if (square[0][1] == userMark && square[1][1] == userMark && square[2][1] == ' '){
        r = 2, r2 = 1;
    } else if (square[0][1] == userMark && square[1][1] == ' ' && square[2][1] == userMark){
        r = 1, r2 = 1;
    } else if (square[0][1] == ' ' && square[1][1] == userMark && square[2][1] == userMark){
        r = 0, r2 = 1;
    } else if (square[0][2] == userMark && square[1][2] == userMark && square[2][2] == ' '){
        r = 2, r2 = 2;
    } else if (square[0][2] == userMark && square[1][2] == ' ' && square[2][2] == userMark){
        r = 1, r2 = 2;
    } else if (square[0][2] == ' ' && square[1][2] == userMark && square[2][2] == userMark){
        r = 0, r2 = 2;
    }

    //Checks all horizontal possibilities.
    if(square[0][0] == userMark && square[0][1] == userMark && square[0][2] == ' '){
        r = 0, r2 = 2;
    } else if (square[0][0] == userMark && square[0][1] == ' ' && square[0][2] == userMark){
        r = 0, r2 = 1;
    } else if (square[0][0] == ' ' && square[0][1] == userMark && square[0][2] == userMark){
        r = 0, r2 = 0;
    } else if (square[1][0] == userMark && square[1][1] == userMark && square[1][2] == ' '){
        r = 1, r2 = 2;
    } else if (square[1][0] == userMark && square[1][1] == ' ' && square[1][2] == userMark){
        r = 1, r2 = 1;
    } else if (square[1][0] == ' ' && square[1][1] == userMark && square[1][2] == userMark){
        r = 1, r2 = 0;
    } else if (square[2][0] == userMark && square[2][1] == userMark && square[2][2] == ' '){
        r = 2, r2 = 2;
    } else if (square[2][0] == userMark && square[2][1] == ' ' && square[2][2] == userMark){
        r = 2, r2 = 1;
    } else if (square[2][0] == ' ' && square[2][1] == userMark && square[2][2] == userMark){
        r = 2, r2 = 0;
    }

    //CODE FOR CHECKING IMMINENT USER VICTORY ENDS HERE.
    //CODE FOR CHECKING IMMINENT COMPUTER VICTORY BEGINS HERE.

    //Checks diagonals.
    if(square[2][0] == aiMark && square[1][1] == aiMark && square[0][2] == ' '){
        r = 0, r2 = 2;
    } else if (square[2][0] == ' ' && square[1][1] == aiMark && square[0][2] == aiMark){
        r = 2, r2 = 0;
    } else if (square[0][0] == ' ' && square[1][1] == aiMark && square[2][2] == aiMark){
        r = 0, r2 = 0;
    } else if (square[0][0] == aiMark && square[1][1] == aiMark && square[2][2] == ' '){
        r = 2, r2 = 2;
    } else if (square[0][0] == aiMark && square[1][1] == ' ' && square[2][2] == aiMark){
        r = 1, r2 = 1;
    } else if (square[2][0] == aiMark && square[1][1] == ' ' && square[0][2] == aiMark){
        r = 1, r2 = 1;
    }

    //Checks all vertical possibilities.
    if(square[0][0] == aiMark && square[1][0] == aiMark && square[2][0] == ' '){
        r = 2, r2 = 0;
    } else if (square[0][0] == aiMark && square[1][0] == ' ' && square[2][0] == aiMark){
        r = 1, r2 = 0;
    } else if (square[0][0] == ' ' && square[1][0] == aiMark && square[2][0] == aiMark){
        r = 0, r2 = 0;
    } else if (square[0][1] == aiMark && square[1][1] == aiMark && square[2][1] == ' '){
        r = 2, r2 = 1;
    } else if (square[0][1] == aiMark && square[1][1] == ' ' && square[2][1] == aiMark){
        r = 1, r2 = 1;
    } else if (square[0][1] == ' ' && square[1][1] == aiMark && square[2][1] == aiMark){
        r = 0, r2 = 1;
    } else if (square[0][2] == aiMark && square[1][2] == aiMark && square[2][2] == ' '){
        r = 2, r2 = 2;
    } else if (square[0][2] == aiMark && square[1][2] == ' ' && square[2][2] == aiMark){
        r = 1, r2 = 2;
    } else if (square[0][2] == ' ' && square[1][2] == aiMark && square[2][2] == aiMark){
        r = 0, r2 = 2;
    }

    //Checks all horizontal possibilities.
    if(square[0][0] == aiMark && square[0][1] == aiMark && square[0][2] == ' '){
        r = 0, r2 = 2;
    } else if (square[0][0] == aiMark && square[0][1] == ' ' && square[0][2] == aiMark){
        r = 0, r2 = 1;
    } else if (square[0][0] == ' ' && square[0][1] == aiMark && square[0][2] == aiMark){
        r = 0, r2 = 0;
    } else if (square[1][0] == aiMark && square[1][1] == aiMark && square[1][2] == ' '){
        r = 1, r2 = 2;
    } else if (square[1][0] == aiMark && square[1][1] == ' ' && square[1][2] == aiMark){
        r = 1, r2 = 1;
    } else if (square[1][0] == ' ' && square[1][1] == aiMark && square[1][2] == aiMark){
        r = 1, r2 = 0;
    } else if (square[2][0] == aiMark && square[2][1] == aiMark && square[2][2] == ' '){
        r = 2, r2 = 2;
    } else if (square[2][0] == aiMark && square[2][1] == ' ' && square[2][2] == aiMark){
        r = 2, r2 = 1;
    } else if (square[2][0] == ' ' && square[2][1] == aiMark && square[2][2] == aiMark){
        r = 2, r2 = 0;
    }

    //CODE FOR CHECKING IMMINENT COMPUTER VICTORY ENDS HERE.

    square[r][r2] = aiMark;

    if(lose()){
        cout<<"You have lost!\n";
        return;
    }

    if(full()){
        cout<<"You have tied the computer!\n";
        return;
    }

    if(!full() && !lose()){
        cout<<"Computer move: "<<r<<" "<<r2<<endl;
    }
}

//Checks to see if the user has made three moves in a row.
bool Board::win()
{
    if(square[0][0] == userMark && square[0][1] == userMark && square[0][2] == userMark){
        return true;
    } else if (square[1][0] == userMark && square[1][1] == userMark && square[1][2] == userMark){
        return true;
    } else if (square[2][0] == userMark && square[2][1] == userMark && square[2][2] == userMark){
        return true;
    } else if (square[0][0] == userMark && square[1][0] == userMark && square[2][0] == userMark){
        return true;
    } else if (square[0][1] == userMark && square[1][1] == userMark && square[2][1] == userMark){
        return true;
    } else if (square[0][2] == userMark && square[1][2] == userMark && square[2][2] == userMark){
        return true;
    } else if (square[0][0] == userMark && square[1][1] == userMark && square[2][2] == userMark){
        return true;
    } else if (square[0][2] == userMark && square[1][1] == userMark && square[2][0] == userMark){
        return true;
    } else {
        return false;
    }
}

//Checks to see if computer has made three moves in a row.
bool Board::lose()
{
    if(square[0][0] == aiMark && square[0][1] == aiMark && square[0][2] == aiMark){
        return true;
    } else if (square[1][0] == aiMark && square[1][1] == aiMark && square[1][2] == aiMark){
        return true;
    } else if (square[2][0] == aiMark && square[2][1] == aiMark && square[2][2] == aiMark){
        return true;
    } else if (square[0][0] == aiMark && square[1][0] == aiMark && square[2][0] == aiMark){
        return true;
    } else if (square[0][1] == aiMark && square[1][1] == aiMark && square[2][1] == aiMark){
        return true;
    } else if (square[0][2] == aiMark && square[1][2] == aiMark && square[2][2] == aiMark){
        return true;
    } else if (square[0][0] == aiMark && square[1][1] == aiMark && square[2][2] == aiMark){
        return true;
    } else if (square[0][2] == aiMark && square[1][1] == aiMark && square[2][0] == aiMark){
        return true;
    } else {
        return false;
    }
}

//Checks to see if all the squares are full; if they are, it returns false to indicate a tie.
bool Board::full()
{
    short count = 0;
    for(short i = 0; i < SIZE; i++){
        for(short j = 0; j < SIZE; j++){
            if(square[i][j] == aiMark || square[i][j] == userMark){
                count++;
            } else {
                continue;
            }
        }
    }

    if(count == 9){
        return true;
    } else {
        return false;
    }
}

//Clears board in event that it is not the first game.
void Board::clear()
{
    for(short i = 0; i < SIZE; i++){
        for(short j = 0; j < SIZE; j++){
            square[i][j] = ' ';
        }
    }
}

int main()
{
    Board bobj;
    short choice, num, num2, count = 0;
    char choice2;

    //Displays instructions for users (only first time).
    bobj.instructions();

    do {
        count++;

        cout<<endl<<"Game "<<count<<"\n";
        for(short i = 0; i < 26; i++){
            cout<<"-";
        }
        cout<<endl;

        cout<<"Select Player 1:\n"
            <<"1. User\n2. AI\nEnter choice (ex. 1 or 2): ";
        cin>>choice;

        //Determines which code to run based on who is Player 1
        //(i.e. runs case 1 if user is Player 1 and case 2 if AI is Player 1).
        switch(choice){
            //Runs when user is Player 1.
            case 1:
                cout<<"The game has begun. You are Player 1. ";
                do {
                    cout<<"Enter your move as a coordinance: ";
                    cin>>num>>num2;

                    while(num > 3 || num < 0 || num2 > 3 || num2 < 0 || !bobj.checker(num, num2)){
                        cout<<"ERROR: you have not entered a valid coordinance.\n";
                        cout<<"Enter your move as a coordinance: ";
                        cin>>num>>num2;
                    }

                    //Executes moves.
                    bobj.userMove(num, num2);
                    bobj.computerMove(1);
                    bobj.showBoard();

                } while(!bobj.lose() && !bobj.win() && !bobj.full());
                break;

            //Runs when AI is Player 1.
            case 2:
                cout<<"The game has begun. The computer is Player 1.\n";

                //First computer move.
                bobj.computerMove(2);
                bobj.showBoard();

                do {
                    cout<<"Enter your move as a coordinance: ";
                    cin>>num>>num2;

                    while(num>3 || num < 0 || num2 > 3 || num2 < 0 || !bobj.checker(num, num2)){
                        cout<<"ERROR: you have not entered a valid coordinance.\n";
                        cout<<"Enter your move as a coordinance: ";
                        cin>>num>>num2;
                    }

                    //Executes moves.
                    bobj.userMove(num, num2);
                    bobj.computerMove(2);
                    bobj.showBoard();

                } while (!bobj.lose() && !bobj.win() && !bobj.full());
                break;

            default:
                //If user does not enter 1 or 2 runs this code.
                cout<<"You have not entered a valid option.\n";
                break;
        }

        bobj.clear();

        cout<<"Would you like to try again? Enter y/n: ";
        cin>>choice2;

    } while (choice2 != 'n' && choice2 != 'N');

    cout<<"Thanks for playing!\n";

    return 0;
}

Community · Accepted Answer · 2020-06-10 13:24:26Z

[..] it seems rather inefficient, as I literally have to type out every case of possible victory or defeat. [..] Everything is in one 500 line program.

Woah. Yes, that is inefficient, regarding developer time and developer annoyance. I'll attempt an answer now nonetheless. My answer consists of two parts: Part one is a (non-exhaustive) list of things that could be improved in your code. Part two is a implementation of the same idea by myself. In order to be able to show you absolutely fine code I'm posting my own code as another question. That way others can review and comment on it easily.

Review

Better not `using namespace std;`

There's a lot of discussion in this stackoverflow post.

`char` is a character, nothing else.

char square[SIZE][SIZE], aiMark, userMark;

and later

userMark = 'x', aiMark = 'o';
// a for loop setting all elements of sqaure to ' '

So a "place" on your board can be either ' ', 'x' or 'o'. And it can be the same as str[0] with char const * str = "BOooO";. At least according to the compiler, wo wouldn't stop you doing place[0][0] = str[0], because they're of the same type char. Instead of trying to enforce such a separation by "being careful" you should better let the compiler and the type system do this:

enum class Mark {
  X, O, None
};
// ...
Mark square[SIZE][SIZE];

Member functions that don't modify data members...

... should be marked const:

// NO:
// void instructions();
// Yes (sort of):
void instructions() const;

But ...

Member functions that shouldn't even be members at all

Why is void instructions(); even a member function? It doesn't use / modify / need any data members / other member functions of Board at all. Better make it a free function (with a descriptive name), like:

void show_instruction_screen();

Names

board.showBoard ? Redundant! Better: board.show(). Even better: stream << board.

checker ... of what? Better: is_valid_move.

bool Board::checker(short n, short n2) ... n and n2? Completely cryptic. x and y could be seen as acceptable, but better is row and column. The same goes for many of your local variables: r, r2, r3, num, num2, ...

computerMove / userMove. Hm. I can infer what could happen inside these functions: The move of the computer/user is "processed". But this also shows another issue ...

Do only one thing per function

Every function should have a clear job, which should be mirrored in the functions name: is_valid_move? Checks if something is a valid move. launch_nukes? launches nukes. ask_for_move? Asks (the user) for a move.

Note that this does not mean that a function "contains" all code necessary to perform its objective: launch_nukes probably calls prepare_silo which possibly calls open_doors. ask_for_move could call a generic ask that returns a string to be parsed by parse_move.

So split your code further into (smaller) functions.

Use loops

Most of your code can be greatly simplified if you use a loop to check whether the places in your square satisfy some criteria. Example:

bool Board::win() const {
  unsigned rowCounts[] = {0, 0, 0};
  unsigned columnCounts[] = {0, 0, 0};
  for (unsigned column = 0; column < SIZE; ++column) {
    for (unsigned row = 0; row < SIZE; ++row) {
      if (square[row][column] == userMark) {
        rowCounts[row]++;
        columnCounts[column]++;
        if (rowCounts[row] == 3 || columnCounts[column] == 3) {
          return true;
        }
      }
    }
    rowCounts[0] = rowCounts[1] = rowCounts[2] = 0;
  }
  // Plus code to check the two diagonals
  return false;
}

Reuse code

Look at your Board::win and Board::lose? What's the difference? One uses userMark, the other aiMark. Make it a single function bool Board::is_winner(Mark mark).

Better not use the `operator,`

r = 2, r2 = 1;

Works, but is unusual at its best. Better make it two clearly separate statements:

r = 2; // Ignoring the bad names here
r2 = 1;

seed only once

double seed;
seed = time(0);
srand(seed);

This is called on every computer move. Not good. Your random values won't be that random (just print them to see what I mean).

Use the standard library

You can get rid of a lot of your code when you use code that's already provided for you in the standard library. Some examples:

The loop in Board::Board: std::fill(). (which is also the same as in Board::clear, so the former should call the later which could use std::fill).
Checking for win/loose/full: std::count() or std::all_of/std::none_of

Thanks very much for your review! I really appreciate it. Though, I am slightly confused about your comment to not use the operator,. Is this considered bad programming practice? — perspicuousreading, Commented Oct 24, 2016 at 20:25

Stack Exchange Network

An unbeatable Tic-Tac-Toe game using exhaustive enumeration of all cases

1 Answer 1

Review

Better not `using namespace std;`

`char` is a character, nothing else.

Member functions that don't modify data members...

Member functions that shouldn't even be members at all

Names

Do only one thing per function

Use loops

Reuse code

Better not use the `operator,`

seed only once

Use the standard library

Not the answer you're looking for? Browse other questions tagged
c++
beginner
tic-tac-toe
ai
or ask your own question.

Linked

Hot Network Questions

An unbeatable Tic-Tac-Toe game using exhaustive enumeration of all cases

1 Answer 1

Review

Better not using namespace std;

char is a character, nothing else.

Member functions that don't modify data members...

Member functions that shouldn't even be members at all

Names

Do only one thing per function

Use loops

Reuse code

Better not use the operator,

seed only once

Use the standard library

Not the answer you're looking for? Browse other questions tagged c++beginnertic-tac-toeai or ask your own question.

Linked

Related

Hot Network Questions

Better not `using namespace std;`

`char` is a character, nothing else.

Better not use the `operator,`

Not the answer you're looking for? Browse other questions tagged
c++
beginner
tic-tac-toe
ai
or ask your own question.