Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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
share|improve this answer
    
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 Zheng Li 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 Zheng Li Jul 14 '12 at 15:30
1  
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 Zheng Li Aug 2 '12 at 2:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.