Remove shuffle extension
authorMichaelB7 <michaelbyrne1978@gmail.com>
Sun, 3 Nov 2019 00:04:05 +0000 (20:04 -0400)
committerStéphane Nicolet <cassio@free.fr>
Mon, 4 Nov 2019 23:01:49 +0000 (00:01 +0100)
It was noted in an earlier patch that all of the positions below needed the
Shuffle Detection idea to be solved:

3r4/p3r1pk/PpBb1pRp/1KpPpP1P/2P1P1R1/8/8/8 b - - 32 86
8/8/8/1k6/2p5/p1K5/N2B2r1/8 b - - 59 109
1r4k1/1r1bq3/4p1p1/3pPpPp/pNpN1P1P/P1PnQ3/1PK5/1R3R2 b - - 13 82
5k2/3b4/5p2/p1p1pPp1/PpPpP1Pp/1P1P3P/8/3R1K2 w - - 20 1

But Stockfish has envolved a bit since the Shuffle Detection patch introduction,
and this patch proves Stockfish is able to solves these drawn positions without it,
even on single core without EGTB.

Passed STC
LLR: 2.96 (-2.94,2.94) [-3.00,1.00]
Total: 14231 W: 3114 L: 2978 D: 8139
http://tests.stockfishchess.org/tests/view/5dbe1a610ebc5925b64f09d9

Passed LTC
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 42781 W: 6917 L: 6831 D: 29033
http://tests.stockfishchess.org/tests/view/5dbe24c20ebc5925b64f0a7a

Passed VLTC
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 32556 W: 4573 L: 4469 D: 23514
http://tests.stockfishchess.org/tests/view/5dbec3830ebc5925b64f11aa

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

Bench: 4362323

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

Example of search by Michael Byrne for the FEN position:
q1B5/1P1q4/8/8/8/6R1/8/1K1k4 w - - 0 1

This position is win for white and the only moves that wins is Rg1 - all other moves
either draw or lose. With single core and 1024M hash, it is solved without shuffle
detection in 38 seconds on my machine (with no EGTB). This was the position that was
locked in a loop in the initial shuffle detection patch!

