bizarre repetition detection issue

[bob]

I have been puzzling with this for a couple of months. First, the basic idea. One should be able to limit the repetition detection loop to go back no further in the repetition list than roughly 50-move-counter / 2 entries. I reset the counter after any capture or pawn push, and after a null-move is made, and thereby hangs a tail.

1. Without the 50 move counter, I check the list from back to front, in its entirety. And I definitely find repetitions after a null-move with positions before the null-move. Disallowing these hurts Elo as measured by my usual testing. I suppose this makes some sense, since a repetition means no real progress by one side, and getting out of the null-move search quickly is a good idea.

2. I never check for repetition if the 50 move counter is < 4, for obvious reasons, since a repetition is impossible when you need 4 plies to make/unmake a move to get back to the starting positon. This is important in the null-move case, because even though I always check back to the beginning of the repetition list, every time (I am not using 50 counter in repcheck for this discussion) I still will not check for a repetition the first 3 moves after a null-move. Since I am not using the 50 move counter, and since making a null-move currently resets the counter, this means that repetitions can not happen within 3 moves of a null. But once you get to the 4th ply and beyond, then the repetition test is done (still going back to the beginning.)

OK, so far. If I change that "4" value, Elo goes down. I have tried 1,2,3,4,5,6 and for whatever reason, <4 is the best value, any other value drops Elo. I have tried not setting 50 counter to zero after a null, which in the current program only affects the above issue since now it will check for repetitions the move after a null. Elo goes down.

