X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=c44d150f7008826abd9fe08ac4c1b0c4798e4985;hp=3dbcb526dbff7187014d5d477df9ae7792f03f04;hb=3c7eebb48d5239cf363c54e082686f5559174518;hpb=55745f410547f22b1edce873b38cc3ce5f3ace5f diff --git a/src/search.cpp b/src/search.cpp index 3dbcb526..c44d150f 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -23,6 +23,7 @@ //// #include +#include #include #include #include @@ -172,9 +173,9 @@ namespace { // best move from the previous iteration, Problem is set back to false. const Value NoProblemMargin = Value(0x14); - // Null move margin. A null move search will not be done if the approximate + // Null move margin. A null move search will not be done if the static // evaluation of the position is more than NullMoveMargin below beta. - const Value NullMoveMargin = Value(0x300); + const Value NullMoveMargin = Value(0x200); // If the TT move is at least SingleReplyMargin better then the // remaining ones we will extend it. @@ -190,18 +191,8 @@ namespace { // Depth limit for razoring const Depth RazorDepth = 4 * OnePly; - // Remaining depth: 1 ply 1.5 ply 2 ply 2.5 ply 3 ply 3.5 ply - const Value RazorMargins[6] = { Value(0x180), Value(0x300), Value(0x300), Value(0x3C0), Value(0x3C0), Value(0x3C0) }; - - // Remaining depth: 1 ply 1.5 ply 2 ply 2.5 ply 3 ply 3.5 ply - const Value RazorApprMargins[6] = { Value(0x520), Value(0x300), Value(0x300), Value(0x300), Value(0x300), Value(0x300) }; - - /// 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; @@ -223,6 +214,9 @@ namespace { IterationInfoType IterationInfo[PLY_MAX_PLUS_2]; int BestMoveChangesByIteration[PLY_MAX_PLUS_2]; + // Search window management + int AspirationDelta; + // MultiPV mode int MultiPV; @@ -242,6 +236,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; @@ -268,11 +266,10 @@ namespace { // History table History H; - /// Functions Value id_loop(const Position& pos, Move searchMoves[]); - Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value alpha, Value beta); + Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value& oldAlpha, Value& beta); Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID); Value search(Position& pos, SearchStack ss[], Value beta, Depth depth, int ply, bool allowNullmove, int threadID, Move excludedMove = MOVE_NONE); Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID); @@ -289,8 +286,10 @@ namespace { bool ok_to_prune(const Position& pos, Move m, Move threat); bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply); Value refine_eval(const TTEntry* tte, Value defaultEval, int ply); + Depth calculate_reduction(double baseReduction, int moveCount, Depth depth, double reductionInhibitor); void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount); void update_killers(Move m, SearchStack& ss); + void update_gains(const Position& pos, Move move, Value before, Value after); bool fail_high_ply_1(); int current_search_time(); @@ -326,13 +325,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. @@ -435,8 +427,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"); @@ -456,6 +446,10 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, { ActiveThreads = newActiveThreads; init_eval(ActiveThreads); + // HACK: init_eval() destroys the static castleRightsMask[] array in the + // Position class. The below line repairs the damage. + Position p(pos.to_fen()); + assert(pos.is_ok()); } // Wake up sleeping threads @@ -566,20 +560,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; @@ -610,12 +603,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); } @@ -659,6 +658,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() { @@ -733,7 +734,10 @@ namespace { int prevDelta1 = IterationInfo[Iteration - 1].speculatedValue - IterationInfo[Iteration - 2].speculatedValue; int prevDelta2 = IterationInfo[Iteration - 2].speculatedValue - IterationInfo[Iteration - 3].speculatedValue; - int delta = Max(2 * abs(prevDelta1) + abs(prevDelta2), ProblemMargin); + int delta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16); + + delta = (delta + 7) / 8 * 8; // Round to match grainSize + AspirationDelta = delta; alpha = Max(IterationInfo[Iteration - 1].value - delta, -VALUE_INFINITE); beta = Min(IterationInfo[Iteration - 1].value + delta, VALUE_INFINITE); @@ -844,7 +848,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 (PonderSearch || InfiniteSearch) + if (!AbortSearch && (PonderSearch || InfiniteSearch)) wait_for_stop_or_ponderhit(); else // Print final search statistics @@ -889,11 +893,23 @@ namespace { // similar to search_pv except that it uses a different move ordering // scheme and prints some information to the standard output. - Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value alpha, Value beta) { + Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value& oldAlpha, Value& beta) { - Value oldAlpha = alpha; + Value alpha = oldAlpha; Value value; CheckInfo ci(pos); + int researchCount = 0; + bool isCheck = pos.is_check(); + + // Evaluate the position statically + EvalInfo ei; + if (!isCheck) + ss[0].eval = evaluate(pos, ei, 0); + else + ss[0].eval = VALUE_NONE; + + while(1) // Fail low loop + { // Loop through all the moves in the root move list for (int i = 0; i < rml.move_count() && !AbortSearch; i++) @@ -936,10 +952,15 @@ namespace { ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous); newDepth = depth + ext; + value = - VALUE_INFINITE; + + while (1) // Fail high loop + { + // Make the move, and search it pos.do_move(move, st, ci, moveIsCheck); - if (i < MultiPV) + if (i < MultiPV || value > alpha) { // Aspiration window is disabled in multi-pv case if (MultiPV > 1) @@ -961,6 +982,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 @@ -971,14 +994,13 @@ 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) { + ss[0].reduction = Depth(0); value = -search(pos, ss, -alpha, newDepth, 1, true, 0); if (value > alpha) @@ -995,6 +1017,46 @@ namespace { pos.undo_move(move); + if (AbortSearch || value < beta) + break; // We are not failing high + + // We are failing high and going to do a research. It's important to update score + // before research in case we run out of time while researching. + rml.set_move_score(i, value); + update_pv(ss, 0); + TT.extract_pv(pos, ss[0].pv, PLY_MAX); + rml.set_move_pv(i, ss[0].pv); + + // Print search information to the standard output + cout << "info depth " << Iteration + << " score " << value_to_string(value) + << ((value >= beta) ? " lowerbound" : + ((value <= alpha)? " upperbound" : "")) + << " time " << current_search_time() + << " nodes " << nodes_searched() + << " nps " << nps() + << " pv "; + + for (int j = 0; ss[0].pv[j] != MOVE_NONE && j < PLY_MAX; j++) + cout << ss[0].pv[j] << " "; + + cout << endl; + + if (UseLogFile) + { + ValueType type = (value >= beta ? VALUE_TYPE_LOWER + : (value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT)); + + LogFile << pretty_pv(pos, current_search_time(), Iteration, + nodes_searched(), value, type, ss[0].pv) << endl; + } + + // Prepare for research + researchCount++; + beta = Min(beta + AspirationDelta * (1 << researchCount), VALUE_INFINITE); + + } // End of fail high loop + // Finished searching the move. If AbortSearch is true, the search // was aborted because the user interrupted the search or because we // ran out of time. In this case, the return value of the search cannot @@ -1089,6 +1151,17 @@ namespace { FailLow = (alpha == oldAlpha); } + + if (AbortSearch || alpha > oldAlpha) + break; // End search, we are not failing low + + // Prepare for research + researchCount++; + alpha = Max(alpha - AspirationDelta * (1 << researchCount), -VALUE_INFINITE); + oldAlpha = alpha; + + } // Fail low loop + return alpha; } @@ -1104,7 +1177,6 @@ namespace { assert(threadID >= 0 && threadID < ActiveThreads); Move movesSearched[256]; - EvalInfo ei; StateInfo st; const TTEntry* tte; Move ttMove, move; @@ -1112,7 +1184,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); @@ -1125,12 +1197,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); @@ -1160,9 +1229,18 @@ namespace { tte = TT.retrieve(pos.get_key()); } + isCheck = pos.is_check(); + if (!isCheck) + { + // Update gain statistics of the previous move that lead + // us in this position. + EvalInfo ei; + ss[ply].eval = evaluate(pos, ei, threadID); + update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval); + } + // Initialize a MovePicker object for the current position, and prepare // to search all moves - isCheck = pos.is_check(); mateThreat = pos.has_mate_threat(opposite_color(pos.side_to_move())); CheckInfo ci(pos); MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]); @@ -1217,6 +1295,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 @@ -1228,14 +1308,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); @@ -1338,11 +1415,11 @@ namespace { const TTEntry* tte; Move ttMove, move; Depth ext, newDepth; - Value staticValue, nullValue, value, futilityValue, futilityValueScaled; - bool isCheck, useFutilityPruning, singleEvasion, moveIsCheck, captureOrPromotion, dangerous; + Value bestValue, staticValue, nullValue, value, futilityValue, futilityValueScaled; + bool isCheck, 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); @@ -1355,12 +1432,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; @@ -1383,23 +1457,36 @@ 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); + const int PostFutilityValueMargin = 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 + PostFutilityValueMargin; //FIXME: Remove me, only for split + staticValue = refine_eval(tte, staticValue, ply); // Enhance accuracy with TT value if possible + update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval); + } + + // Do a "stand pat". If we are above beta by a good margin then + // return immediately. + // FIXME: test with added condition 'allowNullmove || depth <= OnePly' and !value_is_mate(beta) + // FIXME: test with modified condition 'depth < RazorDepth' + if ( !isCheck + && depth < SelectiveDepth + && staticValue - PostFutilityValueMargin >= beta) + return staticValue - PostFutilityValueMargin; // Null move search if ( allowNullmove @@ -1452,13 +1539,14 @@ namespace { } // Null move search not allowed, try razoring else if ( !value_is_mate(beta) + && !isCheck && depth < RazorDepth - && staticValue < beta - RazorApprMargins[int(depth) - 2] + && staticValue < beta - (NullMoveMargin + 16 * depth) && ss[ply - 1].currentMove != MOVE_NULL && ttMove == MOVE_NONE && !pos.has_pawn_on_7th(pos.side_to_move())) { - Value rbeta = beta - RazorMargins[int(depth) - 2]; + Value rbeta = beta - (NullMoveMargin + 16 * depth); Value v = qsearch(pos, ss, rbeta-1, rbeta, Depth(0), ply, threadID); if (v < rbeta) return v; @@ -1466,7 +1554,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]; @@ -1477,7 +1565,6 @@ namespace { // to search all moves. MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]); CheckInfo ci(pos); - useFutilityPruning = depth < SelectiveDepth && !isCheck; // Loop through all legal moves until no moves remain or a beta cutoff occurs while ( bestValue < beta @@ -1523,10 +1610,41 @@ namespace { // Update current move movesSearched[moveCount++] = ss[ply].currentMove = move; + // Futility pruning for captures + // FIXME: test disabling 'Futility pruning for captures' + // FIXME: test with 'newDepth < RazorDepth' + Color them = opposite_color(pos.side_to_move()); + + if ( !isCheck + && newDepth < SelectiveDepth + && !dangerous + && pos.move_is_capture(move) + && !pos.move_is_check(move, ci) + && !move_is_promotion(move) + && move != ttMove + && !move_is_ep(move) + && (pos.type_of_piece_on(move_to(move)) != PAWN || !pos.pawn_is_passed(them, move_to(move)))) // Do not prune passed pawn captures + { + int preFutilityValueMargin = 0; + + if (newDepth >= OnePly) + preFutilityValueMargin = 112 * bitScanReverse32(int(newDepth) * int(newDepth) / 2); + + Value futilityCaptureValue = ss[ply].eval + pos.endgame_value_of_piece_on(move_to(move)) + preFutilityValueMargin + ei.futilityMargin + 90; + + if (futilityCaptureValue < beta) + { + if (futilityCaptureValue > bestValue) + bestValue = futilityCaptureValue; + continue; + } + } + // Futility pruning - if ( useFutilityPruning + if ( !isCheck && !dangerous && !captureOrPromotion + && !move_is_castle(move) && move != ttMove) { // Move count based pruning @@ -1536,13 +1654,29 @@ namespace { continue; // Value based pruning - futilityValueScaled = futilityValue - moveCount * IncrementalFutilityMargin; + Depth predictedDepth = newDepth; - if (futilityValueScaled < beta) + //FIXME HACK: awful code duplication + double red = 0.5 + ln(moveCount) * ln(depth / 2) / 3.0; + if (red >= 1.0) + predictedDepth -= int(floor(red * int(OnePly))); + + if (predictedDepth < SelectiveDepth) { - if (futilityValueScaled > bestValue) - bestValue = futilityValueScaled; - continue; + int preFutilityValueMargin = 0; + if (predictedDepth >= OnePly) + preFutilityValueMargin = 112 * bitScanReverse32(int(predictedDepth) * int(predictedDepth) / 2); + + preFutilityValueMargin += H.gain(pos.piece_on(move_from(move)), move_from(move), move_to(move)) + 45; + + futilityValueScaled = ss[ply].eval + preFutilityValueMargin - moveCount * IncrementalFutilityMargin; + + if (futilityValueScaled < beta) + { + if (futilityValueScaled > bestValue) + bestValue = futilityValueScaled; + continue; + } } } @@ -1551,6 +1685,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 @@ -1563,14 +1699,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); @@ -1598,7 +1731,7 @@ namespace { && idle_thread_exists(threadID) && !AbortSearch && !thread_should_stop(threadID) - && split(pos, ss, ply, &beta, &beta, &bestValue, futilityValue, + && split(pos, ss, ply, &beta, &beta, &bestValue, futilityValue, //FIXME: SMP & futilityValue depth, &moveCount, &mp, threadID, false)) break; } @@ -1651,7 +1784,7 @@ namespace { StateInfo st; Move ttMove, move; Value staticValue, bestValue, value, futilityBase, futilityValue; - bool isCheck, enoughMaterial, moveIsCheck; + bool isCheck, enoughMaterial, moveIsCheck, evasionPrunable; const TTEntry* tte = NULL; int moveCount = 0; bool pvNode = (beta - alpha != 1); @@ -1664,12 +1797,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()); @@ -1684,7 +1814,6 @@ namespace { } isCheck = pos.is_check(); - ei.futilityMargin = Value(0); // Manually initialize futilityMargin // Evaluate the position statically if (isCheck) @@ -1694,6 +1823,12 @@ namespace { else staticValue = evaluate(pos, ei, threadID); + if (!isCheck) + { + ss[ply].eval = staticValue; + update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval); + } + // Initialize "stand pat score", and return it immediately if it is // at least beta. bestValue = staticValue; @@ -1710,10 +1845,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; @@ -1752,8 +1891,15 @@ namespace { } } - // Don't search captures and checks with negative SEE values - if ( !isCheck + // Detect blocking evasions that are candidate to be pruned + evasionPrunable = isCheck + && bestValue != -VALUE_INFINITE + && !pos.move_is_capture(move) + && pos.type_of_piece_on(move_from(move)) != KING + && !pos.can_castle(pos.side_to_move()); + + // Don't search moves with negative SEE values + if ( (!isCheck || evasionPrunable) && move != ttMove && !move_is_promotion(move) && pos.see_sign(move) < 0) @@ -1821,34 +1967,34 @@ namespace { assert(threadID >= 0 && threadID < ActiveThreads); assert(ActiveThreads > 1); - Position pos = Position(sp->pos); + Position pos(*sp->pos); CheckInfo ci(pos); SearchStack* ss = sp->sstack[threadID]; - Value value; + Value value = -VALUE_INFINITE; Move move; + int moveCount; 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 + while ( lock_grab_bool(&(sp->lock)) + && sp->bestValue < sp->beta && !thread_should_stop(threadID) - && (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE) + && (move = sp->mp->get_next_move()) != MOVE_NONE) { + moveCount = ++sp->moves; + lock_release(&(sp->lock)); + assert(move_is_ok(move)); bool moveIsCheck = pos.move_is_check(move, ci); bool captureOrPromotion = pos.move_is_capture_or_promotion(move); - lock_grab(&(sp->lock)); - int moveCount = ++sp->moves; - lock_release(&(sp->lock)); - ss[sp->ply].currentMove = move; - // Decide the new search depth. + // Decide the new search depth bool dangerous; Depth ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, false, false, &dangerous); Depth newDepth = sp->depth - OnePly + ext; @@ -1865,12 +2011,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) @@ -1892,6 +2032,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) @@ -1902,14 +2044,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); @@ -1919,7 +2058,10 @@ namespace { assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); if (thread_should_stop(threadID)) + { + lock_grab(&(sp->lock)); break; + } // New best move? if (value > sp->bestValue) // Less then 2% of cases @@ -1942,7 +2084,7 @@ namespace { } } - lock_grab(&(sp->lock)); + /* Here we have the lock still grabbed */ // If this is the master thread and we have been asked to stop because of // a beta cutoff higher up in the tree, stop all slave threads. @@ -1971,28 +2113,29 @@ namespace { assert(threadID >= 0 && threadID < ActiveThreads); assert(ActiveThreads > 1); - Position pos = Position(sp->pos); + Position pos(*sp->pos); CheckInfo ci(pos); SearchStack* ss = sp->sstack[threadID]; - Value value; + Value value = -VALUE_INFINITE; + int moveCount; Move move; - while ( sp->alpha < sp->beta + while ( lock_grab_bool(&(sp->lock)) + && sp->alpha < sp->beta && !thread_should_stop(threadID) - && (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE) + && (move = sp->mp->get_next_move()) != MOVE_NONE) { - bool moveIsCheck = pos.move_is_check(move, ci); - bool captureOrPromotion = pos.move_is_capture_or_promotion(move); + moveCount = ++sp->moves; + lock_release(&(sp->lock)); assert(move_is_ok(move)); - lock_grab(&(sp->lock)); - int moveCount = ++sp->moves; - lock_release(&(sp->lock)); + bool moveIsCheck = pos.move_is_check(move, ci); + bool captureOrPromotion = pos.move_is_capture_or_promotion(move); ss[sp->ply].currentMove = move; - // Decide the new search depth. + // Decide the new search depth bool dangerous; Depth ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous); Depth newDepth = sp->depth - OnePly + ext; @@ -2003,6 +2146,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) @@ -2011,31 +2156,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; } } @@ -2044,41 +2195,49 @@ namespace { assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); if (thread_should_stop(threadID)) + { + lock_grab(&(sp->lock)); break; + } // New best move? - lock_grab(&(sp->lock)); - if (value > sp->bestValue && !thread_should_stop(threadID)) + if (value > sp->bestValue) // Less then 2% of cases { - sp->bestValue = value; - if (value > sp->alpha) + lock_grab(&(sp->lock)); + if (value > sp->bestValue && !thread_should_stop(threadID)) { - 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 (value >= sp->beta) + sp->bestValue = value; + if (value > sp->alpha) { - for (int i = 0; i < ActiveThreads; i++) - if (i != threadID && (i == sp->master || sp->slaves[i])) - Threads[i].stop = true; + // Ask threads to stop before to modify sp->alpha + if (value >= sp->beta) + { + for (int i = 0; i < ActiveThreads; i++) + if (i != threadID && (i == sp->master || sp->slaves[i])) + Threads[i].stop = true; - sp->finished = true; + 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 - // (from the computer's point of view) since the previous iteration. - if ( sp->ply == 1 - && Iteration >= 2 - && -value <= IterationInfo[Iteration-1].value - ProblemMargin) - Problem = true; + // 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 + // (from the computer's point of view) since the previous iteration. + if ( sp->ply == 1 + && Iteration >= 2 + && -value <= IterationInfo[Iteration-1].value - ProblemMargin) + Problem = true; + } + lock_release(&(sp->lock)); } - lock_release(&(sp->lock)); } - lock_grab(&(sp->lock)); + /* Here we have the lock still grabbed */ // If this is the master thread and we have been asked to stop because of // a beta cutoff higher up in the tree, stop all slave threads. @@ -2457,9 +2616,8 @@ namespace { Square mfrom, mto, tfrom, tto; - // Prune if there isn't any threat move and - // is not a castling move (common case). - if (threat == MOVE_NONE && !move_is_castle(m)) + // Prune if there isn't any threat move + if (threat == MOVE_NONE) return true; mfrom = move_from(m); @@ -2467,15 +2625,11 @@ namespace { tfrom = move_from(threat); tto = move_to(threat); - // Case 1: Castling moves are never pruned - if (move_is_castle(m)) - return false; - - // Case 2: Don't prune moves which move the threatened piece + // Case 1: Don't prune moves which move the threatened piece if (mfrom == tto) return false; - // Case 3: If the threatened piece has value less than or equal to the + // Case 2: If the threatened piece has value less than or equal to the // value of the threatening piece, don't prune move which defend it. if ( pos.move_is_capture(threat) && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto) @@ -2483,7 +2637,7 @@ namespace { && pos.move_attacks_square(m, tto)) return false; - // Case 4: If the moving piece in the threatened move is a slider, don't + // Case 3: If the moving piece in the threatened move is a slider, don't // prune safe moves which block its ray. if ( piece_is_slider(pos.piece_on(tfrom)) && bit_is_set(squares_between(tfrom, tto), mto) @@ -2527,6 +2681,20 @@ namespace { return defaultEval; } + // calculate_reduction() returns reduction in plies based on + // moveCount and depth. Reduction is always at least one ply. + + Depth calculate_reduction(double baseReduction, int moveCount, Depth depth, double reductionInhibitor) { + + double red = baseReduction + ln(moveCount) * ln(depth / 2) / reductionInhibitor; + + if (red >= 1.0) + return Depth(int(floor(red * int(OnePly)))); + else + return Depth(0); + + } + // update_history() registers a good move that produced a beta-cutoff // in history and marks as failures all the other moves of that ply. @@ -2564,6 +2732,21 @@ namespace { } + // update_gains() updates the gains table of a non-capture move given + // the static position evaluation before and after the move. + + void update_gains(const Position& pos, Move m, Value before, Value after) { + + if ( m != MOVE_NULL + && before != VALUE_NONE + && after != VALUE_NONE + && pos.captured_piece() == NO_PIECE_TYPE + && !move_is_castle(m) + && !move_is_promotion(m)) + H.set_gain(pos.piece_on(move_to(m)), move_from(m), move_to(m), -(before + after)); + } + + // fail_high_ply_1() checks if some thread is currently resolving a fail // high at ply 1 at the node below the first root node. This information // is used for time management. @@ -2809,6 +2992,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); @@ -2895,7 +3080,10 @@ namespace { if (!Threads[slave].idle || slave == master) return false; - if (Threads[slave].activeSplitPoints == 0) + // Make a local copy to be sure doesn't change under our feet + int localActiveSplitPoints = Threads[slave].activeSplitPoints; + + if (localActiveSplitPoints == 0) // No active split points means that the thread is available as // a slave for any other thread. return true; @@ -2903,8 +3091,10 @@ namespace { if (ActiveThreads == 2) return true; - // Apply the "helpful master" concept if possible - if (SplitPointStack[slave][Threads[slave].activeSplitPoints - 1].slaves[master]) + // Apply the "helpful master" concept if possible. Use localActiveSplitPoints + // that is known to be > 0, instead of Threads[slave].activeSplitPoints that + // could have been set to 0 by another thread leading to an out of bound access. + if (SplitPointStack[slave][localActiveSplitPoints - 1].slaves[master]) return true; return false; @@ -2954,7 +3144,6 @@ namespace { assert(ActiveThreads > 1); SplitPoint* splitPoint; - int i; lock_grab(&MPLock); @@ -2971,7 +3160,7 @@ namespace { splitPoint = SplitPointStack[master] + Threads[master].activeSplitPoints; Threads[master].activeSplitPoints++; - // Initialize the split point object and copy current position + // Initialize the split point object splitPoint->parent = Threads[master].splitPoint; splitPoint->finished = false; splitPoint->ply = ply; @@ -2985,37 +3174,40 @@ namespace { splitPoint->mp = mp; splitPoint->moves = *moves; splitPoint->cpus = 1; - splitPoint->pos.copy(p); + splitPoint->pos = &p; splitPoint->parentSstack = sstck; - for (i = 0; i < ActiveThreads; i++) + for (int i = 0; i < ActiveThreads; i++) splitPoint->slaves[i] = 0; - // Copy the current search stack to the master thread - memcpy(splitPoint->sstack[master], sstck, (ply+1) * sizeof(SearchStack)); + Threads[master].idle = false; + Threads[master].stop = false; Threads[master].splitPoint = splitPoint; - // Make copies of the current position and search stack for each thread - for (i = 0; i < ActiveThreads && splitPoint->cpus < MaxThreadsPerSplitPoint; i++) + // Allocate available threads setting idle flag to false + for (int i = 0; i < ActiveThreads && splitPoint->cpus < MaxThreadsPerSplitPoint; i++) if (thread_is_available(i, master)) { - memcpy(splitPoint->sstack[i], sstck, (ply+1) * sizeof(SearchStack)); + Threads[i].idle = false; + Threads[i].stop = false; Threads[i].splitPoint = splitPoint; splitPoint->slaves[i] = 1; splitPoint->cpus++; } + assert(splitPoint->cpus > 1); + + // We can release the lock because master and slave threads are already booked + lock_release(&MPLock); + // Tell the threads that they have work to do. This will make them leave - // their idle loop. - for (i = 0; i < ActiveThreads; i++) + // their idle loop. But before copy search stack tail for each thread. + for (int i = 0; i < ActiveThreads; i++) if (i == master || splitPoint->slaves[i]) { - Threads[i].workIsWaiting = true; - Threads[i].idle = false; - Threads[i].stop = false; + memcpy(splitPoint->sstack[i] + ply - 1, sstck + ply - 1, 3 * sizeof(SearchStack)); + Threads[i].workIsWaiting = true; // This makes the slave to exit from idle_loop() } - lock_release(&MPLock); - // Everything is set up. The master thread enters the idle loop, from // which it will instantly launch a search, because its workIsWaiting // slot is 'true'. We send the split point as a second parameter to the