X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=572a8ac8b2e0b1fda34c6d1867d7069d9653a1ae;hp=eb9f63f15bca317f4fa148bf304472f7eb204edf;hb=df31398bb91b0e43661176e2f1681617ee64f1ad;hpb=04ac1bcabefaa5b6895b8c20c3c6e3ba7e3a5a61 diff --git a/src/search.cpp b/src/search.cpp index eb9f63f1..572a8ac8 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -467,7 +467,7 @@ namespace { if (SkillLevelEnabled && depth == 1 + SkillLevel) skillBest = do_skill_level(); - if (Options["Use Search Log"]) + if (!Signals.stop && Options["Use Search Log"]) pv_info_to_log(pos, depth, bestValue, elapsed_time(), &RootMoves[0].pv[0]); // Filter out startup noise when monitoring best move stability @@ -554,7 +554,7 @@ namespace { Key posKey; Move ttMove, move, excludedMove, threatMove; Depth ext, newDepth; - ValueType vt; + Bound bt; Value bestValue, value, oldAlpha; Value refinedValue, nullValue, futilityBase, futilityValue; bool isPvMove, inCheck, singularExtensionNode, givesCheck; @@ -573,20 +573,26 @@ namespace { thread.maxPly = ss->ply; // Step 1. Initialize node - if (!SpNode) - { - ss->currentMove = ss->bestMove = threatMove = (ss+1)->excludedMove = MOVE_NONE; - (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO; - (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; - } - else + if (SpNode) { - sp = ss->sp; tte = NULL; ttMove = excludedMove = MOVE_NONE; + sp = ss->sp; threatMove = sp->threatMove; + bestValue = sp->bestValue; + moveCount = sp->moveCount; // Lock must be held here + + assert(bestValue > -VALUE_INFINITE && moveCount > 0); + goto split_point_start; } + else + { + ss->currentMove = ss->bestMove = threatMove = (ss+1)->excludedMove = MOVE_NONE; + (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO; + (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; + + } // Step 2. Check for aborted search and immediate draw // Enforce node limit here. FIXME: This only works with 1 search thread. @@ -624,7 +630,7 @@ namespace { // a fail high/low. Biggest advantage at 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 && tte && (PvNode ? tte->depth() >= depth && tte->type() == VALUE_TYPE_EXACT + if (!RootNode && tte && (PvNode ? tte->depth() >= depth && tte->type() == BOUND_EXACT : can_return_tt(tte, depth, beta, ss->ply))) { TT.refresh(tte); @@ -656,7 +662,7 @@ namespace { else { refinedValue = ss->eval = evaluate(pos, ss->evalMargin); - TT.store(posKey, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, ss->evalMargin); + TT.store(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, ss->eval, ss->evalMargin); } // Update gain for the parent non-capture move given the static position @@ -818,16 +824,8 @@ split_point_start: // At split points actual search starts from here && depth >= SingularExtensionDepth[PvNode] && ttMove != MOVE_NONE && !excludedMove // Recursive singular search is not allowed - && (tte->type() & VALUE_TYPE_LOWER) + && (tte->type() & BOUND_LOWER) && tte->depth() >= depth - 3 * ONE_PLY; - if (SpNode) - { - lock_grab(&(sp->lock)); - bestValue = sp->bestValue; - moveCount = sp->moveCount; - - assert(bestValue > -VALUE_INFINITE && moveCount > 0); - } // Step 11. Loop through moves // Loop through all pseudo-legal moves until no moves remain or a beta cutoff occurs @@ -854,7 +852,7 @@ split_point_start: // At split points actual search starts from here if (SpNode) { moveCount = ++sp->moveCount; - lock_release(&(sp->lock)); + lock_release(sp->lock); } else moveCount++; @@ -925,7 +923,7 @@ split_point_start: // At split points actual search starts from here && (!threatMove || !connected_threat(pos, move, threatMove))) { if (SpNode) - lock_grab(&(sp->lock)); + lock_grab(sp->lock); continue; } @@ -940,7 +938,7 @@ split_point_start: // At split points actual search starts from here if (futilityValue < beta) { if (SpNode) - lock_grab(&(sp->lock)); + lock_grab(sp->lock); continue; } @@ -950,7 +948,7 @@ split_point_start: // At split points actual search starts from here && pos.see_sign(move) < 0) { if (SpNode) - lock_grab(&(sp->lock)); + lock_grab(sp->lock); continue; } @@ -972,7 +970,7 @@ split_point_start: // At split points actual search starts from here // Step 15. Reduced depth search (LMR). If the move fails high will be // re-searched at full depth. - if ( depth > 4 * ONE_PLY + if ( depth > 3 * ONE_PLY && !isPvMove && !captureOrPromotion && !dangerous @@ -1015,7 +1013,7 @@ split_point_start: // At split points actual search starts from here // Step 18. Check for new best move if (SpNode) { - lock_grab(&(sp->lock)); + lock_grab(sp->lock); bestValue = sp->bestValue; alpha = sp->alpha; } @@ -1100,10 +1098,10 @@ split_point_start: // At split points actual search starts from here if (!SpNode && !Signals.stop && !thread.cutoff_occurred()) { move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove; - vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER - : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT; + bt = bestValue <= oldAlpha ? BOUND_UPPER + : bestValue >= beta ? BOUND_LOWER : BOUND_EXACT; - TT.store(posKey, value_to_tt(bestValue, ss->ply), vt, depth, move, ss->eval, ss->evalMargin); + TT.store(posKey, value_to_tt(bestValue, ss->ply), bt, depth, move, ss->eval, ss->evalMargin); // Update killers and history for non capture cut-off moves if ( bestValue >= beta @@ -1129,14 +1127,6 @@ split_point_start: // At split points actual search starts from here } } - if (SpNode) - { - // Here we have the lock still grabbed - sp->is_slave[pos.thread()] = false; - sp->nodes += pos.nodes_searched(); - lock_release(&(sp->lock)); - } - assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); return bestValue; @@ -1164,7 +1154,7 @@ split_point_start: // At split points actual search starts from here bool inCheck, enoughMaterial, givesCheck, evasionPrunable; const TTEntry* tte; Depth ttDepth; - ValueType vt; + Bound bt; Value oldAlpha = alpha; ss->bestMove = ss->currentMove = MOVE_NONE; @@ -1214,7 +1204,7 @@ 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), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin); + TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin); return bestValue; } @@ -1292,12 +1282,7 @@ split_point_start: // At split points actual search starts from here && !pos.is_capture_or_promotion(move) && ss->eval + PawnValueMidgame / 4 < beta && !check_is_dangerous(pos, move, futilityBase, beta, &bestValue)) - { - if (ss->eval + PawnValueMidgame / 4 > bestValue) - bestValue = ss->eval + PawnValueMidgame / 4; - continue; - } // Check for legality only before to do the move if (!pos.pl_move_is_legal(move, ci.pinned)) @@ -1332,10 +1317,10 @@ split_point_start: // At split points actual search starts from here // Update transposition table move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove; - vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER - : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT; + bt = bestValue <= oldAlpha ? BOUND_UPPER + : bestValue >= beta ? BOUND_LOWER : BOUND_EXACT; - TT.store(pos.key(), value_to_tt(bestValue, ss->ply), vt, ttDepth, move, ss->eval, evalMargin); + TT.store(pos.key(), value_to_tt(bestValue, ss->ply), bt, ttDepth, move, ss->eval, evalMargin); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1373,8 +1358,7 @@ split_point_start: // At split points actual search starts from here return true; // Rule 2. Queen contact check is very dangerous - if ( type_of(pc) == QUEEN - && bit_is_set(kingAtt, to)) + if (type_of(pc) == QUEEN && (kingAtt & to)) return true; // Rule 3. Creating new double threats with checks @@ -1429,23 +1413,21 @@ split_point_start: // At split points actual search starts from here // Case 3: Moving through the vacated square p2 = pos.piece_on(f2); - if ( piece_is_slider(p2) - && bit_is_set(squares_between(f2, t2), f1)) + if (piece_is_slider(p2) && (squares_between(f2, t2) & f1)) return true; // Case 4: The destination square for m2 is defended by the moving piece in m1 p1 = pos.piece_on(t1); - if (bit_is_set(pos.attacks_from(p1, t1), t2)) + if (pos.attacks_from(p1, t1) & t2) return true; // Case 5: Discovered check, checking piece is the piece moved in m1 ksq = pos.king_square(pos.side_to_move()); - if ( piece_is_slider(p1) - && bit_is_set(squares_between(t1, ksq), f2)) + if (piece_is_slider(p1) && (squares_between(t1, ksq) & f2)) { Bitboard occ = pos.occupied_squares(); - clear_bit(&occ, f2); - if (bit_is_set(pos.attacks_from(p1, t1, occ), ksq)) + occ ^= f2; + if (pos.attacks_from(p1, t1, occ) & ksq) return true; } return false; @@ -1515,9 +1497,9 @@ split_point_start: // At split points actual search starts from here // Case 3: If the moving piece in the threatened move is a slider, don't // prune safe moves which block its ray. - if ( piece_is_slider(pos.piece_on(tfrom)) - && bit_is_set(squares_between(tfrom, tto), mto) - && pos.see_sign(m) >= 0) + if ( piece_is_slider(pos.piece_on(tfrom)) + && (squares_between(tfrom, tto) & mto) + && pos.see_sign(m) >= 0) return true; return false; @@ -1535,8 +1517,8 @@ split_point_start: // At split points actual search starts from here || v >= std::max(VALUE_MATE_IN_MAX_PLY, beta) || v < std::min(VALUE_MATED_IN_MAX_PLY, beta)) - && ( ((tte->type() & VALUE_TYPE_LOWER) && v >= beta) - || ((tte->type() & VALUE_TYPE_UPPER) && v < beta)); + && ( ((tte->type() & BOUND_LOWER) && v >= beta) + || ((tte->type() & BOUND_UPPER) && v < beta)); } @@ -1549,8 +1531,8 @@ split_point_start: // At split points actual search starts from here Value v = value_from_tt(tte->value(), ply); - if ( ((tte->type() & VALUE_TYPE_LOWER) && v >= defaultEval) - || ((tte->type() & VALUE_TYPE_UPPER) && v < defaultEval)) + if ( ((tte->type() & BOUND_LOWER) && v >= defaultEval) + || ((tte->type() & BOUND_UPPER) && v < defaultEval)) return v; return defaultEval; @@ -1769,9 +1751,9 @@ split_point_start: // At split points actual search starts from here /// RootMove::extract_pv_from_tt() builds a PV by adding moves from the TT table. -/// We consider also failing high nodes and not only VALUE_TYPE_EXACT nodes so -/// to allow to always have a ponder move even when we fail high at root, and -/// a long PV to print that is important for position analysis. +/// We consider also failing high nodes and not only BOUND_EXACT nodes so to +/// allow to always have a ponder move even when we fail high at root, and a +/// long PV to print that is important for position analysis. void RootMove::extract_pv_from_tt(Position& pos) { @@ -1825,7 +1807,7 @@ void RootMove::insert_pv_in_tt(Position& pos) { if (!tte || tte->move() != pv[ply]) { v = (pos.in_check() ? VALUE_NONE : evaluate(pos, m)); - TT.store(k, VALUE_NONE, VALUE_TYPE_NONE, DEPTH_NONE, pv[ply], v, m); + TT.store(k, VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply], v, m); } pos.do_move(pv[ply], *st++); @@ -1836,34 +1818,34 @@ void RootMove::insert_pv_in_tt(Position& pos) { /// Thread::idle_loop() is where the thread is parked when it has no work to do. -/// The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint object -/// for which the thread is the master. +/// The parameter 'master_sp', if non-NULL, is a pointer to an active SplitPoint +/// object for which the thread is the master. -void Thread::idle_loop(SplitPoint* sp) { +void Thread::idle_loop(SplitPoint* sp_master) { - while (true) + // 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 we are not searching, wait for a condition to be signaled // instead of wasting CPU time polling for work. while ( do_sleep - || do_terminate - || (Threads.use_sleeping_threads() && !is_searching)) + || do_exit + || (!is_searching && Threads.use_sleeping_threads())) { - assert((!sp && threadID) || Threads.use_sleeping_threads()); - - if (do_terminate) + if (do_exit) { - assert(!sp); + assert(!sp_master); return; } // Grab the lock to avoid races with Thread::wake_up() - lock_grab(&sleepLock); + lock_grab(sleepLock); // If we are master and all slaves have finished don't go to sleep - if (sp && Threads.split_point_finished(sp)) + if (sp_master && !sp_master->slavesMask) { - lock_release(&sleepLock); + lock_release(sleepLock); break; } @@ -1872,54 +1854,50 @@ void Thread::idle_loop(SplitPoint* sp) { // 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) - cond_wait(&sleepCond, &sleepLock); + cond_wait(sleepCond, sleepLock); - lock_release(&sleepLock); + lock_release(sleepLock); } // If this thread has been assigned work, launch a search if (is_searching) { - assert(!do_terminate); + assert(!do_sleep && !do_exit); // Copy split point position and search stack and call search() Stack ss[MAX_PLY_PLUS_2]; - SplitPoint* tsp = splitPoint; - Position pos(*tsp->pos, threadID); - - memcpy(ss, tsp->ss - 1, 4 * sizeof(Stack)); - (ss+1)->sp = tsp; - - if (tsp->nodeType == Root) - search(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth); - else if (tsp->nodeType == PV) - search(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth); - else if (tsp->nodeType == NonPV) - search(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth); + SplitPoint* sp = splitPoint; + Position pos(*sp->pos, threadID); + + memcpy(ss, sp->ss - 1, 4 * sizeof(Stack)); + (ss+1)->sp = sp; + + lock_grab(sp->lock); + + if (sp->nodeType == Root) + search(pos, ss+1, sp->alpha, sp->beta, sp->depth); + else if (sp->nodeType == PV) + search(pos, ss+1, sp->alpha, sp->beta, sp->depth); + else if (sp->nodeType == NonPV) + search(pos, ss+1, sp->alpha, sp->beta, sp->depth); else assert(false); assert(is_searching); + // We return from search with lock held + sp->slavesMask &= ~(1ULL << threadID); + sp->nodes += pos.nodes_searched(); + lock_release(sp->lock); + is_searching = false; // 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() - && threadID != tsp->master - && !Threads[tsp->master].is_searching) - Threads[tsp->master].wake_up(); - } - - // 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 (sp && Threads.split_point_finished(sp)) - { - // Because sp->is_slave[] is reset under lock protection, - // be sure sp->lock has been released before to return. - lock_grab(&(sp->lock)); - lock_release(&(sp->lock)); - return; + && threadID != sp->master + && !Threads[sp->master].is_searching) + Threads[sp->master].wake_up(); } } }