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 )
...
}
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