X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=aa63fcb4392d2fbe839b91b2c3bdfc1e764dd69d;hp=d7a8379a14e9507d28950ab7b071e456f2f58a46;hb=5ec63eb6b6f43cbd4e25b8f8b97bc8980dbbabef;hpb=553ead429d94b6314ff14aa3eb724f47987e5a52 diff --git a/src/search.cpp b/src/search.cpp index d7a8379a..aa63fcb4 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -57,16 +57,16 @@ namespace { const bool FakeSplit = false; // Different node types, used as template parameter - enum NodeType { Root, PV, NonPV, SplitPointRoot, SplitPointPV, SplitPointNonPV }; + enum NodeType { Root, PV, NonPV }; // Dynamic razoring margin based on depth - inline Value razor_margin(Depth d) { return Value(512 + 16 * int(d)); } + inline Value razor_margin(Depth d) { return Value(512 + 16 * d); } // Futility lookup tables (initialized at startup) and their access functions int FutilityMoveCounts[2][32]; // [improving][depth] inline Value futility_margin(Depth d) { - return Value(100 * int(d)); + return Value(100 * d); } // Reduction lookup tables (initialized at startup) and their access function @@ -85,7 +85,7 @@ namespace { GainsStats Gains; MovesStats Countermoves, Followupmoves; - template + template Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode); template @@ -94,7 +94,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_stats(Position& pos, Stack* ss, Move move, Depth depth, Move* quiets, int quietsCnt); + void update_stats(const Position& pos, Stack* ss, Move move, Depth depth, Move* quiets, int quietsCnt); string uci_pv(const Position& pos, int depth, Value alpha, Value beta); struct Skill { @@ -129,8 +129,8 @@ void Search::init() { { double pvRed = 0.00 + log(double(hd)) * log(double(mc)) / 3.00; double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25; - Reductions[1][1][hd][mc] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(ONE_PLY)) : 0); - Reductions[0][1][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(ONE_PLY)) : 0); + Reductions[1][1][hd][mc] = int8_t( pvRed >= 1.0 ? pvRed * int(ONE_PLY) : 0); + Reductions[0][1][hd][mc] = int8_t(nonPVRed >= 1.0 ? nonPVRed * int(ONE_PLY) : 0); Reductions[1][0][hd][mc] = Reductions[1][1][hd][mc]; Reductions[0][0][hd][mc] = Reductions[0][1][hd][mc]; @@ -185,7 +185,7 @@ void Search::think() { RootColor = RootPos.side_to_move(); TimeMgr.init(Limits, RootPos.game_ply(), RootColor); - int cf = Options["Contempt Factor"] * PawnValueMg / 100; // From centipawns + int cf = Options["Contempt Factor"] * PawnValueEg / 100; // From centipawns DrawValue[ RootColor] = VALUE_DRAW - Value(cf); DrawValue[~RootColor] = VALUE_DRAW + Value(cf); @@ -219,21 +219,19 @@ void Search::think() { << " time: " << Limits.time[RootColor] << " increment: " << Limits.inc[RootColor] << " moves to go: " << Limits.movestogo - << std::endl; + << "\n" << std::endl; } // Reset the threads, still sleeping: will wake up at split time for (size_t i = 0; i < Threads.size(); ++i) Threads[i]->maxPly = 0; - Threads.sleepWhileIdle = Options["Idle Threads Sleep"]; Threads.timer->run = true; Threads.timer->notify_one(); // Wake up the recurring timer id_loop(RootPos); // Let's start searching ! Threads.timer->run = false; // Stop the timer - Threads.sleepWhileIdle = true; // Send idle threads to sleep if (Options["Write Search Log"]) { @@ -337,7 +335,7 @@ namespace { // high/low anymore. while (true) { - bestValue = search(pos, ss, alpha, beta, depth * ONE_PLY, false); + bestValue = search(pos, ss, alpha, beta, depth * ONE_PLY, false); // Bring the best move to the front. It is critical that sorting // is done with a stable algorithm because all the values but the @@ -443,12 +441,11 @@ namespace { // repeat all this work again. We also don't need to store anything to the hash // table here: This is taken care of after we return from the split point. - template + template Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode) { - const bool PvNode = (NT == PV || NT == Root || NT == SplitPointPV || NT == SplitPointRoot); - const bool SpNode = (NT == SplitPointPV || NT == SplitPointNonPV || NT == SplitPointRoot); - const bool RootNode = (NT == Root || NT == SplitPointRoot); + const bool RootNode = NT == Root; + const bool PvNode = NT == PV || NT == Root; assert(-VALUE_INFINITE <= alpha && alpha < beta && beta <= VALUE_INFINITE); assert(PvNode || (alpha == beta - 1)); @@ -534,7 +531,6 @@ namespace { : ttValue >= beta ? (tte->bound() & BOUND_LOWER) : (tte->bound() & BOUND_UPPER))) { - TT.refresh(tte); ss->currentMove = ttMove; // Can be MOVE_NONE // If ttMove is quiet, update killers, history, counter move and followup move on TT hit @@ -586,6 +582,10 @@ namespace { && abs(beta) < VALUE_MATE_IN_MAX_PLY && !pos.pawn_on_7th(pos.side_to_move())) { + if ( depth <= ONE_PLY + && eval + razor_margin(3 * ONE_PLY) <= alpha) + return qsearch(pos, ss, alpha, beta, DEPTH_ZERO); + Value ralpha = alpha - razor_margin(depth); Value v = qsearch(pos, ss, ralpha, ralpha+1, DEPTH_ZERO); if (v <= ralpha) @@ -622,7 +622,7 @@ namespace { pos.do_null_move(st); (ss+1)->skipNullMove = true; nullValue = depth-R < ONE_PLY ? -qsearch(pos, ss+1, -beta, -beta+1, DEPTH_ZERO) - : - search(pos, ss+1, -beta, -beta+1, depth-R, !cutNode); + : - search(pos, ss+1, -beta, -beta+1, depth-R, !cutNode); (ss+1)->skipNullMove = false; pos.undo_null_move(); @@ -638,7 +638,7 @@ namespace { // Do verification search at high depths ss->skipNullMove = true; Value v = depth-R < ONE_PLY ? qsearch(pos, ss, beta-1, beta, DEPTH_ZERO) - : search(pos, ss, beta-1, beta, depth-R, false); + : search(pos, ss, beta-1, beta, depth-R, false); ss->skipNullMove = false; if (v >= beta) @@ -670,7 +670,7 @@ namespace { { ss->currentMove = move; pos.do_move(move, st, ci, pos.gives_check(move, ci)); - value = -search(pos, ss+1, -rbeta, -rbeta+1, rdepth, !cutNode); + value = -search(pos, ss+1, -rbeta, -rbeta+1, rdepth, !cutNode); pos.undo_move(move); if (value >= rbeta) return value; @@ -680,12 +680,12 @@ namespace { // Step 10. Internal iterative deepening (skipped when in check) if ( depth >= (PvNode ? 5 * ONE_PLY : 8 * ONE_PLY) && !ttMove - && (PvNode || ss->staticEval + Value(256) >= beta)) + && (PvNode || ss->staticEval + 256 >= beta)) { Depth d = depth - 2 * ONE_PLY - (PvNode ? DEPTH_ZERO : depth / 4); ss->skipNullMove = true; - search(pos, ss, alpha, beta, d, true); + search(pos, ss, alpha, beta, d, true); ss->skipNullMove = false; tte = TT.probe(posKey); @@ -785,7 +785,7 @@ moves_loop: // When in check and at SpNode search starts from here Value rBeta = ttValue - int(depth); ss->excludedMove = move; ss->skipNullMove = true; - value = search(pos, ss, rBeta - 1, rBeta, depth / 2, cutNode); + value = search(pos, ss, rBeta - 1, rBeta, depth / 2, cutNode); ss->skipNullMove = false; ss->excludedMove = MOVE_NONE; @@ -820,7 +820,7 @@ moves_loop: // When in check and at SpNode search starts from here if (predictedDepth < 7 * ONE_PLY) { futilityValue = ss->staticEval + futility_margin(predictedDepth) - + Value(128) + Gains[pos.moved_piece(move)][to_sq(move)]; + + 128 + Gains[pos.moved_piece(move)][to_sq(move)]; if (futilityValue <= alpha) { @@ -885,13 +885,13 @@ moves_loop: // When in check and at SpNode search starts from here if (SpNode) alpha = splitPoint->alpha; - value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); + value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); - // Research at intermediate depth if reduction is very high + // Re-search at intermediate depth if reduction is very high if (value > alpha && ss->reduction >= 4 * ONE_PLY) { Depth d2 = std::max(newDepth - 2 * ONE_PLY, ONE_PLY); - value = -search(pos, ss+1, -(alpha+1), -alpha, d2, true); + value = -search(pos, ss+1, -(alpha+1), -alpha, d2, true); } doFullDepthSearch = (value > alpha && ss->reduction != DEPTH_ZERO); @@ -909,7 +909,7 @@ moves_loop: // When in check and at SpNode search starts from here value = newDepth < ONE_PLY ? givesCheck ? -qsearch(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO) : -qsearch(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO) - : - search(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode); + : - search(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode); } // For PV nodes only, do a full PV search on the first move or after a fail @@ -919,7 +919,7 @@ moves_loop: // When in check and at SpNode search starts from here 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); + : - search(pos, ss+1, -beta, -alpha, newDepth, false); // Step 17. Undo move pos.undo_move(move); @@ -933,12 +933,11 @@ moves_loop: // When in check and at SpNode search starts from here alpha = splitPoint->alpha; } - // Finished searching the move. If Signals.stop is true, the search - // was aborted because the user interrupted the search or because we - // ran out of time. In this case, the return value of the search cannot - // be trusted, and we don't update the best move and/or PV. + // Finished searching the move. If a stop or a cutoff occurred, the return + // value of the search cannot be trusted, and we return immediately without + // updating best move, PV and TT. if (Signals.stop || thisThread->cutoff_occurred()) - return value; // To avoid returning VALUE_INFINITE + return VALUE_ZERO; if (RootNode) { @@ -987,14 +986,20 @@ moves_loop: // When in check and at SpNode search starts from here // Step 19. Check for splitting the search if ( !SpNode + && Threads.size() >= 2 && depth >= Threads.minimumSplitDepth - && Threads.available_slave(thisThread) + && ( !thisThread->activeSplitPoint + || !thisThread->activeSplitPoint->allSlavesSearching) && thisThread->splitPointsSize < MAX_SPLITPOINTS_PER_THREAD) { - assert(bestValue < beta); + assert(bestValue > -VALUE_INFINITE && bestValue < beta); thisThread->split(pos, ss, alpha, beta, &bestValue, &bestMove, depth, moveCount, &mp, NT, cutNode); + + if (Signals.stop || thisThread->cutoff_occurred()) + return VALUE_ZERO; + if (bestValue >= beta) break; } @@ -1003,30 +1008,31 @@ moves_loop: // When in check and at SpNode search starts from here if (SpNode) return bestValue; + // Following condition would detect a stop or a cutoff set only after move + // loop has been completed. But in this case bestValue is valid because we + // have fully searched our subtree, and we can anyhow save the result in TT. + /* + if (Signals.stop || thisThread->cutoff_occurred()) + return VALUE_DRAW; + */ + // Step 20. Check for mate and stalemate // All legal moves have been searched and if there are no legal moves, it - // must be mate or stalemate. Note that we can have a false positive in - // case of Signals.stop or thread.cutoff_occurred() are set, but this is - // harmless because return value is discarded anyhow in the parent nodes. - // If we are in a singular extension search then return a fail low score. - // A split node has at least one move - the one tried before to be split. + // must be mate or stalemate. If we are in a singular extension search then + // return a fail low score. if (!moveCount) - return excludedMove ? alpha - : inCheck ? mated_in(ss->ply) : DrawValue[pos.side_to_move()]; + bestValue = excludedMove ? alpha + : inCheck ? mated_in(ss->ply) : DrawValue[pos.side_to_move()]; - // If we have pruned all the moves without searching return a fail-low score - if (bestValue == -VALUE_INFINITE) - bestValue = alpha; + // Quiet best move: update killers, history, countermoves and followupmoves + else if (bestValue >= beta && !pos.capture_or_promotion(bestMove) && !inCheck) + update_stats(pos, ss, bestMove, depth, quietsSearched, quietCount - 1); TT.store(posKey, value_to_tt(bestValue, ss->ply), bestValue >= beta ? BOUND_LOWER : PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER, depth, bestMove, ss->staticEval); - // Quiet best move: update killers, history, countermoves and followupmoves - if (bestValue >= beta && !pos.capture_or_promotion(bestMove) && !inCheck) - update_stats(pos, ss, bestMove, depth, quietsSearched, quietCount - 1); - assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); return bestValue; @@ -1040,7 +1046,7 @@ moves_loop: // When in check and at SpNode search starts from here template Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth) { - const bool PvNode = (NT == PV); + const bool PvNode = NT == PV; assert(NT == PV || NT == NonPV); assert(InCheck == !!pos.checkers()); @@ -1125,7 +1131,7 @@ moves_loop: // When in check and at SpNode search starts from here if (PvNode && bestValue > alpha) alpha = bestValue; - futilityBase = bestValue + Value(128); + futilityBase = bestValue + 128; } // Initialize a MovePicker object for the current position, and prepare @@ -1263,7 +1269,7 @@ moves_loop: // When in check and at SpNode search starts from here // update_stats() updates killers, history, countermoves and followupmoves stats after a fail-high // of a quiet move. - void update_stats(Position& pos, Stack* ss, Move move, Depth depth, Move* quiets, int quietsCnt) { + void update_stats(const Position& pos, Stack* ss, Move move, Depth depth, Move* quiets, int quietsCnt) { if (ss->killers[0] != move) { @@ -1343,7 +1349,7 @@ moves_loop: // When in check and at SpNode search starts from here string uci_pv(const Position& pos, int depth, Value alpha, Value beta) { - std::stringstream s; + std::stringstream ss; Time::point elapsed = Time::now() - SearchTime + 1; size_t uciPVSize = std::min((size_t)Options["MultiPV"], RootMoves.size()); int selDepth = 0; @@ -1362,23 +1368,23 @@ moves_loop: // When in check and at SpNode search starts from here int d = updated ? depth : depth - 1; Value v = updated ? RootMoves[i].score : RootMoves[i].prevScore; - if (s.rdbuf()->in_avail()) // Not at first line - s << "\n"; + if (ss.rdbuf()->in_avail()) // Not at first line + ss << "\n"; - s << "info depth " << d - << " seldepth " << selDepth - << " score " << (i == PVIdx ? score_to_uci(v, alpha, beta) : score_to_uci(v)) - << " nodes " << pos.nodes_searched() - << " nps " << pos.nodes_searched() * 1000 / elapsed - << " time " << elapsed - << " multipv " << i + 1 - << " pv"; + ss << "info depth " << d + << " seldepth " << selDepth + << " score " << (i == PVIdx ? score_to_uci(v, alpha, beta) : score_to_uci(v)) + << " nodes " << pos.nodes_searched() + << " nps " << pos.nodes_searched() * 1000 / elapsed + << " time " << elapsed + << " multipv " << i + 1 + << " pv"; for (size_t j = 0; RootMoves[i].pv[j] != MOVE_NONE; ++j) - s << " " << move_to_uci(RootMoves[i].pv[j], pos.is_chess960()); + ss << " " << move_to_uci(RootMoves[i].pv[j], pos.is_chess960()); } - return s.str(); + return ss.str(); } } // namespace @@ -1458,7 +1464,7 @@ void Thread::idle_loop() { { // If we are not searching, wait for a condition to be signaled instead of // wasting CPU time polling for work. - while ((!searching && Threads.sleepWhileIdle) || exit) + while (!searching || exit) { if (exit) { @@ -1470,7 +1476,7 @@ void Thread::idle_loop() { mutex.lock(); // If we are master and all slaves have finished then exit idle_loop - if (this_sp && !this_sp->slavesMask) + if (this_sp && this_sp->slavesMask.none()) { mutex.unlock(); break; @@ -1511,32 +1517,30 @@ void Thread::idle_loop() { activePosition = &pos; - switch (sp->nodeType) { - case Root: - search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); - break; - case PV: - search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); - break; - case NonPV: - search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); - break; - default: + if (sp->nodeType == NonPV) + search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); + + else if (sp->nodeType == PV) + search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); + + else if (sp->nodeType == Root) + search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); + + else assert(false); - } assert(searching); searching = false; activePosition = NULL; - sp->slavesMask &= ~(1ULL << idx); + sp->slavesMask.reset(idx); + sp->allSlavesSearching = false; sp->nodes += pos.nodes_searched(); // Wake up the master thread so to allow it to return from the idle // loop in case we are the last slave of the split point. - if ( Threads.sleepWhileIdle - && this != sp->masterThread - && !sp->slavesMask) + if ( this != sp->masterThread + && sp->slavesMask.none()) { assert(!sp->masterThread->searching); sp->masterThread->notify_one(); @@ -1544,17 +1548,47 @@ void Thread::idle_loop() { // After releasing the lock we can't access any SplitPoint related data // in a safe way because it could have been released under our feet by - // the sp master. Also accessing other Thread objects is unsafe because - // if we are exiting there is a chance that they are already freed. + // the sp master. sp->mutex.unlock(); + + // Try to late join to another split point if none of its slaves has + // already finished. + if (Threads.size() > 2) + for (size_t i = 0; i < Threads.size(); ++i) + { + int size = Threads[i]->splitPointsSize; // Local copy + sp = size ? &Threads[i]->splitPoints[size - 1] : NULL; + + if ( sp + && sp->allSlavesSearching + && available_to(Threads[i])) + { + // Recheck the conditions under lock protection + Threads.mutex.lock(); + sp->mutex.lock(); + + if ( sp->allSlavesSearching + && available_to(Threads[i])) + { + sp->slavesMask.set(idx); + activeSplitPoint = sp; + searching = true; + } + + sp->mutex.unlock(); + Threads.mutex.unlock(); + + break; // Just a single attempt + } + } } // 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) + if (this_sp && this_sp->slavesMask.none()) { this_sp->mutex.lock(); - bool finished = !this_sp->slavesMask; // Retest under lock protection + bool finished = this_sp->slavesMask.none(); // Retest under lock protection this_sp->mutex.unlock(); if (finished) return; @@ -1597,13 +1631,10 @@ void check_time() { sp.mutex.lock(); nodes += sp.nodes; - Bitboard sm = sp.slavesMask; - while (sm) - { - Position* pos = Threads[pop_lsb(&sm)]->activePosition; - if (pos) - nodes += pos->nodes_searched(); - } + + for (size_t idx = 0; idx < Threads.size(); ++idx) + if (sp.slavesMask.test(idx) && Threads[idx]->activePosition) + nodes += Threads[idx]->activePosition->nodes_searched(); sp.mutex.unlock(); }