Avoid Repetition Pruning again

[Gerd Isenberg]

A small summarize:

If we treat first repetition inside the tree already as draw and the side to move has at least a draw-score, that is alpha >= 0, it is safe to prune nullify-moves with some extra condition, since we can not improve alpha if we allow the opponent to repeat the position. The move about to make unmakes the previous reversible move, made two plies before. Playing that move may at least refuted by the opponent by unmaking his previous reversible move (if any) as well, to immediately repeat the position.

As Uri pointed out, we have to take care the reversible moves of both sides are independent. For instance 1. Rb2-b3 Qd1-a4 2. Rb3-b2 and now the black queen can't move to d1 again.

Code: Select all

   while (( move = getMove(..)) != 0 )
   {
      if (alpha >= 0
       && ply > 1
       && count50 > 1
       && move.from == move2node[ply-1].to
       && move.to   == move2node[ply-1].from
       && move.to is not between(move2node[ply].from, move2node[ply].to)
      ) continue; // prune, since other side may force a repetition

      makeMove(move,..);
      val = -search(depth-1, ply+1, -beta, -alpha);		  
      unmakeMove(move,..);
      if ( val > alpha )
         ...
   }

Advantage:
we save some nodes, likely in a range of one percent, but considerable amounts in rook endings and shuffle positions, where the stronger side can't make progess and likes to keep a positional advantage by doing nothing. We may recognize "no progess" earlier, since avoid repetition pruning is also applied at frontier-nodes, where one usually would not try the quite refutation which repeats the position in qsearch. We safe calls to repetition detection because we prune a lot positions with sufficient count50.

Disadvantage:
Increasing code size of the recursive search routine, which may result in a slowdown. If we reach the same node at a (pre-)frontier node, for instance with a wider window and alpha still less zero before we start to make that move, we may erroneous get a score greater than zero (instead of zero) from that move, because the quite repetition making refutation is usually pruned in qsearch.

Any idea how to solve that possible source of search-instability other than throwing out that pruning? Like additional knowledge which detects stuff one or two plies before - but based on bounds.

Thanks,
Gerd

[michiguel]

A small summarize:

If we treat first repetition inside the tree already as draw and the side to move has at least a draw-score, that is alpha >= 0, it is safe to prune nullify-moves with some extra condition, since we can not improve alpha if we allow the opponent to repeat the position. The move about to make unmakes the previous reversible move, made two plies before. Playing that move may at least refuted by the opponent by unmaking his previous reversible move (if any) as well, to immediately repeat the position.

As Uri pointed out, we have to take care the reversible moves of both sides are independent. For instance 1. Rb2-b3 Qd1-a4 2. Rb3-b2 and now the black queen can't move to d1 again.

Code: Select all

   while (( move = getMove(..)) != 0 )
   {
      if (alpha >= 0
       && ply > 1
       && count50 > 1
       && move.from == move2node[ply-1].to
       && move.to   == move2node[ply-1].from
       && move.to is not between(move2node[ply].from, move2node[ply].to)
      ) continue; // prune, since other side may force a repetition

      makeMove(move,..);
      val = -search(depth-1, ply+1, -beta, -alpha);		  
      unmakeMove(move,..);
      if ( val > alpha )
         ...
   }

Advantage:
we save some nodes, likely in a range of one percent, but considerable amounts in rook endings and shuffle positions, where the stronger side can't make progess and likes to keep a positional advantage by doing nothing. We may recognize "no progess" earlier, since avoid repetition pruning is also applied at frontier-nodes, where one usually would not try the quite refutation which repeats the position in qsearch. We safe calls to repetition detection because we prune a lot positions with sufficient count50.

Disadvantage:
Increasing code size of the recursive search routine, which may result in a slowdown. If we reach the same node at a (pre-)frontier node, for instance with a wider window and alpha still less zero before we start to make that move, we may erroneous get a score greater than zero (instead of zero) from that move, because the quite repetition making refutation is usually pruned in qsearch.

Any idea how to solve that possible source of search-instability other than throwing out that pruning? Like additional knowledge which detects stuff one or two plies before - but based on bounds.

Thanks,
Gerd

How about no pruning at all but including this type of knowledge in move ordering?

For instance, do not prune the move, make it, and if beta < 0 and move[ply-1] is the "back and forth" move[ply-3], choose the "back and forth" move of [ply-2] as first option in the move ordering. It may not even be necessary to generate moves and we can use this information as a superkiller. You are not pruning and you waste a makemove to go from ply-1 to ply, but you avoid all sort of potential problems and/or bugs. I think that the simplicity of the implementation could be worth one node wasted.

Also, if alpha >= 0, moves that come back to the previous square can be placed last in the move ordering (rather than pruned). We may not even need to do any pruning. We may never reach the move.

Miguel

[Gerd Isenberg]

How about no pruning at all but including this type of knowledge in move ordering?

For instance, do not prune the move, make it, and if beta < 0 and move[ply-1] is the "back and forth" move[ply-3], choose the "back and forth" move of [ply-2] as first option in the move ordering. It may not even be necessary to generate moves and we can use this information as a superkiller. You are not pruning and you waste a makemove to go from ply-1 to ply, but you avoid all sort of potential problems and/or bugs. I think that the simplicity of the implementation could be worth one node wasted.

Also, if alpha >= 0, moves that come back to the previous square can be placed last in the move ordering (rather than pruned). We may not even need to do any pruning. We may never reach the move.

Miguel

Good point to delegate it to the child. Then one may increase alpha if less zero even at horizon nodes with open window - and all mentioned search-instabilities with that respect should disappear.

Code: Select all

    if &#40;alpha < 0
       && ply > 2
       && count50 > 2
       && move2node&#91;ply&#93;.from == move2node&#91;ply-2&#93;.to
       && move2node&#91;ply&#93;.to   == move2node&#91;ply-2&#93;.from
       && move2node&#91;ply&#93;.to is not between&#40;move2node&#91;ply-1&#93;.from, move2node&#91;ply-1&#93;.to&#41;
    ) &#123;
       if ( 0 >= beta )
           return 0;
       alpha = 0;
       // tag move which repeats the position as done
    &#125;

Gerd