X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=5426ce489ab851ade016e01d648a98f100de67f9;hp=ab9bcca3b781376cb1a5cef4dbb9eccfb1bdba9d;hb=9eedc0a46346bddb8b29c47a84fe6fe8f80d14af;hpb=80810e4951f9447fd2b92faf56d01b60e6abd1a3 diff --git a/src/search.cpp b/src/search.cpp index ab9bcca3..5426ce48 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -1267,29 +1267,30 @@ namespace { if (depth < OnePly) return qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID); - // Initialize, and make an early exit in case of an aborted search, - // an instant draw, maximum ply reached, etc. + // Step 1. Initialize node and poll + // Polling can abort search. init_node(ss, ply, threadID); - // After init_node() that calls poll() + // Step 2. Check for aborted search and immediate draw if (AbortSearch || TM.thread_should_stop(threadID)) return Value(0); if (pos.is_draw() || ply >= PLY_MAX - 1) return VALUE_DRAW; - // Mate distance pruning + // Step 3. Mate distance pruning if (value_mated_in(ply) >= beta) return beta; if (value_mate_in(ply + 1) < beta) return beta - 1; + // Step 4. Transposition table lookup + // We don't want the score of a partial search to overwrite a previous full search // TT value, so we use a different position key in case of an excluded move exsists. Key posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key(); - // Transposition table lookup tte = TT.retrieve(posKey); ttMove = (tte ? tte->move() : MOVE_NONE); @@ -1299,9 +1300,9 @@ namespace { return value_from_tt(tte->value(), ply); } + // Step 5. Evaluate the position statically isCheck = pos.is_check(); - // Evaluate the position statically if (!isCheck) { if (tte && (tte->type() & VALUE_TYPE_EVAL)) @@ -1315,16 +1316,34 @@ namespace { update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval); } - // Static null move pruning. We're betting that the opponent doesn't have - // a move that will reduce the score by more than FutilityMargins[int(depth)] - // if we do a null move. + // Step 6. Razoring + if ( !value_is_mate(beta) + && !isCheck + && depth < RazorDepth + && staticValue < beta - (0x200 + 16 * depth) + && ss[ply - 1].currentMove != MOVE_NULL + && ttMove == MOVE_NONE + && !pos.has_pawn_on_7th(pos.side_to_move())) + { + Value rbeta = beta - (0x200 + 16 * depth); + Value v = qsearch(pos, ss, rbeta-1, rbeta, Depth(0), ply, threadID); + if (v < rbeta) + return v; //FIXME: Logically should be: return (v + 0x200 + 16 * depth); + } + + // Step 7. Static null move pruning + // We're betting that the opponent doesn't have a move that will reduce + // the score by more than fuility_margin(depth) if we do a null move. if ( !isCheck && allowNullmove && depth < RazorDepth && staticValue - futility_margin(depth, 0) >= beta) return staticValue - futility_margin(depth, 0); - // Null move search + // Step 8. Null move search with verification search + // When we jump directly to qsearch() we do a null move only if static value is + // at least beta. Otherwise we do a null move if static value is not more than + // NullMoveMargin under beta. if ( allowNullmove && depth > OnePly && !isCheck @@ -1373,36 +1392,23 @@ namespace { return beta - 1; } } - // Null move search not allowed, try razoring - else if ( !value_is_mate(beta) - && !isCheck - && depth < RazorDepth - && staticValue < beta - (NullMoveMargin + 16 * depth) - && ss[ply - 1].currentMove != MOVE_NULL - && ttMove == MOVE_NONE - && !pos.has_pawn_on_7th(pos.side_to_move())) - { - Value rbeta = beta - (NullMoveMargin + 16 * depth); - Value v = qsearch(pos, ss, rbeta-1, rbeta, Depth(0), ply, threadID); - if (v < rbeta) - return v; - } - // Go with internal iterative deepening if we don't have a TT move + // Step 9. Internal iterative deepening if (UseIIDAtNonPVNodes && ttMove == MOVE_NONE && depth >= 8*OnePly && !isCheck && ss[ply].eval >= beta - IIDMargin) { - search(pos, ss, beta, Min(depth/2, depth-2*OnePly), ply, false, threadID); + search(pos, ss, beta, depth/2, ply, false, threadID); ttMove = ss[ply].pv[ply]; tte = TT.retrieve(posKey); } - // Initialize a MovePicker object for the current position, and prepare - // to search all moves. + // Step 10. Loop through moves + // Loop through all legal moves until no moves remain or a beta cutoff occurs + + // Initialize a MovePicker object for the current position MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]); CheckInfo ci(pos); - // Loop through all legal moves until no moves remain or a beta cutoff occurs while ( bestValue < beta && (move = mp.get_next_move()) != MOVE_NONE && !TM.thread_should_stop(threadID)) @@ -1416,7 +1422,7 @@ namespace { singleEvasion = (isCheck && mp.number_of_evasions() == 1); captureOrPromotion = pos.move_is_capture_or_promotion(move); - // Decide the new search depth + // Step 11. Decide the new search depth ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous); // Singular extension search. We extend the TT move if its value is much better than @@ -1443,10 +1449,10 @@ namespace { newDepth = depth - OnePly + ext; - // Update current move + // Update current move (this must be done after singular extension search) movesSearched[moveCount++] = ss[ply].currentMove = move; - // Futility pruning + // Step 12. Futility pruning if ( !isCheck && !dangerous && !captureOrPromotion @@ -1472,10 +1478,10 @@ namespace { } } - // Make and search the move + // Step 13. Make the move pos.do_move(move, st, ci, moveIsCheck); - // Try to reduce non-pv search depth by one ply if move seems not problematic, + // Step 14. Reduced search // if the move fails high will be re-searched at full depth. bool doFullDepthSearch = true; @@ -1493,16 +1499,19 @@ namespace { } } - if (doFullDepthSearch) // Go with full depth non-pv search + // Step 15. Full depth search + if (doFullDepthSearch) { ss[ply].reduction = Depth(0); value = -search(pos, ss, -(beta-1), newDepth, ply+1, true, threadID); } + + // Step 16. Undo move pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - // New best move? + // Step 17. Check for new best move if (value > bestValue) { bestValue = value; @@ -1513,7 +1522,7 @@ namespace { ss[ply].mateKiller = move; } - // Split? + // Step 18. Check for split if ( TM.active_threads() > 1 && bestValue < beta && depth >= MinimumSplitDepth @@ -1526,11 +1535,14 @@ namespace { break; } - // All legal moves have been searched. A special case: If there were + // Step 19. Check for mate and stalemate + // All legal moves have been searched and if there were // no legal moves, it must be mate or stalemate. + // If one move was excluded return fail low. if (!moveCount) return excludedMove ? beta - 1 : (pos.is_check() ? value_mated_in(ply) : VALUE_DRAW); + // Step 20. Update tables // If the search is not aborted, update the transposition table, // history counters, and killer moves. if (AbortSearch || TM.thread_should_stop(threadID)) @@ -1835,7 +1847,7 @@ namespace { if (ss[sp->ply].reduction) { value = -search(pos, ss, -(sp->beta-1), newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID); - doFullDepthSearch = (value >= sp->beta); + doFullDepthSearch = (value >= sp->beta && !TM.thread_should_stop(threadID)); } } @@ -1932,7 +1944,7 @@ namespace { { Value localAlpha = sp->alpha; value = -search(pos, ss, -localAlpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID); - doFullDepthSearch = (value > localAlpha); + doFullDepthSearch = (value > localAlpha && !TM.thread_should_stop(threadID)); } } @@ -1942,16 +1954,14 @@ namespace { ss[sp->ply].reduction = Depth(0); value = -search(pos, ss, -localAlpha, newDepth, sp->ply+1, true, threadID); - if (value > localAlpha && value < sp->beta) + if (value > localAlpha && value < sp->beta && !TM.thread_should_stop(threadID)) { // If another thread has failed high then sp->alpha has been increased // to be higher or equal then beta, if so, avoid to start a PV search. localAlpha = sp->alpha; if (localAlpha < sp->beta) value = -search_pv(pos, ss, -sp->beta, -localAlpha, newDepth, sp->ply+1, threadID); - else - assert(TM.thread_should_stop(threadID)); - } + } } pos.undo_move(move); @@ -2583,17 +2593,19 @@ namespace { { // Slave threads can exit as soon as AllThreadsShouldExit raises, // master should exit as last one. - if (AllThreadsShouldExit && !waitSp) + if (AllThreadsShouldExit) { + assert(!waitSp); threads[threadID].state = THREAD_TERMINATED; return; } // If we are not thinking, wait for a condition to be signaled // instead of wasting CPU time polling for work. - while ( threadID != 0 - && (AllThreadsShouldSleep || threadID >= ActiveThreads)) + while (AllThreadsShouldSleep || threadID >= ActiveThreads) { + assert(!waitSp); + assert(threadID != 0); threads[threadID].state = THREAD_SLEEPING; #if !defined(_MSC_VER) @@ -2613,7 +2625,7 @@ namespace { // If this thread has been assigned work, launch a search if (threads[threadID].state == THREAD_WORKISWAITING) { - assert(!AllThreadsShouldExit); + assert(!AllThreadsShouldExit && !AllThreadsShouldSleep); threads[threadID].state = THREAD_SEARCHING; @@ -2959,12 +2971,9 @@ namespace { // This makes the threads to go to sleep AllThreadsShouldSleep = true; - // Wait for the threads to be all sleeping and reset flags - // to a known state. + // Reset flags to a known state. for (int i = 1; i < ActiveThreads; i++) { - while (threads[i].state != THREAD_SLEEPING); - // This flag can be in a random state threads[i].printCurrentLineRequest = false; }