Null-move-spanning repeats

[hgm]

I bumped into the following issue accidentally, because I am working on an SMP implementation where hash entries are marked as 'busy' when you enter a node (immediately created on a hash miss). If the search then hits on a busy node during search of late moves, it can start searching another late move instead, and pick up the score of the busy node searched by another thread later, to minimize overlapping work. But to my surprise the searched bumped into busy nodes even with a single thread. As in this case only the nodes along the path leading to the current position can be marked 'busy', I had figured these would have been caught in the parent node as repeats.

Of course this was stupid of me, because searching for repeats only goes up to the latest irreversible move, and I count null moves as irreversible. The reason for that is that after nullMove - sillyMove - nullMove a side that is losing could refute the second null move by playing the reverse of the sillyMove to cause a repeat and reap a draw score. While in reality pointlessly moving a piece back and forth will of course not pose a real draw threat to the winning side, as the null moves would be substituted to progress-making moves, making the stalling side off worse than he already is. So I don't keep looking for repeats of positions from before the last null move in the repeat detection (which saves time in this repeat detection as well, as on average null moves are never far away), so that such repeats are searched normally.

But this means the search can run into null-move-spanning repeats. Thinking a little bit about this makes me suspect that continuing searching in this case is actually a waste of time. After null - silly - null - 'yllis' the repeating side should not be able to claim a draw, but he did not make any progress either. And you should only be happy with no progress if you are happy with the current evaluation. In fact this situation is mimicking double null move, where neither side attempts anything. Normally you forbid null moves as null-move reply, but by sneakily moving a piece back and force the under-lying side has achieved the same thing as after null - null.

Returning the static evaluation in this case would work in engines that only attempt null move when the current evaluation is above beta. This is equivalent to making the real move creating the repeat fail low. An automatic fail low would be to big a reward, however, when the first null move was attempted with eval < beta. Such null moves could still fail high if there is an irrefutable threat, like a fork or skewer, which you can cash in QS or when the opponent starts solving it, but usually they would fail low. Against such an 'optimistic' null move sitting idle (or moving the same piece back and forth) would be the natural defense. But returning the static eval would unjustly refute null moves with eval < beta and a pending threat that would make up for the difference. But that still seems better than unjustly refuting null moves with eval >= beta in the cases where beta > 0, by returning 0 (= draw score) instead of eval.

Of course the problem remains how to detect such repeats in the first place; scanning to the stack of keys all the way to the last real ply-counter reset can be quite expensive.