```
dep score nodes time (not shown:  tbhits knps seldep)
 50 +1.71  298.9M 2:43.63 Rg1+ Kd2 Rg2+ Kc3 Rc2+ Kb3 Rb2+ Kc3 Bxd7 Qf8 Ba4 Qb8 Bd1 Kd4 Rb5 Kc4 Be2+ Kc3 Rb6 Kd4 Bf3 Ke5 Kb2 Kf4 Bd1 Qe5+ Kb1 Qe4+ Ka2 Qd5+ Rb3 Qd2+ Ka3 Qc1+ Kb4 Qc7 Ka4 Qb8 Rb6 Ke5 Kb3 Qg8+ Kb4 Qf8+ Ka5 Qb8 Bb3 Kd4 Kb4 Qf8+ Ka4 Qb8 Ka5 K
<snip>
 49 +1.68  288.5M 2:38.35 Rg1+ Kd2 Rg2+ Kc3 Rc2+ Kb3 Rb2+ Kc3 Bxd7 Qf8 Ba4 Qb8 Bd1 Kd4 Rb5 Kc4 Be2+ Kc3 Rb6 Kd4 Bf3 Ke5 Kb2 Kf4 Bd1 Qe5+ Kb1 Qe4+ Ka2 Qd5+ Rb3 Qd2+ Ka3 Qc1+ Kb4 Qc7 Ka4 Qb8 Rb6 Ke5 Kb3 Qg8+ Kb4 Qf8+ Ka5 Qb8 Bb3 Kd4 Kb4 Ke3 Be6 Ke4 Bc4 Ke
<snip>
 48 +1.78  228.5M 2:01.93 Rg1+ Kd2 Rg2+ Kc3 Rc2+ Kb3 Rb2+ Kc3 Bxd7 Qf8 Ba4 Qb8 Bd1 Kd4 Rb5 Kc4 Be2+ Kc3 Rb6 Kd4 Bf3 Ke5 Kb2 Kf4 Bd1 Qe5+ Kb1 Qe4+ Ka2 Qd5+ Rb3 Qd2+ Ka3 Qa5+ Kb2 Qe5+ Ka2 Qb8 Rb5 Ke3 Kb1 Ke4 Bb3 Kf4 Be6 Ke3 Rb4 Kd3 Kb2 Ke3 Bd5 Qe5+ Kc2 Qh
<snip>
 46 +1.49  198.4M 1:44.89 Rg1+ Kd2 Rg2+ Kc3 Rc2+ Kb3 Rb2+ Kc3 Bxd7 Qf8 Ba4 Qb8 Bd1 Kd4 Rb5 Kc4 Be2+ Kc3 Rb6 Kd4 Bf3 Ke5 Kb2 Kf4 Bd1 Qe5+ Kb1 Qe4+ Ka2 Qd5+ Rb3 Qd2+ Ka3 Qc1+ Kb4 Qc7 Ka4 Qb8 Rb6 Qe8+ Rb5 Qb8 Bc2 Qa7+ Kb3 Qe3+ Kc4 Qe6+ Kb4 Qd6+ Kb3 Qb8 Rb4
<snip>
 45 +1.45  154.5M 1:20.75 Rg1+ Kd2 Rg2+ Kc3 Rc2+ Kb3 Rb2+ Kc3 Bxd7 Qf8 Ba4 Qb8 Bd1 Kd4 Rb5 Kc4 Be2+ Kc3 Rb6 Kd4 Bf3 Ke3 Bg2 Kd4 Rb5 Kc4 Bf1+ Kd4 Kb2 Qh2+ Kb3 Qg3+ Ka4 Qb8 Be2 Ke3 Bc4 Kf4 Kb4 Qd6+ Kc3 Qb8 Kc2 Ke4 Be6 Qh2+ Kb3 Qg3+ Ka4 Qb8 Bb3 Kd4 Bd5 Ke3
<snip>
 44 +1.36  141.9M 1:14.40 Rg1+ Kd2 Rg2+ Kc3 Rc2+ Kb3 Rb2+ Kc3 Bxd7 Qf8 Ba4 Qb8 Bd1 Qd6 Rc2+ Kd3 Be2+ Ke3 Rb2 Qb8 Bd1 Ke4 Rb5 Kd4 Bf3 Kc4 Be2+ Kc3 Rb6 Kd2 Bc4 Kc3 Bd5 Kd4 Bg2 Ke5 Kb2 Kd4 Rb5 Kc4 Bf1+ Kd4 Be2 Ke4 Bc4 Qh2+ Kb3 Qg3+ Ka4 Qb8 Bd5+ Kd4 Be6 Ke4
<snip>
 43 +1.36  134.1M 1:10.46 Rg1+ Kd2 Rg2+ Kc3 Rc2+ Kb3 Rb2+ Kc3 Bxd7 Qf8 Ba4 Qb8 Bd1 Qd6 Rc2+ Kd3 Be2+ Ke3 Rb2 Qb8 Bd1 Ke4 Rb5 Kd4 Bf3 Kc4 Be2+ Kc3 Rb6 Kd2 Bc4 Kc3 Be6 Kd4 Rb5 Kc3 Bf7 Kd4 Kb2 Ke4 Kb3 Kf4 Kc3 Ke4 Kb2 Qh2+ Kb3 Qg3+ Ka4 Qb8 Rb4+ Ke5 Rb6 Kf4
<snip>
 42 +1.36  118.7M 1:01.60 Rg1+ Kd2 Rg2+ Kc3 Rc2+ Kb3 Rb2+ Kc3 Bxd7 Qf8 Ba4 Qb8 Bd1 Qd6 Rc2+ Kd3 Be2+ Ke3 Rb2 Qb8 Bd1 Ke4 Rb5 Kd4 Bf3 Kc4 Be2+ Kc3 Rb6 Kd2 Bc4 Kc3 Be6 Kd4 Rb5 Kc3 Bf7 Kd4 Kb2 Ke4 Bc4 Qh2+ Kb3 Qg3+ Ka4 Qb8 Bd5+ Kd4 Bb3 Qa7+ Kb4 Qb8 Bc4 Ke4
<snip>
 41 +1.38  110.3M 0:56.80 Rg1+ Kd2 Rg2+ Kc3 Rc2+ Kb3 Rb2+ Kc3 Bxd7 Qf8 Ba4 Qb8 Bd1 Qd6 Rc2+ Kd3 Be2+ Ke3 Rb2 Qb8 Bd1 Ke4 Rb5 Kd4 Bf3 Kc4 Be2+ Kc3 Rb6 Kd2 Bc4 Kc3 Be6 Kd4 Rb5 Kc3 Bd5 Kd4 Ba2 Ke4 Be6 Kd4 Kb2 Qh2+ Kb3 Qb8 Bc4 Ke3 Kc3 Qh8+ Kb4 Qb2+ Ka4 Qa1+
 <snip>
 39 +1.25  87.3M   0:44.48 Rg1+ Kd2 Rg2+ Kc3 Rc2+ Kb3 Rb2+ Kc3 Bxd7 Qf8 Ba4 Qb8 Bd1 Kd4 Rb5 Kc4 Be2+ Kc3 Rb6 Kd4 Bf3 Ke5 Kb2 Kf4 Bd1 Kg5 Kb1 Kf5 Bb3 Ke5 Kb2 Kd4 Rb5 Qh2+ Bc2 Qb8 Bd1 Kc4 Be2+ Kd4 Kc2 Ke3 Bd1 Kd4 Kb3 Qg3+ Ka4 Qb8 Bb3 Kc3 Rb6 Kd4 Kb5 Ke5 K
 38 +1.25  82.0M   0:41.90 Rg1+ Kd2 Rg2+ Kc3 Rc2+ Kb3 Rb2+ Kc3 Bxd7 Qf8 Ba4 Qb8 Bd1 Kd4 Rb5 Kc4 Be2+ Kc3 Rb6 Kd4 Bf3 Ke5 Kb2 Kf4 Bd1 Kg5 Kb1 Kf5 Bb3 Ke5 Kb2 Kd4 Rb5 Qh2+ Bc2 Qb8 Kb3 Qg3+ Ka4 Qb8 Bb3 Kc3 Rb6 Kd4 Kb5 Ke5 Kb4 Kd4 Be6 Kd3 Bd5 Kd4 Bf3 Ke5 Be
<snip>
 37 +0.13  79.3M   0:40.44 Rg1+ Kd2 Rg2+ Kc3 Rc2+ Kb3 Rb2+ Kc3 Bxd7 Qf8 Ba4 Qb8 Bd1 Kc4 Bf3 Kd4 Rb5 Kc4 Rb6 Kd4 Rb2 Ke5 Rb3 Kd6 Rb5 Ke6 Rb4 Kd6 Kc2 Kc5 Kb3 Kd6 Be4 Ke7 Kc3 Qc7+ Kd3 Qg3+ Kc2 Qf2+ Kb3 Qe3+ Ka2 Qa7+ Kb2 Qb8 Kb3 Kd6 Bf3 Qg8+ Ka3 Kc7 b8=R Qx
 37 +0.67! 78.3M   0:39.90 Rg1+!
 37 +0.47! 77.0M   0:39.18 Rg1+!
 37 +0.32! 76.8M   0:39.11 Rg1+!
 37 +0.23! 76.8M   0:39.07 Rg1+!
 36 +0.57! 76.1M   0:38.72 Rg1+!
 36 +0.37! 75.8M   0:38.59 Rg1+!
 36 +0.23! 75.7M   0:38.51 Rg1+!
 36 +0.13! 75.6M   0:38.49 Rg1+!
 35 +0.03? 58.0M   0:29.84 bxa8=Q Qb5+?
```

