nullmove and repetitive draw detection

[bob]

The null move symbolizes any quiet ot defensive move, and although such moves are nort supposed to have tactical consequences, they do make the position different.

The most detrimental effect of not considering the null move irreversible is that it is no longer possible for the side that is ahead to obtain a fail high by doing consecutive null moves for one side. After <null> <passive move> another <null> would be refuted by <reverse passive move>, which would get a draw score. So you would be forced to refute most nonsense moves after <null> by a real move, losing the reduction, where a null move would have been the logical choice.

It is probably correct that the subtree after <passive move> becomes smaller this way, although the subtree after the second <null> is considerably larger. So at least it seems o.k. not to check for repetition after *two consecutive null moves of the same side*. But the "pliesFromNull" implementation skips more repetition draws than that, and I still doubt that this does not hurt, at least in endgames. Also a sequence

Code: Select all

<MOVE1>      <null>
<rev. MOVE1> <MOVE2>
<null>       <rev. MOVE2>

is not evaluated as draw.

It would be interesting to see game results with vs. without "pliesFromNull" implementation, or to get a statement about the test results when that feature was added.

Fruit 2.1 does not have it, Glaurung 2.x does not have it, Crafty 23.1 does not have it, and as far as I can see Ipp* does not have it, too. So if test results are positive then this would indeed look like a unique improvement by Stockfish.

Sven

We had this discussion last year as well. I tested the idea and found that it hurt Crafty's cluster-testing results. It eliminates repetitions that span a null-move and makes the tree larger. A null-move is already an illegal move, so trying to "correct" something that happens after a null seems like a foolish waste of time. I play a null move thinking I am so far ahead that my opponent can do anything he wants and I will still be winning. If he threatens to repeat, more power to him, I'd prefer to do a real search then to see if he can force it or not.

[bob]

Crafty does not have it??? I can't believe that. Bob wrote on several occasions here that a null move should be considered irreversible, and that this is the reason why on the average only very few iterations have to be made in the linear search through previous moves to hunt for repetitions. (And that this is what makes a linear search competative to more advanced methods, such as hashing.)

Nope, Crafty does not have it. This is a tricky subject, but I found it better to let a position after a null match a position before the null if all else is equal. I tested in my usual way, and let the cluster choose the best approach, which I have been using ever since.

I thought this was absolutely standard. In any case, Joker has been doing it for years, HaQiKi D does it from the first draft on.

I think it would be very wrong to consider 'repetitions' of the kind you mention as draws. The purpose of the null move is to probe if the opponent has a threat bad enough so that it is not obvious you can achieve fail high, but have to verify it by search. The observation "if I do nothing, he will do nothing, and we will have a rep-draw" does not count as such a threat. Because it is totally obvious that in reality you will not be allowed "to do nothing", and anything you do will spoil the repetition. The draw would be a totally imaginary threat.

[bob]

Crafty does not have it???

Most programs simply reset fifty move rule counter when doing null move. If I remember correctly Bob said that Crafty uses this trick. The downside is that side can escape fifty move rule by doing null move which perhaps doesn't cost any elo, but is irritating in practice.

While I do reset this counter, I do not use it in my repetition check loop, I loop over all positions stored since the last non-reversible move was played on the real board at the root....

The problem is that side with score below zero can refute a null move with a move which simply repeats the position. Then this dummy move causing fail high can end up saved in transposition table which we really don't want to do.


Consider,
Kd7-e8 Null
Ke8-d7 Null
Kd7-e8 Null
Ke8-d7 Null

If white is down in material we don't want king shuffling cause fail high and refute null move.

I don't think it matters what happens there. If white has nothing better after 4 black nulls, something is odd already.

[bob]

10 Elo is a lot. It corresponds to a 10% speedup! IIRC drastic search techniques like null move or LMR in Crafty only provided 40 Elo.

No. LMR or Null by themselves provides +80. Adding the "other" one adds another +40. Null + LMR is +120, at least in Crafty.

[bob]

I'm going to go back and re-test this since I didn't save the results. I'll post the results when this test is done, but it is queued up after a test of new code submitted by Tracy, so it will likely be late today or tomorrow.

[hgm]

10 Elo is a lot. It corresponds to a 10% speedup! IIRC drastic search techniques like null move or LMR in Crafty only provided 40 Elo.

No. LMR or Null by themselves provides +80. Adding the "other" one adds another +40. Null + LMR is +120, at least in Crafty.

That is what I was saying. The effect of irreversible null-move in Stockfish was tested with all other stuff in place (LMR + null move). So it should be compared to the effect of null move with all other stuff (including LMR) in place. The difference between LMR and LMR+null is +40. Make null irreversible, and you gain another +10. That means null move is only 80% effective when you make it reversible.

