Archived

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

Moagly

minimax problems

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;
}
  
if anyone has any ideas what is wrong please help me!

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
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, i`m getting there slowly but surely! If you have any more comments suggestions or if you want more source!

Cheers

Share this post


Link to post
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, i`m getting there slowly but surely! If you have any more comments suggestions or if you want more source!

Cheers

Share this post


Link to post
Share on other sites
Ha! Finally got it to work, was absolutly nothing wrong with minimax! it was my isWin that was the problem! wasn''t checking for every win!

thanx for all your help anyway!

Share this post


Link to post
Share on other sites