X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=9d3734b89365c670415c0a9f8070526ea1e4bc90;hp=19ebc5e6eeeb79ef8ce12a3835372b1581edae95;hb=8a61b030a6cbfa70b7a473e31ae2662f1b8f39b9;hpb=3ce43c20dee3d0c7afc4ff3b4c67e0530ab2138f diff --git a/src/search.cpp b/src/search.cpp index 19ebc5e6..9d3734b8 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -44,7 +44,6 @@ namespace Search { Color RootColor; Time::point SearchTime; StateStackPtr SetupStates; - MovesVectPtr SetupMoves; } using std::string; @@ -89,6 +88,7 @@ namespace { Value DrawValue[COLOR_NB]; History Hist; Gains Gain; + RefutationTable Refutation; template Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth); @@ -146,7 +146,7 @@ void Search::init() { // Init futility move count array for (d = 0; d < 32; d++) - FutilityMoveCounts[d] = int(3.001 + 0.25 * pow(double(d), 2.0)); + FutilityMoveCounts[d] = int(3.001 + 0.3 * pow(double(d), 1.8)); } @@ -265,6 +265,10 @@ void Search::think() { finalize: + // When search is stopped this info is not printed + sync_cout << "info nodes " << RootPos.nodes_searched() + << " time " << Time::now() - SearchTime + 1 << sync_endl; + // When we reach max depth we arrive here even without Signals.stop is raised, // but if we are pondering or in infinite search, according to UCI protocol, // we shouldn't print the best move before the GUI sends a "stop" or "ponderhit" @@ -294,7 +298,6 @@ namespace { Stack ss[MAX_PLY_PLUS_2]; int depth, prevBestMoveChanges; Value bestValue, alpha, beta, delta; - bool bestMoveNeverChanged = true; memset(ss, 0, 4 * sizeof(Stack)); depth = BestMoveChanges = 0; @@ -303,6 +306,7 @@ namespace { TT.new_search(); Hist.clear(); Gain.clear(); + Refutation.clear(); PVSize = Options["MultiPV"]; Skill skill(Options["Skill Level"]); @@ -417,10 +421,6 @@ namespace { << std::endl; } - // Filter out startup noise when monitoring best move stability - if (depth > 2 && BestMoveChanges) - bestMoveNeverChanged = false; - // Do we have found a "mate in x"? if ( Limits.mate && bestValue >= VALUE_MATE_IN_MAX_PLY @@ -442,18 +442,13 @@ namespace { if (Time::now() - SearchTime > (TimeMgr.available_time() * 62) / 100) stop = true; - bool recapture = pos.is_capture(RootMoves[0].pv[0]) - && pos.captured_piece_type() - && SetupMoves->size() - && to_sq(SetupMoves->back()) == to_sq(RootMoves[0].pv[0]); - // Stop search early if one move seems to be much better than others if ( depth >= 12 && !stop && PVSize == 1 - && ( (bestMoveNeverChanged && recapture) - || RootMoves.size() == 1 - || Time::now() - SearchTime > (TimeMgr.available_time() * 40) / 100)) + && bestValue > VALUE_MATED_IN_MAX_PLY + && ( RootMoves.size() == 1 + || Time::now() - SearchTime > (TimeMgr.available_time() * 20) / 100)) { Value rBeta = bestValue - 2 * PawnValueMg; (ss+1)->excludedMove = RootMoves[0].pv[0]; @@ -534,6 +529,7 @@ namespace { bestValue = -VALUE_INFINITE; ss->currentMove = threatMove = (ss+1)->excludedMove = bestMove = MOVE_NONE; ss->ply = (ss-1)->ply + 1; + ss->futilityMoveCount = 0; (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO; (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; @@ -544,7 +540,7 @@ namespace { if (!RootNode) { // Step 2. Check for aborted search and immediate draw - if (Signals.stop || pos.is_draw() || ss->ply > MAX_PLY) + if (Signals.stop || pos.is_draw() || ss->ply > MAX_PLY) return DrawValue[pos.side_to_move()]; // Step 3. Mate distance pruning. Even if we mate at the next move our score @@ -654,10 +650,11 @@ namespace { && !ss->skipNullMove && depth < 4 * ONE_PLY && !inCheck - && eval - FutilityMargins[depth][0] >= beta + && eval - futility_margin(depth, (ss-1)->futilityMoveCount) >= beta && abs(beta) < VALUE_MATE_IN_MAX_PLY + && abs(eval) < VALUE_KNOWN_WIN && pos.non_pawn_material(pos.side_to_move())) - return eval - FutilityMargins[depth][0]; + return eval - futility_margin(depth, (ss-1)->futilityMoveCount); // Step 8. Null move search with verification search (is omitted in PV nodes) if ( !PvNode @@ -690,7 +687,7 @@ namespace { if (nullValue >= VALUE_MATE_IN_MAX_PLY) nullValue = beta; - if (depth < 6 * ONE_PLY) + if (depth < 12 * ONE_PLY) return nullValue; // Do verification search at high depths @@ -757,7 +754,7 @@ namespace { && ttMove == MOVE_NONE && (PvNode || (!inCheck && ss->staticEval + Value(256) >= beta))) { - Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2); + Depth d = depth - 2 * ONE_PLY - (PvNode ? DEPTH_ZERO : depth / 4); ss->skipNullMove = true; search(pos, ss, alpha, beta, d); @@ -769,7 +766,12 @@ namespace { split_point_start: // At split points actual search starts from here - MovePicker mp(pos, ttMove, depth, Hist, ss, PvNode ? -VALUE_INFINITE : beta); + Move prevMove = (ss-1)->currentMove; + Square prevSq = to_sq(prevMove); + Piece prevP = pos.piece_on(prevSq); + Move refutationMove = Refutation.get(prevP, prevSq); + + MovePicker mp(pos, ttMove, depth, Hist, ss, refutationMove, PvNode ? -VALUE_INFINITE : beta); CheckInfo ci(pos); value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc singularExtensionNode = !RootNode @@ -864,14 +866,15 @@ split_point_start: // At split points actual search starts from here newDepth = depth - ONE_PLY + ext; // Step 13. Futility pruning (is omitted in PV nodes) - if ( !captureOrPromotion + if ( !PvNode + && !captureOrPromotion && !inCheck && !dangerous - && move != ttMove) + /* && move != ttMove Already implicit in the next condition */ + && bestValue > VALUE_MATED_IN_MAX_PLY) { // Move count based pruning - if ( !PvNode - && depth < 16 * ONE_PLY + if ( depth < 16 * ONE_PLY && moveCount >= FutilityMoveCounts[depth] && (!threatMove || !refutes(pos, move, threatMove))) { @@ -888,16 +891,21 @@ split_point_start: // At split points actual search starts from here futilityValue = ss->staticEval + ss->evalMargin + futility_margin(predictedDepth, moveCount) + Gain[pos.piece_moved(move)][to_sq(move)]; - if (!PvNode && futilityValue < beta) + if (futilityValue < beta) { + bestValue = std::max(bestValue, futilityValue); + if (SpNode) + { splitPoint->mutex.lock(); - + if (bestValue > splitPoint->bestValue) + splitPoint->bestValue = bestValue; + } continue; } // Prune moves with negative SEE at low depths - if ( predictedDepth < 2 * ONE_PLY + if ( predictedDepth < 4 * ONE_PLY && pos.see_sign(move) < 0) { if (SpNode) @@ -905,7 +913,13 @@ split_point_start: // At split points actual search starts from here continue; } + + // We have not pruned the move that will be searched, but remember how + // far in the move list we are to be more aggressive in the child node. + ss->futilityMoveCount = moveCount; } + else + ss->futilityMoveCount = 0; // Check for legality only before to do the move if (!RootNode && !SpNode && !pos.pl_move_is_legal(move, ci.pinned)) @@ -1083,6 +1097,7 @@ split_point_start: // At split points actual search starts from here // Increase history value of the cut-off move Value bonus = Value(int(depth) * int(depth)); Hist.update(pos.piece_moved(bestMove), to_sq(bestMove), bonus); + Refutation.update(prevP, prevSq, bestMove); // Decrease history of all the other played non-capture moves for (int i = 0; i < playedMoveCount - 1; i++) @@ -1134,9 +1149,15 @@ split_point_start: // At split points actual search starts from here ss->ply = (ss-1)->ply + 1; // Check for an instant draw or maximum ply reached - if (pos.is_draw() || ss->ply > MAX_PLY) + if (pos.is_draw() || ss->ply > MAX_PLY) return DrawValue[pos.side_to_move()]; + // Decide whether or not to include checks, this fixes also the type of + // TT entry depth that we are going to use. Note that in qsearch we use + // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS. + ttDepth = InCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS + : DEPTH_QS_NO_CHECKS; + // Transposition table lookup. At PV nodes, we don't use the TT for // pruning, but only for move ordering. posKey = pos.key(); @@ -1144,11 +1165,6 @@ split_point_start: // At split points actual search starts from here ttMove = tte ? tte->move() : MOVE_NONE; ttValue = tte ? value_from_tt(tte->value(),ss->ply) : VALUE_NONE; - // Decide whether or not to include checks, this fixes also the type of - // TT entry depth that we are going to use. Note that in qsearch we use - // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS. - ttDepth = InCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS - : DEPTH_QS_NO_CHECKS; if ( tte && tte->depth() >= ttDepth && ttValue != VALUE_NONE // Only in case of TT access race @@ -1229,10 +1245,11 @@ split_point_start: // At split points actual search starts from here continue; } - // Prune moves with negative or equal SEE + // Prune moves with negative or equal SEE and also moves with positive + // SEE where capturing piece loses a tempo and SEE < beta - futilityBase. if ( futilityBase < beta && depth < DEPTH_ZERO - && pos.see(move) <= 0) + && pos.see(move, beta - futilityBase) <= 0) { bestValue = std::max(bestValue, futilityBase); continue; @@ -1582,7 +1599,7 @@ void RootMove::extract_pv_from_tt(Position& pos) { && pos.is_pseudo_legal(m = tte->move()) // Local copy, TT could change && pos.pl_move_is_legal(m, pos.pinned_pieces()) && ply < MAX_PLY - && (!pos.is_draw() || ply < 2)); + && (!pos.is_draw() || ply < 2)); pv.push_back(MOVE_NONE); // Must be zero-terminating @@ -1622,13 +1639,11 @@ void Thread::idle_loop() { // Pointer 'this_sp' is not null only if we are called from split(), and not // at the thread creation. So it means we are the split point's master. - const SplitPoint* this_sp = splitPointsSize ? activeSplitPoint : NULL; + SplitPoint* this_sp = splitPointsSize ? activeSplitPoint : NULL; assert(!this_sp || (this_sp->masterThread == this && searching)); - // If this thread is the master of a split point and all slaves have finished - // their work at this split point, return from the idle loop. - while (!this_sp || this_sp->slavesMask) + while (true) { // If we are not searching, wait for a condition to be signaled instead of // wasting CPU time polling for work. @@ -1721,6 +1736,17 @@ void Thread::idle_loop() { // unsafe because if we are exiting there is a chance are already freed. sp->mutex.unlock(); } + + // If this thread is the master of a split point and all slaves have finished + // their work at this split point, return from the idle loop. + if (this_sp && !this_sp->slavesMask) + { + this_sp->mutex.lock(); + bool finished = !this_sp->slavesMask; // Retest under lock protection + this_sp->mutex.unlock(); + if (finished) + return; + } } }