# 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 on other sites
alvaro    21266
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 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;    }

##### Share on other sites
alvaro    21266
You are still returning a move, when you should be returning a score. Re-read my previous 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 on other sites
alvaro    21266
Quote:
 Original post by alvaroI 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 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 on other sites
alvaro    21266
You still have obvious mistakes. You never update bestscore in your bestmove function.

##### 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 on other sites
alvaro    21266
Quote:
 Original post by OregistreradCan 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 on other sites
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?

##### 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 on other sites
Quote:
 Original post by OregistreradI 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 on other sites
alvaro    21266
Quote:
 Original post by OregistreradI 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 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 on other sites
alvaro    21266
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 on other sites
lingfors    149
int score = negamax(newBoard);

in method bestmove should be

int score = -negamax(newBoard);

##### 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 on other sites
alvaro    21266
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.