nullmove and repetitive draw detection

[bob]

In Stockfish 1.7.1

Code: Select all

void Position::do_null_move(....
// Save the current key to the history[] array, in order to be able to
  // detect repetition draws.
  history[gamePly] = key;
  gamePly++;

Should null moves be excluded from repetitive draw detection?

I think this was answered a couple of years ago. There is no reason to exclude them. If the best one can do below a null move is repeat a position that came before the null-move, why not consider it a draw and get out early?

I ran tests on this and it took a ton of games, but it ended up better to test for repetitions normally after a null-move search, by a fraction of one Elo. You can probably find the thread if you search hard enough... I think the original conclusion was "it makes no significant difference"

[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.

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 reset the 50 move counter after doing a null, but that doesn't cut off the repetition check in the current version. It still checks the entire active path, not just the positions since the null...

[SuneF]

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 think if black keeps doing nothing then white should at some point begin to fail high. Since black is not making any progress and white is happy shuffling (beta <= 0) just conclude that white is okay in this very foolish line and get out.

Is there a TT problem? Well yes, but any kind of shuffling will cause this given the right window, null moving or not.

[hgm]

I think it ismore serious than that. You don't want null moves to be refuted by null-spanning repeats. That would erode the usefulness of the null move, which is detrimental for efficiency. Concluding "white is OK" here, while in fact it is badly losing, (i.e. far below alpha), will cause black to start considering alternatives to the null move, at 2-3 ply larger depth, to finally come to the correct conclusion that white was losing.

This is a bad aspect of recognizing null-spanning repeats as draws, that does not have any upside I can see.

If precision tests show that recognizing null-spanning repeats has a positive effect on playing strength, it can only be because of the opposite case, when a move sequence like above occurs when a draw is good for the null-moving side, because now you can conluce that without searching the null move,and it will only lead to white considering alternatives (which he woulddonomatter how you ame to the conclusion that black was OK) for real moves, i.e. not causing an unnecessary increase in search depth.

But it is not necessary at all to accept the disadvantage because it is outweighed by the advantage. The two cases are easy to distinguish. So I want to urge those that are in a position to test, to also test the following case:

Accept a null-spanning repeat as a draw only if that draw makes a directly preceding null move fail high.

[SuneF]

I think it ismore serious than that. You don't want null moves to be refuted by null-spanning repeats. That would erode the usefulness of the null move, which is detrimental for efficiency. Concluding "white is OK" here, while in fact it is badly losing, (i.e. far below alpha), will cause black to start considering alternatives to the null move, at 2-3 ply larger depth, to finally come to the correct conclusion that white was losing.

Usually Black cannot afford to make multiple consecutive "nothing moves". Almost all those positions will be lost. It's like saying White can capture two pieces for free. So there is a very tiny probability that you get a fail high anyway and therefore it's best to skip this nonsense quickly by e.g. repetition.

But you're right if we assume black is still sound enough to fail-high after the "nothing moves", then White should not be allowed to mess this up with a repetition (which in all likelihood would not be possible had Black actually made some legal moves). However by resetting the repetition counter you also eliminate the possibility of other repetitions, which can lead to a larger subtree.

Which effect is greater is unclear to me, yours a magnitude larger but equally rarer.

This is a bad aspect of recognizing null-spanning repeats as draws, that does not have any upside I can see.

If precision tests show that recognizing null-spanning repeats has a positive effect on playing strength, it can only be because of the opposite case, when a move sequence like above occurs when a draw is good for the null-moving side, because now you can conluce that without searching the null move,and it will only lead to white considering alternatives (which he woulddonomatter how you ame to the conclusion that black was OK) for real moves, i.e. not causing an unnecessary increase in search depth.

But it is not necessary at all to accept the disadvantage because it is outweighed by the advantage. The two cases are easy to distinguish. So I want to urge those that are in a position to test, to also test the following case:

Accept a null-spanning repeat as a draw only if that draw makes a directly preceding null move fail high.

[hgm]

Usually Black cannot afford to make multiple consecutive "nothing moves". Almost all those positions will be lost.

I am not sure I follow this. Basically you seem to say that null move does not work, (if I understand correctly that with "nothing moves" you mean null moves). But we know that it does: very often null move fails high, because the side that fails low plays the all nodes, and plays every conceivable blunder under the sun there. Moves that accomplish something are rare, most moves only suck him deeper into the sh*t he is already in. Null move is by far the largest source of beta cutoffs.

It's like saying White can capture two pieces for free. So there is a very tiny probability that you get a fail high anyway and therefore it's best to skip this nonsense quickly by e.g. repetition.

Statistically it is more likely white will blunder away two more pieces for free. The point is, that to make someone fail low, you have to refute _all_ his moves. The sensical as well as the non-sensical. The non-sensical ones are abundant, and you would like to refute them by null moves. Sequences of non-sensical moves you would like to refute with sequences of null moves. Everything else is a waste of nodes. That he has some sequences of moves that pose a threat bad enough that you cannot afford to keep up the null moving is bad enough, but no reason to be soft in refuting is non-sense branches.

However by resetting the repetition counter you also eliminate the possibility of other repetitions, which can lead to a larger subtree.

Which effect is greater is unclear to me, yours a magnitude larger but equally rarer.

Well, I did not say you should reset the repetition counter, did I? How could you possibly recognize null-spanning repeats and score them as high-failing draws for the side that was doing them, when you would reset that counter? But my point was that it is of no importance what effect is larger.