X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=f50fdf8803fbaa7c58981058e490ff5dac8ecc9d;hp=d9543899a0f7844e2b817b3e2095f321a8ca51fc;hb=dc243a3c880d0a736fb93848cf56e3221e07f8a3;hpb=46ce245763705c89dba60dcfda549dc1f64eb48b diff --git a/src/search.cpp b/src/search.cpp index d9543899..f50fdf88 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -102,6 +102,48 @@ namespace { Move best = MOVE_NONE; }; + // Breadcrumbs are used to mark nodes as being searched by a given thread. + struct Breadcrumb { + std::atomic thread; + std::atomic key; + }; + std::array breadcrumbs; + + // ThreadHolding keeps track of which thread left breadcrumbs at the given node for potential reductions. + // A free node will be marked upon entering the moves loop, and unmarked upon leaving that loop, by the ctor/dtor of this struct. + struct ThreadHolding { + explicit ThreadHolding(Thread* thisThread, Key posKey, int ply) { + location = ply < 8 ? &breadcrumbs[posKey & (breadcrumbs.size() - 1)] : nullptr; + otherThread = false; + owning = false; + if (location) + { + // see if another already marked this location, if not, mark it ourselves. + Thread* tmp = (*location).thread.load(std::memory_order_relaxed); + if (tmp == nullptr) + { + (*location).thread.store(thisThread, std::memory_order_relaxed); + (*location).key.store(posKey, std::memory_order_relaxed); + owning = true; + } + else if ( tmp != thisThread + && (*location).key.load(std::memory_order_relaxed) == posKey) + otherThread = true; + } + } + + ~ThreadHolding() { + if (owning) // free the marked location. + (*location).thread.store(nullptr, std::memory_order_relaxed); + } + + bool marked() { return otherThread; } + + private: + Breadcrumb* location; + bool otherThread, owning; + }; + template Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode); @@ -229,7 +271,7 @@ void MainThread::search() { // Check if there are threads with a better score than main thread if ( Options["MultiPV"] == 1 && !Limits.depth - && !Skill(Options["Skill Level"]).enabled() + && !(Skill(Options["Skill Level"]).enabled() || Options["UCI_LimitStrength"]) && rootMoves[0].pv[0] != MOVE_NONE) { std::map votes; @@ -292,8 +334,20 @@ void Thread::search() { bestValue = delta = alpha = -VALUE_INFINITE; beta = VALUE_INFINITE; - size_t multiPV = Options["MultiPV"]; - Skill skill(Options["Skill Level"]); + multiPV = Options["MultiPV"]; + + // Pick integer skill levels, but non-deterministically round up or down + // such that the average integer skill corresponds to the input floating point one. + // UCI_Elo is converted to a suitable fractional skill level, using anchoring + // to CCRL Elo (goldfish 1.13 = 2000) and a fit through Ordo derived Elo + // for match (TC 60+0.6) results spanning a wide range of k values. + PRNG rng(now()); + double floatLevel = Options["UCI_LimitStrength"] ? + clamp(std::pow((Options["UCI_Elo"] - 1346.6) / 143.4, 1 / 0.806), 0.0, 20.0) : + double(Options["Skill Level"]); + int intLevel = int(floatLevel) + + ((floatLevel - int(floatLevel)) * 1024 > rng.rand() % 1024 ? 1 : 0); + Skill skill(intLevel); // When playing with strength handicap enable MultiPV search that we will // use behind the scenes to retrieve a set of possible moves. @@ -456,7 +510,7 @@ void Thread::search() { // If the bestMove is stable over several iterations, reduce time accordingly timeReduction = lastBestMoveDepth + 10 * ONE_PLY < completedDepth ? 1.95 : 1.0; - double reduction = std::pow(mainThread->previousTimeReduction, 0.528) / timeReduction; + double reduction = (1.25 + mainThread->previousTimeReduction) / (2.25 * timeReduction); // Use part of the gained time from a previous stable move for the current move for (Thread* th : Threads) @@ -531,7 +585,7 @@ namespace { Move ttMove, move, excludedMove, bestMove; Depth extension, newDepth; Value bestValue, value, ttValue, eval, maxValue; - bool ttHit, ttPv, inCheck, givesCheck, improving; + bool ttHit, ttPv, inCheck, givesCheck, improving, doLMR; bool captureOrPromotion, doFullDepthSearch, moveCountPruning, ttCapture; Piece movedPiece; int moveCount, captureCount, quietCount, singularLMR; @@ -692,7 +746,7 @@ namespace { } else if (ttHit) { - // Never assume anything on values stored in TT + // Never assume anything about values stored in TT ss->staticEval = eval = tte->eval(); if (eval == VALUE_NONE) ss->staticEval = eval = evaluate(pos); @@ -847,6 +901,9 @@ moves_loop: // When in check, search starts from here moveCountPruning = false; ttCapture = ttMove && pos.capture_or_promotion(ttMove); + // Mark this node as being searched. + ThreadHolding th(thisThread, posKey, ss->ply); + // Step 12. Loop through all pseudo-legal moves until no moves remain // or a beta cutoff occurs. while ((move = mp.next_move(moveCountPruning)) != MOVE_NONE) @@ -870,6 +927,12 @@ moves_loop: // When in check, search starts from here sync_cout << "info depth " << depth / ONE_PLY << " currmove " << UCI::move(move, pos.is_chess960()) << " currmovenumber " << moveCount + thisThread->pvIdx << sync_endl; + + // In MultiPV mode also skip moves which will be searched later as PV moves + if (rootNode && std::count(thisThread->rootMoves.begin() + thisThread->pvIdx + 1, + thisThread->rootMoves.begin() + thisThread->multiPV, move)) + continue; + if (PvNode) (ss+1)->pv = nullptr; @@ -913,15 +976,16 @@ moves_loop: // When in check, search starts from here // Multi-cut pruning // Our ttMove is assumed to fail high, and now we failed high also on a reduced // search without the ttMove. So we assume this expected Cut-node is not singular, - // that is multiple moves fail high, and we can prune the whole subtree by returning - // the hard beta bound. - else if (cutNode && singularBeta > beta) - return beta; + // that multiple moves fail high, and we can prune the whole subtree by returning + // a soft bound. + else if ( eval >= beta + && singularBeta >= beta) + return singularBeta; } // Check extension (~2 Elo) else if ( givesCheck - && (pos.blockers_for_king(~us) & from_sq(move) || pos.see_ge(move))) + && (pos.is_discovery_check_on_king(~us, move) || pos.see_ge(move))) extension = ONE_PLY; // Castling extension @@ -932,7 +996,7 @@ moves_loop: // When in check, search starts from here else if ( PvNode && pos.rule50_count() > 18 && depth < 3 * ONE_PLY - && ss->ply < 3 * thisThread->rootDepth / ONE_PLY) // To avoid too deep searches + && ++thisThread->shuffleExts < thisThread->nodes.load(std::memory_order_relaxed) / 4) // To avoid too many extensions extension = ONE_PLY; // Passed pawn extension @@ -956,7 +1020,7 @@ moves_loop: // When in check, search starts from here && !givesCheck && (!pos.advanced_pawn_push(move) || pos.non_pawn_material(~us) > BishopValueMg)) { - // Move count based pruning (~30 Elo) + // Move count based pruning if (moveCountPruning) continue; @@ -980,8 +1044,8 @@ moves_loop: // When in check, search starts from here if (!pos.see_ge(move, Value(-29 * lmrDepth * lmrDepth))) continue; } - else if ((!givesCheck || !extension) - && !pos.see_ge(move, -PawnValueEg * (depth / ONE_PLY))) // (~20 Elo) + else if ( (!givesCheck || !extension) + && !pos.see_ge(move, -PawnValueEg * (depth / ONE_PLY))) // (~20 Elo) continue; } @@ -1012,6 +1076,10 @@ moves_loop: // When in check, search starts from here { Depth r = reduction(improving, depth, moveCount); + // Reduction if other threads are searching this position. + if (th.marked()) + r += ONE_PLY; + // Decrease reduction if position is or has been on the PV if (ttPv) r -= 2 * ONE_PLY; @@ -1046,6 +1114,13 @@ moves_loop: // When in check, search starts from here + (*contHist[3])[movedPiece][to_sq(move)] - 4000; + // Reset statScore to zero if negative and most stats shows >= 0 + if ( ss->statScore < 0 + && (*contHist[0])[movedPiece][to_sq(move)] >= 0 + && (*contHist[1])[movedPiece][to_sq(move)] >= 0 + && thisThread->mainHistory[us][from_to(move)] >= 0) + ss->statScore = 0; + // Decrease/increase reduction by comparing opponent's stat score (~10 Elo) if (ss->statScore >= 0 && (ss-1)->statScore < 0) r -= ONE_PLY; @@ -1054,22 +1129,35 @@ 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 -= ss->statScore / 20000 * ONE_PLY; + r -= ss->statScore / 16384 * ONE_PLY; } Depth d = clamp(newDepth - r, ONE_PLY, newDepth); value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); - doFullDepthSearch = (value > alpha && d != newDepth); + doFullDepthSearch = (value > alpha && d != newDepth), doLMR = true; } else - doFullDepthSearch = !PvNode || moveCount > 1; + doFullDepthSearch = !PvNode || moveCount > 1, doLMR = false; // Step 17. Full depth search when LMR is skipped or fails high if (doFullDepthSearch) + { value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode); + if (doLMR && !captureOrPromotion) + { + int bonus = value > alpha ? stat_bonus(newDepth) + : -stat_bonus(newDepth); + + if (move == ss->killers[0]) + bonus += bonus / 4; + + update_continuation_histories(ss, movedPiece, to_sq(move), bonus); + } + } + // For PV nodes only, do a full PV search on the first move or after a fail // high (in the latter case search only if value < beta), otherwise let the // parent node fail low with value <= alpha and try another move. @@ -1280,7 +1368,7 @@ moves_loop: // When in check, search starts from here { if (ttHit) { - // Never assume anything on values stored in TT + // Never assume anything about values stored in TT if ((ss->staticEval = bestValue = tte->eval()) == VALUE_NONE) ss->staticEval = bestValue = evaluate(pos); @@ -1713,4 +1801,10 @@ void Tablebases::rank_root_moves(Position& pos, Search::RootMoves& rootMoves) { if (dtz_available || rootMoves[0].tbScore <= VALUE_DRAW) Cardinality = 0; } + else + { + // Clean up if root_probe() and root_probe_wdl() have failed + for (auto& m : rootMoves) + m.tbRank = 0; + } }