X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=9143f6699192ba8ac9899dd6292081e947a67889;hp=af01050212ceca3ef4c9a4225c4952ede31b683b;hb=5769509d72ab59d1a1856d035c38d84ecdc6f687;hpb=58aee9a9ea522cd9eb40b6a4cc888e37e2da54c5 diff --git a/src/search.cpp b/src/search.cpp index af010502..9143f669 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -66,7 +66,7 @@ namespace { // Futility lookup tables (initialized at startup) and their access functions Value FutilityMargins[16][64]; // [depth][moveNumber] - int FutilityMoveCounts[32]; // [depth] + int FutilityMoveCounts[2][32]; // [improving][depth] inline Value futility_margin(Depth d, int mn) { @@ -75,11 +75,11 @@ namespace { } // Reduction lookup tables (initialized at startup) and their access function - int8_t Reductions[2][64][64]; // [pv][depth][moveNumber] + int8_t Reductions[2][2][64][64]; // [pv][improving][depth][moveNumber] - template inline Depth reduction(Depth d, int mn) { + template inline Depth reduction(bool i, Depth d, int mn) { - return (Depth) Reductions[PvNode][std::min(int(d) / ONE_PLY, 63)][std::min(mn, 63)]; + return (Depth) Reductions[PvNode][i][std::min(int(d) / ONE_PLY, 63)][std::min(mn, 63)]; } size_t PVSize, PVIdx; @@ -136,8 +136,14 @@ void Search::init() { { double pvRed = log(double(hd)) * log(double(mc)) / 3.0; double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25; - Reductions[1][hd][mc] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(ONE_PLY)) : 0); - Reductions[0][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(ONE_PLY)) : 0); + Reductions[1][1][hd][mc] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(ONE_PLY)) : 0); + Reductions[0][1][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(ONE_PLY)) : 0); + + Reductions[1][0][hd][mc] = Reductions[1][1][hd][mc]; + Reductions[0][0][hd][mc] = Reductions[0][1][hd][mc]; + + if (Reductions[0][0][hd][mc] > 2 * ONE_PLY) + Reductions[0][0][hd][mc] += ONE_PLY; } // Init futility margins array @@ -146,14 +152,18 @@ void Search::init() { // Init futility move count array for (d = 0; d < 32; d++) - FutilityMoveCounts[d] = int(3.001 + 0.3 * pow(double(d), 1.8)); + { + FutilityMoveCounts[1][d] = int(3.001 + 0.3 * pow(double(d), 1.8)); + FutilityMoveCounts[0][d] = d < 5 ? FutilityMoveCounts[1][d] + : 3 * FutilityMoveCounts[1][d] / 4; + } } /// Search::perft() is our utility to verify move generation. All the leaf nodes /// up to the given depth are generated and counted and the sum returned. -size_t Search::perft(Position& pos, Depth depth) { +static size_t perft(Position& pos, Depth depth) { StateInfo st; size_t cnt = 0; @@ -163,12 +173,15 @@ size_t Search::perft(Position& pos, Depth depth) { for (MoveList it(pos); *it; ++it) { pos.do_move(*it, st, ci, pos.move_gives_check(*it, ci)); - cnt += leaf ? MoveList(pos).size() : perft(pos, depth - ONE_PLY); + cnt += leaf ? MoveList(pos).size() : ::perft(pos, depth - ONE_PLY); pos.undo_move(*it); } return cnt; } +size_t Search::perft(Position& pos, Depth depth) { + return depth > ONE_PLY ? ::perft(pos, depth) : MoveList(pos).size(); +} /// Search::think() is the external interface to Stockfish's search, and is /// called by the main thread when the program receives the UCI 'go' command. It @@ -212,7 +225,7 @@ void Search::think() { else DrawValue[WHITE] = DrawValue[BLACK] = VALUE_DRAW; - if (Options["Use Search Log"]) + if (Options["Write Search Log"]) { Log log(Options["Search Log Filename"]); log << "\nSearching: " << RootPos.fen() @@ -228,7 +241,7 @@ void Search::think() { for (size_t i = 0; i < Threads.size(); i++) Threads[i]->maxPly = 0; - Threads.sleepWhileIdle = Options["Use Sleeping Threads"]; + Threads.sleepWhileIdle = Options["Idle Threads Sleep"]; // Set best timer interval to avoid lagging under time pressure. Timer is // used to check for remaining available thinking time. @@ -244,7 +257,7 @@ void Search::think() { Threads.timer->msec = 0; // Stop the timer Threads.sleepWhileIdle = true; // Send idle threads to sleep - if (Options["Use Search Log"]) + if (Options["Write Search Log"]) { Time::point elapsed = Time::now() - SearchTime + 1; @@ -291,11 +304,11 @@ namespace { void id_loop(Position& pos) { - Stack stack[MAX_PLY_PLUS_2], *ss = stack+1; // To allow referencing (ss-1) + Stack stack[MAX_PLY_PLUS_3], *ss = stack+2; // To allow referencing (ss-2) int depth, prevBestMoveChanges; Value bestValue, alpha, beta, delta; - memset(ss-1, 0, 4 * sizeof(Stack)); + std::memset(ss-2, 0, 5 * sizeof(Stack)); (ss-1)->currentMove = MOVE_NULL; // Hack to skip update gains depth = BestMoveChanges = 0; @@ -364,6 +377,12 @@ namespace { if (Signals.stop) return; + // When failing high/low give some update (without cluttering + // the UI) before to research. + if ( (bestValue <= alpha || bestValue >= beta) + && Time::now() - SearchTime > 3000) + sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl; + // In case of failing low/high increase aspiration window and // research, otherwise exit the loop. if (bestValue <= alpha) @@ -382,10 +401,6 @@ namespace { delta += delta / 2; assert(alpha >= -VALUE_INFINITE && beta <= VALUE_INFINITE); - - // Give some update (without cluttering the UI) before to research - if (Time::now() - SearchTime > 3000) - sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl; } // Sort the PV lines searched so far and update the GUI @@ -399,7 +414,7 @@ namespace { if (skill.enabled() && skill.time_to_pick(depth)) skill.pick_move(); - if (Options["Use Search Log"]) + if (Options["Write Search Log"]) { RootMove& rm = RootMoves[0]; if (skill.best != MOVE_NONE) @@ -491,13 +506,12 @@ namespace { Depth ext, newDepth; Value bestValue, value, ttValue; Value eval, nullValue, futilityValue; - bool inCheck, givesCheck, pvMove, singularExtensionNode; + bool inCheck, givesCheck, pvMove, singularExtensionNode, improving; bool captureOrPromotion, dangerous, doFullDepthSearch; int moveCount, quietCount; // Step 1. Initialize node Thread* thisThread = pos.this_thread(); - moveCount = quietCount = 0; inCheck = pos.checkers(); if (SpNode) @@ -515,6 +529,7 @@ namespace { goto moves_loop; } + moveCount = quietCount = 0; bestValue = -VALUE_INFINITE; ss->currentMove = threatMove = (ss+1)->excludedMove = bestMove = MOVE_NONE; ss->ply = (ss-1)->ply + 1; @@ -618,7 +633,7 @@ namespace { Gains.update(pos.piece_on(to), to, -(ss-1)->staticEval - ss->staticEval); } - // Step 6. Razoring (is omitted in PV nodes) + // Step 6. Razoring (skipped when in check) if ( !PvNode && depth < 4 * ONE_PLY && eval + razor_margin(depth) < beta @@ -634,7 +649,7 @@ namespace { return v; } - // Step 7. Static null move pruning (is omitted in PV nodes) + // Step 7. Static null move pruning (skipped when in check) // We're betting that the opponent doesn't have a move that will reduce // the score by more than futility_margin(depth) if we do a null move. if ( !PvNode @@ -705,7 +720,7 @@ namespace { } } - // Step 9. ProbCut (is omitted in PV nodes) + // Step 9. ProbCut (skipped when in check) // If we have a very good capture (i.e. SEE > seeValues[captured_piece_type]) // and a reduced search returns a value much above beta, we can (almost) safely // prune the previous move. @@ -736,7 +751,7 @@ namespace { } } - // Step 10. Internal iterative deepening + // Step 10. Internal iterative deepening (skipped when in check) if ( depth >= (PvNode ? 5 * ONE_PLY : 8 * ONE_PLY) && ttMove == MOVE_NONE && (PvNode || ss->staticEval + Value(256) >= beta)) @@ -757,9 +772,13 @@ moves_loop: // When in check and at SpNode search starts from here Move countermoves[] = { Countermoves[pos.piece_on(prevMoveSq)][prevMoveSq].first, Countermoves[pos.piece_on(prevMoveSq)][prevMoveSq].second }; - MovePicker mp(pos, ttMove, depth, History, countermoves, ss, PvNode ? -VALUE_INFINITE : beta); + MovePicker mp(pos, ttMove, depth, History, countermoves, ss); CheckInfo ci(pos); value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc + improving = ss->staticEval >= (ss-2)->staticEval + || ss->staticEval == VALUE_NONE + ||(ss-2)->staticEval == VALUE_NONE; + singularExtensionNode = !RootNode && !SpNode && depth >= (PvNode ? 6 * ONE_PLY : 8 * ONE_PLY) @@ -799,7 +818,7 @@ moves_loop: // When in check and at SpNode search starts from here { Signals.firstRootMove = (moveCount == 1); - if (thisThread == Threads.main_thread() && Time::now() - SearchTime > 3000) + if (thisThread == Threads.main() && Time::now() - SearchTime > 3000) sync_cout << "info depth " << depth / ONE_PLY << " currmove " << move_to_uci(move, pos.is_chess960()) << " currmovenumber " << moveCount + PVIdx << sync_endl; @@ -856,7 +875,7 @@ moves_loop: // When in check and at SpNode search starts from here { // Move count based pruning if ( depth < 16 * ONE_PLY - && moveCount >= FutilityMoveCounts[depth] + && moveCount >= FutilityMoveCounts[improving][depth] && (!threatMove || !refutes(pos, move, threatMove))) { if (SpNode) @@ -868,7 +887,7 @@ moves_loop: // When in check and at SpNode search starts from here // Value based pruning // We illogically ignore reduction condition depth >= 3*ONE_PLY for predicted depth, // but fixing this made program slightly weaker. - Depth predictedDepth = newDepth - reduction(depth, moveCount); + Depth predictedDepth = newDepth - reduction(improving, depth, moveCount); futilityValue = ss->staticEval + ss->evalMargin + futility_margin(predictedDepth, moveCount) + Gains[pos.piece_moved(move)][to_sq(move)]; @@ -927,7 +946,7 @@ moves_loop: // When in check and at SpNode search starts from here && move != ss->killers[0] && move != ss->killers[1]) { - ss->reduction = reduction(depth, moveCount); + ss->reduction = reduction(improving, depth, moveCount); if (!PvNode && cutNode) ss->reduction += ONE_PLY; @@ -1121,7 +1140,7 @@ moves_loop: // When in check and at SpNode search starts from here Key posKey; Move ttMove, move, bestMove; Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha; - bool givesCheck, enoughMaterial, evasionPrunable; + bool givesCheck, evasionPrunable; Depth ttDepth; // To flag BOUND_EXACT a node with eval above alpha and no available moves @@ -1163,7 +1182,6 @@ moves_loop: // When in check and at SpNode search starts from here { ss->staticEval = ss->evalMargin = VALUE_NONE; bestValue = futilityBase = -VALUE_INFINITE; - enoughMaterial = false; } else { @@ -1191,7 +1209,6 @@ moves_loop: // When in check and at SpNode search starts from here alpha = bestValue; futilityBase = ss->staticEval + ss->evalMargin + Value(128); - enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMg; } // Initialize a MovePicker object for the current position, and prepare @@ -1213,7 +1230,6 @@ moves_loop: // When in check and at SpNode search starts from here && !InCheck && !givesCheck && move != ttMove - && enoughMaterial && type_of(move) != PROMOTION && !pos.is_passed_pawn_push(move)) { @@ -1238,8 +1254,7 @@ moves_loop: // When in check and at SpNode search starts from here } // Detect non-capture evasions that are candidate to be pruned - evasionPrunable = !PvNode - && InCheck + evasionPrunable = InCheck && bestValue > VALUE_MATED_IN_MAX_PLY && !pos.is_capture(move) && !pos.can_castle(pos.side_to_move()); @@ -1453,7 +1468,7 @@ moves_loop: // When in check and at SpNode search starts from here | (attacks_bb(m2to, occ) & pos.pieces(color_of(pc), QUEEN, BISHOP)); // Verify attackers are triggered by our move and not already existing - if (xray && (xray ^ (xray & pos.attacks_from(m2to)))) + if (unlikely(xray) && (xray & ~pos.attacks_from(m2to))) return true; } @@ -1561,7 +1576,7 @@ moves_loop: // When in check and at SpNode search starts from here void RootMove::extract_pv_from_tt(Position& pos) { - StateInfo state[MAX_PLY_PLUS_2], *st = state; + StateInfo state[MAX_PLY_PLUS_3], *st = state; const TTEntry* tte; int ply = 0; Move m = pv[0]; @@ -1594,7 +1609,7 @@ void RootMove::extract_pv_from_tt(Position& pos) { void RootMove::insert_pv_in_tt(Position& pos) { - StateInfo state[MAX_PLY_PLUS_2], *st = state; + StateInfo state[MAX_PLY_PLUS_3], *st = state; const TTEntry* tte; int ply = 0; @@ -1664,14 +1679,15 @@ void Thread::idle_loop() { Threads.mutex.lock(); assert(searching); + assert(activeSplitPoint); SplitPoint* sp = activeSplitPoint; Threads.mutex.unlock(); - Stack stack[MAX_PLY_PLUS_2], *ss = stack+1; // To allow referencing (ss-1) + Stack stack[MAX_PLY_PLUS_3], *ss = stack+2; // To allow referencing (ss-2) Position pos(*sp->pos, this); - memcpy(ss-1, sp->ss-1, 4 * sizeof(Stack)); + std::memcpy(ss-2, sp->ss-2, 5 * sizeof(Stack)); ss->splitPoint = sp; sp->mutex.lock();