From 4739037f967ac3c818907e89cc88c7b97021d027 Mon Sep 17 00:00:00 2001 From: Gary Linscott Date: Wed, 12 Nov 2014 16:13:55 -0500 Subject: [PATCH] 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 --- src/search.cpp | 95 +++++++++++++++++++++----------------------------- src/search.h | 15 +++++++- src/thread.cpp | 2 +- src/thread.h | 4 +-- 4 files changed, 56 insertions(+), 60 deletions(-) diff --git a/src/search.cpp b/src/search.cpp index 63481d36..376705d1 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -394,6 +394,7 @@ namespace { assert(PvNode || (alpha == beta - 1)); assert(depth > DEPTH_ZERO); + PVEntry pv; 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. - if ( !RootNode + if ( !PvNode && 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 @@ -699,6 +699,9 @@ moves_loop: // When in check and at SpNode search starts from here << " currmovenumber " << moveCount + PVIdx << sync_endl; } + if (PvNode) + (ss+1)->pv = NULL; + 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. - 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(pos, ss+1, -beta, -alpha, DEPTH_ZERO) : -qsearch(pos, ss+1, -beta, -alpha, DEPTH_ZERO) : - search(pos, ss+1, -beta, -alpha, newDepth, false); + } // 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; - 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 @@ -917,6 +925,12 @@ moves_loop: // When in check and at SpNode search starts from here { 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 @@ -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); + PVEntry pv; 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; - // 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; + (ss+1)->pv = &pv; + ss->pv->pv[0] = MOVE_NONE; + } + 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; - if ( tte + if ( !PvNode + && tte && 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; @@ -1161,6 +1180,9 @@ moves_loop: // When in check and at SpNode search starts from here if (value > alpha) { + if (PvNode) + ss->pv->update(move, &pv); + 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"; - 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()); } @@ -1341,43 +1363,6 @@ moves_loop: // When in check and at SpNode search starts from here } // 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(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. @@ -1386,19 +1371,17 @@ void RootMove::insert_pv_in_tt(Position& pos) { 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(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]); } diff --git a/src/search.h b/src/search.h index 2a943dd9..afa12b3a 100644 --- a/src/search.h +++ b/src/search.h @@ -32,12 +32,26 @@ struct SplitPoint; 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; + PVEntry* pv; 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; } - void extract_pv_from_tt(Position& pos); void insert_pv_in_tt(Position& pos); Value score; diff --git a/src/thread.cpp b/src/thread.cpp index bd20361d..4fc0953e 100644 --- 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. -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) { diff --git a/src/thread.h b/src/thread.h index 26aed392..8a512c96 100644 --- 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 Search::Stack* ss; + Search::Stack* ss; 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; - 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]; -- 2.39.2