Precompute repetition info (#2132)

Store repetition info in StateInfo instead of recomputing it in
three different places. This saves some work in has_game_cycle()
where this info is needed for positions before the root.

Tested for non-regression at STC:
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 34104 W: 7586 L: 7489 D: 19029
http://tests.stockfishchess.org/tests/view/5cd0676e0ebc5925cf044b56

No functional change.

diff --git a/src/position.cpp b/src/position.cpp
index a86d77ad7707bcfc6337f293cfa7180af31c6635..901e91a70f2f93d49191aa9e2c65e38d8c9e653f 100644 (file)
--- a/src/position.cpp
+++ b/src/position.cpp
@@ -879,6 +879,25 @@ void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
   // Update king attacks used for fast check detection
   set_check_info(st);
 
+  // Calculate the repetition info. It is the ply distance from the previous
+  // occurrence of the same position, negative in the 3-fold case, or zero
+  // if the position was not repeated.
+  st->repetition = 0;
+  int end = std::min(st->rule50, st->pliesFromNull);
+  if (end >= 4)
+  {
+      StateInfo* stp = st->previous->previous;
+      for (int i=4; i <= end; i += 2)
+      {
+          stp = stp->previous->previous;
+          if (stp->key == st->key)
+          {
+              st->repetition = stp->repetition ? -i : i;
+              break;
+          }
+      }
+  }
+
   assert(pos_is_ok());
 }
 
@@ -994,6 +1013,8 @@ void Position::do_null_move(StateInfo& newSt) {
 
   set_check_info(st);
 
+  st->repetition = 0;
+
   assert(pos_is_ok());
 }
 
@@ -1117,24 +1138,10 @@ bool Position::is_draw(int ply) const {
   if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
       return true;
 
-  int end = std::min(st->rule50, st->pliesFromNull);
-
-  if (end < 4)
-    return false;
-
-  StateInfo* stp = st->previous->previous;
-  int cnt = 0;
-
-  for (int i = 4; i <= end; i += 2)
-  {
-      stp = stp->previous->previous;
-
-      // Return a draw score if a position repeats once earlier but strictly
-      // after the root, or repeats twice before or at the root.
-      if (   stp->key == st->key
-          && ++cnt + (ply > i) == 2)
-          return true;
-  }
+  // Return a draw score if a position repeats once earlier but strictly
+  // after the root, or repeats twice before or at the root.
+  if (st->repetition && st->repetition < ply)
+      return true;
 
   return false;
 }
@@ -1146,26 +1153,15 @@ bool Position::is_draw(int ply) const {
 bool Position::has_repeated() const {
 
     StateInfo* stc = st;
-    while (true)
+    int end = std::min(st->rule50, st->pliesFromNull);
+    while (end-- >= 4)
     {
-        int i = 4, end = std::min(stc->rule50, stc->pliesFromNull);
-
-        if (end < i)
-            return false;
-
-        StateInfo* stp = stc->previous->previous;
-
-        do {
-            stp = stp->previous->previous;
-
-            if (stp->key == stc->key)
-                return true;
-
-            i += 2;
-        } while (i <= end);
+        if (stc->repetition)
+            return true;
 
         stc = stc->previous;
     }
+    return false;
 }
 
 
@@ -1212,13 +1208,8 @@ bool Position::has_game_cycle(int ply) const {
                   continue;
 
               // For repetitions before or at the root, require one more
-              StateInfo* next_stp = stp;
-              for (int k = i + 2; k <= end; k += 2)
-              {
-                  next_stp = next_stp->previous->previous;
-                  if (next_stp->key == stp->key)
-                     return true;
-              }
+              if (stp->repetition)
+                  return true;
           }
       }
   }

diff --git a/src/position.h b/src/position.h
index a3fb16b8e6c2c871a6e9ac3ab5ca3e11d36f9863..5ff3d1ace8d3b908da4f39ff6c1247b58f7ccfde 100644 (file)
--- a/src/position.h
+++ b/src/position.h
@@ -46,6 +46,7 @@ struct StateInfo {
   Square epSquare;
 
   // Not copied when making a move (will be recomputed anyhow)
+  int repetition;
   Key        key;
   Bitboard   checkersBB;
   Piece      capturedPiece;