Why is my minimax algorithm not working?

Hi, I am a new user here and I would like somebody to help me with my minimax algorithm. I have been trying to get this to work for 3 days and even though I would make small progress every day, I feel like I reached a dead end at this point and I really need somebody's help because my understanding of the algorithm itself is not very clear and if you can help explain it to a simpleton like me I'd really appreciate it.

So from what I understand, the algorithm works like this:
- Find a terminal state and assign it a score
- Store the score
- Make the best move

I will post my attempt below, but as a background, by default I made it so that the human player is X (maximizer) and the opposite player (the AI) is O (minimizer). I understand that the algorithm should flip back and forth between the players but I don't think my algorithm is flipping at all. Okay, enough small talk, I'll just post the code below for you to have a look at, I will also comment it so that you can easily understand what each part is doing.

 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667`` ``````int BestMove(std::vector& board, char player) { // Check for end state char result = Winner(board); if (result == O) return -10; else if (result == X) return 10; else if (result == TIE) return 0; // Vector to store all the moves std::vector moves; // Loop through the entire board for (unsigned int i = 0; i < 9; ++i) { // Check if a move can be made (cell is empty) if (AvailableMove(i, board)) { // Make the move board[i] = player; // Check if the current player is the O player if (player == O) // Return the best move for X bestScore = BestMove(board, Opposite(player)); else // Return the best move for O bestScore = BestMove(board, player); // Record the move and set the cell back to empty moves.push_back(bestScore); board[i] = EMPTY; } } // Determine the best move to be made int desiredMove = 0; if (player == X) { int score = -99999; for (unsigned int i = 0; i < moves.size(); ++i) { if (moves[i] > score) { desiredMove = i; score = moves[i]; } } } else { int score = 99999; for (unsigned int i = 0; i < moves.size(); ++i) { if (moves[i] < score) { desiredMove = i; score = moves[i]; } } } return desiredMove; }``````

Thank you very much for reading my thread and I hope you can point out my mistake, this has been driving me crazy and I'm really burned out because of it to say the least.

EDIT: Sorry, missed out a small part, here is how I am calling the function whenever it's the computer's turn:

 `` `` ``move = BestMove(board, computerPiece);``

Note that move is an integer which should hold a value from 0 to 9 (0 being the top left cell while 9 being the bottom right cell of the Tic Tac Toe board)
Last edited on
The if statement on line 26-31 doesn't look right.

 ``12345678`` ``````if (player == O) // I assume Opposite(player) returns X when // player is O. This seems to be okay. bestScore = BestMove(board, Opposite(player)); else // So if player is X you are asking for the best // move for player X? This doesn't seem right. bestScore = BestMove(board, player); ``````

Don't you always want to ask for the best move for the opposite player no matter what the current player is?

 ``12`` ``````// Isn't this all you need? bestScore = BestMove(board, Opposite(player));``````
Hello, thanks for your reply. I believe you're right, I modified the function and it now looks like this:

 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162`` ``````int BestMove(std::vector& board, char player) { // Check for end state char result = Winner(board); if (result == O) return -10; else if (result == X) return 10; else if (result == TIE) return 0; // Vector to store all the moves std::vector moves; // Loop through the entire board for (unsigned int i = 0; i < 9; ++i) { // Check if a move can be made (cell is empty) if (AvailableMove(i, board)) { // Make the move board[i] = player; // Return the best move of the opposite player bestScore = BestMove(board, Opposite(player)); // Record the move and set the cell back to empty moves.push_back(bestScore); board[i] = EMPTY; } } // Determine the best move to be made int desiredMove = 0; if (player == X) { int score = -99999; for (unsigned int i = 0; i < moves.size(); ++i) { if (moves[i] > score) { desiredMove = i; score = moves[i]; } } } else { int score = 99999; for (unsigned int i = 0; i < moves.size(); ++i) { if (moves[i] < score) { desiredMove = i; score = moves[i]; } } } return desiredMove; }``````

It is flipping back and forth between both players just fine now, but for some reason the computer is sometimes playing a piece on an occupied cell. I debugged the function, went into it line by line and the if condition which checks for available moves:
 `` `` ``if (AvailableMove(i, board))``

is detecting that the cell is occupied and its skipping it just fine, but for some reason the function still returns a move that is occupied... I'm not sure if it's my vector or the way I am determining what the best move is really.
Last edited on
Maybe the problem is that you're sharing the same bestScore variable between all invocations of BestMove.
 ``12345678910111213141516171819`` ``````// ... // Loop through the entire board for (unsigned int i = 0; i < 9; ++i) { // Check if a move can be made (cell is empty) if (AvailableMove(i, board)) { // Make the move board[i] = player; // Return the best move of the opposite player int bestScore = BestMove(board, Opposite(player)); // Record the move and set the cell back to empty moves.push_back(bestScore); board[i] = EMPTY; } } // .... ``````

Still same problem :(
At the end of the function you don't return a score.
Yes Peter, you are right, I wasn't returning a score at the end of the function. All this is because of my lack of understanding of the algorithm itself, it seemed convoluted at the beginning but I feel like I understand it very well right now. The AI is playing correctly now, everything seems fine, thank you for your assistance.

Regards.