minmax problem
21,607
December 13, 2005 04:40 PM
MinMaxCall should also use a `-' in front of the call to MinMax.
138
December 14, 2005 08:40 AM
tmpVal = -1000000;
tmpVal = -MinMax2(pGameBoard, depth - 1, pTurn);
Did you mean to do that?
tmpVal = -MinMax2(pGameBoard, depth - 1, pTurn);
Did you mean to do that?
______Tom
190
December 15, 2005 09:52 AM
I donot wish to hijack this thread , but i had a question on the same, i am reading about the algorithm here : http://ai-depot.com/LogicGames/MiniMax.html
From the looks of it , it looks fine. I have a small doubt with respect to the selection of moves by min (in the code), specifically the part where it states :
shouldnt this be :
MinMax (GamePosition game) { return MaxMove (game);}MaxMove (GamePosition game) { if (GameEnded(game)) { return EvalGameState(game); } else { best_move <- {}; moves <- GenerateMoves(game); ForEach moves { move <- MinMove(ApplyMove(game)); if (Value(move) > Value(best_move)) { best_move <- move; } } return best_move; }}MinMove (GamePosition game) { best_move <- {}; moves <- GenerateMoves(game); ForEach moves { move <- MaxMove(ApplyMove(game)); if (Value(move) > Value(best_move)) { best_move <- move; } } return best_move;}From the looks of it , it looks fine. I have a small doubt with respect to the selection of moves by min (in the code), specifically the part where it states :
if (Value(move) > Value(best_move)) { best_move <- move;}shouldnt this be :
if (Value(move) < Value(best_move)) { best_move <- move;
"I think there is a world market for maybe five computers." -- Thomas Watson, Chairman of IBM, 1943
21,607
December 15, 2005 10:55 AM
Quote: Original post by Nokturnal
shouldnt this be :
*** Source Snippet Removed ***
Yes, that looks like a typo. It is so easy to make that type of mistake and the two functions are so similar, that you should really consider using the NegaMax idea: Always consider scores from the point of view of the side to move (positive is good for the side to move). Then you only need the Max version of the function, and when you do the recursive call, you change the sign of the result.
190
December 15, 2005 12:04 PM
Thanks alvaro , that had me rattled to an extent.I will check out negamax too ,but i ve already specified alpha-beta pruning as the algorithm of choice in my project synopsis.
Alvaro , you mentioned the use of global arrays to store all possible moves,i guess for a game like tic tac toe , where the number of moves dont exceed 9 , a *fixed size* array can be used , but wouldnt that be a waste of space as the tree grows? I cant seem to picture global array to hold the moves , could you throw some pseudocode at me :)
Cheers!
Alvaro , you mentioned the use of global arrays to store all possible moves,i guess for a game like tic tac toe , where the number of moves dont exceed 9 , a *fixed size* array can be used , but wouldnt that be a waste of space as the tree grows? I cant seem to picture global array to hold the moves , could you throw some pseudocode at me :)
Cheers!
"I think there is a world market for maybe five computers." -- Thomas Watson, Chairman of IBM, 1943
21,607
December 15, 2005 12:39 PM
I can explain how the global array works for a game like checkers, but I am not saying that it's the best way of doing things.
We are not going to store the whole tree anywhere. Because minimax traverses the tree in a depth-first fashion, you can forget any subtrees that you have already evaluated. All you need at any given time is one set of moves for each position in between the root and the current board position.
The easy way to do this is having a collection of moves as a local variable in your minimax function. Something like this:
In case you don't know much C++, std::vector<Move> is a collection of Moves that behaves like a variable-size array. Of course this uses dynamic memory allocation, which is something that you may want to avoid because it's slow. Instead, you can just use a fixed size array. Something like `Move moves[128];' will probably do for checkers, but you may want to think carefully about what the maximum number of legal moves in your game is.
This has the problem that it uses too much memory, which can mess your stack (not a problem these days, but this used to be a big problem with 16-bit compilers), or it can ruin the efficiency of your cache memory (it's better to keep the memory you use contiguous). One possible solution for both of those problems is the global array of moves. You just declare something like `Move gMoves[2048];' as a global variable (the awkward `g' in front of the name will remind people that this is a global variable; you can use a different convention if you want). You will need to keep track of how far from the root you are (how many calls to minimax are there in your call stack), which can be done by passing an extra argument to minimax or by keeping a global variable that is incremented when you call minimax and decremented immediatly after, or maybe you can use a move counter from your board representation. Anyway, you need to use that number (let's call it distance_from_root) to index this array:
unsigned gPlyBegin[64];
This tells you how the big global array is split into several ranges, each corresponding to a set of "brothers" generated at the same time.
Your code would look more like this:
I hope that was clear enough.
We are not going to store the whole tree anywhere. Because minimax traverses the tree in a depth-first fashion, you can forget any subtrees that you have already evaluated. All you need at any given time is one set of moves for each position in between the root and the current board position.
The easy way to do this is having a collection of moves as a local variable in your minimax function. Something like this:
int minimax(Position &P, int depth){ if(P.is_final()) return P.final_score(); if(depth<=0) return static_eval(P); std::vector<Move> moves; generate_moves(P,moves); // Passes `moves' by reference, so it can fill it with all the legal moves int best_score=-INFINITY; for(unsigned i=0; i<moves.size(); ++i){ Position child=P.make_move(moves); int value=-minimax(child, depth-1); if(best_score<value) best_score=value; } return best_score;}In case you don't know much C++, std::vector<Move> is a collection of Moves that behaves like a variable-size array. Of course this uses dynamic memory allocation, which is something that you may want to avoid because it's slow. Instead, you can just use a fixed size array. Something like `Move moves[128];' will probably do for checkers, but you may want to think carefully about what the maximum number of legal moves in your game is.
This has the problem that it uses too much memory, which can mess your stack (not a problem these days, but this used to be a big problem with 16-bit compilers), or it can ruin the efficiency of your cache memory (it's better to keep the memory you use contiguous). One possible solution for both of those problems is the global array of moves. You just declare something like `Move gMoves[2048];' as a global variable (the awkward `g' in front of the name will remind people that this is a global variable; you can use a different convention if you want). You will need to keep track of how far from the root you are (how many calls to minimax are there in your call stack), which can be done by passing an extra argument to minimax or by keeping a global variable that is incremented when you call minimax and decremented immediatly after, or maybe you can use a move counter from your board representation. Anyway, you need to use that number (let's call it distance_from_root) to index this array:
unsigned gPlyBegin[64];
This tells you how the big global array is split into several ranges, each corresponding to a set of "brothers" generated at the same time.
Your code would look more like this:
int minimax(Position &P, int depth){ if(P.is_final()) return P.final_score(); if(depth<=0) return static_eval(P); PlyBegin[P.distance_from_root+1] = generate_moves(P,PlyBegin[P.distance_from_root]); // We pass the index into gMoves where the first move will be written // generate_moves then returns an index to one-past the last move written int best_score=-INFINITY; for(unsigned i=PlyBegin[P.distance_from_root]; i<PlyBegin[P.distance_from_root+1]; ++i){ Position child=P.make_move(gMoves); int value=-minimax(child, depth-1); if(best_score<value) best_score=value; } return best_score;}I hope that was clear enough.
190
December 16, 2005 08:28 AM
That ought to suffice.Thanks :)
"I think there is a world market for maybe five computers." -- Thomas Watson, Chairman of IBM, 1943
December 18, 2005 09:20 PM
Quote: Original post by tomcant
tmpVal = -1000000;
tmpVal = -MinMax2(pGameBoard, depth - 1, pTurn);
Did you mean to do that?
thanks,
That's doesn't need to be there, as tmpVal will be set to the minimax return value anyway.
Quote: Original post by alvaro
MinMaxCall should also use a `-' in front of the call to MinMax.
Thanks alvaro, I changed that but I'm still seems to have problems!
I'm liking the Christmas look :D!
I have posted the code as requested.
Link to the C# code and Visual studio project:
CODE LINK
I'm not exactly sure what the problem is? If I set the depth at 1 or 9 it seems to make the computer moves not really any stronger?
If anyone has any suggestions on my code or where a problem is, please let me know.
thanks
[Edited by - kaddy69 on December 18, 2005 10:20:06 PM]
138
December 19, 2005 01:36 PM
You have three seperate functions which all try to search the tree. There should only really be 2, MinMax() and MinMaxCall(). CompMove() is not needed at all, here. MinMaxCall() needs to be the function which returns the best move, it doesn't need to know about a best score. This means that your functions should look like this: (roughly, I don't know C# very well)
I hope this helps! :)
void MinMaxCall(BoardSquare[] pTempBoard, int depth, int pTurn){ int best = -1000000,val; ArrayList compMoves = new ArrayList(); IEnumerator listIt; if (depth <= 0) return Evaluate(pTempBoard, pTurn); compMoves = gameBoard.MakeMoveList(pTempBoard, compMoves, pTurn); listIt = compMoves.GetEnumerator(); listIt.Reset(); while(listIt.MoveNext()) { gameBoard.DoMove(pTempBoard, ((Moves)listIt.Current)); val = -MinMax(pTempBoard, depth-1, opponent(pTurn)); //you need to define opponent() gameBoard.UndoMove(pTempBoard, ((Moves)listIt.Current)); if (val > best) { best = val; bestMove = ((Moves)listIt.Current); } } gameBoard.DoMove(pTempBoard, bestMove);}int MinMax(BoardSquare[] pTempBoard, int depth, int pTurn){ ArrayList compMoves = new ArrayList(); IEnumerator listIt; int best=-1000000,val; if (depth <= 0) return Evaluate(pTempBoard, pTurn); compMoves = gameBoard.MakeMoveList(pTempBoard, compMoves, pTurn); listIt = compMoves.GetEnumerator(); listIt.Reset(); while(listIt.MoveNext()) { gameBoard.DoMove(pTempBoard, ((Moves)listIt.Current)); val = -MinMax(pTempBoard,depth - 1, opponent(pTurn)); gameBoard.UndoMove(pTempBoard, ((Moves)listIt.Current)); if (val > best) best = val; } return best;}I hope this helps! :)
______Tom
December 21, 2005 01:30 AM
Quote: Original post by tomcant
You have three seperate functions which all try to search the tree. There should only really be 2, MinMax() and MinMaxCall(). CompMove() is not needed at all, here. MinMaxCall() needs to be the function which returns the best move, it doesn't need to know about a best score. This means that your functions should look like this: (roughly, I don't know C# very well)
*** Source Snippet Removed ***
I hope this helps! :)
Thanks for your reply! That did help me out a bit, but I'm still having a major problem. My code is broken down into these two functions (ComputerMove & MinMax). ComputerMove is the function that calls minmax(negamax) for each of the the computers possible moves. The computer is WHITE and trying to maximize.
The problem is that the last move in the list of possible moves (compMoves in the function ComputerMove) is always selected as the bestMove. No matter what. I could run it for a depth of 9, and it would still do the same thing.
example:
list of possible moves:
move 1, move 2, move 3, move 4, move 5, move 6, move 7
move 7 will be the computers best move choice all the time.
I don't seem to see where the problem is?
Here is my source code:
//This function will call the minmax algorithm. WHITE is the computer and it's trying to maximize public void ComputerMove(BoardSquare[] pCurrentBoard) { IEnumerator listIt; int val; //minimax score int best = -1000000;//best score turn = RED; System.Windows.Forms.MessageBox.Show("Computers Move"); //make a move list of the current board compMoves = gameBoard.MakeMoveList(pCurrentBoard, compMoves, WHITE); //check if the game is over if (!(gameBoard.GameOver(WHITE, compMoves))) { //make a copy of the current board which is used for the minmax search. copyBoard = copyGameBoard(pCurrentBoard); listIt = compMoves.GetEnumerator(); listIt.Reset(); //loop through all the possible moves and calculate minmax on each one. while(listIt.MoveNext()) { val = -MinMax(copyBoard, searchDepth, gameBoard.Opponent(turn)); if (val >= best) { best = val; //save best move value bestMove = ((Moves)listIt.Current); //save bestmove } } //make the best move from minmax algorithm. If the move is a jump, it will return other possible jump moves. compMoves = gameBoard.MakeMove(pCurrentBoard, bestMove, compMoves); } } int MinMax(BoardSquare[] pTempBoard, int pDepth, int pTurn) { ArrayList compMoves = new ArrayList(); IEnumerator listIt; int val; int best = -1000000; if (pDepth <= 0) return Evaluate(pTempBoard, pTurn); compMoves = gameBoard.MakeMoveList(pTempBoard, compMoves, pTurn); if ((compMoves) != null) { listIt = compMoves.GetEnumerator(); listIt.Reset(); while(listIt.MoveNext()) { gameBoard.DoMove(pTempBoard, ((Moves)listIt.Current)); //make the move val = -MinMax(pTempBoard,pDepth - 1, gameBoard.Opponent(pTurn)); gameBoard.UndoMove(pTempBoard, ((Moves)listIt.Current)); //undo move if (val >= best) best = val; //save the move value } } return best; } If anyone has any questions please let me know. I don't think it should be this hard to get minmax (negamax working :(). I want to use the alphabeta search if I get this working.
Download link to the code:
CODE LINK
Thanks kaddy69
[Edited by - kaddy69 on December 21, 2005 1:30:43 AM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
