Simplifying away the progressKey

Simplifying away all the progressKey stuff gives exactly the same bench,
without any speed impact. Tested for speed against master with two benches
at depth 22 ran in parallel:

**testedpatch**
Total time (ms) : 92350
Nodes searched : 178962949
Nodes/second : 1937877

**master**
Total time (ms) : 92358
Nodes searched : 178962949
Nodes/second : 1937709

We also tested the patch at STC for no-regression with [-3, 1] bounds:

LLR: 2.96 (-2.94,2.94) [-3.00,1.00]
Total: 57299 W: 11529 L: 11474 D: 34296
http://tests.stockfishchess.org/tests/view/5b015a1c0ebc5914abc126e5

Closes https://github.com/official-stockfish/Stockfish/pull/1603

No functional change.

diff --git a/src/position.cpp b/src/position.cpp
index c07e6964fac76006c874ade7e2d3423b9fdd3862..00e673b2bd662b1e1c03523de1be4250bebf5e90 100644 (file)
--- a/src/position.cpp
+++ b/src/position.cpp
@@ -130,13 +130,13 @@ std::ostream& operator<<(std::ostream& os, const Position& pos) {
 }
 
 
 }
 
 

-// Marcel van Kervink's cuckoo algorithm for fast detection of "upcoming repetition"/
-// "no progress" situations. Description of the algorithm in the following paper:
+// Marcel van Kervinck's cuckoo algorithm for fast detection of "upcoming repetition"
+// situations. Description of the algorithm in the following paper:

 // https://marcelk.net/2013-04-06/paper/upcoming-rep-v2.pdf
 
 // First and second hash functions for indexing the cuckoo tables
 // https://marcelk.net/2013-04-06/paper/upcoming-rep-v2.pdf
 
 // First and second hash functions for indexing the cuckoo tables

-inline Key H1(Key h) { return h & 0x1fff; }
-inline Key H2(Key h) { return (h >> 16) & 0x1fff; }
+inline int H1(Key h) { return h & 0x1fff; }
+inline int H2(Key h) { return (h >> 16) & 0x1fff; }

 
 // Cuckoo tables with Zobrist hashes of valid reversible moves, and the moves themselves
 Key cuckoo[8192];
 
 // Cuckoo tables with Zobrist hashes of valid reversible moves, and the moves themselves
 Key cuckoo[8192];


@@ -180,7 +180,7 @@ void Position::init() {
               {
                   Move move = make_move(s1, s2);
                   Key key = Zobrist::psq[pc][s1] ^ Zobrist::psq[pc][s2] ^ Zobrist::side;
               {
                   Move move = make_move(s1, s2);
                   Key key = Zobrist::psq[pc][s1] ^ Zobrist::psq[pc][s2] ^ Zobrist::side;

-                  unsigned int i = H1(key);
+                  int i = H1(key);

                   while (true)
                   {
                       std::swap(cuckoo[i], key);
                   while (true)
                   {
                       std::swap(cuckoo[i], key);


@@ -1148,9 +1148,9 @@ bool Position::has_repeated() const {
     StateInfo* stc = st;
     while (true)
     {
     StateInfo* stc = st;
     while (true)
     {

-        int i = 4, e = std::min(stc->rule50, stc->pliesFromNull);
+        int i = 4, end = std::min(stc->rule50, stc->pliesFromNull);

 
 

-        if (e < i)
+        if (end < i)

             return false;
 
         StateInfo* stp = st->previous->previous;
             return false;
 
         StateInfo* stp = st->previous->previous;


@@ -1162,7 +1162,7 @@ bool Position::has_repeated() const {
                 return true;
 
             i += 2;
                 return true;
 
             i += 2;

-        } while (i <= e);
+        } while (i <= end);

 
         stc = stc->previous;
     }
 
         stc = stc->previous;
     }


@@ -1174,7 +1174,7 @@ bool Position::has_repeated() const {
 
 bool Position::has_game_cycle(int ply) const {
 
 
 bool Position::has_game_cycle(int ply) const {
 

-  unsigned int j;
+  int j;

 
   int end = std::min(st->rule50, st->pliesFromNull);
 
 
   int end = std::min(st->rule50, st->pliesFromNull);
 


@@ -1183,40 +1183,38 @@ bool Position::has_game_cycle(int ply) const {
 
   Key originalKey = st->key;
   StateInfo* stp = st->previous;
 
   Key originalKey = st->key;
   StateInfo* stp = st->previous;

-  Key progressKey = stp->key ^ Zobrist::side;

 
   for (int i = 3; i <= end; i += 2)
   {
 
   for (int i = 3; i <= end; i += 2)
   {

-      stp = stp->previous;
-      progressKey ^= stp->key ^ Zobrist::side;
-      stp = stp->previous;
+      stp = stp->previous->previous;

 
 

-      // "originalKey == " detects upcoming repetition, "progressKey == " detects no-progress
-      if (   originalKey == (progressKey ^ stp->key)
-          || progressKey == Zobrist::side)
+      Key moveKey = originalKey ^ stp->key;
+      if (   (j = H1(moveKey), cuckoo[j] == moveKey)
+          || (j = H2(moveKey), cuckoo[j] == moveKey))

       {
       {

-          Key moveKey = originalKey ^ stp->key;
-          if (   (j = H1(moveKey), cuckoo[j] == moveKey)
-              || (j = H2(moveKey), cuckoo[j] == moveKey))
+          Move move = cuckooMove[j];
+          Square from = from_sq(move);
+          Square to = to_sq(move);
+
+          if (!(between_bb(from, to) & pieces()))

           {
           {

-              Move m = Move(cuckooMove[j]);
-              if (!(between_bb(from_sq(m), to_sq(m)) & pieces()))
-              {
-                  if (ply > i)
-                      return true;
+              // Take care to reverse the move in the no-progress case (opponent to move)
+              if (empty(from))
+                  move = make_move(to, from);

 
 

-                  // 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 (ply > i)
+                  return true;
+
+              // 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;

               }
           }
       }
               }
           }
       }

-      progressKey ^= stp->key;

   }
   return false;
 }
   }
   return false;
 }