Has anyone experimented with this at all (repetitions thru a null-move)? If I turn null-move off, then the 50 counter limit in repcheck will produce the identical results as with the counter not being used which makes it check every entry, not just the last N. But repetitions around a null-move are an interesting thing since part of the above is not exactly intuitive (why should repetitions within 3 plies of a null-move cause problems, while repetitions beyond 3 plies improve Elo?

One of those "things that make you go hmmm." And to verify, yes, the above has been tested multiple times with 30K game matches. So it isn't a fluke, just a strange fact. A _very_ strange fact...

comments??

[opraus]

1. Without the 50 move counter, I check the list from back to front, in its entirety. And I definitely find repetitions after a null-move with positions before the null-move. Disallowing these hurts Elo as measured by my usual testing. I suppose this makes some sense, since a repetition means no real progress by one side, and getting out of the null-move search quickly is a good idea.

2. I never check for repetition if the 50 move counter is < 4, for obvious reasons, since a repetition is impossible when you need 4 plies to make/unmake a move to get back to the starting positon. This is important in the null-move case, because even though I always check back to the beginning of the repetition list, every time (I am not using 50 counter in repcheck for this discussion) I still will not check for a repetition the first 3 moves after a null-move.

comments??

position
Null; ply=p; counter reset; position'
move ply=p+1 counter=1; position''
Null ply=p+2 counter reset; position'''
move ply=p+3 counter=1 and position is restored

it seems that counter<4 is a false exclusion after null moves

no?

[bob]

1. Without the 50 move counter, I check the list from back to front, in its entirety. And I definitely find repetitions after a null-move with positions before the null-move. Disallowing these hurts Elo as measured by my usual testing. I suppose this makes some sense, since a repetition means no real progress by one side, and getting out of the null-move search quickly is a good idea.

2. I never check for repetition if the 50 move counter is < 4, for obvious reasons, since a repetition is impossible when you need 4 plies to make/unmake a move to get back to the starting positon. This is important in the null-move case, because even though I always check back to the beginning of the repetition list, every time (I am not using 50 counter in repcheck for this discussion) I still will not check for a repetition the first 3 moves after a null-move.

comments??

position
Null; ply=p; counter reset; position'
move ply=p+1 counter=1; position''
Null ply=p+2 counter reset; position'''
move ply=p+3 counter=1 and position is restored

it seems that counter<4 is a false exclusion after null moves

no?

Yes, but it works. That's the issue. I do not quite understand why. If I remove the restriction, which is done by just not resetting the 50-move counter, then Elo drops a bit...

[Uri Blass]

My guess is that the search simply have a better killer move for non null moves
if you do not alllow repetition in the first plies after null move.

In other words not allowing repetition immediately after null move improves the order of moves after moves that are not null.

[hgm]

OK, let me throw in my 2 cents:

The main reason I forbid null-spanning rep-draws is to allow the cut-side two consecutive null moves when defending his lead against pointless non-capture moves of the all-side:

<null> - <poinless move> - <null> - <reverse pointless move> DRAW!?!

As most moves tried by the all side are pointless non-captures, this happens quite a lot. Recognizing this as a draw would then force you to use an expensive real move to refute all his pointless non-captures after the first null. This would make it much more expensive to make a null move fail high. So I can understand why testing for null-spanning repeats immediately after null its detrimental: it gives the all-side a powerful weapon to unjustly refute null moves.

Why it would also be bad 2 or 3 moves after null is harder to see. In such a case the cut-side must have played a non-null, and these must have been played for reason of a threat, otherwise he would have preferred null. (It can't be for reason of a recapture, for that is not reversible.) Especially the case 2 after null is strange. to get a repeat there, the cut-side must have evaded into a repeat, and if that would be bad for him, he would simply play another evasion, without much harm being done, (as detecting the repeat was cheap). So it should only be an issue when it was a forced evasion (i.e. there were no acceptable alternatives).

Suggestion: let Crafty print the board + all moves of the repeat loop when it detects a repeat (2 or 3) moves after null, so that we get a better idea what these cases typically are.

For null-spanning repeats 4 or more moves after null, the "no progress" argument probably is the dominat factor, as this is far enough to not affect the fail-high probability of the last null move, unless the opponent really has a series of threats that can force the cut-side into repetition, which raises legitimate draw concern: 4 moves after null must mean that the cut-side could not afford null two times in a row. A draw score assigned here would only propagate to the last null move if the cut side would not have an alternative sequence of threat evasions that did not run into a (pre-null) repeat.


Now that we are talking about repeats, this is a very interesting issue in Shogi / Crazyhouse. There you have the issue of pseudo-repeats, where the board position is the same, but you have different pieces in hand. Not recognizing those leads to severe horizon effects, as a side that gets into trouble can start sacrificing all its in-hand Pawns by dropping them with a maor threat. Like (+ = check):

<drop P>+, <withdraw K>, <advance P>+, KxP {pseudo-repeat with one less P in hand}

So one P sacrifice buys you 4 ply, and you can have 3 or 4. While to the Human it is obvious that this can lead nowhere.

The point is that having one more P (or whatever) in hand is _always_ better than not having it. This unlike having an extra P on the board, which might make the position arbitrary worse (e.g. you are now checkmated in one because the pawn blocked your Kings's only evasion square). So it make sense to recognize hash or repeat hits on positions with the same board position, even if the holdngs are different. If that position is in the hash with, say, a lower-bound score you could still use that lower bound if you have now extra pieces in hand. You could even correct it for the nominal piece value of those. And if you hit on a pseudo-repeat with less pieces in hand, you should immediately fail low, as you are apparently in a loop burning material, which cannot possibly lead to anything good.

Now normal Chess does not have holdings, of course, but I wonder if a similar case does not exist for having the move. The assumption underlying null move pruning is that there will not be any zugzwang, so it would be consistent to assume having the move is always better in situations here NMP is enabled. If you then would get a pseudo-repeat on a board position you have visited earlier on the branch, but now the opponent has the move, while before you had the move, you should fail low, as you only wasted a tempo. (This should not applied immediately after null move, obviously!)

[opraus]

1. Without the 50 move counter, I check the list from back to front, in its entirety. And I definitely find repetitions after a null-move with positions before the null-move. Disallowing these hurts Elo as measured by my usual testing. I suppose this makes some sense, since a repetition means no real progress by one side, and getting out of the null-move search quickly is a good idea.

2. I never check for repetition if the 50 move counter is < 4, for obvious reasons, since a repetition is impossible when you need 4 plies to make/unmake a move to get back to the starting positon. This is important in the null-move case, because even though I always check back to the beginning of the repetition list, every time (I am not using 50 counter in repcheck for this discussion) I still will not check for a repetition the first 3 moves after a null-move.

comments??

position
Null; ply=p; counter reset; position'
move ply=p+1 counter=1; position''
Null ply=p+2 counter reset; position'''
move ply=p+3 counter=1 and position is restored

it seems that counter<4 is a false exclusion after null moves

no?

Yes, but it works. That's the issue. I do not quite understand why. If I remove the restriction, which is done by just not resetting the 50-move counter, then Elo drops a bit...

I see.

Perhaps if the original position is WON, and would otherwise be a null move cut, it now returns a 'false' draw score - so you lose many good cuts???

position (WON)
Null; ply=p; counter reset; position'
move ply=p+1 counter=1; position''
Null ply=p+2 counter reset; position'''
move ply=p+3 counter=1 and position is restored (DRAW) no cut! position must be searched.

if the 'won' position truly has but one move & unmove then the real search will find the real draw score.

So, if null move returns draw, perhaps a zero window, reduced depth, verification is warranted??

[bob]

1. Without the 50 move counter, I check the list from back to front, in its entirety. And I definitely find repetitions after a null-move with positions before the null-move. Disallowing these hurts Elo as measured by my usual testing. I suppose this makes some sense, since a repetition means no real progress by one side, and getting out of the null-move search quickly is a good idea.

2. I never check for repetition if the 50 move counter is < 4, for obvious reasons, since a repetition is impossible when you need 4 plies to make/unmake a move to get back to the starting positon. This is important in the null-move case, because even though I always check back to the beginning of the repetition list, every time (I am not using 50 counter in repcheck for this discussion) I still will not check for a repetition the first 3 moves after a null-move.

comments??

position
Null; ply=p; counter reset; position'
move ply=p+1 counter=1; position''
Null ply=p+2 counter reset; position'''
move ply=p+3 counter=1 and position is restored

it seems that counter<4 is a false exclusion after null moves

no?

Yes, but it works. That's the issue. I do not quite understand why. If I remove the restriction, which is done by just not resetting the 50-move counter, then Elo drops a bit...

I see.

Perhaps if the original position is WON, and would otherwise be a null move cut, it now returns a 'false' draw score - so you lose many good cuts???

position (WON)
Null; ply=p; counter reset; position'
move ply=p+1 counter=1; position''
Null ply=p+2 counter reset; position'''
move ply=p+3 counter=1 and position is restored (DRAW) no cut! position must be searched.

if the 'won' position truly has but one move & unmove then the real search will find the real draw score.

So, if null move returns draw, perhaps a zero window, reduced depth, verification is warranted??

That was my original thought. But it seems strange that not doing rep tests for the first 4 plies after null is good, changing that 4 to any other value is worse.

The 4 is correct for normal search since you need 4 plies beyond a non-reversible move to create a repetition. But null makes this behave unexpectedly...

I am still playing with it to come up with an explanation.

[bob]

OK, let me throw in my 2 cents:

The main reason I forbid null-spanning rep-draws is to allow the cut-side two consecutive null moves when defending his lead against pointless non-capture moves of the all-side:

<null> - <poinless move> - <null> - <reverse pointless move> DRAW!?!

I don't disagree. But practice doesn't follow this. If I disallow repetitions beyond a null, Elo goes _down_. Not by 20, but by maybe 8-10. In fact, this is the way Crafty was working for quite a while, as I used the 50-move counter to limit how far back I check for reps, and null-move always resets the 50-move counter to 0, which effectively prevents looking back past the most recent null-move.

It is interesting that it is worse. And this result has been confirmed several times in testing.

As most moves tried by the all side are pointless non-captures, this happens quite a lot. Recognizing this as a draw would then force you to use an expensive real move to refute all his pointless non-captures after the first null. This would make it much more expensive to make a null move fail high. So I can understand why testing for null-spanning repeats immediately after null its detrimental: it gives the all-side a powerful weapon to unjustly refute null moves.

Why it would also be bad 2 or 3 moves after null is harder to see. In such a case the cut-side must have played a non-null, and these must have been played for reason of a threat, otherwise he would have preferred null. (It can't be for reason of a recapture, for that is not reversible.) Especially the case 2 after null is strange. to get a repeat there, the cut-side must have evaded into a repeat, and if that would be bad for him, he would simply play another evasion, without much harm being done, (as detecting the repeat was cheap). So it should only be an issue when it was a forced evasion (i.e. there were no acceptable alternatives).

Suggestion: let Crafty print the board + all moves of the repeat loop when it detects a repeat (2 or 3) moves after null, so that we get a better idea what these cases typically are.

Already done, and no surprises. The repetition _always_ happens across the null-move, usually only 1-2 moves back. Has to be a non-capture / non-pawn-move since that would make repetition impossible anyway.

What I actually did was to first use the 50-move counter to limit how far back to look. And assuming no repetition, I then looked from that point back to the beginning of the repetition list to see if there is a match. When there was, I simply dumped the move stack completely, along with the replist. It was rare to repeat a position more than 3-4-5 plies back...

For null-spanning repeats 4 or more moves after null, the "no progress" argument probably is the dominat factor, as this is far enough to not affect the fail-high probability of the last null move, unless the opponent really has a series of threats that can force the cut-side into repetition, which raises legitimate draw concern: 4 moves after null must mean that the cut-side could not afford null two times in a row. A draw score assigned here would only propagate to the last null move if the cut side would not have an alternative sequence of threat evasions that did not run into a (pre-null) repeat.


Now that we are talking about repeats, this is a very interesting issue in Shogi / Crazyhouse. There you have the issue of pseudo-repeats, where the board position is the same, but you have different pieces in hand. Not recognizing those leads to severe horizon effects, as a side that gets into trouble can start sacrificing all its in-hand Pawns by dropping them with a maor threat. Like (+ = check):

<drop P>+, <withdraw K>, <advance P>+, KxP {pseudo-repeat with one less P in hand}

So one P sacrifice buys you 4 ply, and you can have 3 or 4. While to the Human it is obvious that this can lead nowhere.

The point is that having one more P (or whatever) in hand is _always_ better than not having it. This unlike having an extra P on the board, which might make the position arbitrary worse (e.g. you are now checkmated in one because the pawn blocked your Kings's only evasion square). So it make sense to recognize hash or repeat hits on positions with the same board position, even if the holdngs are different. If that position is in the hash with, say, a lower-bound score you could still use that lower bound if you have now extra pieces in hand. You could even correct it for the nominal piece value of those. And if you hit on a pseudo-repeat with less pieces in hand, you should immediately fail low, as you are apparently in a loop burning material, which cannot possibly lead to anything good.

Now normal Chess does not have holdings, of course, but I wonder if a similar case does not exist for having the move. The assumption underlying null move pruning is that there will not be any zugzwang, so it would be consistent to assume having the move is always better in situations here NMP is enabled. If you then would get a pseudo-repeat on a board position you have visited earlier on the branch, but now the opponent has the move, while before you had the move, you should fail low, as you only wasted a tempo. (This should not applied immediately after null move, obviously!)

My next step is going to be to systematically test every possibility here, to produce some sensible data that should tell the story.. Might not tell why, but it will certainly identify what is better and what is worse...

[hgm]

I don't disagree. But practice doesn't follow this. If I disallow repetitions beyond a null, Elo goes _down_. Not by 20, but by maybe 8-10. In fact, this is the way Crafty was working for quite a while, as I used the 50-move counter to limit how far back I check for reps, and null-move always resets the 50-move counter to 0, which effectively prevents looking back past the most recent null-move.

It seems to me that this is not what you were writing. You wrote that Elo went down if you did not inhibit testing (that is, alow it, not disallow it), for repeats on the first 3 moves after null, but only on 0, 1, 2 or 3 moves after 0. To "drop" is go down, not?:

I have tried 1,2,3,4,5,6 and for whatever reason, <4 is the best value, any other value drops Elo.

Suggestion: let Crafty print the board + all moves of the repeat loop when it detects a repeat (2 or 3) moves after null, so that we get a better idea what these cases typically are.

Already done, and no surprises. The repetition _always_ happens across the null-move, usually only 1-2 moves back. Has to be a non-capture / non-pawn-move since that would make repetition impossible anyway.

Well, I am not asking for surprises, just for examples. I want to get an idea what kind of positions this are, and why it would be wrong to assume that the cut-side could avoid the repetition by playing a real move rather than the null move.

[bob]

I don't disagree. But practice doesn't follow this. If I disallow repetitions beyond a null, Elo goes _down_. Not by 20, but by maybe 8-10. In fact, this is the way Crafty was working for quite a while, as I used the 50-move counter to limit how far back I check for reps, and null-move always resets the 50-move counter to 0, which effectively prevents looking back past the most recent null-move.

It seems to me that this is not what you were writing. You wrote that Elo went down if you did not inhibit testing (that is, alow it, not disallow it), for repeats on the first 3 moves after null, but only on 0, 1, 2 or 3 moves after 0. To "drop" is go down, not?:

Sorry for not being clear. Two issues:

(1) if I disallow repetitions beyond a null with positions that occur before the null move, Elo goes down.

(2) if I allow repetitions beyond a null-move within the first 4 plies, Elo also goes down.

The best I have found, via testing (so far) is to allow repetition detection everywhere, across nulls included, but after a null, do not allow repetitions for the first 4 plies, then turn them back on so that they can go across the null-move.

Why that is best I am not certain. But the funny part is that the 4 plies beyond the null move is really a "sweet spot". Changing it to any value other than 4 (larger or smaller) hurts...

I will rerun this specific test once some current tests are finished and post the results, using 0,l 1, 2, 3, 4, 5, 6 so that the sweet spot is visible. This is not a huge gain, but it is definitely measurable and going beyond 4 hurts more than just 2-3 Elo, ditto for backing up to 0 and allowing repetitions everywhere...

I have tried 1,2,3,4,5,6 and for whatever reason, <4 is the best value, any other value drops Elo.

Suggestion: let Crafty print the board + all moves of the repeat loop when it detects a repeat (2 or 3) moves after null, so that we get a better idea what these cases typically are.

Already done, and no surprises. The repetition _always_ happens across the null-move, usually only 1-2 moves back. Has to be a non-capture / non-pawn-move since that would make repetition impossible anyway.

Well, I am not asking for surprises, just for examples. I want to get an idea what kind of positions this are, and why it would be wrong to assume that the cut-side could avoid the repetition by playing a real move rather than the null move.

Edit:

I first noticed this when I (during testing of new repetition code) removed that 4 ply limit, since once the 50 move counter is reset you can't really have a repetition for 4 plies, so it saves checking the list. But it is nothing more than a simple speed optimization. When I removed it, the Elo jumped enough that it suggested a significant improvement in NPS. In reality the improvement was minimal (NPS) but the Elo reduction was real. Turns out it was solely dropping because of the "null-move repetition protection" idea that won't allow a repetition for the first 3 plies after zeroing the 50 move counter. So the original intent of that check at the front of RepetitionCheck() was a minor speed optimization, but in reality in was an improvement for somewhat mysterious reasons. All this came to my attention when we had that last repetition beyond a null-move discussion here several months back. And I have been going back to this every time I have a chance, in the hope that either I find a bizarre bug and fix it, or find a rational explanation. So far, neither...