100% accurate PV display

This gives SF accurate PVs, such that the evaluation of the leaf node in
the PV matches the score backed up to the root (99% of the time.
q-search will use the value stored in the hash table instead of the eval
value sometimes).

One drawback is that fail-high/low only get a minimal 2 move PV.

It doesn't add any additional overhead to the non-PV codepath except an
extra eight bytes to the SearchStack structure in multi-threaded
searches.

A core part of this is not pruning based on TT score in PV nodes. This
was measured as not being a regression at multiple TCs, except for one
exception, fast TC with huge hash, which is not realistic for longer
searches.

STC - 1 thread, 128 mb hash
ELO: 1.42 +-3.1 (95%) LOS: 81.9%
Total: 20000 W: 4078 L: 3996 D: 11926

STC - 3 thread, 128 mb hash
ELO: -3.60 +-2.9 (95%) LOS: 0.8%
Total: 20000 W: 3575 L: 3782 D: 12643

STC - 3 thread, 8 mb hash
ELO: 0.12 +-2.9 (95%) LOS: 53.3%
Total: 20000 W: 3654 L: 3647 D: 12699

LTC - 3 thread, 32mb hash
ELO: 2.29 +-2.0 (95%) LOS: 98.8%
Total: 35740 W: 5618 L: 5382 D: 24740

Bench: 6984058

Resolves #102

