Repetition of move in Draughts game

Question

I am having a little problem in my draughts game. Lets say my red piece (moving through AI) has arrived at the border of black pieces and now it has become a king, lets assume it is at index 2. Now when its next AI's turn, this piece moves to index 5, thats ok. But on next turn it moves to index 2 and then this transition between index 2 and 5 continues in every turn. I can't figure out whats wrong. I have revised my generate_moves() and it seems ok. Any idea what can be wrong? – My evaluation function is as follows:

public double Evaluation(int type, int aBoard[]) {


  double reds, blacks, ret=0.0;
  int loop;     

  for(reds=blacks=loop=0;loop<32;loop++) {
    switch(aBoard[loop]) {
                case 2: //redKingType:
                  reds+=1;
                case 0://redType:
                  reds+=1;
                  break;
                case 3://blackKingType:
                  blacks+=1;
                case 1://blackType:
                  blacks+=1;
                  break;
                default:
                  break;
    }
  }
  switch(type) {
              case 0://redType:
              case 2://redKingType
                if(reds==0) {
                  return 0.0;
                }
                if(blacks==0) {
                  return 24.0;
                }
                ret=reds/blacks;
                    return ret;
              case 1://blackType
              case 3://blackKingType
                if(reds==0) {
                  return 24.0;
                }
                if(blacks==0) {
                  return 0.0;
                }
                ret=blacks/reds;
                   return ret;
              default:
                break;
  }




  return ret;
} 

Note: I know this a very simple evaluation function ,but please consider the fact that I am doing this for the first time, under a hard deadline.

Answer 1

Your evaluation function seems to consider only material, so when there is no obvious tactical lines, your root search function will simply return whatever moves were generated first. This leads to repetitive behaviour; your program is unaware of any potential progress and so simply waits for the opponent to make a mistake or force a tactical line.

To fix this, you need to add positional factors to your evaluation and implement a repetition detection scheme inside your search. The program should play towards improving its position if there are no obvious tactics within the search horizon. If the position has been repeated a number of times, you can return a draw score. If it is propagated to the root as the best score, you can then make a draw offer.

Answer 2

It's pretty common for robots to prefer meaningless to-and-fro moves in games that permit them, and in situations where there is no immediately obvious good move. There's nothing wrong per se; but fixing this is all part of crafting a good program.

The first thing you need to do is detect the repetition and end the game. It may also be useful for the evaluator to score games that end this way as worse than ties, (still better than losses) to add incentive to avoid this behavior.