Threefold repetition detection

Implement a threefold repetition detection. Below are the examples of
problems fixed by this change.

    Loosing move in a drawn position.
    position fen 8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1 moves a1a2 a7a8 a2a1
    The old code suggested a loosing move "bestmove a8a7", the new code suggests "bestmove a8b7" leading to a draw.

    Incorrect evaluation (happened in a real game in TCEC Season 9).
    position fen 4rbkr/1q3pp1/b3pn2/7p/1pN5/1P1BBP1P/P1R2QP1/3R2K1 w - - 5 31 moves e3d4 h8h6 d4e3
    The old code evaluated it as "cp 0", the new code evaluation is around "cp -50" which is adequate.

Brings 0.5-1 ELO gain. Passes [-3.00,1.00].

STC: http://tests.stockfishchess.org/tests/view/584ece040ebc5903140c5aea
LLR: 2.96 (-2.94,2.94) [-3.00,1.00]
Total: 47744 W: 8537 L: 8461 D: 30746

LTC: http://tests.stockfishchess.org/tests/view/584f134d0ebc5903140c5b37
LLR: 2.96 (-2.94,2.94) [-3.00,1.00]
Total: 36775 W: 4739 L: 4639 D: 27397

Patch has been rewritten into current form for simplification and
logic slightly changed so that return a draw score if the position
repeats once earlier but after or at the root, or repeats twice
strictly before the root. In its original form, repetition at root
was not returned as an immediate draw.

After retestimng testing both version with SPRT[-3, 1], both passed
succesfully, but this version was chosen becuase more natural. There is
an argument about MultiPV in which an extended draw at root may be sensible.
See discussion here:

   https://github.com/official-stockfish/Stockfish/pull/925

For documentation, current version passed both at STC and LTC:

STC
LLR: 2.96 (-2.94,2.94) [-3.00,1.00]
Total: 51562 W: 9314 L: 9245 D: 33003

LTC
LLR: 2.96 (-2.94,2.94) [-3.00,1.00]
Total: 115663 W: 14904 L: 14906 D: 85853

bench: 5468995

diff --git a/src/position.cpp b/src/position.cpp
index 1b82b6c01f48013a85f02abc50bea48ce4ae97fc..6a393ebb9b0730d5058a21c81ee622c71ec54225 100644 (file)
--- a/src/position.cpp
+++ b/src/position.cpp
@@ -1079,25 +1079,30 @@ bool Position::see_ge(Move m, Value v) const {
 /// Position::is_draw() tests whether the position is drawn by 50-move rule
 /// or by repetition. It does not detect stalemates.
 
-bool Position::is_draw() const {
+bool Position::is_draw(int ply) const {
 
   if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
       return true;
 
-  int e = std::min(st->rule50, st->pliesFromNull);
+  int end = std::min(st->rule50, st->pliesFromNull);
 
-  if (e < 4)
+  if (end < 4)
     return false;
 
   StateInfo* stp = st->previous->previous;
+  int cnt = 0;
 
-  do {
+  for (int i = 4; i <= end; i += 2)
+  {
       stp = stp->previous->previous;
 
-      if (stp->key == st->key)
-          return true; // Draw at first repetition
-
-  } while ((e -= 2) >= 4);
+      // At root position ply is 1, so return a draw score if a position
+      // repeats once earlier but after or at the root, or repeats twice
+      // strictly before the root.
+      if (   stp->key == st->key
+          && ++cnt + (ply - i > 0) == 2)
+          return true;
+  }
 
   return false;
 }

diff --git a/src/position.h b/src/position.h
index 69bf40b18a5092231821e0af840c6afaee243a1c..1ee247e944d4b9bdfb0882137e5deb4c93b1959b 100644 (file)
--- a/src/position.h
+++ b/src/position.h
@@ -150,7 +150,7 @@ public:
   bool is_chess960() const;
   Thread* this_thread() const;
   uint64_t nodes_searched() const;
-  bool is_draw() const;
+  bool is_draw(int ply) const;
   int rule50_count() const;
   Score psq_score() const;
   Value non_pawn_material(Color c) const;

diff --git a/src/search.cpp b/src/search.cpp
index 8089130e594c153a8f87955fde79f4a05dbff1ab..75d388b945ea2573b211f6078ab7006c006ac4a3 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -597,7 +597,7 @@ namespace {
     if (!rootNode)
     {
         // Step 2. Check for aborted search and immediate draw
-        if (Signals.stop.load(std::memory_order_relaxed) || pos.is_draw() || ss->ply >= MAX_PLY)
+        if (Signals.stop.load(std::memory_order_relaxed) || pos.is_draw(ss->ply) || ss->ply >= MAX_PLY)
             return ss->ply >= MAX_PLY && !inCheck ? evaluate(pos)
                                                   : DrawValue[pos.side_to_move()];
 
@@ -1180,7 +1180,7 @@ moves_loop: // When in check search starts from here
     ss->ply = (ss-1)->ply + 1;
 
     // Check for an instant draw or if the maximum ply has been reached
-    if (pos.is_draw() || ss->ply >= MAX_PLY)
+    if (pos.is_draw(ss->ply) || ss->ply >= MAX_PLY)
         return ss->ply >= MAX_PLY && !InCheck ? evaluate(pos)
                                               : DrawValue[pos.side_to_move()];