X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=31edcc2f8845e37774cfb915163bccdcd2cc3577;hp=29dc00a996d2e97337c819b29a99681c49f9806f;hb=bd7a0d4ce4945b3bde229fce9e3c886152a48d79;hpb=e5463eb3ae6c1a035fe1da717fb88568ee654237 diff --git a/src/search.cpp b/src/search.cpp index 29dc00a9..31edcc2f 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -62,28 +62,9 @@ namespace { const bool Slidings[18] = { 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1 }; inline bool piece_is_slider(Piece p) { return Slidings[p]; } - // Maximum depth for razoring - const Depth RazorDepth = 4 * ONE_PLY; - // Dynamic razoring margin based on depth inline Value razor_margin(Depth d) { return Value(512 + 16 * int(d)); } - // Maximum depth for use of dynamic threat detection when null move fails low - const Depth ThreatDepth = 5 * ONE_PLY; - - // Minimum depth for use of internal iterative deepening - const Depth IIDDepth[] = { 8 * ONE_PLY, 5 * ONE_PLY }; - - // At Non-PV nodes we do an internal iterative deepening search - // when the static evaluation is bigger then beta - IIDMargin. - const Value IIDMargin = Value(256); - - // Minimum depth for use of singular extension - const Depth SingularExtensionDepth[] = { 8 * ONE_PLY, 6 * ONE_PLY }; - - // Futility margin for quiescence search - const Value FutilityMarginQS = Value(128); - // Futility lookup tables (initialized at startup) and their access functions Value FutilityMargins[16][64]; // [depth][moveNumber] int FutilityMoveCounts[32]; // [depth] @@ -107,10 +88,6 @@ namespace { return (Depth) Reductions[PvNode][std::min(int(d) / ONE_PLY, 63)][std::min(mn, 63)]; } - // Easy move margin. An easy move candidate must be at least this much better - // than the second best move. - const Value EasyMoveMargin = Value(0x150); - // This is the minimum interval in msec between two check_time() calls const int TimerResolution = 5; @@ -279,6 +256,8 @@ void Search::think() { // used to check for remaining available thinking time. if (Limits.use_time_management()) Threads.set_timer(std::min(100, std::max(TimeMgr.available_time() / 16, TimerResolution))); + else if (Limits.nodes) + Threads.set_timer(2 * TimerResolution); else Threads.set_timer(100); @@ -467,7 +446,7 @@ namespace { && ( (bestMoveNeverChanged && pos.captured_piece_type()) || Time::now() - SearchTime > (TimeMgr.available_time() * 40) / 100)) { - Value rBeta = bestValue - EasyMoveMargin; + Value rBeta = bestValue - 2 * PawnValueMg; (ss+1)->excludedMove = RootMoves[0].pv[0]; (ss+1)->skipNullMove = true; Value v = search(pos, ss+1, rBeta - 1, rBeta, (depth - 3) * ONE_PLY); @@ -526,49 +505,42 @@ namespace { Key posKey; Move ttMove, move, excludedMove, bestMove, threatMove; Depth ext, newDepth; - Bound bt; Value bestValue, value, oldAlpha, ttValue; Value refinedValue, nullValue, futilityValue; bool pvMove, inCheck, singularExtensionNode, givesCheck; bool captureOrPromotion, dangerous, doFullDepthSearch; int moveCount, playedMoveCount; + // Step 1. Initialize node Thread* thisThread = pos.this_thread(); moveCount = playedMoveCount = 0; oldAlpha = alpha; inCheck = pos.in_check(); - ss->ply = (ss-1)->ply + 1; - - // Used to send selDepth info to GUI - if (PvNode && thisThread->maxPly < ss->ply) - thisThread->maxPly = ss->ply; - // Step 1. Initialize node if (SpNode) { + sp = ss->sp; + bestMove = sp->bestMove; + threatMove = sp->threatMove; + bestValue = sp->bestValue; tte = NULL; ttMove = excludedMove = MOVE_NONE; ttValue = VALUE_NONE; - sp = ss->sp; - bestMove = sp->bestMove; - threatMove = sp->threatMove; - bestValue = sp->bestValue; - assert(bestValue > -VALUE_INFINITE && sp->moveCount > 0); + assert(sp->bestValue > -VALUE_INFINITE && sp->moveCount > 0); goto split_point_start; } - else - { - bestValue = -VALUE_INFINITE; - ss->currentMove = threatMove = (ss+1)->excludedMove = bestMove = MOVE_NONE; - (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO; - (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; - } - // Enforce node limit here. FIXME: This only works with 1 search thread. - if (Limits.nodes && pos.nodes_searched() >= Limits.nodes) - Signals.stop = true; + bestValue = -VALUE_INFINITE; + ss->currentMove = threatMove = (ss+1)->excludedMove = bestMove = MOVE_NONE; + ss->ply = (ss-1)->ply + 1; + (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO; + (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; + + // Used to send selDepth info to GUI + if (PvNode && thisThread->maxPly < ss->ply) + thisThread->maxPly = ss->ply; if (!RootNode) { @@ -649,7 +621,7 @@ namespace { // Step 6. Razoring (is omitted in PV nodes) if ( !PvNode - && depth < RazorDepth + && depth < 4 * ONE_PLY && !inCheck && refinedValue + razor_margin(depth) < beta && ttMove == MOVE_NONE @@ -669,7 +641,7 @@ namespace { // the score by more than futility_margin(depth) if we do a null move. if ( !PvNode && !ss->skipNullMove - && depth < RazorDepth + && depth < 4 * ONE_PLY && !inCheck && refinedValue - futility_margin(depth, 0) >= beta && abs(beta) < VALUE_MATE_IN_MAX_PLY @@ -728,7 +700,7 @@ namespace { // parent node, which will trigger a re-search with full depth). threatMove = (ss+1)->currentMove; - if ( depth < ThreatDepth + if ( depth < 5 * ONE_PLY && (ss-1)->reduction && threatMove != MOVE_NONE && connected_moves(pos, (ss-1)->currentMove, threatMove)) @@ -741,7 +713,7 @@ namespace { // and a reduced search returns a value much above beta, we can (almost) safely // prune the previous move. if ( !PvNode - && depth >= RazorDepth + ONE_PLY + && depth >= 5 * ONE_PLY && !inCheck && !ss->skipNullMove && excludedMove == MOVE_NONE @@ -770,9 +742,9 @@ namespace { } // Step 10. Internal iterative deepening - if ( depth >= IIDDepth[PvNode] + if ( depth >= (PvNode ? 5 * ONE_PLY : 8 * ONE_PLY) && ttMove == MOVE_NONE - && (PvNode || (!inCheck && ss->eval + IIDMargin >= beta))) + && (PvNode || (!inCheck && ss->eval + Value(256) >= beta))) { Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2); @@ -791,7 +763,7 @@ split_point_start: // At split points actual search starts from here value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc singularExtensionNode = !RootNode && !SpNode - && depth >= SingularExtensionDepth[PvNode] + && depth >= (PvNode ? 6 * ONE_PLY : 8 * ONE_PLY) && ttMove != MOVE_NONE && !excludedMove // Recursive singular search is not allowed && (tte->type() & BOUND_LOWER) @@ -868,7 +840,7 @@ split_point_start: // At split points actual search starts from here ss->excludedMove = MOVE_NONE; if (value < rBeta) - ext = ONE_PLY; + ext = rBeta >= beta ? ONE_PLY + ONE_PLY / 2 : ONE_PLY; } // Update current move (this must be done after singular extension search) @@ -1007,7 +979,6 @@ split_point_start: // At split points actual search starts from here // is not a problem when sorting becuase sort is stable and move // position in the list is preserved, just the PV is pushed up. rm.score = -VALUE_INFINITE; - } if (value > bestValue) @@ -1018,15 +989,17 @@ split_point_start: // At split points actual search starts from here if ( PvNode && value > alpha && value < beta) // We want always alpha < beta - alpha = value; + { + alpha = bestValue; // Update alpha here! + } if (SpNode && !thisThread->cutoff_occurred()) { - sp->bestValue = value; - sp->bestMove = move; + sp->bestValue = bestValue; + sp->bestMove = bestMove; sp->alpha = alpha; - if (value >= beta) + if (bestValue >= beta) sp->cutoff = true; } } @@ -1039,7 +1012,7 @@ split_point_start: // At split points actual search starts from here && !Signals.stop && !thisThread->cutoff_occurred()) bestValue = Threads.split(pos, ss, alpha, beta, bestValue, &bestMove, - depth, threatMove, moveCount, &mp, NT); + depth, threatMove, moveCount, mp, NT); } // Step 20. Check for mate and stalemate @@ -1048,41 +1021,42 @@ split_point_start: // At split points actual search starts from here // case of Signals.stop or thread.cutoff_occurred() are set, but this is // harmless because return value is discarded anyhow in the parent nodes. // If we are in a singular extension search then return a fail low score. - if (!moveCount) - return excludedMove ? oldAlpha : inCheck ? mated_in(ss->ply) : VALUE_DRAW; + // A split node has at least one move, the one tried before to be splitted. + if (!SpNode && !moveCount) + return excludedMove ? alpha : inCheck ? mated_in(ss->ply) : VALUE_DRAW; // If we have pruned all the moves without searching return a fail-low score if (bestValue == -VALUE_INFINITE) { assert(!playedMoveCount); - bestValue = oldAlpha; + bestValue = alpha; } // Step 21. Update tables // Update transposition table entry, killers and history if (!SpNode && !Signals.stop && !thisThread->cutoff_occurred()) { - move = bestValue <= oldAlpha ? MOVE_NONE : bestMove; - bt = bestValue <= oldAlpha ? BOUND_UPPER - : bestValue >= beta ? BOUND_LOWER : BOUND_EXACT; + Move ttm = bestValue <= oldAlpha ? MOVE_NONE : bestMove; + Bound bt = bestValue <= oldAlpha ? BOUND_UPPER + : bestValue >= beta ? BOUND_LOWER : BOUND_EXACT; - TT.store(posKey, value_to_tt(bestValue, ss->ply), bt, depth, move, ss->eval, ss->evalMargin); + TT.store(posKey, value_to_tt(bestValue, ss->ply), bt, depth, ttm, ss->eval, ss->evalMargin); // Update killers and history for non capture cut-off moves if ( bestValue >= beta - && !pos.is_capture_or_promotion(move) + && !pos.is_capture_or_promotion(bestMove) && !inCheck) { - if (move != ss->killers[0]) + if (bestMove != ss->killers[0]) { ss->killers[1] = ss->killers[0]; - ss->killers[0] = move; + ss->killers[0] = bestMove; } // Increase history value of the cut-off move Value bonus = Value(int(depth) * int(depth)); - H.add(pos.piece_moved(move), to_sq(move), bonus); + H.add(pos.piece_moved(bestMove), to_sq(bestMove), bonus); // Decrease history of all the other played non-capture moves for (int i = 0; i < playedMoveCount - 1; i++) @@ -1178,7 +1152,7 @@ split_point_start: // At split points actual search starts from here if (PvNode && bestValue > alpha) alpha = bestValue; - futilityBase = ss->eval + evalMargin + FutilityMarginQS; + futilityBase = ss->eval + evalMargin + Value(128); enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMg; } @@ -1516,7 +1490,7 @@ split_point_start: // At split points actual search starts from here int s = RootMoves[i].score; // Don't allow crazy blunders even at very low skills - if (i > 0 && RootMoves[i-1].score > s + EasyMoveMargin) + if (i > 0 && RootMoves[i-1].score > s + 2 * PawnValueMg) break; // This is our magic formula @@ -1712,6 +1686,10 @@ void Thread::idle_loop() { sp->mutex.lock(); + assert(sp->activePositions[idx] == NULL); + + sp->activePositions[idx] = &pos; + if (sp->nodeType == Root) search(pos, ss+1, sp->alpha, sp->beta, sp->depth); else if (sp->nodeType == PV) @@ -1724,6 +1702,7 @@ void Thread::idle_loop() { assert(is_searching); is_searching = false; + sp->activePositions[idx] = NULL; sp->slavesMask &= ~(1ULL << idx); sp->nodes += pos.nodes_searched(); @@ -1754,6 +1733,7 @@ void Thread::idle_loop() { void check_time() { static Time::point lastInfoTime = Time::now(); + int64_t nodes = 0; // Workaround silly 'uninitialized' gcc warning if (Time::now() - lastInfoTime >= 1000) { @@ -1764,6 +1744,35 @@ void check_time() { if (Limits.ponder) return; + if (Limits.nodes) + { + Threads.mutex.lock(); + + nodes = RootPosition.nodes_searched(); + + // Loop across all split points and sum accumulated SplitPoint nodes plus + // all the currently active slaves positions. + for (size_t i = 0; i < Threads.size(); i++) + for (int j = 0; j < Threads[i].splitPointsCnt; j++) + { + SplitPoint& sp = Threads[i].splitPoints[j]; + + sp.mutex.lock(); + + nodes += sp.nodes; + Bitboard sm = sp.slavesMask; + while (sm) + { + Position* pos = sp.activePositions[pop_lsb(&sm)]; + nodes += pos ? pos->nodes_searched() : 0; + } + + sp.mutex.unlock(); + } + + Threads.mutex.unlock(); + } + Time::point elapsed = Time::now() - SearchTime; bool stillAtFirstMove = Signals.firstRootMove && !Signals.failedLowAtRoot @@ -1773,6 +1782,7 @@ void check_time() { || stillAtFirstMove; if ( (Limits.use_time_management() && noMoreTime) - || (Limits.movetime && elapsed >= Limits.movetime)) + || (Limits.movetime && elapsed >= Limits.movetime) + || (Limits.nodes && nodes >= Limits.nodes)) Signals.stop = true; }