MiniMax not working properly(for checkers game)

I am creating a checkers game but My miniMax is not functioning properly,it is always switching between two positions for its move(index 20 and 17).Here is my code:

 public double MiniMax(int[] board, int depth, int turn, int red_best, int black_best)
{

int source;
int dest;
double MAX_SCORE=-INFINITY,newScore;
int MAX_DEPTH=3;
int[] newBoard=new int[32];
generateMoves(board,turn);
System.arraycopy(board, 0, newBoard, 0, 32);
if(depth==MAX_DEPTH)
{ return Evaluation(turn,board);}
for(int z=0;z<possibleMoves.size();z+=2){
source=Integer.parseInt(possibleMoves.elementAt(z).toString());
System.out.println("SOURCE= "+source);

dest=Integer.parseInt(possibleMoves.elementAt(z+1).toString());//(int[])possibleMoves.elementAt(z+1);
System.out.println("DEST = "+dest);
applyMove(newBoard,source,dest);
newScore=MiniMax(newBoard,depth+1,opponent(turn),red_best, black_best);
if(newScore>MAX_SCORE)
{MAX_SCORE=newScore;maxSource=source; maxDest=dest;}//maxSource and maxDest will be used to perform the move.

if (MAX_SCORE > black_best)
{
if (MAX_SCORE >= red_best)
break;  /*  alpha_beta cutoff  */
else
black_best = (int) MAX_SCORE;  //the_score
}
if (MAX_SCORE < red_best)
{
if (MAX_SCORE<= black_best)
break;  /*  alpha_beta cutoff  */
else
red_best = (int) MAX_SCORE;  //the_score
}

}//for ends

return MAX_SCORE;
} //end minimax


I am unable to find out the logical mistake. Any idea what's going wrong?

For your current implementation, this line:

return Evaluation(turn, board);


should be

return Evaluation(rootTurn, board); // rootTurn is black, probably?


so your evaluation is in the perspective of the max player. Also,

double MAX_SCORE = -INFINITY;


should be

double MAX_SCORE = turn == rootTurn ? -INFINITY : INFINITY;


since if you're minimizing the score as you're doing for red, it can't already be -INFINITY.

As you don't seem to be convinced, you can avoid this entire mess of keeping track of sides and whether it's a min or max node, I'd advise using negamax. It gives the same result, but is simpler:

public double Negamax(int[] board, int depth, int turn, double alpha, double beta) {
if (depth == 0)
return Evaluation(turn, board);
int[] newBoard = new int[32];
generateMoves(board, turn);
System.arraycopy(board, 0, newBoard, 0, 32);
for (int z = 0; z < possibleMoves.size(); z += 2) {
int source = Integer.parseInt(possibleMoves.elementAt(z).toString());
//System.out.println("SOURCE= " + source);
int dest = Integer.parseInt(possibleMoves.elementAt(z + 1).toString());// (int[])possibleMoves.elementAt(z+1);
//System.out.println("DEST = " + dest);
applyMove(newBoard, source, dest);

double newScore = -Negamax(newBoard, depth - 1, opponent(turn), -beta, -alpha);
if (newScore >= beta) // alpha-beta cutoff
return newScore;
if(newScore > alpha)
alpha = newScore;
}// for ends

return alpha;
} // end minimax


In this case it's probably actually faster because you didn't set your alpha bound correctly. It works because of symmetry; max(a, b) = -min(-a, -b). In your root node, you should start the search like this:

depth := 3   // what depth to search to?
alpha:= -infinity
foreach move in move list
do move
newScore := -Negamax(newBoard, depth - 1, opponent(turn), -infinity, -alpha);
if newScore > alpha
alpha := newScore
bestMove := move
return bestMove

• I did the changes as you told, the move didn't happened. If player's color is black, then the move which is to be performed through AI is of red piece, and hence rootTurn is red. Am I right? – engineer Jul 13 '12 at 12:19
• Usually, the max player (black in this case) is the one you start with. I strongly suggest you don't hard code sides into your search; I'll update my answer. – Zong Jul 13 '12 at 15:00
• In the algorithm of your updated answer, foreach move in move list do move , Here which player's move to be generated? – engineer Jul 14 '12 at 8:00
• The reason we have a root node is that minimax only returns the value of the node, not the best move. We need a different routine to begin the search so that we can choose the best move. From your original implementation it seems you didn't quite realize this. It should be clear that the root represents the program's turn, and having a separate routine also makes it easy to implement other features such as iterative deepening. I'd advise taking a careful look at the code to understand each part. It will make it easier to implement other features. – Zong Jul 14 '12 at 15:30
• I'm sorry, but your problem is too general and this discussion is getting too lengthy. I recommend posting a new question with more specific details. – Zong Aug 2 '12 at 2:22

You say 'it is always switching between two positions for its move(index 20 and 17)' — once you have debugged and tested your search code (and use the negamax suggested by zong) — you may find that the output still results in an oscillation between two squares.

This may not necessarily be a problem with the search — I've found search result oscillations can occur when the evaluation function doesn't provide sufficient discrimination between the advantages of two different positions in the static eval.

So check both places that your search is scoring as index 20 and index 17 — they may have very similair or identical static scores, and there is insufficient evaluational information for the engine to definitively decide between them.

For debugging negamax, putting in some debug/print statements immediately after the recursive call to negaMax:

moveScore = -negaSearch(theBoard, -beta, -alpha, depth-1)

if depth>2 {print (moveIndex, depth, moveScore)}