X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=9f2786230477737160147feba907bb5fed0ed02b;hp=63481d367e260f1292978aee0fc96cd61ea4d926;hb=7ad59d9ac9cbeae8b95843a720a53c99bb1f0d3b;hpb=b777b17f6ff7fe9670d864cf31106fdefdca3001 diff --git a/src/search.cpp b/src/search.cpp index 63481d36..9f278623 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -87,6 +87,7 @@ namespace { void id_loop(Position& pos); Value value_to_tt(Value v, int ply); Value value_from_tt(Value v, int ply); + void update_pv(Move* pv, Move move, Move* childPv); void update_stats(const Position& pos, Stack* ss, Move move, Depth depth, Move* quiets, int quietsCnt); string uci_pv(const Position& pos, Depth depth, Value alpha, Value beta); @@ -255,7 +256,7 @@ namespace { multiPV = std::max(multiPV, skill.candidates_size()); // Iterative deepening loop until requested to stop or target depth reached - while (++depth < MAX_PLY && !Signals.stop && (!Limits.depth || depth <= Limits.depth)) + while (++depth < DEPTH_MAX && !Signals.stop && (!Limits.depth || depth <= Limits.depth)) { // Age out PV variability metric BestMoveChanges *= 0.5; @@ -394,7 +395,7 @@ namespace { assert(PvNode || (alpha == beta - 1)); assert(depth > DEPTH_ZERO); - Move quietsSearched[64]; + Move pv[MAX_PLY+1], quietsSearched[64]; StateInfo st; const TTEntry *tte; SplitPoint* splitPoint; @@ -465,17 +466,13 @@ namespace { ss->ttMove = ttMove = RootNode ? RootMoves[PVIdx].pv[0] : tte ? tte->move() : MOVE_NONE; ttValue = tte ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; - // At PV nodes we check for exact scores, whilst at non-PV nodes we check for - // 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 + // At non-PV nodes we check for a fail high/low. We don't probe at PV nodes + 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 +696,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); @@ -863,10 +863,16 @@ moves_loop: // When in check and at SpNode search starts from here // 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)))) + { + (ss+1)->pv = pv; + (ss+1)->pv[0] = MOVE_NONE; + 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,12 @@ 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); + + assert((ss+1)->pv); + + for (Move* m = (ss+1)->pv; *m != MOVE_NONE; ++m) + rm.pv.push_back(*m); // We record how often the best move has been changed in each // iteration. This information is used for time management: When @@ -917,6 +928,9 @@ moves_loop: // When in check and at SpNode search starts from here { bestMove = SpNode ? splitPoint->bestMove = move : move; + if (PvNode && !RootNode) // Update pv even in fail-high case + update_pv(SpNode ? splitPoint->ss->pv : ss->pv, 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); + Move pv[MAX_PLY+1]; StateInfo st; const TTEntry* tte; Key posKey; @@ -1009,9 +1024,12 @@ 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) - oldAlpha = alpha; + { + oldAlpha = alpha; // To flag BOUND_EXACT when eval above alpha and no available moves + (ss+1)->pv = pv; + ss->pv[0] = MOVE_NONE; + } ss->currentMove = bestMove = MOVE_NONE; ss->ply = (ss-1)->ply + 1; @@ -1034,12 +1052,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 +1179,9 @@ moves_loop: // When in check and at SpNode search starts from here if (value > alpha) { + if (PvNode) // Update pv even in fail-high case + update_pv(ss->pv, move, (ss+1)->pv); + if (PvNode && value < beta) // Update alpha here! Always alpha < beta { alpha = value; @@ -1217,6 +1238,15 @@ moves_loop: // When in check and at SpNode search starts from here } + // update_pv() adds current move and appends child pv[] + + void update_pv(Move* pv, Move move, Move* childPv) { + + for (*pv++ = move; childPv && *childPv != MOVE_NONE; ) + *pv++ = *childPv++; + *pv = MOVE_NONE; + } + // update_stats() updates killers, history, countermoves and followupmoves stats after a fail-high // of a quiet move. @@ -1230,7 +1260,7 @@ moves_loop: // When in check and at SpNode search starts from here // Increase history value of the cut-off move and decrease all the other // played quiet moves. - Value bonus = Value(4 * int(depth) * int(depth)); + Value bonus = Value(int(depth) * int(depth)); History.update(pos.moved_piece(move), to_sq(move), bonus); for (int i = 0; i < quietsCnt; ++i) { @@ -1331,7 +1361,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 +1371,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,9 +1379,10 @@ 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 + size_t idx = 0; - do { + for ( ; idx < pv.size(); ++idx) + { tte = TT.probe(pos.key()); if (!tte || tte->move() != pv[idx]) // Don't overwrite correct entries @@ -1396,9 +1390,8 @@ void RootMove::insert_pv_in_tt(Position& pos) { 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]); } @@ -1540,7 +1533,11 @@ void check_time() { dbg_print(); } - if (Limits.use_time_management() && !Limits.ponder) + // An engine may not stop pondering until told so by the GUI + if (Limits.ponder) + return; + + if (Limits.use_time_management()) { bool stillAtFirstMove = Signals.firstRootMove && !Signals.failedLowAtRoot