X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=4eaf2e5ee07c2caea5ce159be013a68a6451d94c;hp=46636787f58ee7afa99059126c80761b394a6b4c;hb=8737b26a23afb36d70cb32e3d53eeac7239685bf;hpb=9d1978e217812eaa3626f5e1058962c0aca1bc46 diff --git a/src/search.cpp b/src/search.cpp index 46636787..4eaf2e5e 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -99,7 +99,6 @@ namespace { Value value_to_tt(Value v, int ply); Value value_from_tt(Value v, int ply); bool check_is_dangerous(Position& pos, Move move, Value futilityBase, Value beta); - bool allows_move(const Position& pos, Move first, Move second); bool prevents_move(const Position& pos, Move first, Move second); string uci_pv(const Position& pos, int depth, Value alpha, Value beta); @@ -194,7 +193,7 @@ void Search::think() { goto finalize; } - if (Options["OwnBook"] && !Limits.infinite) + if (Options["OwnBook"] && !Limits.infinite && !Limits.mate) { Move bookMove = book.probe(RootPos, Options["Book File"], Options["Best Book Move"]); @@ -227,22 +226,25 @@ void Search::think() { << std::endl; } - Threads.wake_up(); + // Reset the threads, still sleeping: will be wake up at split time + for (size_t i = 0; i < Threads.size(); i++) + Threads[i].maxPly = 0; + + Threads.sleepWhileIdle = Options["Use Sleeping Threads"]; // Set best timer interval to avoid lagging under time pressure. Timer is // used to check for remaining available thinking time. - if (Limits.use_time_management()) - Threads.set_timer(std::min(100, std::max(TimeMgr.available_time() / 16, - TimerResolution))); - else if (Limits.nodes) - Threads.set_timer(2 * TimerResolution); - else - Threads.set_timer(100); + Threads.timer_thread()->msec = + Limits.use_time_management() ? std::min(100, std::max(TimeMgr.available_time() / 16, TimerResolution)) : + Limits.nodes ? 2 * TimerResolution + : 100; + + Threads.timer_thread()->notify_one(); // Wake up the recurring timer id_loop(RootPos); // Let's start searching ! - Threads.set_timer(0); // Stop timer - Threads.sleep(); + Threads.timer_thread()->msec = 0; // Stop the timer + Threads.sleepWhileIdle = true; // Send idle threads to sleep if (Options["Use Search Log"]) { @@ -262,10 +264,15 @@ void Search::think() { finalize: // When we reach max depth we arrive here even without Signals.stop is raised, - // but if we are pondering or in infinite search, we shouldn't print the best - // move before we are told to do so. + // 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" + // command. We simply wait here until GUI sends one of those commands (that + // raise Signals.stop). if (!Signals.stop && (Limits.ponder || Limits.infinite)) - RootPos.this_thread()->wait_for_stop_or_ponderhit(); + { + Signals.stopOnPonderhit = true; + RootPos.this_thread()->wait_for(Signals.stop); + } // Best move could be MOVE_NONE when searching on a stalemate position sync_cout << "bestmove " << move_to_uci(RootMoves[0].pv[0], RootPos.is_chess960()) @@ -410,6 +417,12 @@ namespace { if (depth > 2 && BestMoveChanges) bestMoveNeverChanged = false; + // Do we have found a "mate in x"? + if ( Limits.mate + && bestValue >= VALUE_MATE_IN_MAX_PLY + && VALUE_MATE - bestValue <= 2 * Limits.mate) + Signals.stop = true; + // Do we have time for the next iteration? Can we stop searching now? if (Limits.use_time_management() && !Signals.stopOnPonderhit) { @@ -485,13 +498,12 @@ namespace { Value bestValue, value, ttValue; Value eval, nullValue, futilityValue; bool inCheck, givesCheck, pvMove, singularExtensionNode; - bool captureOrPromotion, dangerous, doFullDepthSearch, threatExtension; + bool captureOrPromotion, dangerous, doFullDepthSearch; int moveCount, playedMoveCount; // Step 1. Initialize node Thread* thisThread = pos.this_thread(); moveCount = playedMoveCount = 0; - threatExtension = false; inCheck = pos.checkers(); if (SpNode) @@ -575,17 +587,25 @@ namespace { // Step 5. Evaluate the position statically and update parent's gain statistics if (inCheck) ss->staticEval = ss->evalMargin = eval = VALUE_NONE; - else + + else if (tte) { - eval = ss->staticEval = evaluate(pos, ss->evalMargin); + // Never assume anything on values stored in TT + if ( (ss->staticEval = eval = tte->static_value()) == VALUE_NONE + ||(ss->evalMargin = tte->static_value_margin()) == VALUE_NONE) + eval = ss->staticEval = evaluate(pos, ss->evalMargin); // Can ttValue be used as a better position evaluation? - if (tte && ttValue != VALUE_NONE) - { + if (ttValue != VALUE_NONE) if ( ((tte->type() & BOUND_LOWER) && ttValue > eval) || ((tte->type() & BOUND_UPPER) && ttValue < eval)) eval = ttValue; - } + } + else + { + eval = ss->staticEval = evaluate(pos, ss->evalMargin); + TT.store(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, + ss->staticEval, ss->evalMargin); } // Update gain for the parent non-capture move given the static position @@ -672,20 +692,9 @@ namespace { return nullValue; } else - { // The null move failed low, which means that we may be faced with - // some kind of threat. If the previous move was reduced, check if - // the move that refuted the null move was somehow connected to the - // move which was reduced. If a connection is found extend moves that - // defend against threat. + // some kind of threat. threatMove = (ss+1)->currentMove; - - if ( depth < 5 * ONE_PLY - && (ss-1)->reduction - && threatMove != MOVE_NONE - && allows_move(pos, (ss-1)->currentMove, threatMove)) - threatExtension = true; - } } // Step 9. ProbCut (is omitted in PV nodes) @@ -802,9 +811,6 @@ split_point_start: // At split points actual search starts from here if (PvNode && dangerous) ext = ONE_PLY; - else if (threatExtension && prevents_move(pos, move, threatMove)) - ext = ONE_PLY; - else if (givesCheck && pos.see_sign(move) >= 0) ext = ONE_PLY / 2; @@ -841,13 +847,12 @@ split_point_start: // At split points actual search starts from here && !inCheck && !dangerous && move != ttMove + && (!threatMove || !prevents_move(pos, move, threatMove)) && (bestValue > VALUE_MATED_IN_MAX_PLY || ( bestValue == -VALUE_INFINITE && alpha > VALUE_MATED_IN_MAX_PLY))) { // Move count based pruning - if ( depth < 16 * ONE_PLY - && moveCount >= FutilityMoveCounts[depth] - && (!threatMove || !prevents_move(pos, move, threatMove))) + if (depth < 16 * ONE_PLY && moveCount >= FutilityMoveCounts[depth]) { if (SpNode) sp->mutex.lock(); @@ -888,7 +893,7 @@ split_point_start: // At split points actual search starts from here continue; } - pvMove = PvNode ? moveCount == 1 : false; + pvMove = PvNode && moveCount == 1; ss->currentMove = move; if (!SpNode && !captureOrPromotion && playedMoveCount < 64) movesSearched[playedMoveCount++] = move; @@ -980,24 +985,21 @@ split_point_start: // At split points actual search starts from here if (value > bestValue) { - bestValue = value; - if (SpNode) sp->bestValue = value; + bestValue = SpNode ? sp->bestValue = value : value; if (value > alpha) { - bestMove = move; - if (SpNode) sp->bestMove = move; + bestMove = SpNode ? sp->bestMove = move : move; - if (PvNode && value < beta) - { - alpha = value; // Update alpha here! Always alpha < beta - if (SpNode) sp->alpha = value; - } + if (PvNode && value < beta) // Update alpha! Always alpha < beta + alpha = SpNode ? sp->alpha = value : value; else { assert(value >= beta); // Fail high - if (SpNode) sp->cutoff = true; + if (SpNode) + sp->cutoff = true; + break; } } @@ -1041,7 +1043,8 @@ split_point_start: // At split points actual search starts from here if (bestValue >= beta) // Failed high { - TT.store(posKey, value_to_tt(bestValue, ss->ply), BOUND_LOWER, depth, bestMove); + TT.store(posKey, value_to_tt(bestValue, ss->ply), BOUND_LOWER, depth, + bestMove, ss->staticEval, ss->evalMargin); if (!pos.is_capture_or_promotion(bestMove) && !inCheck) { @@ -1066,7 +1069,7 @@ split_point_start: // At split points actual search starts from here else // Failed low or PV search TT.store(posKey, value_to_tt(bestValue, ss->ply), PvNode && bestMove != MOVE_NONE ? BOUND_EXACT : BOUND_UPPER, - depth, bestMove); + depth, bestMove, ss->staticEval, ss->evalMargin); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1094,7 +1097,7 @@ split_point_start: // At split points actual search starts from here Key posKey; Move ttMove, move, bestMove; Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha; - bool givesCheck, enoughMaterial, evasionPrunable, fromNull; + bool givesCheck, enoughMaterial, evasionPrunable; Depth ttDepth; // To flag BOUND_EXACT a node with eval above alpha and no available moves @@ -1103,7 +1106,6 @@ split_point_start: // At split points actual search starts from here ss->currentMove = bestMove = MOVE_NONE; ss->ply = (ss-1)->ply + 1; - fromNull = (ss-1)->currentMove == MOVE_NULL; // Check for an instant draw or maximum ply reached if (pos.is_draw() || ss->ply > MAX_PLY) @@ -1141,11 +1143,12 @@ split_point_start: // At split points actual search starts from here } else { - if (fromNull) + if (tte) { - // Approximated score. Real one is slightly higher due to tempo - ss->staticEval = bestValue = -(ss-1)->staticEval; - ss->evalMargin = VALUE_ZERO; + // Never assume anything on values stored in TT + if ( (ss->staticEval = bestValue = tte->static_value()) == VALUE_NONE + ||(ss->evalMargin = tte->static_value_margin()) == VALUE_NONE) + ss->staticEval = bestValue = evaluate(pos, ss->evalMargin); } else ss->staticEval = bestValue = evaluate(pos, ss->evalMargin); @@ -1154,7 +1157,8 @@ split_point_start: // At split points actual search starts from here if (bestValue >= beta) { if (!tte) - TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER, DEPTH_NONE, MOVE_NONE); + TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER, + DEPTH_NONE, MOVE_NONE, ss->staticEval, ss->evalMargin); return bestValue; } @@ -1183,7 +1187,6 @@ split_point_start: // At split points actual search starts from here // Futility pruning if ( !PvNode && !InCheck - && !fromNull && !givesCheck && move != ttMove && enoughMaterial @@ -1263,7 +1266,9 @@ split_point_start: // At split points actual search starts from here } else // Fail high { - TT.store(posKey, value_to_tt(value, ss->ply), BOUND_LOWER, ttDepth, move); + TT.store(posKey, value_to_tt(value, ss->ply), BOUND_LOWER, + ttDepth, move, ss->staticEval, ss->evalMargin); + return value; } } @@ -1277,7 +1282,7 @@ split_point_start: // At split points actual search starts from here TT.store(posKey, value_to_tt(bestValue, ss->ply), PvNode && bestValue > oldAlpha ? BOUND_EXACT : BOUND_UPPER, - ttDepth, bestMove); + ttDepth, bestMove, ss->staticEval, ss->evalMargin); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1346,47 +1351,6 @@ split_point_start: // At split points actual search starts from here } - // allows_move() tests whether the move at previous ply (first) somehow makes a - // second move possible, for instance if the moving piece is the same in both - // moves. Normally the second move is the threat move (the best move returned - // from a null search that fails low). - - bool allows_move(const Position& pos, Move first, Move second) { - - assert(is_ok(first)); - assert(is_ok(second)); - assert(color_of(pos.piece_on(from_sq(second))) == ~pos.side_to_move()); - assert(color_of(pos.piece_on(to_sq(first))) == ~pos.side_to_move()); - - Square m1from = from_sq(first); - Square m2from = from_sq(second); - Square m1to = to_sq(first); - Square m2to = to_sq(second); - - // The piece is the same or second's destination was vacated by the first move - if (m1to == m2from || m2to == m1from) - return true; - - // Second one moves through the square vacated by first one - if (between_bb(m2from, m2to) & m1from) - return true; - - // Second's destination is defended by the first move's piece - Bitboard m1att = pos.attacks_from(pos.piece_on(m1to), m1to, pos.pieces() ^ m2from); - if (m1att & m2to) - return true; - - // Second move gives a discovered check through the first's checking piece - if (m1att & pos.king_square(pos.side_to_move())) - { - assert(between_bb(m1to, pos.king_square(pos.side_to_move())) & m2from); - return true; - } - - return false; - } - - // prevents_move() tests whether a move (first) is able to defend against an // opponent's move (second). In this case will not be pruned. Normally the // second move is the threat move (the best move returned from a null search @@ -1574,7 +1538,7 @@ void RootMove::insert_pv_in_tt(Position& pos) { tte = TT.probe(pos.key()); if (!tte || tte->move() != pv[ply]) // Don't overwrite correct entries - TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply]); + TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply], VALUE_NONE, VALUE_NONE); assert(MoveList(pos).contains(pv[ply])); @@ -1602,9 +1566,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 ( do_sleep - || do_exit - || (!is_searching && Threads.use_sleeping_threads())) + while (do_exit || (!is_searching && Threads.sleepWhileIdle)) { if (do_exit) { @@ -1626,7 +1588,7 @@ void Thread::idle_loop() { // particular we need to avoid a deadlock in case a master thread has, // in the meanwhile, allocated us and sent the wake_up() call before we // had the chance to grab the lock. - if (do_sleep || !is_searching) + if (!is_searching && Threads.sleepWhileIdle) sleepCondition.wait(mutex); mutex.unlock(); @@ -1635,7 +1597,7 @@ void Thread::idle_loop() { // If this thread has been assigned work, launch a search if (is_searching) { - assert(!do_sleep && !do_exit); + assert(!do_exit); Threads.mutex.lock(); @@ -1674,12 +1636,12 @@ void Thread::idle_loop() { // Wake up 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.use_sleeping_threads() + if ( Threads.sleepWhileIdle && this != sp->master && !sp->slavesMask) { assert(!sp->master->is_searching); - sp->master->wake_up(); + sp->master->notify_one(); } // After releasing the lock we cannot access anymore any SplitPoint