Sign in to follow this  
Oregistrerad

Minimax TicTacToe

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[i] == 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
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[i] == 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
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[i] == 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[i] == 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
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
I tried to revmove this "[board[move] = 0;]" pice of code in both bestmove function and negamax and now the AI actually can play rather good. I don't know if the program is working absolutely right because it's playing very dumb in some senarios... Was that code the biggest error of my code? And if there are more errors plz tell me, you don't need to say where, just tell if there is something.

Share this post


Link to post
Share on other sites
Quote:
Original post by Oregistrerad
I don't think I know how to use a debugger, i'm currently using a program called JCreator and I think there is a debugg button or something. Are there any tutorials or anything on how to use a debugger?


Look for a way to step through your code execution line-by-line. Same thing.

Share this post


Link to post
Share on other sites
Quote:
Original post by Oregistrerad
I tried to revmove this "[board[move] = 0;]" pice of code in both bestmove function and negamax and now the AI actually can play rather good.


That assignment should have no effect, unless makeMove has very unusual semantics (does it modify the board that you pass to it?).

Share this post


Link to post
Share on other sites
Yes, my makeMove function does modify the board that I pass to it. Here is my makeMove function... I've made it so player 1 will always start to move (player 1 is the AI). It starts with a for loop to see how many plies that there are and out of that information it decides who the player it is to move.


static int[] makeMove(int[] board, int move){
int ply = 0;

for (int i = 1; i<9; i++)
{
if(board[i] == 1 || board[i] == -1)
{
ply++;
}
}

if(ply == 0)
{
board[move] = 1;
return board;
}
else if (ply == 1)
{
board[move] = -1;
return board;
}
else if (ply == 2)
{
board[move] = 1;
return board;
}
else if(ply == 3)
{
board[move] = -1;
return board;
}
else if(ply == 4)
{
board[move] = 1;
return board;
}
else if(ply == 5)
{
board[move] = -1;
return board;
}
else if(ply == 6)
{
board[move] = 1;
return board;
}
else if(ply == 7)
{
board[move] = -1;
return board;
}
else
{
board[move] = 1;
return board;
}

}

Share this post


Link to post
Share on other sites
That is ugly. If you are going to return a new board, why not make a copy at the beginning of the function and then just modify the copy?

If you are going to modify the board and you will undo the move later, then there is no need to copy the board.

Also, store the side to move somewhere instead of counting the occupied spots on the board. It makes sense to have a Board class that includes that information.

Finally, you can check if a number is odd or even like this:
if (n%2) {
// odd
}
else {
// even
}

Share this post


Link to post
Share on other sites
@lingfors still won't work.

@alvaro is it my makeMove functions that ruins my whole program? I'm not sure how i will store the side to move somewhere. I'm not so good with all this object oriented programming...

Share this post


Link to post
Share on other sites
Quote:
Original post by Oregistrerad
@alvaro is it my makeMove functions that ruins my whole program? I'm not sure how i will store the side to move somewhere. I'm not so good with all this object oriented programming...


I don't know what your program looks like at this point, so it's hard to tell if that's what's ruining your program. The larger issue is that you wrote a whole lot of code without verifying that parts of it were working correctly. The chances that it will all just work when you run it the first time are minuscule.

Did you manage to use a debugger to see what your code is doing?

Defining a class of objects that contain a description of the board including side to move is a trivial programming exercise. If you don't know how to do that, perhaps you should put minimax aside and spend some more time studying your language and tools.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this