src/search.cpp
src/thread.cpp
src/thread.h

index b571cdf1787204e6c3e7c919da7c782de33439d4..4b90ab1c973fc7fd60fdca3da67c4bada26648d8 100644 (file)
@@ -999,13 +999,6 @@ moves_loop: // When in check, search starts from here
                && (pos.is_discovery_check_on_king(~us, move) || pos.see_ge(move)))
           extension = 1;
 
-      // Shuffle extension
-      else if (   PvNode
-               && pos.rule50_count() > 18
-               && depth < 3
-               && ++thisThread->shuffleExts < thisThread->nodes.load(std::memory_order_relaxed) / 4)  // To avoid too many extensions
-          extension = 1;
-
       // Passed pawn extension
       else if (   move == ss->killers[0]
                && pos.advanced_pawn_push(move)
index 680cd3adb8c3dc52bf87c9225f2a08db33e65cd7..6eb00d63a649b463d6dc1edea86ee3fe51f6b72a 100644 (file)
@@ -207,7 +207,7 @@ void ThreadPool::start_thinking(Position& pos, StateListPtr& states,
 
   for (Thread* th : *this)
   {
-      th->shuffleExts = th->nodes = th->tbHits = th->nmpMinPly = 0;
+      th->nodes = th->tbHits = th->nmpMinPly = 0;
       th->rootDepth = th->completedDepth = 0;
       th->rootMoves = rootMoves;
       th->rootPos.set(pos.fen(), pos.is_chess960(), &setupStates->back(), th);
index 0517afc5d149d6f0318f0f44a611d35569fb67f6..087ed3820fd217fd0af42eed4fdf62545d0df5ff 100644 (file)
@@ -60,7 +60,7 @@ public:
 
   Pawns::Table pawnsTable;
   Material::Table materialTable;
-  size_t pvIdx, pvLast, shuffleExts;
+  size_t pvIdx, pvLast;
   int selDepth, nmpMinPly;
   Color nmpColor;
   std::atomic<uint64_t> nodes, tbHits, bestMoveChanges;