Repetition check

[Codesquid]

We had this discussion last year. And the net result was that it is BETTER to leave repetition detection on through null-moves. I don't remember the exact Elo numbers, but I suppose one might be able to do a search to find the thread...

Interesting, will try this out.

[hgm]

This is a bit suspect, though. Because it makes it impossible for the side that is ahead to use two null moves in a row: the losing side would refute him by taking back the move it played in between, for a draw (null, move, null, reverse move = repeat). So the winning side will be forced to use a much more expensive real move in stead of the second null move.

If this tests as better, it indicates that the null move reduction is too large, so that grabbing it twice backfires more often than not.

To me this suggests that it should be possible to do better than what tested as best, by playing with the null-move reduction. E.g. simply forbidding to make a second null move if you did one two ply earlier (as when this is better for the side that is ahead, why wouldn't it be better for the side that is behind?). Or taking the null-move reduction smaller in the first place, or the accumulated reduction smaller (e.g. rather than forbidding the second null move, play it with a reduction R-1 in stead of R).

[Tom Likens]

Does Fairymax do nullmoves? Repetition information carried over from before the null move seems problematic.

This is interesting. Are you suggesting that it's best to xor something in the zobrist key when doing/undoing a null move, to make sure that there won't be any repetition between positions before/after the null move? The null move does change the zobrist via the turn of play already.

But the latter does not prevent detecting a repetition of a previous position with the same side to move. In fact you will usually check every second hash key only since there is no point in checking for a repetition of positions with the opponent to move, so the effect of changing the turn when making the null move is not relevant here.

Isn't the typical solution to set the half move clock to 0 when making a null move? That makes the null move irreversible for the 50 moves rule, and implicitly also for repetition checks if your hash key comparison loop does not go back further than the value of the half move clock.

Sven

We had this discussion last year. And the net result was that it is BETTER to leave repetition detection on through null-moves. I don't remember the exact Elo numbers, but I suppose one might be able to do a search to find the thread...

Bob,

To me this doesn't make intuitive sense. What was the reasoning behind it?

regards,
--tom

[Adam Hair]

Does Fairymax do nullmoves? Repetition information carried over from before the null move seems problematic.

This is interesting. Are you suggesting that it's best to xor something in the zobrist key when doing/undoing a null move, to make sure that there won't be any repetition between positions before/after the null move? The null move does change the zobrist via the turn of play already.

But the latter does not prevent detecting a repetition of a previous position with the same side to move. In fact you will usually check every second hash key only since there is no point in checking for a repetition of positions with the opponent to move, so the effect of changing the turn when making the null move is not relevant here.

Isn't the typical solution to set the half move clock to 0 when making a null move? That makes the null move irreversible for the 50 moves rule, and implicitly also for repetition checks if your hash key comparison loop does not go back further than the value of the half move clock.

Sven

We had this discussion last year. And the net result was that it is BETTER to leave repetition detection on through null-moves. I don't remember the exact Elo numbers, but I suppose one might be able to do a search to find the thread...

Is this the thread:

http://www.talkchess.com/forum/viewtopi ... +null+move

[lucasart]

Does Fairymax do nullmoves? Repetition information carried over from before the null move seems problematic.

This is interesting. Are you suggesting that it's best to xor something in the zobrist key when doing/undoing a null move, to make sure that there won't be any repetition between positions before/after the null move? The null move does change the zobrist via the turn of play already.

But the latter does not prevent detecting a repetition of a previous position with the same side to move. In fact you will usually check every second hash key only since there is no point in checking for a repetition of positions with the opponent to move, so the effect of changing the turn when making the null move is not relevant here.

Isn't the typical solution to set the half move clock to 0 when making a null move? That makes the null move irreversible for the 50 moves rule, and implicitly also for repetition checks if your hash key comparison loop does not go back further than the value of the half move clock.

Sven

Ah OK, now I understand better what Tim Kosse was proposing. I will give this a try: when a null move is played rule50 counter is set to zero. So IIUC Bob Hyatt tested it in Crafty and it was regressive, but Tim Kosse does it in OctoChess (but hasn't tested it?). Anyway, I'll try it in DiscoCheck, and we will see. At least it makes sense intuitively.

[hgm]

To me this doesn't make intuitive sense. What was the reasoning behind it?

The most likely explanation is that the null-move reduction is more than the search can afford when you allow a null move every other ply. So forbidding the null move when there already was a null move two ply earlier effectively undoes part of the reduction. (E.g. with R=2 after two null moves you reduce 4 ply, but with R=3 it would be 6, which is too much and makes you tactically blind. Forbidding the second leaves you at a reduction of 3 ply, which is still OK.)

The null-spanning replies are then just used as a kludge to forbid the second null move for the side that is ahead (because it would lead to a rep draw, which is a fail low when your root score is positive). It doesn't have any effect when you are behind, but something is better than nothing at all.

[Tom Likens]

To me this doesn't make intuitive sense. What was the reasoning behind it?

The most likely explanation is that the null-move reduction is more than the search can afford when you allow a null move every other ply. So forbidding the null move when there already was a null move two ply earlier effectively undoes part of the reduction. (E.g. with R=2 after two null moves you reduce 4 ply, but with R=3 it would be 6, which is too much and makes you tactically blind. Forbidding the second leaves you at a reduction of 3 ply, which is still OK.)

The null-spanning replies are then just used as a kludge to forbid the second null move for the side that is ahead (because it would lead to a rep draw, which is a fail low when your root score is positive). It doesn't have any effect when you are behind, but something is better than nothing at all.

That's interesting. I wonder if anyone has experimented with reducing the null-search reduction value 'R' value depending on how many null moves have already been made to reach this position? It seems like it might be a way to remove a bit of the null-move induced blindness that this theoretically (and accidently) helps.

[hgm]

Apart from the system that allowed only a single null move per branch, (now abandoned by everyone in favor of 'recursive null move') I have never heard of such an investigation.

[bob]

This is a bit suspect, though. Because it makes it impossible for the side that is ahead to use two null moves in a row: the losing side would refute him by taking back the move it played in between, for a draw (null, move, null, reverse move = repeat). So the winning side will be forced to use a much more expensive real move in stead of the second null move.

If this tests as better, it indicates that the null move reduction is too large, so that grabbing it twice backfires more often than not.

To me this suggests that it should be possible to do better than what tested as best, by playing with the null-move reduction. E.g. simply forbidding to make a second null move if you did one two ply earlier (as when this is better for the side that is ahead, why wouldn't it be better for the side that is behind?). Or taking the null-move reduction smaller in the first place, or the accumulated reduction smaller (e.g. rather than forbidding the second null move, play it with a reduction R-1 in stead of R).

I've never allowed two consecutive null-moves, so I can't comment. I tried it once and found it to be slightly worse, and null-move still failed in the usual pawn-only endings too frequently.

BTW my null-move reduction hasn't always been a constant, but once I added q-search checks, the constant actually was a bit better...

[bob]

Does Fairymax do nullmoves? Repetition information carried over from before the null move seems problematic.

This is interesting. Are you suggesting that it's best to xor something in the zobrist key when doing/undoing a null move, to make sure that there won't be any repetition between positions before/after the null move? The null move does change the zobrist via the turn of play already.

But the latter does not prevent detecting a repetition of a previous position with the same side to move. In fact you will usually check every second hash key only since there is no point in checking for a repetition of positions with the opponent to move, so the effect of changing the turn when making the null move is not relevant here.

Isn't the typical solution to set the half move clock to 0 when making a null move? That makes the null move irreversible for the 50 moves rule, and implicitly also for repetition checks if your hash key comparison loop does not go back further than the value of the half move clock.

Sven

We had this discussion last year. And the net result was that it is BETTER to leave repetition detection on through null-moves. I don't remember the exact Elo numbers, but I suppose one might be able to do a search to find the thread...

Bob,

To me this doesn't make intuitive sense. What was the reasoning behind it?

regards,
--tom

I'm only giving results, not theories about why. I didn't give it much thought, but my quick-and-dirty conjecture was that a repetition is a repetition, even after a null. If one side can repeat after a null, then that's suspect anyway since one side didn't move anything...

We had the discussion when someone was asking about how to check for repetitions, and I had mentioned that you only need to go back as far as your 50-move counter carries you, not over the complete repetition list, which saves some time.

Thing was, it was measurably better to do this, and I changed my repetition detection to do so (I originally altered the hash signature after a null, which prevented repetitions, but I took that out and it played stronger in cluster testing. I tried taking the hash signature update out, but STILL not do repetition scanning beyond the 50 move counter and that was no improvement at all, so it was the repetition testing across the null-move that was somehow helping...