Use cycle detection to bound search value

A position which has a move which draws by repetition, or which could have
been reached from an earlier position in the game tree, is considered to be
at least a draw for the side to move.

Cycle detection algorithm by Marcel van Kervink:

       https://marcelk.net/2013-04-06/paper/upcoming-rep-v2.pdf

----------------------------

How does the algorithm work in practice? The algorithm is an efficient
method to detect if the side to move has a drawing move, without doing any
move generation, thus possibly giving a cheap cutoffThe most interesting
conditions are both on line 1195:

```
  if (   originalKey == (progressKey ^ stp->key)
      || progressKey == Zobrist::side)
```

This uses the position keys as a sort-of Bloom filter, to avoid the expensive
checks which follow. For "upcoming repetition" consider the opening Nf3 Nf6 Ng1.
The XOR of this position's key with the starting position gives their difference,
which can be used to look up black's repeating move (Ng8). But that look-up is
expensive, so line 1195 checks that the white pieces are on their original squares.

This is the subtlest part of the algorithm, but the basic idea in the above game
is there are 4 positions (starting position and the one after each move). An XOR
of the first pair (startpos and after Nf3) gives a key matching Nf3. An XOR of
the second pair (after Nf6 and after Ng1) gives a key matching the move Ng1. But
since the difference in each pair is the location of the white knight those keys
are "identical" (not quite because while there are 4 keys the the side to move
changed 3 times, so the keys differ by Zobrist::side). The loop containing line
1195 does this pair-wise XOR-ing.

Continuing the example, after line 1195 determines that the white pieces are
back where they started we still need to make sure the changes in the black
pieces represents a legal move. This is done by looking up the "moveKey" to
see if it corresponds to possible move, and that there are no pieces blocking
its way. There is the additional complication that, to match the behavior of
is_draw(), if the repetition is not inside the search tree then there must be
an additional repetition in the game history. Since a position can have more
than one upcoming repetition a simple count does not suffice. So there is a
search loop ending on line 1215.

On the other hand, the "no-progress' is the same thing but offset by 1 ply.
I like the concept but think it currently has minimal or negative benefit,
and I'd be happy to remove it if that would get the patch accepted. This
will not, however, save many lines of code.

-----------------------------

STC:
LLR: 2.95 (-2.94,2.94) [0.00,5.00]
Total: 36430 W: 7446 L: 7150 D: 21834
http://tests.stockfishchess.org/tests/view/5afc123f0ebc591fdf408dfc

LTC:
LLR: 2.96 (-2.94,2.94) [0.00,5.00]
Total: 12998 W: 2045 L: 1876 D: 9077
http://tests.stockfishchess.org/tests/view/5afc2c630ebc591fdf408e0c

How could we continue after the patch:

• The code in search() that checks for cycles has numerous possible variants.
  Perhaps the check need could be done in qsearch() too.

• The biggest improvement would be to get "no progress" to be of actual benefit,
  and it would be helpful understand why it (probably) isn't. Perhaps there is an
  interaction with the transposition table or the (fantastically complex) tree
  search. Perhaps this would be hard to fix, but there may be a simple oversight.

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

Bench: 4550412

diff --git a/src/position.cpp b/src/position.cpp
index 0be309ee60cac3d0ea78bcec0ad6c38237e7768b..c07e6964fac76006c874ade7e2d3423b9fdd3862 100644 (file)
--- a/src/position.cpp
+++ b/src/position.cpp
@@ -130,6 +130,19 @@ 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:
+// 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; }
+
+// Cuckoo tables with Zobrist hashes of valid reversible moves, and the moves themselves
+Key cuckoo[8192];
+Move cuckooMove[8192];
+
+
 /// Position::init() initializes at startup the various arrays used to compute
 /// hash keys.
 
@@ -157,6 +170,28 @@ void Position::init() {
 
   Zobrist::side = rng.rand<Key>();
   Zobrist::noPawns = rng.rand<Key>();
+
+  // Prepare the cuckoo tables
+  int count = 0;
+  for (Piece pc : Pieces)
+      for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1)
+          for (Square s2 = Square(s1 + 1); s2 <= SQ_H8; ++s2)
+              if (PseudoAttacks[type_of(pc)][s1] & s2)
+              {
+                  Move move = make_move(s1, s2);
+                  Key key = Zobrist::psq[pc][s1] ^ Zobrist::psq[pc][s2] ^ Zobrist::side;
+                  unsigned int i = H1(key);
+                  while (true)
+                  {
+                      std::swap(cuckoo[i], key);
+                      std::swap(cuckooMove[i], move);
+                      if (move == 0)   // Arrived at empty slot ?
+                          break;
+                      i = (i == H1(key)) ? H2(key) : H1(key); // Push victim to alternative slot
+                  }
+                  count++;
+             }
+  assert(count == 3668);
 }
 
 
@@ -1134,6 +1169,59 @@ bool Position::has_repeated() const {
 }
 
 
+/// Position::has_game_cycle() tests if the position has a move which draws by repetition,
+/// or an earlier position has a move that directly reaches the current position.
+
+bool Position::has_game_cycle(int ply) const {
+
+  unsigned int j;
+
+  int end = std::min(st->rule50, st->pliesFromNull);
+
+  if (end < 3)
+    return false;
+
+  Key originalKey = st->key;
+  StateInfo* stp = st->previous;
+  Key progressKey = stp->key ^ Zobrist::side;
+
+  for (int i = 3; i <= end; i += 2)
+  {
+      stp = stp->previous;
+      progressKey ^= stp->key ^ Zobrist::side;
+      stp = stp->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))
+          {
+              Move m = Move(cuckooMove[j]);
+              if (!(between_bb(from_sq(m), to_sq(m)) & pieces()))
+              {
+                  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;
+}
+
+
 /// Position::flip() flips position with the white and black sides reversed. This
 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
 

diff --git a/src/position.h b/src/position.h
index 0c8f7972d7f599b614de8336a3847b152faaa20c..06000e0ff264abfa7f993ce2fc8b248f1b24e58b 100644 (file)
--- a/src/position.h
+++ b/src/position.h
@@ -152,6 +152,7 @@ public:
   bool is_chess960() const;
   Thread* this_thread() const;
   bool is_draw(int ply) const;
+  bool has_game_cycle(int ply) const;
   bool has_repeated() const;
   int rule50_count() const;
   Score psq_score() const;

diff --git a/src/search.cpp b/src/search.cpp
index 1a4f654d10539a998cc248a5fa5c0c2d2f0eade9..025c1141c97546e6e98693877fad9afff26336d5 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -577,6 +577,17 @@ namespace {
         beta = std::min(mate_in(ss->ply+1), beta);
         if (alpha >= beta)
             return alpha;
+
+        // Check if there exists a move which draws by repetition, or an alternative
+        // earlier move to this position.
+        if (   pos.rule50_count() >= 3
+            && alpha < VALUE_DRAW
+            && pos.has_game_cycle(ss->ply))
+        {
+            alpha = VALUE_DRAW;
+            if (alpha >= beta)
+                return alpha;
+        }
     }
 
     assert(0 <= ss->ply && ss->ply < MAX_PLY);