X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=e8809f149170c31ceeea0ff821cd2751932506df;hp=46636787f58ee7afa99059126c80761b394a6b4c;hb=9f94d2280110a1ba5eb9eb15b0756883037a817d;hpb=9d1978e217812eaa3626f5e1058962c0aca1bc46 diff --git a/src/search.cpp b/src/search.cpp index 46636787..e8809f14 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -194,7 +194,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 +227,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 +265,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 +418,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 +499,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) @@ -522,7 +535,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 @@ -575,17 +588,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 @@ -647,12 +668,12 @@ namespace { if (eval - PawnValueMg > beta) R += ONE_PLY; - pos.do_null_move(st); + pos.do_null_move(st); (ss+1)->skipNullMove = true; nullValue = depth-R < ONE_PLY ? -qsearch(pos, ss+1, -beta, -alpha, DEPTH_ZERO) : - search(pos, ss+1, -beta, -alpha, depth-R); (ss+1)->skipNullMove = false; - pos.do_null_move(st); + pos.undo_null_move(); if (nullValue >= beta) { @@ -676,15 +697,16 @@ namespace { // 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. + // move which was reduced. If a connection is found, return a fail + // low score (which will cause the reduced move to fail high in the + // parent node, which will trigger a re-search with full depth). threatMove = (ss+1)->currentMove; if ( depth < 5 * ONE_PLY && (ss-1)->reduction && threatMove != MOVE_NONE && allows_move(pos, (ss-1)->currentMove, threatMove)) - threatExtension = true; + return beta - 1; } } @@ -802,9 +824,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; @@ -829,7 +848,7 @@ split_point_start: // At split points actual search starts from here ss->excludedMove = MOVE_NONE; if (value < rBeta) - ext = rBeta >= beta ? ONE_PLY + ONE_PLY / 2 : ONE_PLY; + ext = ONE_PLY; } // Update current move (this must be done after singular extension search) @@ -888,7 +907,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 +999,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; } } @@ -1005,8 +1021,9 @@ split_point_start: // At split points actual search starts from here // Step 19. Check for splitting the search if ( !SpNode - && depth >= Threads.min_split_depth() - && Threads.available_slave_exists(thisThread)) + && depth >= Threads.minimumSplitDepth + && Threads.slave_available(thisThread) + && thisThread->splitPointsSize < MAX_SPLITPOINTS_PER_THREAD) { assert(bestValue < beta); @@ -1041,7 +1058,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 +1084,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 +1112,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,10 +1121,9 @@ 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) + if (pos.is_draw() || ss->ply > MAX_PLY) return DrawValue[pos.side_to_move()]; // Transposition table lookup. At PV nodes, we don't use the TT for @@ -1141,11 +1158,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 +1172,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 +1202,6 @@ split_point_start: // At split points actual search starts from here // Futility pruning if ( !PvNode && !InCheck - && !fromNull && !givesCheck && move != ttMove && enoughMaterial @@ -1263,7 +1281,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 +1297,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); @@ -1552,7 +1572,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 @@ -1574,7 +1594,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])); @@ -1590,33 +1610,31 @@ void RootMove::insert_pv_in_tt(Position& pos) { void Thread::idle_loop() { - // Pointer 'sp_master', if non-NULL, points to the active SplitPoint - // object for which the thread is the master. - const SplitPoint* sp_master = splitPointsCnt ? curSplitPoint : NULL; + // 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; - assert(!sp_master || (sp_master->master == this && is_searching)); + assert(!this_sp || (this_sp->master == 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 (!sp_master || sp_master->slavesMask) + // 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) { - // 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())) + // 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) { - if (do_exit) + if (exit) { - assert(!sp_master); + assert(!this_sp); return; } - // Grab the lock to avoid races with Thread::wake_up() + // Grab the lock to avoid races with Thread::notify_one() mutex.lock(); - // If we are master and all slaves have finished don't go to sleep - if (sp_master && !sp_master->slavesMask) + // If we are master and all slaves have finished then exit idle_loop + if (this_sp && !this_sp->slavesMask) { mutex.unlock(); break; @@ -1624,23 +1642,23 @@ void Thread::idle_loop() { // Do sleep after retesting sleep conditions under lock protection, in // 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) + // in the meanwhile, allocated us and sent the notify_one() call before + // we had the chance to grab the lock. + if (!searching && !exit) sleepCondition.wait(mutex); mutex.unlock(); } // If this thread has been assigned work, launch a search - if (is_searching) + if (searching) { - assert(!do_sleep && !do_exit); + assert(!exit); Threads.mutex.lock(); - assert(is_searching); - SplitPoint* sp = curSplitPoint; + assert(searching); + SplitPoint* sp = activeSplitPoint; Threads.mutex.unlock(); @@ -1652,34 +1670,39 @@ void Thread::idle_loop() { sp->mutex.lock(); - assert(sp->activePositions[idx] == NULL); + assert(sp->slavesPositions[idx] == NULL); - sp->activePositions[idx] = &pos; + sp->slavesPositions[idx] = &pos; - if (sp->nodeType == Root) + switch (sp->nodeType) { + case Root: search(pos, ss+1, sp->alpha, sp->beta, sp->depth); - else if (sp->nodeType == PV) + break; + case PV: search(pos, ss+1, sp->alpha, sp->beta, sp->depth); - else if (sp->nodeType == NonPV) + break; + case NonPV: search(pos, ss+1, sp->alpha, sp->beta, sp->depth); - else + break; + default: assert(false); + } - assert(is_searching); + assert(searching); - is_searching = false; - sp->activePositions[idx] = NULL; + searching = false; + sp->slavesPositions[idx] = NULL; sp->slavesMask &= ~(1ULL << idx); sp->nodes += pos.nodes_searched(); - // 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() + // 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.sleepWhileIdle && this != sp->master && !sp->slavesMask) { - assert(!sp->master->is_searching); - sp->master->wake_up(); + assert(!sp->master->searching); + sp->master->notify_one(); } // After releasing the lock we cannot access anymore any SplitPoint @@ -1719,7 +1742,7 @@ void check_time() { // Loop across all split points and sum accumulated SplitPoint nodes plus // all the currently active slaves positions. for (size_t i = 0; i < Threads.size(); i++) - for (int j = 0; j < Threads[i].splitPointsCnt; j++) + for (int j = 0; j < Threads[i].splitPointsSize; j++) { SplitPoint& sp = Threads[i].splitPoints[j]; @@ -1729,7 +1752,7 @@ void check_time() { Bitboard sm = sp.slavesMask; while (sm) { - Position* pos = sp.activePositions[pop_lsb(&sm)]; + Position* pos = sp.slavesPositions[pop_lsb(&sm)]; nodes += pos ? pos->nodes_searched() : 0; }