diff --git a/src/search.cpp b/src/search.cpp
index 63481d367e260f1292978aee0fc96cd61ea4d926..376705d1d4118e97ed3af675c5c243f5629dc0b5 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -394,6 +394,7 @@ namespace {
     assert(PvNode || (alpha == beta - 1));
     assert(depth > DEPTH_ZERO);
 
     assert(PvNode || (alpha == beta - 1));
     assert(depth > DEPTH_ZERO);
 

+    PVEntry pv;

     Move quietsSearched[64];
     StateInfo st;
     const TTEntry *tte;
     Move quietsSearched[64];
     StateInfo st;
     const TTEntry *tte;


@@ -469,13 +470,12 @@ namespace {
     // a fail high/low. The biggest advantage to probing at PV nodes is to have a
     // smooth experience in analysis mode. We don't probe at Root nodes otherwise
     // we should also update RootMoveList to avoid bogus output.
     // a fail high/low. The biggest advantage to probing at PV nodes is to have a
     // smooth experience in analysis mode. We don't probe at Root nodes otherwise
     // we should also update RootMoveList to avoid bogus output.

-    if (   !RootNode
+    if (   !PvNode

         && tte
         && tte->depth() >= depth
         && ttValue != VALUE_NONE // Only in case of TT access race
         && tte
         && tte->depth() >= depth
         && ttValue != VALUE_NONE // Only in case of TT access race

-        && (           PvNode ?  tte->bound() == BOUND_EXACT
-            : ttValue >= beta ? (tte->bound() &  BOUND_LOWER)
-                              : (tte->bound() &  BOUND_UPPER)))
+        && (ttValue >= beta ? (tte->bound() & BOUND_LOWER)
+                            : (tte->bound() & BOUND_UPPER)))

     {
         ss->currentMove = ttMove; // Can be MOVE_NONE
 
     {
         ss->currentMove = ttMove; // Can be MOVE_NONE
 


@@ -699,6 +699,9 @@ moves_loop: // When in check and at SpNode search starts from here
                         << " currmovenumber " << moveCount + PVIdx << sync_endl;
       }
 
                         << " currmovenumber " << moveCount + PVIdx << sync_endl;
       }
 

+      if (PvNode)
+          (ss+1)->pv = NULL;
+

       ext = DEPTH_ZERO;
       captureOrPromotion = pos.capture_or_promotion(move);
 
       ext = DEPTH_ZERO;
       captureOrPromotion = pos.capture_or_promotion(move);
 


@@ -862,11 +865,14 @@ moves_loop: // When in check and at SpNode search starts from here
       // For PV nodes only, do a full PV search on the first move or after a fail
       // high (in the latter case search only if value < beta), otherwise let the
       // parent node fail low with value <= alpha and to try another move.
       // For PV nodes only, do a full PV search on the first move or after a fail
       // high (in the latter case search only if value < beta), otherwise let the
       // parent node fail low with value <= alpha and to try another move.

-      if (PvNode && (moveCount == 1 || (value > alpha && (RootNode || value < beta))))
+      if (PvNode && (moveCount == 1 || (value > alpha && (RootNode || value < beta)))) {
+          pv.pv[0] = MOVE_NONE;
+          (ss+1)->pv = &pv;

           value = newDepth <   ONE_PLY ?
                             givesCheck ? -qsearch<PV,  true>(pos, ss+1, -beta, -alpha, DEPTH_ZERO)
                                        : -qsearch<PV, false>(pos, ss+1, -beta, -alpha, DEPTH_ZERO)
                                        : - search<PV, false>(pos, ss+1, -beta, -alpha, newDepth, false);
           value = newDepth <   ONE_PLY ?
                             givesCheck ? -qsearch<PV,  true>(pos, ss+1, -beta, -alpha, DEPTH_ZERO)
                                        : -qsearch<PV, false>(pos, ss+1, -beta, -alpha, DEPTH_ZERO)
                                        : - search<PV, false>(pos, ss+1, -beta, -alpha, newDepth, false);

+      }

       // Step 17. Undo move
       pos.undo_move(move);
 
       // Step 17. Undo move
       pos.undo_move(move);
 


@@ -894,7 +900,9 @@ moves_loop: // When in check and at SpNode search starts from here
           if (moveCount == 1 || value > alpha)
           {
               rm.score = value;
           if (moveCount == 1 || value > alpha)
           {
               rm.score = value;

-              rm.extract_pv_from_tt(pos);
+              rm.pv.resize(1);
+              for (int i = 0; (ss+1)->pv && i < MAX_PLY && (ss+1)->pv->pv[i] != MOVE_NONE; ++i)
+                  rm.pv.push_back((ss+1)->pv->pv[i]);

 
               // We record how often the best move has been changed in each
               // iteration. This information is used for time management: When
 
               // We record how often the best move has been changed in each
               // iteration. This information is used for time management: When


@@ -917,6 +925,12 @@ moves_loop: // When in check and at SpNode search starts from here
           {
               bestMove = SpNode ? splitPoint->bestMove = move : move;
 
           {
               bestMove = SpNode ? splitPoint->bestMove = move : move;
 

+              if (NT == PV) {
+                  ss->pv->update(move, (ss+1)->pv);
+                  if (SpNode)
+                      splitPoint->ss->pv->update(move, (ss+1)->pv);
+              }
+

               if (PvNode && value < beta) // Update alpha! Always alpha < beta
                   alpha = SpNode ? splitPoint->alpha = value : value;
               else
               if (PvNode && value < beta) // Update alpha! Always alpha < beta
                   alpha = SpNode ? splitPoint->alpha = value : value;
               else


@@ -1001,6 +1015,7 @@ moves_loop: // When in check and at SpNode search starts from here
     assert(PvNode || (alpha == beta - 1));
     assert(depth <= DEPTH_ZERO);
 
     assert(PvNode || (alpha == beta - 1));
     assert(depth <= DEPTH_ZERO);
 

+    PVEntry pv;

     StateInfo st;
     const TTEntry* tte;
     Key posKey;
     StateInfo st;
     const TTEntry* tte;
     Key posKey;


@@ -1009,10 +1024,14 @@ moves_loop: // When in check and at SpNode search starts from here
     bool givesCheck, evasionPrunable;
     Depth ttDepth;
 
     bool givesCheck, evasionPrunable;
     Depth ttDepth;
 

-    // To flag BOUND_EXACT a node with eval above alpha and no available moves
-    if (PvNode)
+    if (PvNode) {
+        // To flag BOUND_EXACT a node with eval above alpha and no available moves

         oldAlpha = alpha;
 
         oldAlpha = alpha;
 

+        (ss+1)->pv = &pv;
+        ss->pv->pv[0] = MOVE_NONE;
+    }
+

     ss->currentMove = bestMove = MOVE_NONE;
     ss->ply = (ss-1)->ply + 1;
 
     ss->currentMove = bestMove = MOVE_NONE;
     ss->ply = (ss-1)->ply + 1;
 


@@ -1034,12 +1053,12 @@ moves_loop: // When in check and at SpNode search starts from here
     ttMove = tte ? tte->move() : MOVE_NONE;
     ttValue = tte ? value_from_tt(tte->value(),ss->ply) : VALUE_NONE;
 
     ttMove = tte ? tte->move() : MOVE_NONE;
     ttValue = tte ? value_from_tt(tte->value(),ss->ply) : VALUE_NONE;
 

-    if (   tte
+    if (  !PvNode 
+        && tte

         && tte->depth() >= ttDepth
         && ttValue != VALUE_NONE // Only in case of TT access race
         && tte->depth() >= ttDepth
         && ttValue != VALUE_NONE // Only in case of TT access race

-        && (           PvNode ?  tte->bound() == BOUND_EXACT
-            : ttValue >= beta ? (tte->bound() &  BOUND_LOWER)
-                              : (tte->bound() &  BOUND_UPPER)))
+        && (ttValue >= beta ? (tte->bound() &  BOUND_LOWER)
+                            : (tte->bound() &  BOUND_UPPER)))

     {
         ss->currentMove = ttMove; // Can be MOVE_NONE
         return ttValue;
     {
         ss->currentMove = ttMove; // Can be MOVE_NONE
         return ttValue;


@@ -1161,6 +1180,9 @@ moves_loop: // When in check and at SpNode search starts from here
 
           if (value > alpha)
           {
 
           if (value > alpha)
           {

+              if (PvNode)
+                  ss->pv->update(move, &pv);
+

               if (PvNode && value < beta) // Update alpha here! Always alpha < beta
               {
                   alpha = value;
               if (PvNode && value < beta) // Update alpha here! Always alpha < beta
               {
                   alpha = value;


@@ -1331,7 +1353,7 @@ moves_loop: // When in check and at SpNode search starts from here
            << " time "      << elapsed
            << " pv";
 
            << " time "      << elapsed
            << " pv";
 

-        for (size_t j = 0; RootMoves[i].pv[j] != MOVE_NONE; ++j)
+        for (size_t j = 0; j < RootMoves[i].pv.size(); ++j)

             ss << " " << UCI::format_move(RootMoves[i].pv[j], pos.is_chess960());
     }
 
             ss << " " << UCI::format_move(RootMoves[i].pv[j], pos.is_chess960());
     }
 


@@ -1341,43 +1363,6 @@ moves_loop: // When in check and at SpNode search starts from here
 } // namespace
 
 
 } // namespace
 
 

-/// RootMove::extract_pv_from_tt() builds a PV by adding moves from the TT table.
-/// We also consider both failing high nodes and BOUND_EXACT nodes here to
-/// ensure that we have a ponder move even when we fail high at root. This
-/// results in a long PV to print that is important for position analysis.
-
-void RootMove::extract_pv_from_tt(Position& pos) {
-
-  StateInfo state[MAX_PLY], *st = state;
-  const TTEntry* tte;
-  int ply = 1;    // At root ply is 1...
-  Move m = pv[0]; // ...instead pv[] array starts from 0
-  Value expectedScore = score;
-
-  pv.clear();
-
-  do {
-      pv.push_back(m);
-
-      assert(MoveList<LEGAL>(pos).contains(pv[ply - 1]));
-
-      pos.do_move(pv[ply++ - 1], *st++);
-      tte = TT.probe(pos.key());
-      expectedScore = -expectedScore;
-
-  } while (   tte
-           && expectedScore == value_from_tt(tte->value(), ply)
-           && pos.pseudo_legal(m = tte->move()) // Local copy, TT could change
-           && pos.legal(m, pos.pinned_pieces(pos.side_to_move()))
-           && ply < MAX_PLY
-           && (!pos.is_draw() || ply <= 2));
-
-  pv.push_back(MOVE_NONE); // Must be zero-terminating
-
-  while (--ply) pos.undo_move(pv[ply - 1]);
-}
-
-

 /// RootMove::insert_pv_in_tt() is called at the end of a search iteration, and
 /// inserts the PV back into the TT. This makes sure the old PV moves are searched
 /// first, even if the old TT entries have been overwritten.
 /// RootMove::insert_pv_in_tt() is called at the end of a search iteration, and
 /// inserts the PV back into the TT. This makes sure the old PV moves are searched
 /// first, even if the old TT entries have been overwritten.


@@ -1386,19 +1371,17 @@ void RootMove::insert_pv_in_tt(Position& pos) {
 
   StateInfo state[MAX_PLY], *st = state;
   const TTEntry* tte;
 
   StateInfo state[MAX_PLY], *st = state;
   const TTEntry* tte;

-  int idx = 0; // Ply starts from 1, we need to start from 0
+  int idx = 0;

 
 

-  do {
+  for (; idx < int(pv.size()); ++idx) {

       tte = TT.probe(pos.key());
 
       if (!tte || tte->move() != pv[idx]) // Don't overwrite correct entries
           TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[idx], VALUE_NONE);
 
       assert(MoveList<LEGAL>(pos).contains(pv[idx]));
       tte = TT.probe(pos.key());
 
       if (!tte || tte->move() != pv[idx]) // Don't overwrite correct entries
           TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[idx], VALUE_NONE);
 
       assert(MoveList<LEGAL>(pos).contains(pv[idx]));

-
-      pos.do_move(pv[idx++], *st++);
-
-  } while (pv[idx] != MOVE_NONE);
+      pos.do_move(pv[idx], *st++);
+  }

 
   while (idx) pos.undo_move(pv[--idx]);
 }
 
   while (idx) pos.undo_move(pv[--idx]);
 }

diff --git a/src/search.h b/src/search.h
index 2a943dd9ede78723d3063eb9597adf419f079b3e..afa12b3a4ee6b56104918178aeee4bdd50e6845a 100644 (file)
--- a/src/search.h
+++ b/src/search.h
@@ -32,12 +32,26 @@ struct SplitPoint;
 
 namespace Search {
 
 
 namespace Search {
 

+struct PVEntry {
+  Move pv[MAX_PLY+1];
+
+  void update(Move move, PVEntry* child) {
+      pv[0] = move;
+
+      int i = 1;
+      for (; child && i < MAX_PLY && child->pv[i - 1] != MOVE_NONE; ++i)
+          pv[i] = child->pv[i - 1];
+      pv[i] = MOVE_NONE;
+  } 
+};
+

 /// The Stack struct keeps track of the information we need to remember from
 /// nodes shallower and deeper in the tree during the search. Each search thread
 /// has its own array of Stack objects, indexed by the current ply.
 
 struct Stack {
   SplitPoint* splitPoint;
 /// The Stack struct keeps track of the information we need to remember from
 /// nodes shallower and deeper in the tree during the search. Each search thread
 /// has its own array of Stack objects, indexed by the current ply.
 
 struct Stack {
   SplitPoint* splitPoint;

+  PVEntry* pv;

   int ply;
   Move currentMove;
   Move ttMove;
   int ply;
   Move currentMove;
   Move ttMove;


@@ -62,7 +76,6 @@ struct RootMove {
   bool operator<(const RootMove& m) const { return score > m.score; } // Ascending sort
   bool operator==(const Move& m) const { return pv[0] == m; }
 
   bool operator<(const RootMove& m) const { return score > m.score; } // Ascending sort
   bool operator==(const Move& m) const { return pv[0] == m; }
 

-  void extract_pv_from_tt(Position& pos);

   void insert_pv_in_tt(Position& pos);
 
   Value score;
   void insert_pv_in_tt(Position& pos);
 
   Value score;

diff --git a/src/thread.cpp b/src/thread.cpp
index bd20361daff658cd31a9e955fe585d3473a1c7e4..4fc0953eac6ec7145ba8ade4e16b228db6d70e0f 100644 (file)
--- a/src/thread.cpp
+++ b/src/thread.cpp
@@ -255,7 +255,7 @@ Thread* ThreadPool::available_slave(const Thread* master) const {
 // leave their idle loops and call search(). When all threads have returned from
 // search() then split() returns.
 
 // leave their idle loops and call search(). When all threads have returned from
 // search() then split() returns.
 

-void Thread::split(Position& pos, const Stack* ss, Value alpha, Value beta, Value* bestValue,
+void Thread::split(Position& pos, Stack* ss, Value alpha, Value beta, Value* bestValue,

                    Move* bestMove, Depth depth, int moveCount,
                    MovePicker* movePicker, int nodeType, bool cutNode) {
 
                    Move* bestMove, Depth depth, int moveCount,
                    MovePicker* movePicker, int nodeType, bool cutNode) {
 

diff --git a/src/thread.h b/src/thread.h
index 26aed392fd34bf1977eb7f1edf7366ffbad67787..8a512c96dd22f5fa84f04c1733c45ccf4fb6b38c 100644 (file)
--- a/src/thread.h
+++ b/src/thread.h
@@ -63,7 +63,7 @@ struct SplitPoint {
 
   // Const data after split point has been setup
   const Position* pos;
 
   // Const data after split point has been setup
   const Position* pos;

-  const Search::Stack* ss;
+  Search::Stack* ss;

   Thread* masterThread;
   Depth depth;
   Value beta;
   Thread* masterThread;
   Depth depth;
   Value beta;


@@ -117,7 +117,7 @@ struct Thread : public ThreadBase {
   bool cutoff_occurred() const;
   bool available_to(const Thread* master) const;
 
   bool cutoff_occurred() const;
   bool available_to(const Thread* master) const;
 

-  void split(Position& pos, const Search::Stack* ss, Value alpha, Value beta, Value* bestValue, Move* bestMove,
+  void split(Position& pos, Search::Stack* ss, Value alpha, Value beta, Value* bestValue, Move* bestMove,

              Depth depth, int moveCount, MovePicker* movePicker, int nodeType, bool cutNode);
 
   SplitPoint splitPoints[MAX_SPLITPOINTS_PER_THREAD];
              Depth depth, int moveCount, MovePicker* movePicker, int nodeType, bool cutNode);
 
   SplitPoint splitPoints[MAX_SPLITPOINTS_PER_THREAD];