minimax c++ implementation for tic tac toe

Question

void generate_moves(int gameBoard[9], list<int> &moves)
{
   for (int i = 0; i < 9; i++)
   {
        if (gameBoard[i] == 0){
            moves.push_back(i);
        }
   }
}



 int evaluate_position(int gameBoard[9], int playerTurn)        
 {
   state currentGameState = checkWin(gameBoard);

   if (currentGameState != PLAYING)
    {
       if ((playerTurn == 1 && currentGameState == XWIN) || (playerTurn == -1 && currentGameState == OWIN))
          return +infinity;
       else if ((playerTurn == -1 && currentGameState == XWIN) || (playerTurn == 1 && currentGameState == OWIN))
          return -infinity;
       else if (currentGameState == DRAW)
            return 0;
   }

     return -1;
  }




 int MinMove(int gameBoard[9], int playerTurn)
 {
     //if (checkWin(gameBoard) != PLAYING) { return evaluate_board(gameBoard); };
    int pos_val = evaluate_position(gameBoard, playerTurn);
     if (pos_val != -1) return pos_val;

     int bestScore = +infinity;
     list<int> movesList;
     generate_moves(gameBoard, movesList);

     while (!movesList.empty())
     {
         gameBoard[movesList.front()] = playerTurn;
         int score = MaxMove(gameBoard, playerTurn*-1); 
         if (score < bestScore)
         {
            bestScore = score;
         }
         gameBoard[movesList.front()] = 0;
         movesList.pop_front();
     }

    return bestScore;
 }



  int MaxMove(int gameBoard[9], int playerTurn)
  {
     //if (checkWin(gameBoard) != PLAYING) { return evaluate_board(gameBoard); };
     int pos_val = evaluate_position(gameBoard, playerTurn);
     if (pos_val != -1) return pos_val;

      int bestScore = -infinity;
      list<int> movesList;
      generate_moves(gameBoard, movesList);

      while (!movesList.empty())
      {
         gameBoard[movesList.front()] = playerTurn;
         int score = MinMove(gameBoard, playerTurn*-1);
         if (score > bestScore)
         {
             bestScore = score;
         }
         gameBoard[movesList.front()] = 0;
         movesList.pop_front();
       }

      return bestScore;
  }


  int MiniMax(int gameBoard[9], int playerTurn)
  {
     int bestScore = -infinity;
     int index = 0;
     list<int> movesList;
     vector<int> bestMoves;
     generate_moves(gameBoard, movesList);

     while (!movesList.empty())
     {
          gameBoard[movesList.front()] = playerTurn;
          int score = MinMove(gameBoard, playerTurn);
          if (score > bestScore)
          {
             bestScore = score;
             bestMoves.clear();
             bestMoves.push_back(movesList.front());
          }
          else if (score == bestScore)
          {
             bestMoves.push_back(movesList.front());
          }
        gameBoard[movesList.front()] = 0;
        movesList.pop_front();
     }

    index = bestMoves.size();
    if (index > 0) {
        time_t secs;
        time(&secs);
        srand((uint32_t)secs);
        index = rand() % index;
     }

    return bestMoves[index];
  }

I created a tic tac toe program in C++ and tried to implement a MiniMax algorithm with exhaustive search tree. These are the functions I have written using wiki and with the help of some websites. But the AI just doesn't work right and at times doesn't play its turn at all.

Could someone have a look and please point out if there is anything wrong with the logic?

This is how I think it works:

Minimax : This function starts with very large -ve number as best score and goal is to maximize that number. It calls minMove function. If new score > best score, then best score = new score...

MinMove : This function evaluates game board. If game over then it returns -infinity or +infinity depending on who won. If game is going on this function starts with max +infinity value as best score and goal is to minimize it as much possible. It calls MaxMove with opponent player's turn. (since players alternate turns). If score < best score then best score = score. ...

MaxMove : This function evaluates game board. If game over then it returns -infinity or +infinity depending on who won. If game is going on this function starts with least -infinity value as best score and goal is to maximize it as much possible. It calls MinMove with opponent player's turn. (since players alternate turns). If score > best score then best score = score. ...

Minmove and MaxMove call each other mutually recursively, MaxMove maximizing the value and MinMove minimizing it. Finally it returns the best possible moves list.

If there are more than 1 best moves, then a random of them is picked as the computer's move.

Answer 1

In MiniMax, MinMove(gameBoard, playerTurn) should be MinMove(gameBoard, -playerTurn) as you do in MaxMove.

As you use MinMove and MaxMove, your evaluation function should be absolute. I mean +infinity for XWIN and -infinity for OWIN. And so MinMove can only be use when player == -1 and MaxMove when player == 1, thus the parameter become useless. And so MiniMax can only be used by player == 1.

I have done some changes in your code and it works (https://ideone.com/Ihy1SR).