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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
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)
Last edited on
The if statement on line 26-31 doesn't look right.

1
2
3
4
5
6
7
8
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?

1
2
// 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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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.
Last edited on
Maybe the problem is that you're sharing the same bestScore variable between all invocations of BestMove.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// ...
// 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.
Registered users can post here. Sign in or register to post.