How to write minimax algorithm in tictactoe?

See more:

C++14

Hi, I'm new to C++ and this is my second personal mini project. I'm learning about algorithm in TicTacToe.

I'm having problem to implement the minimax algorithm into my code here. Anywhere I look, all example have different game implementation from me making it difficult to understand the algorithm. Anyway I've read quite a bit on the algorithm itself from few sites. But those example always have different implementations or even different programming language. I'm having trouble to wrap my head around the idea of the algorithm were implemented.

All my code here is quite complete and runs OK for multiplayer game(with minimal edit). I just need to complete the aiMove() function for the computer to make a move.


Can someone who quite familiar with the minimax to help me a bit here?

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <chrono>
#include <thread>

using namespace std::literals;
using std::cout;
using std::endl;
using std::cin;
using std::string;

#ifdef _WIN32
#define CLEAR "cls"
#else
#define CLEAR "clear"
#endif

using board_t = std::vector<char>;

const int MIN_NUMBER = 1;
const int MAX_NUMBER = 9;
const int HUMAN1 = 1;
const int COMPUTER = 2;
//const int HUMAN2 = 3;

auto initBoard(){
    board_t board (9);
    std::fill(board.begin(), board.end(), '_');
    return board;
}

auto createPlayer(){
    cout<<"Enter your name:";
    string name;
    std::getline(cin,name);
    system(CLEAR);
    return name;
}

bool victoryFound(const board_t &board){
    //i'm doing board.at(1-1) because easier for me to visualize the board instead of board.at(0)
    if      ( board.at(1-1) != '_' && (board.at(1-1) == board.at(2-1) && board.at(2-1) == board.at(3-1))) return true;
    else if ( board.at(4-1) != '_' && (board.at(4-1) == board.at(5-1) && board.at(5-1) == board.at(6-1))) return true;
    else if ( board.at(7-1) != '_' && (board.at(7-1) == board.at(8-1) && board.at(8-1) == board.at(9-1))) return true;
    else if ( board.at(1-1) != '_' && (board.at(1-1) == board.at(4-1) && board.at(4-1) == board.at(7-1))) return true;
    else if ( board.at(2-1) != '_' && (board.at(2-1) == board.at(5-1) && board.at(5-1) == board.at(8-1))) return true;
    else if ( board.at(3-1) != '_' && (board.at(3-1) == board.at(6-1) && board.at(6-1) == board.at(9-1))) return true;
    else if ( board.at(1-1) != '_' && (board.at(1-1) == board.at(5-1) && board.at(5-1) == board.at(9-1))) return true;
    else if ( board.at(3-1) != '_' && (board.at(3-1) == board.at(5-1) && board.at(5-1) == board.at(7-1))) return true;
    else return false;
}

bool gameIsDraw(const board_t &board){
    auto temp = std::find(board.begin(),board.end(),'_');
    if ( temp == board.end()){
        return true;
    } else return false;
}

void displayBoard(const board_t &board, const string &playerName){
    system(CLEAR);
    cout<<"Board\tBox Number"<<endl;
    cout<<board.at(0)<<" "<<board.at(1)<<" "<<board.at(2)<<"\t  1 2 3"<<endl;
    cout<<board.at(3)<<" "<<board.at(4)<<" "<<board.at(5)<<"\t  4 5 6"<<endl;
    cout<<board.at(6)<<" "<<board.at(7)<<" "<<board.at(8)<<"\t  7 8 9"<<endl;
    cout<<"    "<<playerName<<"'s turn"<<endl;
}

void enterMoves(board_t &board, const int &turns){
    cout<<"Enter a number 1 through 9"<<endl;
    bool invalidInput = true;
    unsigned int boxNumber;
    while (invalidInput){
        bool inputIsInteger = false;
        while (!inputIsInteger){
            inputIsInteger = true;
            if (turns == HUMAN1){
                cout<<"Enter the box number to fill the O: ";
            } else if (turns == COMPUTER){
                cout<<"Enter the box number to fill the X: ";
            }
            cin >> boxNumber;
            //from this points on, it is just different checks for valid input.
            if(cin.fail()){
                cin.clear();
                cin.ignore();
                cout << "Please enter an Integer only." << endl;
                inputIsInteger = false;
                std::this_thread::sleep_for(0.7s);
                system(CLEAR);
            } else {
                cin.clear();
                cin.ignore();
            }
        }
        if (boxNumber < MIN_NUMBER || boxNumber > MAX_NUMBER){
            cout<<"You've entered an invalid box number. Try again."<<endl;
            std::this_thread::sleep_for(0.7s);
        } else if ( board.at(boxNumber - 1 ) != '_'){
            cout<<"Box is occupied"<<endl;
            std::this_thread::sleep_for(0.7s);
        } else {
            if (turns == HUMAN1) board[boxNumber - 1] = 'O';
            else if (turns == COMPUTER) board[boxNumber - 1] = 'X';
            invalidInput = false;
        }
    }
}

void swapTurn(int &turns){
    if (turns == HUMAN1) turns = COMPUTER;
    else if (turns == COMPUTER) turns = HUMAN1;
}

bool checkGameState(const board_t &masterBoard, const string &playerName, int &turns){
    if ( victoryFound(masterBoard) == true){
        cout<<playerName<<" wins"<<endl;
        return false;
    } else if (gameIsDraw(masterBoard) == true){
        cout<<"Draw"<<endl;
        return false;
    } else {
        swapTurn(turns);
        return true;
    }
}

void aiMove(board_t &masterBoard, const string &playerName, int &turns){

    for (int i = 0; i < masterBoard.size(); i++){
        if (masterBoard.at(i) == '_'){
            masterBoard[i] = 'X';
            if (victoryFound(masterBoard) == true) break;
            //else // ? i'm stuck
        }
    }
}

int main(){
   auto masterBoard = initBoard();
   auto p1Name = createPlayer();
   auto p2Name = "Computer";
   int turns = HUMAN1;
   bool gameLoop = true;
   while (gameLoop)
   {
       if (turns == HUMAN1){
           displayBoard(masterBoard,p1Name);
           enterMoves(masterBoard,turns);
           displayBoard(masterBoard,p1Name);
           gameLoop = checkGameState(masterBoard,p1Name,turns);
       } else if (turns == COMPUTER){
           displayBoard(masterBoard,p2Name);
           aiMove(masterBoard, p2Name, turns);
           displayBoard(masterBoard,p2Name);
           gameLoop = checkGameState(masterBoard,p2Name,turns);
       }
   }
   return 0;
}

Thanks.

What I have tried:

For few days I've sufficiently tried to implement the algorithm to the best of my understanding but the the closest I get was resulted in stack overflow error (resulting from my immature recursion).