int MinMaxCall(GameState[] pTempBoard, int pDepth, int pTurn)
{
best = -1000000;
tmpBest = -1000000;
ArrayList compMoves = new ArrayList();
IEnumerator listIt;
if (pDepth<= 0)
return Evaluate(pTempBoard, pTurn);
compMoves = gameBoard.MakeMoveList(pTempBoard, compMoves, pTurn);
listIt = compMoves.GetEnumerator();
listIt.Reset();
try
{
while(listIt.MoveNext())
{
val = MinMax(pTempBoard, pDepth, pTurn);
if (val > best)
{
best = val;
bestMove = ((Moves)listIt.Current);
}
tmpBest = -1000000;
tmpVal = -1000000;
}
}
catch
{
return best;
}
return best;
}
int MinMax(GameState[] pTempBoard, int pDepth, int pTurn)
{
ArrayList compMoves = new ArrayList();
IEnumerator listIt;
if (pDepth<= 0)
return Evaluate(pTempBoard, pTurn);
compMoves = gameBoard.MakeMoveList(pTempBoard, compMoves, pTurn);
listIt = compMoves.GetEnumerator();
listIt.Reset();
try
{
while(listIt.MoveNext())
{
gameBoard.DoMove(pTempBoard, ((Moves)listIt.Current));
tmpVal = MinMax(pTempBoard,pDepth- 1, pTurn);
gameBoard.UndoMove(pTempBoard, ((Moves)listIt.Current));
if (tmpVal > tmpBest)
tmpBest = tmpVal;
}
}
catch
{
return tmpBest;
}
return tmpBest;
}
}
[/Source]minmax problem
December 12, 2005 06:48 AM
I'm having a minmax problem. I'm designing a checkers game. The minimax always seems to take the first move out of all the possible moves on the current board. The code is crude, but I just want to get it working, so I can change it to an alphabeta function.
I should add that this is my first game. If anyone could help me out that would really be appreciated.
Here is my code:
Thanks kaddy69
[Edited by - kaddy69 on December 21, 2005 1:48:32 AM]
21,607
December 12, 2005 08:47 AM
Quote: ArrayList compMoves = new ArrayList();
Java programmer, aren't you? You probably don't want to use new or malloc in your search function at all. Did this even compile? Can you post what an ArrayList is?
I am having a hard time reading your code, since it depends on so many classes being implemented elsewhere.
I don't see where you are implementing minimax. It looks like you are taking the maximum all the time. You either take maximums on white moves and minimums on black moves, or you use the negamax mechanism, where scores are always expressed as from the point of view of the side to move, but then you need to insert a minus sign (`-') before the calls to MinMax.
132
December 12, 2005 11:02 AM
Hey man,
I've actually been working on basically the same thing for the last week or so. I was doing it for a connect 4 game though, but the idea is basically the same.
As Alvaro said, it is a bit hard to read through your code as you have a lot of classes where its hard to know what they do or represent without seeing their code.
If you are doing the minimax, I believe you are going to need one more function, which will be almost identical, however it returns a minimum value. And then your max function calls your min function, your min function calls you max function...etc, until you get to your desired depth or to an end move.
Another suggestion, is to look at the post I just made, I believe it is called "ANOTHER negamax problem..." and I was trying to implement negamax, which is the same concept as minimax, just with the one function...basically what you have now just with a few adjustments.
The code I posted there didn't work right, but I figured it out and made a couple small changes and now I have a connect 4 that beats me 9 out of 10 games. So if you need any help, I spent a good amount of time trying to figure it out. I'd be more than happy.
I've actually been working on basically the same thing for the last week or so. I was doing it for a connect 4 game though, but the idea is basically the same.
As Alvaro said, it is a bit hard to read through your code as you have a lot of classes where its hard to know what they do or represent without seeing their code.
If you are doing the minimax, I believe you are going to need one more function, which will be almost identical, however it returns a minimum value. And then your max function calls your min function, your min function calls you max function...etc, until you get to your desired depth or to an end move.
Another suggestion, is to look at the post I just made, I believe it is called "ANOTHER negamax problem..." and I was trying to implement negamax, which is the same concept as minimax, just with the one function...basically what you have now just with a few adjustments.
The code I posted there didn't work right, but I figured it out and made a couple small changes and now I have a connect 4 that beats me 9 out of 10 games. So if you need any help, I spent a good amount of time trying to figure it out. I'd be more than happy.
If you want the rainbow, you've gotta put up with the rain - do you know which philosopher said that? Dolly Parton. And people say she's just a big pair of tits.
December 13, 2005 02:39 AM
Quote: Original post by alvaroQuote: ArrayList compMoves = new ArrayList();
Java programmer, aren't you? You probably don't want to use new or malloc in your search function at all. Did this even compile? Can you post what an ArrayList is?
I am having a hard time reading your code, since it depends on so many classes being implemented elsewhere.
I don't see where you are implementing minimax. It looks like you are taking the maximum all the time. You either take maximums on white moves and minimums on black moves, or you use the negamax mechanism, where scores are always expressed as from the point of view of the side to move, but then you need to insert a minus sign (`-') before the calls to MinMax.
Thanks for the reply. Yeah, I'm mainly a java programer :D. An Arraylist is just a dynamic array. Yes it compiles, but it the AI aspect doesn't work. I don't see what other options I have, other then creating a "new" array list to hold the possible moves?
I added some code that switches turns everytime you call minimax and I put a minus sign in front of my MinMax code. I will do some more testing.
Core-Nut, I looked at you code. It helped me make some changes. Thank you
I must say this forum is great. I hope to learn a lot from this place. Thanks for the replys so far.
21,607
December 13, 2005 05:55 AM
Most minimax searchers avoid dynamic memory allocation by having a few big arrays allocated globally, or by having fixed-size arrays of moves to contain all possible moves at a given position. Anyway, it's not a big deal if for now you use dynamic memory allocation, and you consider getting rid of it in the future as a possible optimization.
Now I realize that your code *is* Java, and not C++. No wonder I had a hard time understanding it. :)
No matter what programming language you use, you should get in the habit of testing small units of your program and you should get familiar with a debugger. It looks like your code didn't work for too many reasons at the same time, which means that you probably wrote too much code at the same time without properly testing small increments.
Feel free to post a new version of the code if you are still having problems.
Now I realize that your code *is* Java, and not C++. No wonder I had a hard time understanding it. :)
No matter what programming language you use, you should get in the habit of testing small units of your program and you should get familiar with a debugger. It looks like your code didn't work for too many reasons at the same time, which means that you probably wrote too much code at the same time without properly testing small increments.
Feel free to post a new version of the code if you are still having problems.
December 13, 2005 06:14 AM
well I'm still having a problems. In the checkers game the user is RED, the computer is the BLACK.
It seems like whatever depth I use, the moves generated are the same.
Here is some code, which is easier to read, because the classes are abstrated.
Does anyone notice anything wrong with my minmax, or I should say negamax? If anyone has any question or wants more info, please let me know.
It seems like whatever depth I use, the moves generated are the same.
Here is some code, which is easier to read, because the classes are abstrated.
int MinMaxCall(pGameBoard, pDepth, pTurn)//state of gameboard, search depth, turn{ best = -1000000; tmpBest = -1000000; if (pDepth <= 0) { return Evaluate(pGameBoard, pTurn); GenerateMoveList(); //move list for the current board. while(MovesLeft()) { val = MinMax(pGameBoard, depth, pTurn); if (val >= best) { best = val; bestMove = CurrentMove(); } tmpBest = -1000000; tmpVal = -1000000; return best; } }}int MinMax(pGameBoard, pDepth, pTurn){ if (pTurn == BLACK) pTurn = RED; else pTurn = BLACK; if (depth <= 0) return Evaluate(pGameBoard, pTurn); GenerateMoveList(); while(MovesLeft()) { doMove(); tmpVal = -1000000; tmpVal = -MinMax2(pGameBoard, depth - 1, pTurn); undoMove(); if (tmpVal >= tmpBest) tmpBest = tmpVal; } return tmpBest; }Does anyone notice anything wrong with my minmax, or I should say negamax? If anyone has any question or wants more info, please let me know.
21,607
December 13, 2005 08:05 AM
Oh, please post the entire code, even if we have a hard time understanding it. You should add some comments, at least one before each function explaining what it does (MinMax, MinMax2, MinMaxCall?).
138
December 13, 2005 08:59 AM
I think you have mis-understood the idea behind negamax, since you still have two functions for minimax (MinMax and MinMax2). The basic idea is that by negating the return value from minimax, we can see the game from the opponents point of view (ie. the complete opposite of the other player). For negamax to work correctly, you need to functions, which look alike, but have some subtle differences. The first, which I call `think()', calls the second, `minimax()', which searches the game tree from each move at the current position. They look like this: (pseudo-code)
I'm not sure if this is particuarly clear or not, so please let me know if you didn't understand something. Otherwise, try implementing something along those lines, then come back if you have problems.
Note: I havn't tried compiling any of the code I posted.
Move think(int depth){ //this returns the best move found, once we've done searching Move best_move,m[128]; int num_moves=generate_moves(m), best_score=-INFINITY, eval; for(int i=0;i<num_moves;++i){ do_move(board,m); eval=-minimax(board,depth-1); undo_move(board,m); if(eval>best_score){ best_score=eval; best_move=m; } } return best_move;}int minimax(Board b,int depth){ //this returns a value, which we use to determine if this line of play is good for the side to move if(depth<=0) return static_evaluation(b); Move m[128]; int num_moves=generate_moves(m), best_score=-INFINITY, eval; for(int i=0;i<num_moves;++i){ do_move(board,m); eval=-minimax(board,depth-1); undo_move(board,m); if(best_score>eval) best_score=eval; } return best_score;}I'm not sure if this is particuarly clear or not, so please let me know if you didn't understand something. Otherwise, try implementing something along those lines, then come back if you have problems.
Note: I havn't tried compiling any of the code I posted.
______Tom
132
December 13, 2005 12:46 PM
Can you post your code that generates the moves, if that is what you are having trouble with? If you are trying to generate moves for a specific player, I would guess that you would probably need to send that player as an argument for the function, depending on how you are implementing it. Also, there are still a few functions you are calling that are a bit ambigious to us, such as minmax2?
It looks a little bit like you are combining both minimax and negamax. If you are trying to implement negamax(which it looks like) you shouldn't need to call a different minimax2 function.
Here are a couple of links that I found useful...theres a lot more out there, just search for chess algorithms and most of them will discuss minimax and alpha-beta.
http://www.fierz.ch/strategy1.htm
http://www.seanet.com/~brucemo/topics/topics.htm
It looks a little bit like you are combining both minimax and negamax. If you are trying to implement negamax(which it looks like) you shouldn't need to call a different minimax2 function.
Here are a couple of links that I found useful...theres a lot more out there, just search for chess algorithms and most of them will discuss minimax and alpha-beta.
http://www.fierz.ch/strategy1.htm
http://www.seanet.com/~brucemo/topics/topics.htm
If you want the rainbow, you've gotta put up with the rain - do you know which philosopher said that? Dolly Parton. And people say she's just a big pair of tits.
December 13, 2005 02:48 PM
I'm sorry, there should be not such a thing as MinMax2, I was cleaing up my code for posting it. I had a few different minmax functions with variations that I was trying.
I will post my more code later, after I add a few comments and clean it up.
This is the code that's above, but with minmax instead of minmax2. I understand the principle behind negamax. It's just "-" the values on successive calls to simimulate alternating between min and max.
[Edited by - kaddy69 on December 13, 2005 4:48:16 PM]
I will post my more code later, after I add a few comments and clean it up.
This is the code that's above, but with minmax instead of minmax2. I understand the principle behind negamax. It's just "-" the values on successive calls to simimulate alternating between min and max.
int MinMaxCall(pGameBoard, pDepth, pTurn)//state of gameboard, search depth, turn{ best = -1000000; tmpBest = -1000000; if (pDepth <= 0) { return Evaluate(pGameBoard, pTurn); GenerateMoveList(); //move list for the current board. while(MovesLeft()) { val = MinMax(pGameBoard, depth, pTurn); if (val >= best) { best = val; bestMove = CurrentMove(); } tmpBest = -1000000; tmpVal = -1000000; return best; } }}int MinMax(pGameBoard, pDepth, pTurn){ if (pTurn == BLACK) pTurn = RED; else pTurn = BLACK; if (depth <= 0) return Evaluate(pGameBoard, pTurn); GenerateMoveList(); while(MovesLeft()) { doMove(); tmpVal = -1000000; tmpVal = -MinMax(pGameBoard, depth - 1, pTurn); undoMove(); if (tmpVal >= tmpBest) tmpBest = tmpVal; } return tmpBest; }[Edited by - kaddy69 on December 13, 2005 4:48:16 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
