X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=50f3a01b5c2bdf54c97ab935c4f134aee67bf95e;hp=7a8d3253048d2db2d7595493cb242692970f6d57;hb=b88374b14a7baa2f8e4c37b16a2e653e7472adcc;hpb=62937d1007e0f97e629f376adca4f4ad738e95d1 diff --git a/src/search.cpp b/src/search.cpp index 7a8d3253..50f3a01b 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -72,6 +72,16 @@ namespace { return Value((175 - 50 * improving) * d / ONE_PLY); } + // Margin for pruning capturing moves: almost linear in depth + constexpr int CapturePruneMargin[] = { 0, + 1 * PawnValueEg * 1055 / 1000, + 2 * PawnValueEg * 1042 / 1000, + 3 * PawnValueEg * 963 / 1000, + 4 * PawnValueEg * 1038 / 1000, + 5 * PawnValueEg * 950 / 1000, + 6 * PawnValueEg * 930 / 1000 + }; + // Futility and reductions lookup tables, initialized at startup int FutilityMoveCounts[2][16]; // [improving][depth] int Reductions[2][2][64][64]; // [pv][improving][depth][moveNumber] @@ -160,7 +170,7 @@ void Search::init() { Reductions[PV][imp][d][mc] = std::max(Reductions[NonPV][imp][d][mc] - 1, 0); // Increase reduction for non-PV nodes when eval is not improving - if (!imp && Reductions[NonPV][imp][d][mc] >= 2) + if (!imp && r > 1.0) Reductions[NonPV][imp][d][mc]++; } @@ -309,8 +319,8 @@ void Thread::search() { multiPV = std::min(multiPV, rootMoves.size()); int ct = Options["Contempt"] * PawnValueEg / 100; // From centipawns - Eval::Contempt = (us == WHITE ? make_score(ct, ct / 2) - : -make_score(ct, ct / 2)); + contempt = (us == WHITE ? make_score(ct, ct / 2) + : -make_score(ct, ct / 2)); // Iterative deepening loop until requested to stop or the target depth is reached while ( (rootDepth += ONE_PLY) < DEPTH_MAX @@ -343,17 +353,18 @@ void Thread::search() { // Reset aspiration window starting size if (rootDepth >= 5 * ONE_PLY) { + Value previousScore = rootMoves[PVIdx].previousScore; delta = Value(18); - alpha = std::max(rootMoves[PVIdx].previousScore - delta,-VALUE_INFINITE); - beta = std::min(rootMoves[PVIdx].previousScore + delta, VALUE_INFINITE); + alpha = std::max(previousScore - delta,-VALUE_INFINITE); + beta = std::min(previousScore + delta, VALUE_INFINITE); ct = Options["Contempt"] * PawnValueEg / 100; // From centipawns - // Adjust contempt based on current bestValue (dynamic contempt) - ct += int(std::round(48 * atan(float(bestValue) / 128))); + // Adjust contempt based on root move's previousScore (dynamic contempt) + ct += int(std::round(48 * atan(float(previousScore) / 128))); - Eval::Contempt = (us == WHITE ? make_score(ct, ct / 2) - : -make_score(ct, ct / 2)); + contempt = (us == WHITE ? make_score(ct, ct / 2) + : -make_score(ct, ct / 2)); } // Start with a small aspiration window and, in the case of a fail @@ -510,7 +521,7 @@ namespace { Move ttMove, move, excludedMove, bestMove; Depth extension, newDepth; Value bestValue, value, ttValue, eval, maxValue; - bool ttHit, inCheck, givesCheck, singularExtensionNode, improving; + bool ttHit, inCheck, givesCheck, improving; bool captureOrPromotion, doFullDepthSearch, moveCountPruning, skipQuiets, ttCapture, pvExact; Piece movedPiece; int moveCount, captureCount, quietCount; @@ -687,7 +698,7 @@ namespace { if (skipEarlyPruning || !pos.non_pawn_material(pos.side_to_move())) goto moves_loop; - // Step 7. Razoring (skipped when in check) + // Step 7. Razoring (skipped when in check, ~2 Elo) if ( !PvNode && depth < 3 * ONE_PLY && eval <= alpha - RazorMargin[depth / ONE_PLY]) @@ -698,14 +709,14 @@ namespace { return v; } - // Step 8. Futility pruning: child node (skipped when in check) + // Step 8. Futility pruning: child node (skipped when in check, ~30 Elo) if ( !rootNode && depth < 7 * ONE_PLY && eval - futility_margin(depth, improving) >= beta && eval < VALUE_KNOWN_WIN) // Do not return unproven wins return eval; - // Step 9. Null move search with verification search + // Step 9. Null move search with verification search (~40 Elo) if ( !PvNode && eval >= beta && ss->staticEval >= beta - 36 * depth / ONE_PLY + 225 @@ -748,7 +759,7 @@ namespace { } } - // Step 10. ProbCut (skipped when in check) + // Step 10. ProbCut (skipped when in check, ~10 Elo) // If we have a good enough capture and a reduced search returns a value // much above beta, we can (almost) safely prune the previous move. if ( !PvNode @@ -788,7 +799,7 @@ namespace { } } - // Step 11. Internal iterative deepening (skipped when in check) + // Step 11. Internal iterative deepening (skipped when in check, ~2 Elo) if ( depth >= 6 * ONE_PLY && !ttMove && (PvNode || ss->staticEval + 128 >= beta)) @@ -809,13 +820,6 @@ moves_loop: // When in check, search starts from here MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, &thisThread->captureHistory, contHist, countermove, ss->killers); value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc - singularExtensionNode = !rootNode - && depth >= 8 * ONE_PLY - && ttMove != MOVE_NONE - && ttValue != VALUE_NONE - && !excludedMove // Recursive singular search is not allowed - && (tte->bound() & BOUND_LOWER) - && tte->depth() >= depth - 3 * ONE_PLY; skipQuiets = false; ttCapture = false; pvExact = PvNode && ttHit && tte->bound() == BOUND_EXACT; @@ -853,15 +857,20 @@ moves_loop: // When in check, search starts from here moveCountPruning = depth < 16 * ONE_PLY && moveCount >= FutilityMoveCounts[improving][depth / ONE_PLY]; - // Step 13. Extensions + // Step 13. Extensions (~70 Elo) - // Singular extension search. If all moves but one fail low on a search - // of (alpha-s, beta-s), and just one fails high on (alpha, beta), then - // that move is singular and should be extended. To verify this we do a - // reduced search on on all the other moves but the ttMove and if the + // Singular extension search (~60 Elo). If all moves but one fail low on a + // search of (alpha-s, beta-s), and just one fails high on (alpha, beta), + // then that move is singular and should be extended. To verify this we do + // a reduced search on on all the other moves but the ttMove and if the // result is lower than ttValue minus a margin then we will extend the ttMove. - if ( singularExtensionNode + if ( depth >= 8 * ONE_PLY && move == ttMove + && !rootNode + && !excludedMove // Recursive singular search is not allowed + && ttValue != VALUE_NONE + && (tte->bound() & BOUND_LOWER) + && tte->depth() >= depth - 3 * ONE_PLY && pos.legal(move)) { Value rBeta = std::max(ttValue - 2 * depth / ONE_PLY, -VALUE_MATE); @@ -872,7 +881,7 @@ moves_loop: // When in check, search starts from here if (value < rBeta) extension = ONE_PLY; } - else if ( givesCheck // Check extension + else if ( givesCheck // Check extension (~2 Elo) && !moveCountPruning && pos.see_ge(move)) extension = ONE_PLY; @@ -880,7 +889,7 @@ moves_loop: // When in check, search starts from here // Calculate new depth for this move newDepth = depth - ONE_PLY + extension; - // Step 14. Pruning at shallow depth + // Step 14. Pruning at shallow depth (~170 Elo) if ( !rootNode && pos.non_pawn_material(pos.side_to_move()) && bestValue > VALUE_MATED_IN_MAX_PLY) @@ -889,7 +898,7 @@ moves_loop: // When in check, search starts from here && !givesCheck && (!pos.advanced_pawn_push(move) || pos.non_pawn_material() >= Value(5000))) { - // Move count based pruning + // Move count based pruning (~30 Elo) if (moveCountPruning) { skipQuiets = true; @@ -899,26 +908,26 @@ moves_loop: // When in check, search starts from here // Reduced depth of the next LMR search int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount), DEPTH_ZERO) / ONE_PLY; - // Countermoves based pruning + // Countermoves based pruning (~20 Elo) if ( lmrDepth < 3 && (*contHist[0])[movedPiece][to_sq(move)] < CounterMovePruneThreshold && (*contHist[1])[movedPiece][to_sq(move)] < CounterMovePruneThreshold) continue; - // Futility pruning: parent node + // Futility pruning: parent node (~2 Elo) if ( lmrDepth < 7 && !inCheck && ss->staticEval + 256 + 200 * lmrDepth <= alpha) continue; - // Prune moves with negative SEE + // Prune moves with negative SEE (~10 Elo) if ( lmrDepth < 8 && !pos.see_ge(move, Value(-35 * lmrDepth * lmrDepth))) continue; } - else if ( depth < 7 * ONE_PLY + else if ( depth < 7 * ONE_PLY // (~20 Elo) && !extension - && !pos.see_ge(move, -PawnValueEg * (depth / ONE_PLY))) + && !pos.see_ge(move, -Value(CapturePruneMargin[depth / ONE_PLY]))) continue; } @@ -1076,6 +1085,7 @@ moves_loop: // When in check, search starts from here else { assert(value >= beta); // Fail high + ss->statScore = std::max(ss->statScore, 0); break; } } @@ -1495,7 +1505,7 @@ void MainThread::check_time() { static TimePoint lastInfoTime = now(); - int elapsed = Time.elapsed(); + TimePoint elapsed = Time.elapsed(); TimePoint tick = Limits.startTime + elapsed; if (tick - lastInfoTime >= 1000) @@ -1521,7 +1531,7 @@ void MainThread::check_time() { string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) { std::stringstream ss; - int elapsed = Time.elapsed() + 1; + TimePoint elapsed = Time.elapsed() + 1; const RootMoves& rootMoves = pos.this_thread()->rootMoves; size_t PVIdx = pos.this_thread()->PVIdx; size_t multiPV = std::min((size_t)Options["MultiPV"], rootMoves.size());