nullmove and repetitive draw detection

[edwardyu]

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?

[zamar]

They are already excluded, note the use of st->pliesFromNull:

// Draw by repetition?
for (int i = 4; i <= Min(Min(gamePly, st->rule50), st->pliesFromNull); i += 2)
if (history[gamePly - i] == st->key)
return true;

[Sven]

They are already excluded, note the use of st->pliesFromNull:

// Draw by repetition?
for (int i = 4; i <= Min(Min(gamePly, st->rule50), st->pliesFromNull); i += 2)
if (history[gamePly - i] == st->key)
return true;

Could you explain the reason why you exclude move sequences containing a null move from repetition detection? As far as I can see Glaurung did not contain this "pliesFromNull" code, and it seems to be new after SF 1.5.1.

If I consider this sequence with White to move:

Code: Select all

Ke4-e5 Kd8-d7
<null> Kd7-e8
Ke5-e4 Ke8-d8

then the last move Ke8-d8 repeats the position before Ke4-e5, why should this be ignored? Couldn't this lead to a wrong null move pruning since Ke5-e4 gets a better (i.e., positive) value than the draw value it deserves (SF evaluates first rep as draw in the tree), and can pretend that Black has a "hopeless" position? Or at least you could miss that Ke5-e4 is pretty bad since it allows Black to draw.

Also, don't you allow for an "infinite repetition" by doing so? Consider this sequence:

Code: Select all

(X1)
Ke4-e5 (Y1) Kd8-d7
<null>      Kd7-e8 &#40;Z1&#41;
Ke5-e4      Ke8-d8
&#40;X2&#41;
<null>      Kd8-d7
Ke4-e5      Kd7-e7
Ke5-e4      Ke7-d8
&#40;X3&#41;
Ke4-e5 &#40;Y2&#41; Kd8-e8 &#40;Z2&#41;
<null>      Ke8-e7
Ke5-e4      Ke7-d8
&#40;X4&#41;

X1 == X2 == X3 == X4 and Y1 == Y2 and Z1 == Z2 but never detected as repetition. There may be even more repetitions in this sequence, I did not check it perfectly.

Might this be an explanation for the endgame behaviour (KQPkq) that had been discussed here a while ago?

Sven

[hgm]

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.

[Sven]

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

[hgm]

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

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.

[zamar]

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.

[mcostalba]

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.

Code: Select all

Date: Wed, 7 Oct 2009 09:03:17 +0100
Subject: Do not claim repetition after null move

Null moves can artificially create a repetition
draw where instead there is no one.

So use a second counter to reset history after
a null move.

Idea from Joona.

After 999 games at 1+0

Mod vs Orig +238 =553 -208 51.50%  514.5/999  +10 ELO

---
 src/position.cpp |    8 ++++++--
 src/position.h   |    2 +-
 2 files changed, 7 insertions(+), 3 deletions(-)

diff --git a/src/position.cpp b/src/position.cpp
index e0e9aa3..4e9a6dc 100644
--- a/src/position.cpp
+++ b/src/position.cpp
@@ -703,7 +703,7 @@ void Position::do_move(Move m, StateInfo& newSt, Bitboard dcCandidates) {
   // pointer to point to the new, ready to be updated, state.
   struct ReducedStateInfo {
     Key key, pawnKey, materialKey;
-    int castleRights, rule50;
+    int castleRights, rule50, pliesFromNull;
     Square epSquare;
     Value mgValue, egValue;
     Value npMaterial[2];
@@ -724,6 +724,7 @@ void Position::do_move(Move m, StateInfo& newSt, Bitboard dcCandidates) {
   // Increment the 50 moves rule draw counter. Resetting it to zero in the
   // case of non-reversible moves is taken care of later.
   st->rule50++;
+  st->pliesFromNull++;
 
   if (move_is_castle(m))
   {
@@ -1242,6 +1243,7 @@ void Position::do_null_move(StateInfo& backupSt) {
   backupSt.mgValue  = st->mgValue;
   backupSt.egValue  = st->egValue;
   backupSt.previous = st->previous;
+  backupSt.pliesFromNull = st->pliesFromNull;
   st->previous = &backupSt;
 
   // Save the current key to the history[] array, in order to be able to
@@ -1258,6 +1260,7 @@ void Position::do_null_move(StateInfo& backupSt) {
   sideToMove = opposite_color(sideToMove);
   st->epSquare = SQ_NONE;
   st->rule50++;
+  st->pliesFromNull = 0;
   gamePly++;
 
   st->mgValue += (sideToMove == WHITE)? TempoValueMidgame : -TempoValueMidgame;
@@ -1279,6 +1282,7 @@ void Position::undo_null_move() {
   st->mgValue  = backupSt->mgValue;
   st->egValue  = backupSt->egValue;
   st->previous = backupSt->previous;
+  st->pliesFromNull = backupSt->pliesFromNull;
 
   // Update the necessary information
   sideToMove = opposite_color(sideToMove);
@@ -1683,7 +1687,7 @@ bool Position::is_draw() const {
       return true;
 
   // Draw by repetition?
-  for &#40;int i = 2; i < Min&#40;gamePly, st->rule50&#41;; i += 2&#41;
+  for &#40;int i = 2; i < Min&#40;Min&#40;gamePly, st->rule50&#41;, st->pliesFromNull&#41;; i += 2&#41;
       if &#40;history&#91;gamePly - i&#93; == st->key&#41;
           return true;
 
diff --git a/src/position.h b/src/position.h
index 370bb1d..606c748 100644
--- a/src/position.h
+++ b/src/position.h
@@ -88,7 +88,7 @@ enum Phase &#123;
 
 struct StateInfo &#123;
   Key key, pawnKey, materialKey;
-  int castleRights, rule50;
+  int castleRights, rule50, pliesFromNull;
   Square epSquare;
   Value mgValue, egValue;
   Value npMaterial&#91;2&#93;;
-- 
1.6.5.1.1367.gcd48

[Sven]

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.

Thanks for your clarification, also to Marco for showing the exact patch and corresponding test results. Regarding Crafty, I missed that "reset 50 moves counter" trick.

I still see the main purpose of the "pliesFromNull" implementation for the "two consecutive null moves by the same side" case, but the way how it is implemented also applies for many other cases, including those which I mentioned.

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

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