Why is my minimax algorithm not working?

[Chris LF]

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.

int BestMove(std::vector<char>& 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<int> 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)

[Peter87]

The if statement on line 26-31 doesn't look right.

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?

// Isn't this all you need?
bestScore = BestMove(board, Opposite(player));

[Chris LF]

Hello, thanks for your reply. I believe you're right, I modified the function and it now looks like this:

int BestMove(std::vector<char>& 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<int> 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.

[Peter87]

Maybe the problem is that you're sharing the same bestScore variable between all invocations of BestMove.

[Chris LF]

// ...
// 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 :(

[Peter87]

At the end of the function you don't return a score.

[Chris LF]

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.