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;
Minimax TicTacToe
Author
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.
// Oregistrerad
[Edited by - Oregistrerad on May 5, 2010 11:32:06 AM]
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.
Author
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?
// Oregistrerad
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
You are still returning a move, when you should be returning a score. Re-read my previous post.
Author
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?
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.
Author
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?
[Edited by - Oregistrerad on May 6, 2010 1:05:39 PM]
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]
Author
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?
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
