#### Archived

This topic is now archived and is closed to further replies.

# minimax problems

This topic is 5795 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Could someone please help me, i am trying to implement the minimax algorithm in c++ in a simple tic tac toe game. however my minimax function just returns the first move it can find rather than the best move here is my minimax class:

int AIMinimaxAgent::findBestMove(bool nodeType, Board  b, int depth)
{
if((depth == 0))
return b.evaluateBoard();

Board c;		// temp board

int best;		// the best so far for this level

int value;		// the value for each node

// which node are we looking at?

switch(nodeType)
{
// min node, i.e. human move

case MINNODE :
{
best = 99;
// for each square

for(int i=0;i<9;i++)
{
// make a copy of the board

c.copy(b);
// if this move is legal

if(c.isLegal(i))
{
//make the move

c.makeMove(X, i);

value = findBestMove(!nodeType, c, depth-1);

// if this move is less than the best at this level

if(value < best)
best = value; // update the best

// unmake the move so the next move can be tested

c.setSquares(EMPTY, i);
}
}
// return the best score that was found

return best;
} break;

// max node, i.e computer move

case MAXNODE :
{
best = -99;
// for each square

for(int i=0;i<9;i++)
{
// make a copy of the board

c.copy(b);
// if this move is legal

if(c.isLegal(i))
{
// make the move

c.makeMove(O, i);

// find the best move from this position

value = findBestMove(!nodeType, c, depth-1);

// if this move is better than the current best for this level

if(value > best)
best = value; // update the best score

// unmake the move so we can test the next move

c.setSquares(EMPTY, i);
}
}
// return the best score found for this level of recursion

return best;
} break;
}
return 0;
}

int AIMinimaxAgent::getMove(Board b)
{
int best;
int value;
int theMove;

for(int i=0;i<9;i++)
{
if(b.isLegal(i))
{
b.setSquares(EMPTY, i);

value = findBestMove(MINNODE, b, 6);
if(value > best)
{
best    = value;
theMove = i;
}
}
}

return theMove;
}

and here is my evaluation function :

int Board::evaluateBoard()
{
if(isWin())
{
switch(winner)
{
case HUMAN    : return -1;
case COMPUTER : return  1;
}
}

if(numPieces = 9)
return 0;
}


##### Share on other sites
I''m not sure here, but I suspect that you might be causing a problem when you do this:

value = findBestMove(!nodeType, c, depth-1);

It depends what the values of MINNODE and MAXNODE are. For example, what I think might be happening is that when you call findBestMove(!nodeType, c, depth-1); recursively for the first time, you are setting the new nodeType to something other than MINNODE or MAXNODE, and so it falls through your case statement and returns 0.

When I have alternating things like that, I usually XOR to flip them. For example, if I had:

#define MINNODE 0
#define MAXNODE 1

Then I could do nodeType^1 to flip the node from MIN to MAX.

Russell

##### Share on other sites
Cheers for the post but i don''t think its that.

  const bool MAXNODE = true;const bool MINNODE = false;

That''s what i''m doing with MINNODE and MAXNODE, However in the code i posted earlier i wasn''t actually applying the move in my getMove member, i''ve corrected that and it still doesn''t work, it IS searching recursively because it takes it''s time to come up with the move! It''s just that when it returns the move instead of being the best move it is the first legal move it can find.

here is what my new getMove member looks like :

  int AIMinimaxAgent::getMove(Board b){	int best;	int value;	int theMove;	// for each square	for(int i=0;i<9;i++)	{		// if the move is possible		if(b.isLegal(i))		{			// make the move			b.makeMove(O, i);			// and look at the consequences			value = findBestMove(MINNODE, b, 6);			if(value > best)			{				best    = value;				theMove = i;			}			b.setSquares(EMPTY, i);		}	}		return theMove;}

If anyone has any ideas?

cheers.

##### Share on other sites
I''m not sure if this is the problem either, but in tic-tac-toe the "best" move is always going to lead to a draw (at least in 3x3). So if the first move it searches is a drawing move, then it will always return the first move it searches. Just a thought.

Russell

##### Share on other sites
First thing:

Odd.. Your code looks fine from here. Have you tried setting up some test boards, where one player can win?

One other thing, that will make the game play more logically:
In your evaluation function, adjust the score by depth, so that a win in 1 move scores higher than a win in 2 moves. By this way, your program will always go for the closest win, making it play more ''human''.

Good luck,
Will

##### Share on other sites
Hi, There is definatly something wrong because when it has a possible win it will not make the winning move, and when i have a possible win it will never block my move! I added a line which prints out the value and best, however throughout the entire recursive tree these are just zero. I''m perplexed! and pulling my hair out! cheers for the ideas if you have any more please help me!

Moagly

##### Share on other sites
What does the isLegal function do? Check to make sure it''s not failing every time.

Cheers,
Will

##### Share on other sites
hehe. Sorry for the double post, but I just noticed something else.

You''re calling MakeMove for 0 to 9.. What happens if board[1] = O and you call MakeMove(X, 1)?

I suspect you''re overwriting the old value.. This is bad.

If you''re not overwriting it, you''re still calling AlphaBeta with a ''null'' move which is effectivley letting the opponent move twice in a row. Also very bad. By ''null'' I don''t mean an empty board, I mean a board in which no new move has been played.

If either of these cases are true, then it would explain why you''re algorithm doesn''t care about winning.

Let me know if this is it,
Will

##### Share on other sites
Sorry not posting from my comp so dont have code to hand but isLegal basically checks if the square is empty if it is then it returns true, if the board has already been won it returns false, if the board is a draw it returns false and if the square is occupied it returns false. I dont think there are any major problems with it.

However I found a major problem with my copy member, in that it wasnt copying properly! I fixed that problem by using the assignment operator, so insteqd of c.copy(b) i have c = b
This makes it work a bit better it no longer returns the first legal move, HURRAY!

BUT it sometimes returns -99 (it should never do this) and for each possible move it NEVER returns a positive number(it should do this!) so as far as it is concerned it is never going for a win, it is always looking to stop me from winning or looking for a draw!

Basically if the square is occupied then it will not make that move and will not search any succesors from that move, it will only search a move if isLegal(move) is true. If you get what I mean! So it is not overwriting or searching pointless boards.

Thanx for all the help, im getting there slowly but surely! If you have any more comments suggestions or if you want more source!

Cheers

##### Share on other sites
Sorry not posting from my comp so dont have code to hand but isLegal basically checks if the square is empty if it is then it returns true, if the board has already been won it returns false, if the board is a draw it returns false and if the square is occupied it returns false. I dont think there are any major problems with it.

However I found a major problem with my copy member, in that it wasnt copying properly! I fixed that problem by using the assignment operator, so insteqd of c.copy(b) i have c = b
This makes it work a bit better it no longer returns the first legal move, HURRAY!

BUT it sometimes returns -99 (it should never do this) and for each possible move it NEVER returns a positive number(it should do this!) so as far as it is concerned it is never going for a win, it is always looking to stop me from winning or looking for a draw!

Basically if the square is occupied then it will not make that move and will not search any succesors from that move, it will only search a move if isLegal(move) is true. If you get what I mean! So it is not overwriting or searching pointless boards.

Thanx for all the help, im getting there slowly but surely! If you have any more comments suggestions or if you want more source!

Cheers

1. 1
2. 2
3. 3
Rutin
14
4. 4
5. 5

• 12
• 12
• 9
• 14
• 10
• ### Forum Statistics

• Total Topics
632655
• Total Posts
3007670
• ### Who's Online (See full list)

There are no registered users currently online

×