Apparently you removed this from Crafty since the last time we discussed it.

[zamar]

Also, from the "+ 10 ELO" result from 999 games I would derive that not having this feature does not hurt really much, despite the claim that it were already "standard".

Sven

+10 elo (+- 8 elo). This practically means the change is improvement with around 90% propability. For more exact results you need a cluster

[bob]

10 Elo is a lot. It corresponds to a 10% speedup! IIRC drastic search techniques like null move or LMR in Crafty only provided 40 Elo.

No. LMR or Null by themselves provides +80. Adding the "other" one adds another +40. Null + LMR is +120, at least in Crafty.

That is what I was saying. The effect of irreversible null-move in Stockfish was tested with all other stuff in place (LMR + null move). So it should be compared to the effect of null move with all other stuff (including LMR) in place. The difference between LMR and LMR+null is +40. Make null irreversible, and you gain another +10. That means null move is only 80% effective when you make it reversible.

Apparently you removed this from Crafty since the last time we discussed it.

I am going to re-test this again. I do not remember the specifics and it is easier to just try it both ways and report the results here. All I can say for certain is that we never _intentionally_ change something without cluster validation. However, there is an occasional case where we are testing several changes and lose one in the flurry. We've changed the way we test a bit to avoid this
happening again (the change in testing was about 6 months ago, where we test exactly one change at a time, whether we "believe" them to be orthogonal or not.)

[bob]

10 Elo is a lot. It corresponds to a 10% speedup! IIRC drastic search techniques like null move or LMR in Crafty only provided 40 Elo.

No. LMR or Null by themselves provides +80. Adding the "other" one adds another +40. Null + LMR is +120, at least in Crafty.

That is what I was saying. The effect of irreversible null-move in Stockfish was tested with all other stuff in place (LMR + null move). So it should be compared to the effect of null move with all other stuff (including LMR) in place. The difference between LMR and LMR+null is +40. Make null irreversible, and you gain another +10. That means null move is only 80% effective when you make it reversible.

Apparently you removed this from Crafty since the last time we discussed it.

I am going to re-test this again. I do not remember the specifics and it is easier to just try it both ways and report the results here. All I can say for certain is that we never _intentionally_ change something without cluster validation. However, there is an occasional case where we are testing several changes and lose one in the flurry. We've changed the way we test a bit to avoid this
happening again (the change in testing was about 6 months ago, where we test exactly one change at a time, whether we "believe" them to be orthogonal or not.)

OK, results are in. After 30K games with this change, and 30K ignoring the issue so that repetitions can occur across null-move, I found absolutely no difference. I re-ran the test for a verification. Using the 50-move counter to stop rep testing vs not using it (which would check across null-moves all the way back to the top of the history list) makes zero difference.

[Don]

10 Elo is a lot. It corresponds to a 10% speedup! IIRC drastic search techniques like null move or LMR in Crafty only provided 40 Elo.

No. LMR or Null by themselves provides +80. Adding the "other" one adds another +40. Null + LMR is +120, at least in Crafty.

That is what I was saying. The effect of irreversible null-move in Stockfish was tested with all other stuff in place (LMR + null move). So it should be compared to the effect of null move with all other stuff (including LMR) in place. The difference between LMR and LMR+null is +40. Make null irreversible, and you gain another +10. That means null move is only 80% effective when you make it reversible.

Apparently you removed this from Crafty since the last time we discussed it.

I am going to re-test this again. I do not remember the specifics and it is easier to just try it both ways and report the results here. All I can say for certain is that we never _intentionally_ change something without cluster validation. However, there is an occasional case where we are testing several changes and lose one in the flurry. We've changed the way we test a bit to avoid this
happening again (the change in testing was about 6 months ago, where we test exactly one change at a time, whether we "believe" them to be orthogonal or not.)

OK, results are in. After 30K games with this change, and 30K ignoring the issue so that repetitions can occur across null-move, I found absolutely no difference. I re-ran the test for a verification. Using the 50-move counter to stop rep testing vs not using it (which would check across null-moves all the way back to the top of the history list) makes zero difference.

I actually revisited repetition detection when I ran across this thread (from about 1 year ago.) Does anyone else have any more experience with this issue? It seems to me that there were a lot of good reasons to consider the null move as irreversible, and yet either method seems valid.

My current testing implies that null move should be treated like a quiet move and that you can test across null move boundaries - but I only have 900 games, 10.7 ELO and 20.8 error margin so it's far from a done deal.

So is this the latest thinking on the matter? It doesn't matter either way? Is one way particularly zugzwang friendly compared to the other?