X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=c3ebf9abc302dd0974e25fef4a6bc32d19e43956;hp=dfc0e5bf79a9b1ef40064de18c85a603dad8ee26;hb=10ead8a724671132df60ca2e23ddcad7eff7b3e5;hpb=bae019b53e5c2bfcf0d69b4ebfc52b4f4de762eb diff --git a/src/search.cpp b/src/search.cpp index dfc0e5bf..c3ebf9ab 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -79,7 +79,7 @@ namespace { } constexpr int futility_move_count(bool improving, Depth depth) { - return (5 + depth * depth) * (1 + improving) / 2 - 1; + return (4 + depth * depth) / (2 - improving); } // History and stats update bonus, based on depth @@ -290,13 +290,13 @@ void MainThread::search() { votes[th->rootMoves[0].pv[0]] += (th->rootMoves[0].score - minScore + 14) * int(th->completedDepth); - if (bestThread->rootMoves[0].score >= VALUE_MATE_IN_MAX_PLY) + if (bestThread->rootMoves[0].score >= VALUE_TB_WIN_IN_MAX_PLY) { // Make sure we pick the shortest mate if (th->rootMoves[0].score > bestThread->rootMoves[0].score) bestThread = th; } - else if ( th->rootMoves[0].score >= VALUE_MATE_IN_MAX_PLY + else if ( th->rootMoves[0].score >= VALUE_TB_WIN_IN_MAX_PLY || votes[th->rootMoves[0].pv[0]] > votes[bestThread->rootMoves[0].pv[0]]) bestThread = th; } @@ -393,6 +393,8 @@ void Thread::search() { contempt = (us == WHITE ? make_score(ct, ct / 2) : -make_score(ct, ct / 2)); + int searchAgainCounter = 0; + // Iterative deepening loop until requested to stop or the target depth is reached while ( ++rootDepth < MAX_PLY && !Threads.stop @@ -410,6 +412,9 @@ void Thread::search() { size_t pvFirst = 0; pvLast = 0; + if (!Threads.increaseDepth) + searchAgainCounter++; + // MultiPV loop. We perform a full root search for each PV line for (pvIdx = 0; pvIdx < multiPV && !Threads.stop; ++pvIdx) { @@ -445,7 +450,7 @@ void Thread::search() { int failedHighCnt = 0; while (true) { - Depth adjustedDepth = std::max(1, rootDepth - failedHighCnt); + Depth adjustedDepth = std::max(1, rootDepth - failedHighCnt - searchAgainCounter); bestValue = ::search(rootPos, ss, alpha, beta, adjustedDepth, false); // Bring the best move to the front. It is critical that sorting @@ -558,6 +563,12 @@ void Thread::search() { else Threads.stop = true; } + else if ( Threads.increaseDepth + && !mainThread->ponder + && Time.elapsed() > Time.optimum() * fallingEval * reduction * bestMoveInstability * 0.6) + Threads.increaseDepth = false; + else + Threads.increaseDepth = true; } mainThread->iterValue[iterIdx] = bestValue; @@ -744,9 +755,10 @@ namespace { int drawScore = TB::UseRule50 ? 1 : 0; - value = wdl < -drawScore ? -VALUE_MATE + MAX_PLY + ss->ply + 1 - : wdl > drawScore ? VALUE_MATE - MAX_PLY - ss->ply - 1 - : VALUE_DRAW + 2 * wdl * drawScore; + // use the range VALUE_MATE_IN_MAX_PLY to VALUE_TB_WIN_IN_MAX_PLY to score + value = wdl < -drawScore ? VALUE_MATED_IN_MAX_PLY + ss->ply + 1 + : wdl > drawScore ? VALUE_MATE_IN_MAX_PLY - ss->ply - 1 + : VALUE_DRAW + 2 * wdl * drawScore; Bound b = wdl < -drawScore ? BOUND_UPPER : wdl > drawScore ? BOUND_LOWER : BOUND_EXACT; @@ -808,16 +820,16 @@ namespace { tte->save(posKey, VALUE_NONE, ttPv, BOUND_NONE, DEPTH_NONE, MOVE_NONE, eval); } - // Step 7. Razoring (~2 Elo) + // Step 7. Razoring (~1 Elo) if ( !rootNode // The required rootNode PV handling is not available in qsearch && depth < 2 && eval <= alpha - RazorMargin) return qsearch(pos, ss, alpha, beta); - improving = (ss-2)->staticEval == VALUE_NONE ? (ss->staticEval >= (ss-4)->staticEval - || (ss-4)->staticEval == VALUE_NONE) : ss->staticEval >= (ss-2)->staticEval; + improving = (ss-2)->staticEval == VALUE_NONE ? (ss->staticEval > (ss-4)->staticEval + || (ss-4)->staticEval == VALUE_NONE) : ss->staticEval > (ss-2)->staticEval; - // Step 8. Futility pruning: child node (~30 Elo) + // Step 8. Futility pruning: child node (~50 Elo) if ( !PvNode && depth < 6 && eval - futility_margin(depth, improving) >= beta @@ -830,7 +842,7 @@ namespace { && (ss-1)->statScore < 23397 && eval >= beta && eval >= ss->staticEval - && ss->staticEval >= beta - 32 * depth + 292 - improving * 30 + && ss->staticEval >= beta - 32 * depth - 30 * improving + 120 * ttPv + 292 && !excludedMove && pos.non_pawn_material(us) && (ss->ply >= thisThread->nmpMinPly || us != thisThread->nmpColor)) @@ -852,7 +864,7 @@ namespace { if (nullValue >= beta) { // Do not return unproven mate scores - if (nullValue >= VALUE_MATE_IN_MAX_PLY) + if (nullValue >= VALUE_TB_WIN_IN_MAX_PLY) nullValue = beta; if (thisThread->nmpMinPly || (abs(beta) < VALUE_KNOWN_WIN && depth < 13)) @@ -879,7 +891,7 @@ namespace { // much above beta, we can (almost) safely prune the previous move. if ( !PvNode && depth >= 5 - && abs(beta) < VALUE_MATE_IN_MAX_PLY) + && abs(beta) < VALUE_TB_WIN_IN_MAX_PLY) { Value raisedBeta = std::min(beta + 189 - 45 * improving, VALUE_INFINITE); MovePicker mp(pos, ttMove, raisedBeta - ss->staticEval, &thisThread->captureHistory); @@ -917,7 +929,7 @@ namespace { } } - // Step 11. Internal iterative deepening (~2 Elo) + // Step 11. Internal iterative deepening (~1 Elo) if (depth >= 7 && !ttMove) { search(pos, ss, alpha, beta, depth - 7, cutNode); @@ -982,10 +994,10 @@ moves_loop: // When in check, search starts from here // Calculate new depth for this move newDepth = depth - 1; - // Step 13. Pruning at shallow depth (~170 Elo) + // Step 13. Pruning at shallow depth (~200 Elo) if ( !rootNode && pos.non_pawn_material(us) - && bestValue > VALUE_MATED_IN_MAX_PLY) + && bestValue > VALUE_TB_LOSS_IN_MAX_PLY) { // Skip quiet moves if movecount exceeds our FutilityMoveCount threshold moveCountPruning = moveCount >= futility_move_count(improving, depth); @@ -1002,27 +1014,27 @@ moves_loop: // When in check, search starts from here && (*contHist[1])[movedPiece][to_sq(move)] < CounterMovePruneThreshold) continue; - // Futility pruning: parent node (~2 Elo) + // Futility pruning: parent node (~5 Elo) if ( lmrDepth < 6 && !inCheck - && ss->staticEval + 255 + 182 * lmrDepth <= alpha + && ss->staticEval + 235 + 172 * lmrDepth <= alpha && thisThread->mainHistory[us][from_to(move)] + (*contHist[0])[movedPiece][to_sq(move)] + (*contHist[1])[movedPiece][to_sq(move)] - + (*contHist[3])[movedPiece][to_sq(move)] < 30000) + + (*contHist[3])[movedPiece][to_sq(move)] < 25000) continue; - // Prune moves with negative SEE (~10 Elo) + // Prune moves with negative SEE (~20 Elo) if (!pos.see_ge(move, Value(-(32 - std::min(lmrDepth, 18)) * lmrDepth * lmrDepth))) continue; } - else if (!pos.see_ge(move, Value(-194) * depth)) // (~20 Elo) - continue; + else if (!pos.see_ge(move, Value(-194) * depth)) // (~25 Elo) + continue; } - // Step 14. Extensions (~70 Elo) + // Step 14. Extensions (~75 Elo) - // Singular extension search (~60 Elo). If all moves but one fail low on a + // Singular extension search (~70 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 all the other moves but the ttMove and if the @@ -1037,7 +1049,7 @@ moves_loop: // When in check, search starts from here && tte->depth() >= depth - 3 && pos.legal(move)) { - Value singularBeta = ttValue - 2 * depth; + Value singularBeta = ttValue - (((ttPv && !PvNode) + 4) * depth) / 2; Depth halfDepth = depth / 2; ss->excludedMove = move; value = search(pos, ss, singularBeta - 1, singularBeta, halfDepth, cutNode); @@ -1101,7 +1113,7 @@ moves_loop: // When in check, search starts from here // Step 15. Make the move pos.do_move(move, st, givesCheck); - // Step 16. Reduced depth search (LMR). If the move fails high it will be + // Step 16. Reduced depth search (LMR, ~200 Elo). If the move fails high it will be // re-searched at full depth. if ( depth >= 3 && moveCount > 1 + 2 * rootNode @@ -1122,34 +1134,34 @@ moves_loop: // When in check, search starts from here if (th.marked()) r++; - // Decrease reduction if position is or has been on the PV + // Decrease reduction if position is or has been on the PV (~10 Elo) if (ttPv) r -= 2; - // Decrease reduction if opponent's move count is high (~10 Elo) + // Decrease reduction if opponent's move count is high (~5 Elo) if ((ss-1)->moveCount > 14) r--; - // Decrease reduction if ttMove has been singularly extended + // Decrease reduction if ttMove has been singularly extended (~3 Elo) if (singularLMR) r -= 2; if (!captureOrPromotion) { - // Increase reduction if ttMove is a capture (~0 Elo) + // Increase reduction if ttMove is a capture (~5 Elo) if (ttCapture) r++; - // Increase reduction for cut nodes (~5 Elo) + // Increase reduction for cut nodes (~10 Elo) if (cutNode) r += 2; // Decrease reduction for moves that escape a capture. Filter out // castling moves, because they are coded as "king captures rook" and - // hence break make_move(). (~5 Elo) + // hence break make_move(). (~2 Elo) else if ( type_of(move) == NORMAL && !pos.see_ge(reverse_move(move))) - r -= 2; + r -= 2 + ttPv; ss->statScore = thisThread->mainHistory[us][from_to(move)] + (*contHist[0])[movedPiece][to_sq(move)] @@ -1175,6 +1187,10 @@ moves_loop: // When in check, search starts from here r -= ss->statScore / 16384; } + // Increase reduction for captures/promotions if late move and at low depth + else if (depth < 8 && moveCount > 2) + r++; + Depth d = clamp(newDepth - r, 1, newDepth); value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); @@ -1479,7 +1495,7 @@ moves_loop: // When in check, search starts from here // Detect non-capture evasions that are candidates to be pruned evasionPrunable = inCheck && (depth != 0 || moveCount > 2) - && bestValue > VALUE_MATED_IN_MAX_PLY + && bestValue > VALUE_TB_LOSS_IN_MAX_PLY && !pos.capture(move); // Don't search moves with negative SEE values @@ -1545,28 +1561,47 @@ moves_loop: // When in check, search starts from here } - // value_to_tt() adjusts a mate score from "plies to mate from the root" to - // "plies to mate from the current position". Non-mate scores are unchanged. + // value_to_tt() adjusts a mate or TB score from "plies to mate from the root" to + // "plies to mate from the current position". standard scores are unchanged. // The function is called before storing a value in the transposition table. Value value_to_tt(Value v, int ply) { assert(v != VALUE_NONE); - return v >= VALUE_MATE_IN_MAX_PLY ? v + ply - : v <= VALUE_MATED_IN_MAX_PLY ? v - ply : v; + return v >= VALUE_TB_WIN_IN_MAX_PLY ? v + ply + : v <= VALUE_TB_LOSS_IN_MAX_PLY ? v - ply : v; } - // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score + // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate or TB score // from the transposition table (which refers to the plies to mate/be mated - // from current position) to "plies to mate/be mated from the root". + // from current position) to "plies to mate/be mated (TB win/loss) from the root". + // However, for mate scores, to avoid potentially false mate scores related to the 50 moves rule, + // and the graph history interaction, return an optimal TB score instead. Value value_from_tt(Value v, int ply, int r50c) { - return v == VALUE_NONE ? VALUE_NONE - : v >= VALUE_MATE_IN_MAX_PLY ? VALUE_MATE - v > 99 - r50c ? VALUE_MATE_IN_MAX_PLY : v - ply - : v <= VALUE_MATED_IN_MAX_PLY ? VALUE_MATE + v > 99 - r50c ? VALUE_MATED_IN_MAX_PLY : v + ply : v; + if (v == VALUE_NONE) + return VALUE_NONE; + + if (v >= VALUE_TB_WIN_IN_MAX_PLY) // TB win or better + { + if (v >= VALUE_MATE_IN_MAX_PLY && VALUE_MATE - v > 99 - r50c) + return VALUE_MATE_IN_MAX_PLY - 1; // do not return a potentially false mate score + + return v - ply; + } + + if (v <= VALUE_TB_LOSS_IN_MAX_PLY) // TB loss or worse + { + if (v <= VALUE_MATED_IN_MAX_PLY && VALUE_MATE + v > 99 - r50c) + return VALUE_MATED_IN_MAX_PLY + 1; // do not return a potentially false mate score + + return v + ply; + } + + return v; } @@ -1752,7 +1787,7 @@ string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) { Depth d = updated ? depth : depth - 1; Value v = updated ? rootMoves[i].score : rootMoves[i].previousScore; - bool tb = TB::RootInTB && abs(v) < VALUE_MATE - MAX_PLY; + bool tb = TB::RootInTB && abs(v) < VALUE_MATE_IN_MAX_PLY; v = tb ? rootMoves[i].tbScore : v; if (ss.rdbuf()->in_avail()) // Not at first line