algorithm - 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        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?

Answer

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