X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=639c5bc55bf9a1d6d676d29bf2678ed80241cccf;hp=97ad9912b6b38e21c890e462f30cca55efbacba5;hb=9fff27220917d706988185cbd847e3f355a7fe09;hpb=3279655f12ff64603b62a99fe9d7e2c9ea6fb4ef diff --git a/src/search.cpp b/src/search.cpp index 97ad9912..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 : 32 * d * d + 64 * d - 64; + 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; + } - // 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)) + // 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 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; + } } } @@ -290,7 +312,7 @@ void Thread::search() { std::memset(ss-4, 0, 7 * sizeof(Stack)); for (int i = 4; i > 0; i--) - (ss-i)->contHistory = this->contHistory[NO_PIECE][0].get(); // Use as sentinel + (ss-i)->continuationHistory = &this->continuationHistory[NO_PIECE][0]; // Use as sentinel bestValue = delta = alpha = -VALUE_INFINITE; beta = VALUE_INFINITE; @@ -331,7 +353,7 @@ void Thread::search() { if (idx > 0) { int i = (idx - 1) % 20; - if (((rootDepth / ONE_PLY + rootPos.game_ply() + SkipPhase[i]) / SkipSize[i]) % 2) + if (((rootDepth / ONE_PLY + SkipPhase[i]) / SkipSize[i]) % 2) continue; // Retry with an incremented rootDepth } @@ -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 @@ -587,7 +610,7 @@ namespace { (ss+1)->ply = ss->ply + 1; ss->currentMove = (ss+1)->excludedMove = bestMove = MOVE_NONE; - ss->contHistory = thisThread->contHistory[NO_PIECE][0].get(); + ss->continuationHistory = &thisThread->continuationHistory[NO_PIECE][0]; (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; Square prevSq = to_sq((ss-1)->currentMove); @@ -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; + + 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, - ss->staticEval); + 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,10 +773,10 @@ 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->contHistory = thisThread->contHistory[NO_PIECE][0].get(); + ss->continuationHistory = &thisThread->continuationHistory[NO_PIECE][0]; pos.do_null_move(st); @@ -797,12 +822,12 @@ namespace { while ( (move = mp.next_move()) != MOVE_NONE && probCutCount < 3) - if (pos.legal(move)) + if (move != excludedMove && pos.legal(move)) { probCutCount++; ss->currentMove = move; - ss->contHistory = thisThread->contHistory[pos.moved_piece(move)][to_sq(move)].get(); + ss->continuationHistory = &thisThread->continuationHistory[pos.moved_piece(move)][to_sq(move)]; assert(depth >= 5 * ONE_PLY); @@ -835,7 +860,7 @@ namespace { moves_loop: // When in check, search starts from here - const PieceToHistory* contHist[] = { (ss-1)->contHistory, (ss-2)->contHistory, nullptr, (ss-4)->contHistory }; + const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, nullptr, (ss-4)->continuationHistory }; Move countermove = thisThread->counterMoves[pos.piece_on(prevSq)][prevSq]; MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, @@ -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; @@ -935,7 +959,7 @@ moves_loop: // When in check, search starts from here int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount), DEPTH_ZERO) / ONE_PLY; // Countermoves based pruning (~20 Elo) - if ( lmrDepth < 3 + if ( lmrDepth < 3 + ((ss-1)->statScore > 0) && (*contHist[0])[movedPiece][to_sq(move)] < CounterMovePruneThreshold && (*contHist[1])[movedPiece][to_sq(move)] < CounterMovePruneThreshold) continue; @@ -965,12 +989,9 @@ 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->contHistory = thisThread->contHistory[movedPiece][to_sq(move)].get(); + ss->continuationHistory = &thisThread->continuationHistory[movedPiece][to_sq(move)]; // Step 15. Make the move pos.do_move(move, st, givesCheck); @@ -983,20 +1004,12 @@ moves_loop: // When in check, search starts from here { Depth r = reduction(improving, depth, moveCount); - if (captureOrPromotion) // (~5 Elo) - { - // Increase reduction by comparing opponent's stat score - if ((ss-1)->statScore >= 0) - r += ONE_PLY; + // Decrease reduction if opponent's move count is high (~10 Elo) + if ((ss-1)->moveCount > 15) + r -= ONE_PLY; - r -= r ? ONE_PLY : DEPTH_ZERO; - } - else + if (!captureOrPromotion) { - // Decrease reduction if opponent's move count is high (~5 Elo) - if ((ss-1)->moveCount > 15) - r -= ONE_PLY; - // Decrease reduction for exact PV nodes (~0 Elo) if (pvExact) r -= ONE_PLY; @@ -1030,10 +1043,10 @@ moves_loop: // When in check, search starts from here r += ONE_PLY; // Decrease/increase reduction for moves with a good/bad history (~30 Elo) - r = std::max(DEPTH_ZERO, (r / ONE_PLY - ss->statScore / 20000) * ONE_PLY); + r -= ss->statScore / 20000 * ONE_PLY; } - Depth d = std::max(newDepth - r, ONE_PLY); + Depth d = std::max(newDepth - std::max(r, DEPTH_ZERO), ONE_PLY); value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); @@ -1175,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); @@ -1212,8 +1225,10 @@ moves_loop: // When in check, search starts from here ss->pv[0] = MOVE_NONE; } + Thread* thisThread = pos.this_thread(); (ss+1)->ply = ss->ply + 1; ss->currentMove = bestMove = MOVE_NONE; + ss->continuationHistory = &thisThread->continuationHistory[NO_PIECE][0]; inCheck = pos.checkers(); moveCount = 0; @@ -1239,8 +1254,8 @@ moves_loop: // When in check, search starts from here && ttHit && tte->depth() >= ttDepth && ttValue != VALUE_NONE // Only in case of TT access race - && (ttValue >= beta ? (tte->bound() & BOUND_LOWER) - : (tte->bound() & BOUND_UPPER))) + && (ttValue >= beta ? (tte->bound() & BOUND_LOWER) + : (tte->bound() & BOUND_UPPER))) return ttValue; // Evaluate the position statically @@ -1258,7 +1273,7 @@ moves_loop: // When in check, search starts from here ss->staticEval = bestValue = evaluate(pos); // Can ttValue be used as a better position evaluation? - if ( ttValue != VALUE_NONE + if ( ttValue != VALUE_NONE && (tte->bound() & (ttValue > bestValue ? BOUND_LOWER : BOUND_UPPER))) bestValue = ttValue; } @@ -1283,12 +1298,15 @@ moves_loop: // When in check, search starts from here futilityBase = bestValue + 128; } + const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, nullptr, (ss-4)->continuationHistory }; + // Initialize a MovePicker object for the current position, and prepare // to search the moves. Because the depth is <= 0 here, only captures, // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will // be generated. - MovePicker mp(pos, ttMove, depth, &pos.this_thread()->mainHistory, - &pos.this_thread()->captureHistory, + MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, + &thisThread->captureHistory, + contHist, to_sq((ss-1)->currentMove)); // Loop through the moves until no moves remain or a beta cutoff occurs @@ -1345,6 +1363,7 @@ moves_loop: // When in check, search starts from here } ss->currentMove = move; + ss->continuationHistory = &thisThread->continuationHistory[pos.moved_piece(move)][to_sq(move)]; // Make and search the move pos.do_move(move, st, givesCheck); @@ -1436,7 +1455,7 @@ moves_loop: // When in check, search starts from here for (int i : {1, 2, 4}) if (is_ok((ss-i)->currentMove)) - (*(ss-i)->contHistory)[pc][to] << bonus; + (*(ss-i)->continuationHistory)[pc][to] << bonus; }