X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=639c5bc55bf9a1d6d676d29bf2678ed80241cccf;hp=e36c69593e307d17aa18bf0fe9d2d60fc1b39305;hb=9fff27220917d706988185cbd847e3f355a7fe09;hpb=571f54b176b5c30aaac35bc7bbd255c79cdcb926 diff --git a/src/search.cpp b/src/search.cpp index e36c6959..639c5bc5 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -66,7 +66,7 @@ namespace { constexpr int SkipPhase[] = { 0, 1, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 6, 7 }; // Razor and futility margins - constexpr int RazorMargin[] = {0, 590, 604}; + constexpr int RazorMargin = 600; Value futility_margin(Depth d, bool improving) { return Value((175 - 50 * improving) * d / ONE_PLY); } @@ -82,7 +82,14 @@ namespace { // History and stats update bonus, based on depth int stat_bonus(Depth depth) { int d = depth / ONE_PLY; - return d > 17 ? 0 : 33 * d * d + 66 * d - 66; + return d > 17 ? 0 : 29 * d * d + 138 * d - 134; + } + + // Add a small random component to draw evaluations to keep search dynamic + // and to avoid 3fold-blindness. + Value value_draw(Depth depth, Thread* thisThread) { + return depth < 4 ? VALUE_DRAW + : VALUE_DRAW + Value(2 * (thisThread->nodes.load(std::memory_order_relaxed) % 2) - 1); } // Skill structure is used to implement strength limit @@ -246,15 +253,30 @@ void MainThread::search() { && !Skill(Options["Skill Level"]).enabled() && rootMoves[0].pv[0] != MOVE_NONE) { - for (Thread* th : Threads) + std::map votes; + Value minScore = this->rootMoves[0].score; + + // Find out minimum score and reset votes for moves which can be voted + for (Thread* th: Threads) { - Depth depthDiff = th->completedDepth - bestThread->completedDepth; - Value scoreDiff = th->rootMoves[0].score - bestThread->rootMoves[0].score; + minScore = std::min(minScore, th->rootMoves[0].score); + votes[th->rootMoves[0].pv[0]] = 0; + } + + // Vote according to score and depth + for (Thread* th : Threads) + votes[th->rootMoves[0].pv[0]] += int(th->rootMoves[0].score - minScore) + + int(th->completedDepth); - // Select the thread with the best score, always if it is a mate - if ( scoreDiff > 0 - && (depthDiff >= 0 || th->rootMoves[0].score >= VALUE_MATE_IN_MAX_PLY)) + // Select best thread + int bestVote = votes[this->rootMoves[0].pv[0]]; + for (Thread* th : Threads) + { + if (votes[th->rootMoves[0].pv[0]] > bestVote) + { + bestVote = votes[th->rootMoves[0].pv[0]]; bestThread = th; + } } } @@ -520,7 +542,7 @@ namespace { && !rootNode && pos.has_game_cycle(ss->ply)) { - alpha = VALUE_DRAW; + alpha = value_draw(depth, pos.this_thread()); if (alpha >= beta) return alpha; } @@ -541,7 +563,7 @@ namespace { Key posKey; Move ttMove, move, excludedMove, bestMove; Depth extension, newDepth; - Value bestValue, value, ttValue, eval, maxValue; + Value bestValue, value, ttValue, eval, maxValue, pureStaticEval; bool ttHit, inCheck, givesCheck, improving; bool captureOrPromotion, doFullDepthSearch, moveCountPruning, skipQuiets, ttCapture, pvExact; Piece movedPiece; @@ -569,7 +591,8 @@ namespace { if ( Threads.stop.load(std::memory_order_relaxed) || pos.is_draw(ss->ply) || ss->ply >= MAX_PLY) - return (ss->ply >= MAX_PLY && !inCheck) ? evaluate(pos) : VALUE_DRAW; + return (ss->ply >= MAX_PLY && !inCheck) ? evaluate(pos) + : value_draw(depth, pos.this_thread()); // Step 3. Mate distance pruning. Even if we mate at the next move our score // would be at best mate_in(ss->ply+1), but if alpha is already bigger because @@ -689,15 +712,16 @@ namespace { // Step 6. Static evaluation of the position if (inCheck) { - ss->staticEval = eval = VALUE_NONE; + ss->staticEval = eval = pureStaticEval = VALUE_NONE; improving = false; goto moves_loop; // Skip early pruning when in check } else if (ttHit) { // Never assume anything on values stored in TT - if ((ss->staticEval = eval = tte->eval()) == VALUE_NONE) - eval = ss->staticEval = evaluate(pos); + ss->staticEval = eval = pureStaticEval = tte->eval(); + if (eval == VALUE_NONE) + ss->staticEval = eval = pureStaticEval = evaluate(pos); // Can ttValue be used as a better position evaluation? if ( ttValue != VALUE_NONE @@ -706,24 +730,25 @@ namespace { } else { - ss->staticEval = eval = - (ss-1)->currentMove != MOVE_NULL ? evaluate(pos) - : -(ss-1)->staticEval + 2 * Eval::Tempo; + if ((ss-1)->currentMove != MOVE_NULL) + { + int p = (ss-1)->statScore; + int bonus = p > 0 ? (-p - 2500) / 512 : + p < 0 ? (-p + 2500) / 512 : 0; - tte->save(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, - ss->staticEval); + pureStaticEval = evaluate(pos); + ss->staticEval = eval = pureStaticEval + bonus; + } + else + ss->staticEval = eval = pureStaticEval = -(ss-1)->staticEval + 2 * Eval::Tempo; + + tte->save(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, pureStaticEval); } // Step 7. Razoring (~2 Elo) - if ( !PvNode - && depth < 3 * ONE_PLY - && eval <= alpha - RazorMargin[depth / ONE_PLY]) - { - Value ralpha = alpha - (depth >= 2 * ONE_PLY) * RazorMargin[depth / ONE_PLY]; - Value v = qsearch(pos, ss, ralpha, ralpha+1); - if (depth < 2 * ONE_PLY || v <= ralpha) - return v; - } + if ( depth < 2 * ONE_PLY + && eval <= alpha - RazorMargin) + return qsearch(pos, ss, alpha, beta); improving = ss->staticEval >= (ss-2)->staticEval || (ss-2)->staticEval == VALUE_NONE; @@ -738,9 +763,9 @@ namespace { // Step 9. Null move search with verification search (~40 Elo) if ( !PvNode && (ss-1)->currentMove != MOVE_NULL - && (ss-1)->statScore < 22500 + && (ss-1)->statScore < 23200 && eval >= beta - && ss->staticEval >= beta - 36 * depth / ONE_PLY + 225 + && pureStaticEval >= beta - 36 * depth / ONE_PLY + 225 && !excludedMove && pos.non_pawn_material(us) && (ss->ply >= thisThread->nmpMinPly || us != thisThread->nmpColor)) @@ -748,7 +773,7 @@ namespace { assert(eval - beta >= 0); // Null move dynamic reduction based on depth and value - Depth R = ((823 + 67 * depth / ONE_PLY) / 256 + std::min((eval - beta) / PawnValueMg, 3)) * ONE_PLY; + Depth R = ((823 + 67 * depth / ONE_PLY) / 256 + std::min(int(eval - beta) / 200, 3)) * ONE_PLY; ss->currentMove = MOVE_NULL; ss->continuationHistory = &thisThread->continuationHistory[NO_PIECE][0]; @@ -797,7 +822,7 @@ namespace { while ( (move = mp.next_move()) != MOVE_NONE && probCutCount < 3) - if (pos.legal(move)) + if (move != excludedMove && pos.legal(move)) { probCutCount++; @@ -846,7 +871,7 @@ moves_loop: // When in check, search starts from here value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc skipQuiets = false; - ttCapture = false; + ttCapture = ttMove && pos.capture_or_promotion(ttMove); pvExact = PvNode && ttHit && tte->bound() == BOUND_EXACT; // Step 12. Loop through all pseudo-legal moves until no moves remain @@ -888,7 +913,7 @@ moves_loop: // When in check, search starts from here // 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 + // a reduced search 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 ( depth >= 8 * ONE_PLY && move == ttMove @@ -908,7 +933,6 @@ moves_loop: // When in check, search starts from here extension = ONE_PLY; } else if ( givesCheck // Check extension (~2 Elo) - && !moveCountPruning && pos.see_ge(move)) extension = ONE_PLY; @@ -965,9 +989,6 @@ moves_loop: // When in check, search starts from here continue; } - if (move == ttMove && captureOrPromotion) - ttCapture = true; - // Update the current move (this must be done after singular extension search) ss->currentMove = move; ss->continuationHistory = &thisThread->continuationHistory[movedPiece][to_sq(move)]; @@ -983,18 +1004,12 @@ moves_loop: // When in check, search starts from here { Depth r = reduction(improving, depth, moveCount); - if (captureOrPromotion) // (~5 Elo) - { - // Decrease reduction by comparing opponent's stat score - if ((ss-1)->statScore < 0) - r -= ONE_PLY; - } - else - { - // Decrease reduction if opponent's move count is high (~5 Elo) - if ((ss-1)->moveCount > 15) - r -= ONE_PLY; + // Decrease reduction if opponent's move count is high (~10 Elo) + if ((ss-1)->moveCount > 15) + r -= ONE_PLY; + if (!captureOrPromotion) + { // Decrease reduction for exact PV nodes (~0 Elo) if (pvExact) r -= ONE_PLY; @@ -1173,7 +1188,7 @@ moves_loop: // When in check, search starts from here tte->save(posKey, value_to_tt(bestValue, ss->ply), bestValue >= beta ? BOUND_LOWER : PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER, - depth, bestMove, ss->staticEval); + depth, bestMove, pureStaticEval); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);