3-fold repetition

[flok]

Hi,

I get a lot of "3-fold repetition" endings.
What are ways to prevent this?

I was thinking of:

Code: Select all

   int global_extension = 0;

   for(move in moves) {
        doMove()

        score = search(a, b, depth + global_extension);

        if (score > alpha) {
              if (move repeats)
                 global_extension = 1;

              ...
              remember move
              update alpha, beta-cut-off, etc
         }
   }

The idea is that if the last best move was one that causes repetition, then if no beta-cut-off took place, try by deepening to find a move that causes no move repetition.



Another approach could be:

Code: Select all

      for(...) {

         if (score >= alpha) {  // notice the >= instead of >

              if (!move_repeats && score == alpha)
                    continue;

              ...
              remember move
              update alpha, beta-cut-off, etc
         }
     }

Here if the current move is not a move that may cause a 3-fold rep., then if the score is the same as alpha then remember this move instead of the previous which may have been the move that caused the repetition.

What do you think?

[hgm]

The first question is whether you should want to avoid it. If you are badly behind you should be very happy when you achieve a 3-fold repetition.

When you are ahead, your score should reflect that, and be positive. Because in Chess repetitions are draws, which are usually scored as 0, that should make the engine automatically avoid them. If it would still go for repetition in that case, it is not selecting the best move, and you obviously have a search bug.

If you also want to avoid repetitions in near-equal positions, you shouldintroduce 'contempt', and score repetitions negatively for the engine. E.g. when you score it as -90cP, the engine should only make repetitions when it is a Pawn or more behind as only alternative.

[flok]

If you also want to avoid repetitions in near-equal positions,

that's indeed often the case

you shouldintroduce 'contempt', and score repetitions negatively for the engine. E.g. when you score it as -90cP, the engine should only make repetitions when it is a Pawn or more behind as only alternative.

Something like this?

Code: Select all

   if (moveRepetition) {
       if (moveIndex >= 1 && abs(bestVal) < 10) // e.g. not the first move)
         score = -90;
       else
         score = 0;
   }
   else {
        score = -search()
   }

[hgm]

Something like that, but you should score from the engine-side POV, not from the side-to-move POV. So

score = (sideToMove == colorPlayedByEngine ? -90 : +90);

Otherwise it would assume his opponent tries to avoid repetition too, and be surprised if he didn't (e.g. by perpetually checking him). And there is no reason for the condition on bestVal. If bestVal > -90, the repetition will simply be a rejected (non-best) move, and its score will have no effect. I also don't see whether you want to exempt the first move. Why would you not want to discourage repetition on the search of the first move?

[flok]

Something like that, but you should score from the engine-side POV, not from the side-to-move POV. So

score = (sideToMove == colorPlayedByEngine ? -90 : +90);

Oh indeed, not the first time I made such a bug

I also don't see whether you want to exempt the first move. Why would you not want to discourage repetition on the search of the first move?

Because I need some base-score. But I could of course look at abs(alpha) instead I assume? Because alpha would be either the value of a previous iteration or the result of a sibling move (thinking out aloud).

[hgm]

Why would you need a base score? -90 is either the best you can do, or not. The search should be able to figure that out.

[Robert Pope]

My search code has:

Code: Select all

if(draw>0) {
    // Draws get a contempt factor instead of 0 to lower the number of draws
    val=(bd2.movingColor==mainBoard.movingColor)?DRAW_CONTEMPT:-DRAW_CONTEMPT;
    ...
}

I think my draw rate went from 25% to 15% after implementing this.

That reminds me, though - when I converted my eval from centipawns to 0.01centipawns, I never changed the contempt scale. Sigh. Bugs are always there.

[flok]

To compare to, to see if we're near 0 score already?

[hgm]

Why would that be different for a move that throws away 90 cP by repeating from a move that throws away 90 cP by losing a Pawn? Do you also set the Pawn value to 0 during the first move because you have nothing to compare to?

[flok]

oooh! I was under the impression it was something dynamic - it did not work in that way my test showed
will now try with pawn-value - 10