X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=5d2e5175b052bdc35fc5019bdf45dfa39bbd9860;hp=44bd9530d3e6a5f362de24fcb1ce438b5e86d24c;hb=5894c759cd20bac8183f8c53cb833eee23e6b4eb;hpb=e817a55bc6cc60b831f74ce5c180ec8b07c41d8a diff --git a/src/search.cpp b/src/search.cpp index 44bd9530..5d2e5175 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -23,6 +23,7 @@ //// #include +#include #include #include #include @@ -192,9 +193,6 @@ namespace { /// Variables initialized by UCI options - // Minimum number of full depth (i.e. non-reduced) moves at PV and non-PV nodes - int LMRPVMoves, LMRNonPVMoves; - // Depth limit for use of dynamic threat detection Depth ThreatDepth; @@ -235,6 +233,10 @@ namespace { bool UseLogFile; std::ofstream LogFile; + // Natural logarithmic lookup table and its getter function + double lnArray[512]; + inline double ln(int i) { return lnArray[i]; } + // MP related variables int ActiveThreads = 1; Depth MinimumSplitDepth; @@ -319,13 +321,6 @@ namespace { //// Functions //// -//FIXME: HACK -static double lnArray[512]; - -inline double ln(int i) -{ - return lnArray[i]; -} /// perft() is our utility to verify move generation is bug free. All the legal /// moves up to given depth are generated and counted and the sum returned. @@ -428,8 +423,6 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, MateThreatExtension[1] = Depth(get_option_value_int("Mate Threat Extension (PV nodes)")); MateThreatExtension[0] = Depth(get_option_value_int("Mate Threat Extension (non-PV nodes)")); - LMRPVMoves = get_option_value_int("Full Depth Moves (PV nodes)") + 1; - LMRNonPVMoves = get_option_value_int("Full Depth Moves (non-PV nodes)") + 1; ThreatDepth = get_option_value_int("Threat Depth") * OnePly; Chess960 = get_option_value_bool("UCI_Chess960"); @@ -559,20 +552,19 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, /// and initializes the split point stack and the global locks and condition /// objects. -#include //FIXME: HACK - void init_threads() { - // FIXME: HACK!! - for (int i = 0; i < 512; i++) - lnArray[i] = log(double(i)); - volatile int i; + bool ok; #if !defined(_MSC_VER) pthread_t pthread[1]; #endif + // Init our logarithmic lookup table + for (i = 0; i < 512; i++) + lnArray[i] = log(double(i)); // log() returns base-e logarithm + for (i = 0; i < THREAD_MAX; i++) Threads[i].activeSplitPoints = 0; @@ -603,12 +595,18 @@ void init_threads() { for (i = 1; i < THREAD_MAX; i++) { #if !defined(_MSC_VER) - pthread_create(pthread, NULL, init_thread, (void*)(&i)); + ok = (pthread_create(pthread, NULL, init_thread, (void*)(&i)) == 0); #else DWORD iID[1]; - CreateThread(NULL, 0, init_thread, (LPVOID)(&i), 0, iID); + ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&i), 0, iID) != NULL); #endif + if (!ok) + { + cout << "Failed to create thread number " << i << endl; + Application::exit_with_failure(); + } + // Wait until the thread has finished launching while (!Threads[i].running); } @@ -652,6 +650,8 @@ void SearchStack::init(int ply) { pv[ply] = pv[ply + 1] = MOVE_NONE; currentMove = threatMove = MOVE_NONE; reduction = Depth(0); + eval = VALUE_NONE; + evalInfo = NULL; } void SearchStack::initKillers() { @@ -837,7 +837,7 @@ namespace { // If we are pondering or in infinite search, we shouldn't print the // best move before we are told to do so. - if (!AbortSearch && (PonderSearch || InfiniteSearch)) + if (!AbortSearch && !ExactMaxTime && (PonderSearch || InfiniteSearch)) wait_for_stop_or_ponderhit(); else // Print final search statistics @@ -885,7 +885,7 @@ namespace { Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value alpha, Value beta) { Value oldAlpha = alpha; - Value value; + Value value = -VALUE_INFINITE; CheckInfo ci(pos); // Loop through all the moves in the root move list @@ -954,6 +954,8 @@ namespace { { // Try to reduce non-pv search depth by one ply if move seems not problematic, // if the move fails high will be re-searched at full depth. + bool doFullDepthSearch = true; + if ( depth >= 3*OnePly // FIXME was newDepth && !dangerous && !captureOrPromotion @@ -964,13 +966,11 @@ namespace { { ss[0].reduction = Depth(int(floor(red * int(OnePly)))); value = -search(pos, ss, -alpha, newDepth-ss[0].reduction, 1, true, 0); + doFullDepthSearch = (value > alpha); } - else - value = alpha + 1; // Just to trigger next condition - } else - value = alpha + 1; // Just to trigger next condition + } - if (value > alpha) + if (doFullDepthSearch) { value = -search(pos, ss, -alpha, newDepth, 1, true, 0); @@ -1097,7 +1097,6 @@ namespace { assert(threadID >= 0 && threadID < ActiveThreads); Move movesSearched[256]; - EvalInfo ei; StateInfo st; const TTEntry* tte; Move ttMove, move; @@ -1105,7 +1104,7 @@ namespace { Value oldAlpha, value; bool isCheck, mateThreat, singleEvasion, moveIsCheck, captureOrPromotion, dangerous; int moveCount = 0; - Value bestValue = -VALUE_INFINITE; + Value bestValue = value = -VALUE_INFINITE; if (depth < OnePly) return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID); @@ -1118,12 +1117,9 @@ namespace { if (AbortSearch || thread_should_stop(threadID)) return Value(0); - if (pos.is_draw()) + if (pos.is_draw() || ply >= PLY_MAX - 1) return VALUE_DRAW; - if (ply >= PLY_MAX - 1) - return pos.is_check() ? quick_evaluate(pos) : evaluate(pos, ei, threadID); - // Mate distance pruning oldAlpha = alpha; alpha = Max(value_mated_in(ply), alpha); @@ -1210,6 +1206,8 @@ namespace { { // Try to reduce non-pv search depth by one ply if move seems not problematic, // if the move fails high will be re-searched at full depth. + bool doFullDepthSearch = true; + if ( depth >= 3*OnePly && !dangerous && !captureOrPromotion @@ -1221,14 +1219,11 @@ namespace { { ss[ply].reduction = Depth(int(floor(red * int(OnePly)))); value = -search(pos, ss, -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID); + doFullDepthSearch = (value > alpha); } - else - value = alpha + 1; // Just to trigger next condition } - else - value = alpha + 1; // Just to trigger next condition - if (value > alpha) // Go with full depth non-pv search + if (doFullDepthSearch) // Go with full depth non-pv search { ss[ply].reduction = Depth(0); value = -search(pos, ss, -alpha, newDepth, ply+1, true, threadID); @@ -1331,11 +1326,11 @@ namespace { const TTEntry* tte; Move ttMove, move; Depth ext, newDepth; - Value staticValue, nullValue, value, futilityValue, futilityValueScaled; + Value bestValue, staticValue, nullValue, value, futilityValue, futilityValueScaled; bool isCheck, useFutilityPruning, singleEvasion, moveIsCheck, captureOrPromotion, dangerous; bool mateThreat = false; int moveCount = 0; - Value bestValue = -VALUE_INFINITE; + futilityValue = staticValue = bestValue = value = -VALUE_INFINITE; if (depth < OnePly) return qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID); @@ -1348,12 +1343,9 @@ namespace { if (AbortSearch || thread_should_stop(threadID)) return Value(0); - if (pos.is_draw()) + if (pos.is_draw() || ply >= PLY_MAX - 1) return VALUE_DRAW; - if (ply >= PLY_MAX - 1) - return pos.is_check() ? quick_evaluate(pos) : evaluate(pos, ei, threadID); - // Mate distance pruning if (value_mated_in(ply) >= beta) return beta; @@ -1376,23 +1368,26 @@ namespace { } isCheck = pos.is_check(); - ei.futilityMargin = Value(0); // Manually initialize futilityMargin - - // Evaluate the position statically - if (isCheck) - staticValue = quick_evaluate(pos); - else if (tte && (tte->type() & VALUE_TYPE_EVAL)) - staticValue = value_from_tt(tte->value(), ply); - else - staticValue = evaluate(pos, ei, threadID); // Calculate depth dependant futility pruning parameters const int FutilityMoveCountMargin = 3 + (1 << (3 * int(depth) / 8)); const int FutilityValueMargin = 112 * bitScanReverse32(int(depth) * int(depth) / 2); - // Enhance score accuracy with TT value if possible - futilityValue = staticValue + FutilityValueMargin; - staticValue = refine_eval(tte, staticValue, ply); + // Evaluate the position statically + if (!isCheck) + { + if (tte && (tte->type() & VALUE_TYPE_EVAL)) + staticValue = value_from_tt(tte->value(), ply); + else + { + staticValue = evaluate(pos, ei, threadID); + ss[ply].evalInfo = &ei; + } + + ss[ply].eval = staticValue; + futilityValue = staticValue + FutilityValueMargin; + staticValue = refine_eval(tte, staticValue, ply); // Enhance accuracy with TT value if possible + } // Null move search if ( allowNullmove @@ -1445,8 +1440,9 @@ namespace { } // Null move search not allowed, try razoring else if ( !value_is_mate(beta) + && !isCheck && depth < RazorDepth - && staticValue < beta - (depth > OnePly ? NullMoveMargin + 16 * depth : 2*NullMoveMargin) + && staticValue < beta - (NullMoveMargin + 16 * depth) && ss[ply - 1].currentMove != MOVE_NULL && ttMove == MOVE_NONE && !pos.has_pawn_on_7th(pos.side_to_move())) @@ -1459,7 +1455,7 @@ namespace { // Go with internal iterative deepening if we don't have a TT move if (UseIIDAtNonPVNodes && ttMove == MOVE_NONE && depth >= 8*OnePly && - !isCheck && evaluate(pos, ei, threadID) >= beta - IIDMargin) + !isCheck && ss[ply].eval >= beta - IIDMargin) { search(pos, ss, beta, Min(depth/2, depth-2*OnePly), ply, false, threadID); ttMove = ss[ply].pv[ply]; @@ -1544,6 +1540,8 @@ namespace { // Try to reduce non-pv search depth by one ply if move seems not problematic, // if the move fails high will be re-searched at full depth. + bool doFullDepthSearch = true; + if ( depth >= 3*OnePly && !dangerous && !captureOrPromotion @@ -1556,14 +1554,11 @@ namespace { { ss[ply].reduction = Depth(int(floor(red * int(OnePly)))); value = -search(pos, ss, -(beta-1), newDepth-ss[ply].reduction, ply+1, true, threadID); + doFullDepthSearch = (value >= beta); } - else - value = beta; // Just to trigger next condition } - else - value = beta; // Just to trigger next condition - if (value >= beta) // Go with full depth non-pv search + if (doFullDepthSearch) // Go with full depth non-pv search { ss[ply].reduction = Depth(0); value = -search(pos, ss, -(beta-1), newDepth, ply+1, true, threadID); @@ -1657,12 +1652,9 @@ namespace { if (AbortSearch || thread_should_stop(threadID)) return Value(0); - if (pos.is_draw()) + if (pos.is_draw() || ply >= PLY_MAX - 1) return VALUE_DRAW; - if (ply >= PLY_MAX - 1) - return pos.is_check() ? quick_evaluate(pos) : evaluate(pos, ei, threadID); - // Transposition table lookup. At PV nodes, we don't use the TT for // pruning, but only for move ordering. tte = TT.retrieve(pos.get_key()); @@ -1677,7 +1669,6 @@ namespace { } isCheck = pos.is_check(); - ei.futilityMargin = Value(0); // Manually initialize futilityMargin // Evaluate the position statically if (isCheck) @@ -1703,10 +1694,14 @@ namespace { if (bestValue > alpha) alpha = bestValue; + // If we are near beta then try to get a cutoff pushing checks a bit further + bool deepChecks = depth == -OnePly && staticValue >= beta - PawnValueMidgame / 8; + // 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 == 0) will be generated. - MovePicker mp = MovePicker(pos, ttMove, depth, H); + // to search the moves. Because the depth is <= 0 here, only captures, + // queen promotions and checks (only if depth == 0 or depth == -OnePly + // and we are near beta) will be generated. + MovePicker mp = MovePicker(pos, ttMove, deepChecks ? Depth(0) : depth, H); CheckInfo ci(pos); enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame; futilityBase = staticValue + FutilityMarginQS + ei.futilityMargin; @@ -1817,14 +1812,13 @@ namespace { Position pos = Position(sp->pos); CheckInfo ci(pos); SearchStack* ss = sp->sstack[threadID]; - Value value; + Value value = -VALUE_INFINITE; Move move; bool isCheck = pos.is_check(); bool useFutilityPruning = sp->depth < SelectiveDepth && !isCheck; const int FutilityMoveCountMargin = 3 + (1 << (3 * int(sp->depth) / 8)); - const int FutilityValueMargin = 112 * bitScanReverse32(int(sp->depth) * int(sp->depth) / 2); while ( sp->bestValue < sp->beta && !thread_should_stop(threadID) @@ -1858,12 +1852,6 @@ namespace { continue; // Value based pruning - if (sp->futilityValue == VALUE_NONE) - { - EvalInfo ei; - sp->futilityValue = evaluate(pos, ei, threadID) + FutilityValueMargin; - } - Value futilityValueScaled = sp->futilityValue - moveCount * IncrementalFutilityMargin; if (futilityValueScaled < sp->beta) @@ -1885,6 +1873,8 @@ namespace { // Try to reduce non-pv search depth by one ply if move seems not problematic, // if the move fails high will be re-searched at full depth. + bool doFullDepthSearch = true; + if ( !dangerous && !captureOrPromotion && !move_is_castle(move) @@ -1895,14 +1885,11 @@ namespace { { ss[sp->ply].reduction = Depth(int(floor(red * int(OnePly)))); value = -search(pos, ss, -(sp->beta-1), newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID); + doFullDepthSearch = (value >= sp->beta); } - else - value = sp->beta; // Just to trigger next condition } - else - value = sp->beta; // Just to trigger next condition - if (value >= sp->beta) // Go with full depth non-pv search + if (doFullDepthSearch) // Go with full depth non-pv search { ss[sp->ply].reduction = Depth(0); value = -search(pos, ss, -(sp->beta - 1), newDepth, sp->ply+1, true, threadID); @@ -1967,7 +1954,7 @@ namespace { Position pos = Position(sp->pos); CheckInfo ci(pos); SearchStack* ss = sp->sstack[threadID]; - Value value; + Value value = -VALUE_INFINITE; Move move; while ( sp->alpha < sp->beta @@ -1996,6 +1983,8 @@ namespace { // Try to reduce non-pv search depth by one ply if move seems not problematic, // if the move fails high will be re-searched at full depth. + bool doFullDepthSearch = true; + if ( !dangerous && !captureOrPromotion && !move_is_castle(move) @@ -2004,31 +1993,37 @@ namespace { double red = 0.5 + ln(moveCount) * ln(sp->depth / 2) / 6.0; if (red >= 1.0) { + Value localAlpha = sp->alpha; ss[sp->ply].reduction = Depth(int(floor(red * int(OnePly)))); - value = -search(pos, ss, -sp->alpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID); + value = -search(pos, ss, -localAlpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID); + doFullDepthSearch = (value > localAlpha); } - else - value = sp->alpha + 1; // Just to trigger next condition } - else - value = sp->alpha + 1; // Just to trigger next condition - if (value > sp->alpha) // Go with full depth non-pv search + if (doFullDepthSearch) // Go with full depth non-pv search { + Value localAlpha = sp->alpha; ss[sp->ply].reduction = Depth(0); - value = -search(pos, ss, -sp->alpha, newDepth, sp->ply+1, true, threadID); + value = -search(pos, ss, -localAlpha, newDepth, sp->ply+1, true, threadID); - if (value > sp->alpha && value < sp->beta) + if (value > localAlpha && value < sp->beta) { // When the search fails high at ply 1 while searching the first - // move at the root, set the flag failHighPly1. This is used for + // move at the root, set the flag failHighPly1. This is used for // time managment: We don't want to stop the search early in // such cases, because resolving the fail high at ply 1 could // result in a big drop in score at the root. if (sp->ply == 1 && RootMoveNumber == 1) Threads[threadID].failHighPly1 = true; - value = -search_pv(pos, ss, -sp->beta, -sp->alpha, newDepth, sp->ply+1, threadID); + // If another thread has failed high then sp->alpha has been increased + // to be higher or equal then beta, if so, avoid to start a PV search. + localAlpha = sp->alpha; + if (localAlpha < sp->beta) + value = -search_pv(pos, ss, -sp->beta, -localAlpha, newDepth, sp->ply+1, threadID); + else + assert(thread_should_stop(threadID)); + Threads[threadID].failHighPly1 = false; } } @@ -2046,11 +2041,7 @@ namespace { sp->bestValue = value; if (value > sp->alpha) { - sp->alpha = value; - sp_update_pv(sp->parentSstack, ss, sp->ply); - if (value == value_mate_in(sp->ply + 1)) - ss[sp->ply].mateKiller = move; - + // Ask threads to stop before to modify sp->alpha if (value >= sp->beta) { for (int i = 0; i < ActiveThreads; i++) @@ -2059,6 +2050,12 @@ namespace { sp->finished = true; } + + sp->alpha = value; + + sp_update_pv(sp->parentSstack, ss, sp->ply); + if (value == value_mate_in(sp->ply + 1)) + ss[sp->ply].mateKiller = move; } // If we are at ply 1, and we are searching the first root move at // ply 0, set the 'Problem' variable if the score has dropped a lot @@ -2802,6 +2799,8 @@ namespace { // If this thread has been assigned work, launch a search if (Threads[threadID].workIsWaiting) { + assert(!Threads[threadID].idle); + Threads[threadID].workIsWaiting = false; if (Threads[threadID].splitPoint->pvNode) sp_search_pv(Threads[threadID].splitPoint, threadID);