Jump to content
  • Advertisement
Sign in to follow this  
Oregistrerad

Minimax TicTacToe

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello, For a very long time i've been trying to implement a minimax algorithm for my tic tac tac toe game. But i've come across some problems and the primaly problem i have is that i can't really figure it out... I've been trying to do a lot of things but I can't get it to work properly. No matter what i do it only returns the next move that is "open" and not the best. I would appreciate if someone could help me with it. Here is the minimax implementation in my java code. As you can see the function receives an array of 9 positions and which player it is. The evaluation function simply just returns 1, 0 or -1 depending how the terminal node looks like. If you need more information to help me just tell me.
    public static int minimax(int[] board, int player){
    	Stack<Integer> movelist = new Stack<Integer>();
    	boolean gameover = GameOver(board);
    	int score = 0;
    	int bestscore;
    	int bestmove = 0;
    	int[] newBoard = new int[9];
    	if(gameover == true)
    	{
    		return evaluate(board, player);
    	}
    	else
    	{
    		if (currentplayer(board) == player)
    		{
    			bestscore = -1;
    		}
    		else
    		{
    			bestscore = 1;
    		}
    		// Generate moves
    		for (int i = 0; i < 9; i++)
			{
				if (board == 0)
				{
					movelist.push(i);
				}
			}
    		while(!movelist.empty())
    		{
    			int move = movelist.peek();
    			movelist.pop();
    			int moveplayer = currentplayer(board);
    			board[move] = moveplayer;
    			newBoard = board;
    			score = minimax(newBoard, player);
    			board[move] = 0;
    			if (currentplayer(board) == player)
    			{
    				if(score > bestscore)
    				{
    					bestscore = score;
    					bestmove = move;
    				}
    			}
    			else
    			{
    				if(score < bestscore)
    				{
    					bestscore = score;
    					bestmove = move;
    				}
    			}
    			
    		}
    	}
    	return bestmove;


// Oregistrerad [Edited by - Oregistrerad on May 5, 2010 11:32:06 AM]

Share this post


Link to post
Share on other sites
Advertisement
Quote:
score = minimax(newBoard, player);

Your function returns a move, not a score. Of course you want to get a move out of your initial call to minimax, but the algorithm is usually described as a recursive function that returns a score. I recommend having a separate function to deal with the root, which calls minimax for the positions that arise after each possible move by the player.

You could also benefit from the NegaMax idea: Make the score be positive when the player to move is ahead, and flip the sign at each recursive call:
score = -minimax(newBoard, player); // Edit: I'm not sure you are passing the right player in your code...

This makes your code shorter and easier to get right.

Share this post


Link to post
Share on other sites
Thanks for the help, i've implemented a negamax algorithm now as you said and it's working a bit better. It can judge good now if there is a move that will lead to a victory. For example if you put it like this:
1 0 1
-1 0 -1
0 0 0
But if there isn't a move that will lead to victory it will just place it where there is an open position. I think that the problem is that it does not generate the whole gametree. Here is the new code. Do you think it could be the tree generateing i'm doing worng? Do this code create a new movelist Stack every recursion?


public static int negamax(int[] board){
Stack<Integer> movelist = new Stack<Integer>();
boolean gameover = GameOver(board);
int score = 0;
int bestscore;
int bestmove = 0;
int[] newBoard = new int[9];
if(gameover == true)
{
return evaluate(board);
}
else
{
bestscore = Integer.MIN_VALUE;

for (int i = 0; i < 9; i++)
{
if (board == 0)
{
//System.out.println(i);
movelist.push(i);
}
}

//System.out.println(movelist.size());

while(!movelist.empty())
{
int move = movelist.peek();
movelist.pop();
newBoard = makeMove(board,move);
score = -negamax(newBoard);
board[move] = 0;
if(score > bestscore)
{
bestscore = score;
bestmove = move;
}

}

}
return bestmove;
}




// Oregistrerad

Share this post


Link to post
Share on other sites
You are still returning a move, when you should be returning a score. Re-read my previous post.

Share this post


Link to post
Share on other sites
Ok, sry but how am i suppose to get a move out of a score when the function only returns a score? Most of the Pseudo-Codes i've looked at returns some kind of move or have I gotten it worng?

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
I recommend having a separate function to deal with the root, which calls minimax for the positions that arise after each possible move by the player.

Share this post


Link to post
Share on other sites
Sry for my misunderstanding, I think I know what you mean now and i tried to do so. Is this what you ment? Anyway it still won't work... Is there any other way to generate the gametree? Or could it be my evaluation function?


public static int bestmove(int[] board){
Stack<Integer> movelist = new Stack<Integer>();
int bestscore = Integer.MIN_VALUE;
int bestmove = 0;
for (int i = 0; i < 9; i++)
{
if (board == 0)
{
movelist.push(i);
}
}
while(!movelist.empty())
{
int move = movelist.peek();
movelist.pop();
int[] newBoard = makeMove(board,move);
int score = negamax(newBoard);
board[move] = 0;
if (score > bestscore)
{
bestscore = score;
bestmove = move;
}

}
return bestmove;
}

public static int negamax(int[] board){
Stack<Integer> movelist = new Stack<Integer>();
boolean gameover = GameOver(board);
int score = 0;
int bestscore=0;
int[] newBoard = new int[9];
if(gameover == true)
{
return eval(board);
}
else
{
bestscore = Integer.MIN_VALUE;

for (int i = 0; i < 9; i++)
{
if (board == 0)
{
movelist.push(i);
}
}

while(!movelist.empty())
{
int move = movelist.peek();
movelist.pop();
newBoard = makeMove(board,move);
score = -negamax(newBoard);
board[move] = 0;
if(score > bestscore)
{
bestscore = score;
}
}
}
return bestscore;
}





[Edited by - Oregistrerad on May 6, 2010 1:05:39 PM]

Share this post


Link to post
Share on other sites
You still have obvious mistakes. You never update bestscore in your bestmove function.

Share this post


Link to post
Share on other sites
Can you see any other mistakes? I just can't figure it out, it's so frustrating... I fixed that obvious mistake you told me. I know that the negamax function creates a whole new Stack at every recursion, should it be so?

Share this post


Link to post
Share on other sites
Quote:
Original post by Oregistrerad
Can you see any other mistakes?

I do, but you have to learn to find your own mistakes. Do you know how to use a debugger?

Quote:
I know that the negamax function creates a whole new Stack at every recursion, should it be so?

Well, you don't really need it, and you don't need to make copies of the board either. But those are matters of efficiency, and you should not worry about them for now. Correctness is way more important.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!