X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=37c3bd71bb40e2aab91f4e45751684b0e86d7ebb;hp=e6ffcb19f42cf73abcbb082f7a4789442ba36a06;hb=b4870595a5652f7a5ecf577e33d0302b725b7f51;hpb=909e3adede210a124ed9ec4a2f21d73fda61c26d diff --git a/src/search.cpp b/src/search.cpp index e6ffcb19..37c3bd71 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -52,7 +52,7 @@ using std::endl; namespace { /// Types - + enum NodeType { NonPV, PV }; // ThreadsManager class is used to handle all the threads related stuff in search, // init, starting, parking and, the most important, launching a slave thread at a @@ -82,7 +82,7 @@ namespace { bool thread_should_stop(int threadID) const; void wake_sleeping_threads(); void put_threads_to_sleep(); - void idle_loop(int threadID, SplitPoint* waitSp); + void idle_loop(int threadID, SplitPoint* sp); bool split(const Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue, Depth depth, bool mateThreat, int* moves, MovePicker* mp, int master, bool pvNode); @@ -194,8 +194,7 @@ namespace { Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2]; // Minimum depth for use of singular extension - const Depth SingularExtensionDepthAtPVNodes = 6 * OnePly; - const Depth SingularExtensionDepthAtNonPVNodes = 8 * OnePly; + const Depth SingularExtensionDepth[2] = { 8 * OnePly /* non-PV */, 6 * OnePly /* PV */}; // If the TT move is at least SingularExtensionMargin better then the // remaining ones we will extend it. @@ -216,11 +215,10 @@ namespace { // Step 14. Reduced search // Reduction lookup tables (initialized at startup) and their getter functions - int8_t PVReductionMatrix[64][64]; // [depth][moveNumber] - int8_t NonPVReductionMatrix[64][64]; // [depth][moveNumber] + int8_t ReductionMatrix[2][64][64]; // [pv][depth][moveNumber] - inline Depth pv_reduction(Depth d, int mn) { return (Depth) PVReductionMatrix[Min(d / 2, 63)][Min(mn, 63)]; } - inline Depth nonpv_reduction(Depth d, int mn) { return (Depth) NonPVReductionMatrix[Min(d / 2, 63)][Min(mn, 63)]; } + template + inline Depth reduction(Depth d, int mn) { return (Depth) ReductionMatrix[PV][Min(d / 2, 63)][Min(mn, 63)]; } // Common adjustments @@ -232,7 +230,7 @@ namespace { const Value EasyMoveMargin = Value(0x200); // Last seconds noise filtering (LSN) - const bool UseLSNFiltering = false; + const bool UseLSNFiltering = true; const int LSNTime = 4000; // In milliseconds const Value LSNValue = value_from_centipawns(200); bool loseOnTime = false; @@ -280,8 +278,13 @@ namespace { Value id_loop(const Position& pos, Move searchMoves[]); Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value* alphaPtr, Value* betaPtr); - 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); + + template + Value search(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, bool allowNullmove, int threadID, Move excludedMove = MOVE_NONE); + + template + Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous); + Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID); void sp_search(SplitPoint* sp, int threadID); void sp_search_pv(SplitPoint* sp, int threadID); @@ -291,10 +294,9 @@ namespace { bool connected_moves(const Position& pos, Move m1, Move m2); bool value_is_mate(Value value); bool move_is_killer(Move m, const SearchStack& ss); - Depth extension(const Position&, Move, bool, bool, bool, bool, bool, bool*); bool ok_to_do_nullmove(const Position& pos); 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, bool allowNullmove); + bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply); Value refine_eval(const TTEntry* tte, Value defaultEval, int ply); void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount); void update_killers(Move m, SearchStack& ss); @@ -387,7 +389,7 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, if (get_option_value_string("Book File") != OpeningBook.file_name()) OpeningBook.open(get_option_value_string("Book File")); - Move bookMove = OpeningBook.get_move(pos); + Move bookMove = OpeningBook.get_move(pos, get_option_value_bool("Best Book Move")); if (bookMove != MOVE_NONE) { if (PonderSearch) @@ -549,10 +551,10 @@ void init_search() { for (int i = 1; i < 64; i++) // i == depth (OnePly = 1) for (int j = 1; j < 64; j++) // j == moveNumber { - double pvRed = 0.5 + log(double(i)) * log(double(j)) / 6.0; - double nonPVRed = 0.5 + log(double(i)) * log(double(j)) / 3.0; - PVReductionMatrix[i][j] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(OnePly)) : 0); - NonPVReductionMatrix[i][j] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(OnePly)) : 0); + double pvRed = log(double(i)) * log(double(j)) / 3.0; + double nonPVRed = log(double(i)) * log(double(j)) / 1.5; + ReductionMatrix[PV][i][j] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(OnePly)) : 0); + ReductionMatrix[NonPV][i][j] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(OnePly)) : 0); } // Init futility margins array @@ -560,7 +562,7 @@ void init_search() { for (int j = 0; j < 64; j++) // j == moveNumber { // FIXME: test using log instead of BSR - FutilityMarginsMatrix[i][j] = (i < 2 ? 0 : 112 * bitScanReverse32(i * i / 2)) - 8 * j; + FutilityMarginsMatrix[i][j] = (i < 2 ? 0 : 112 * bitScanReverse32(i * i / 2)) - 8 * j + 45; } // Init futility move count array @@ -844,7 +846,7 @@ namespace { // Step 11. Decide the new search depth depth = (Iteration - 2) * OnePly + InitialDepth; - ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous); + ext = extension(pos, move, captureOrPromotion, moveIsCheck, false, false, &dangerous); newDepth = depth + ext; // Step 12. Futility pruning (omitted at root) @@ -869,7 +871,7 @@ namespace { alpha = -VALUE_INFINITE; // Full depth PV search, done on first move or after a fail high - value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0); + value = -search(pos, ss, -beta, -alpha, newDepth, 1, false, 0); } else { @@ -882,11 +884,11 @@ namespace { && !captureOrPromotion && !move_is_castle(move)) { - ss[0].reduction = pv_reduction(depth, i - MultiPV + 2); + ss[0].reduction = reduction(depth, i - MultiPV + 2); if (ss[0].reduction) { // Reduced depth non-pv search using alpha as upperbound - value = -search(pos, ss, -alpha, newDepth-ss[0].reduction, 1, true, 0); + value = -search(pos, ss, -(alpha+1), -alpha, newDepth-ss[0].reduction, 1, true, 0); doFullDepthSearch = (value > alpha); } } @@ -896,12 +898,12 @@ namespace { { // Full depth non-pv search using alpha as upperbound ss[0].reduction = Depth(0); - value = -search(pos, ss, -alpha, newDepth, 1, true, 0); + value = -search(pos, ss, -(alpha+1), -alpha, newDepth, 1, true, 0); // If we are above alpha then research at same depth but as PV // to get a correct score or eventually a fail high above beta. if (value > alpha) - value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0); + value = -search(pos, ss, -beta, -alpha, newDepth, 1, false, 0); } } @@ -1023,8 +1025,9 @@ namespace { // search_pv() is the main search function for PV nodes. - Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta, - Depth depth, int ply, int threadID) { + template + Value search(Position& pos, SearchStack ss[], Value alpha, Value beta, + Depth depth, int ply, bool allowNullmove, int threadID, Move excludedMove) { assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE); assert(beta > alpha && beta <= VALUE_INFINITE); @@ -1038,10 +1041,12 @@ namespace { Move ttMove, move; Depth ext, newDepth; Value bestValue, value, oldAlpha; + Value refinedValue, nullValue, futilityValueScaled; // Non-PV specific bool isCheck, singleEvasion, moveIsCheck, captureOrPromotion, dangerous; bool mateThreat = false; int moveCount = 0; - bestValue = value = -VALUE_INFINITE; + refinedValue = bestValue = value = -VALUE_INFINITE; + oldAlpha = alpha; if (depth < OnePly) return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID); @@ -1058,13 +1063,20 @@ namespace { return VALUE_DRAW; // Step 3. Mate distance pruning - oldAlpha = alpha; alpha = Max(value_mated_in(ply), alpha); beta = Min(value_mate_in(ply+1), beta); if (alpha >= beta) return alpha; // Step 4. Transposition table lookup + + // We don't want the score of a partial search to overwrite a previous full search + // TT value, so we use a different position key in case of an excluded move exists. + Key posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key(); + + tte = TT.retrieve(posKey); + ttMove = (tte ? tte->move() : MOVE_NONE); + // At PV nodes, we don't use the TT for pruning, but only for move ordering. // This is to avoid problems in the following areas: // @@ -1072,245 +1084,22 @@ namespace { // * Fifty move rule detection // * Searching for a mate // * Printing of full PV line - tte = TT.retrieve(pos.get_key()); - ttMove = (tte ? tte->move() : MOVE_NONE); - - // Step 5. Evaluate the position statically - // At PV nodes we do this only to update gain statistics - isCheck = pos.is_check(); - if (!isCheck) - { - ss[ply].eval = evaluate(pos, ei, threadID); - update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval); - } - - // Step 6. Razoring (is omitted in PV nodes) - // Step 7. Static null move pruning (is omitted in PV nodes) - // Step 8. Null move search with verification search (is omitted in PV nodes) - // Step 9. Internal iterative deepening - if ( depth >= IIDDepthAtPVNodes - && ttMove == MOVE_NONE) + if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply)) { - search_pv(pos, ss, alpha, beta, depth-2*OnePly, ply, threadID); - ttMove = ss[ply].pv[ply]; - tte = TT.retrieve(pos.get_key()); - } - - // Initialize a MovePicker object for the current position - mateThreat = pos.has_mate_threat(opposite_color(pos.side_to_move())); - MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]); - CheckInfo ci(pos); - - // Step 10. Loop through moves - // Loop through all legal moves until no moves remain or a beta cutoff occurs - while ( alpha < beta - && (move = mp.get_next_move()) != MOVE_NONE - && !TM.thread_should_stop(threadID)) - { - assert(move_is_ok(move)); - - singleEvasion = (isCheck && mp.number_of_evasions() == 1); - moveIsCheck = pos.move_is_check(move, ci); - captureOrPromotion = pos.move_is_capture_or_promotion(move); - - // Step 11. Decide the new search depth - ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous); - - // Singular extension search. We extend the TT move if its value is much better than - // its siblings. To verify this we do a reduced search on all the other moves but the - // ttMove, if result is lower then ttValue minus a margin then we extend ttMove. - if ( depth >= SingularExtensionDepthAtPVNodes - && tte - && move == tte->move() - && ext < OnePly - && is_lower_bound(tte->type()) - && tte->depth() >= depth - 3 * OnePly) - { - Value ttValue = value_from_tt(tte->value(), ply); - - if (abs(ttValue) < VALUE_KNOWN_WIN) - { - Value excValue = search(pos, ss, ttValue - SingularExtensionMargin, depth / 2, ply, false, threadID, move); - - if (excValue < ttValue - SingularExtensionMargin) - ext = OnePly; - } - } - - newDepth = depth - OnePly + ext; + // Refresh tte entry to avoid aging + TT.store(posKey, tte->value(), tte->type(), tte->depth(), ttMove); - // Update current move (this must be done after singular extension search) - movesSearched[moveCount++] = ss[ply].currentMove = move; - - // Step 12. Futility pruning (is omitted in PV nodes) - - // Step 13. Make the move - pos.do_move(move, st, ci, moveIsCheck); - - // Step extra. pv search (only in PV nodes) - // The first move in list is the expected PV - if (moveCount == 1) - value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID); - else - { - // Step 14. Reduced search - // if the move fails high will be re-searched at full depth. - bool doFullDepthSearch = true; - - if ( depth >= 3 * OnePly - && !dangerous - && !captureOrPromotion - && !move_is_castle(move) - && !move_is_killer(move, ss[ply])) - { - ss[ply].reduction = pv_reduction(depth, moveCount); - if (ss[ply].reduction) - { - value = -search(pos, ss, -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID); - doFullDepthSearch = (value > alpha); - } - } - - // Step 15. Full depth search - if (doFullDepthSearch) - { - ss[ply].reduction = Depth(0); - value = -search(pos, ss, -alpha, newDepth, ply+1, true, threadID); - - // Step extra. pv search (only in PV nodes) - if (value > alpha && value < beta) - value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID); - } - } - - // Step 16. Undo move - pos.undo_move(move); - - assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - - // Step 17. Check for new best move - if (value > bestValue) - { - bestValue = value; - if (value > alpha) - { - alpha = value; - update_pv(ss, ply); - if (value == value_mate_in(ply + 1)) - ss[ply].mateKiller = move; - } - } - - // Step 18. Check for split - if ( TM.active_threads() > 1 - && bestValue < beta - && depth >= MinimumSplitDepth - && Iteration <= 99 - && TM.available_thread_exists(threadID) - && !AbortSearch - && !TM.thread_should_stop(threadID) - && TM.split(pos, ss, ply, &alpha, beta, &bestValue, - depth, mateThreat, &moveCount, &mp, threadID, true)) - break; - } - - // Step 19. Check for mate and stalemate - // All legal moves have been searched and if there were - // no legal moves, it must be mate or stalemate. - if (moveCount == 0) - return (isCheck ? value_mated_in(ply) : VALUE_DRAW); - - // Step 20. Update tables - // If the search is not aborted, update the transposition table, - // history counters, and killer moves. - if (AbortSearch || TM.thread_should_stop(threadID)) - return bestValue; - - if (bestValue <= oldAlpha) - TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE); - - else if (bestValue >= beta) - { - TM.incrementBetaCounter(pos.side_to_move(), depth, threadID); - move = ss[ply].pv[ply]; - if (!pos.move_is_capture_or_promotion(move)) - { - update_history(pos, move, depth, movesSearched, moveCount); - update_killers(move, ss[ply]); - } - TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move); - } - else - TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, depth, ss[ply].pv[ply]); - - return bestValue; - } - - - // search() is the search function for zero-width nodes. - - Value search(Position& pos, SearchStack ss[], Value beta, Depth depth, - int ply, bool allowNullmove, int threadID, Move excludedMove) { - - assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE); - assert(ply >= 0 && ply < PLY_MAX); - assert(threadID >= 0 && threadID < TM.active_threads()); - - Move movesSearched[256]; - EvalInfo ei; - StateInfo st; - const TTEntry* tte; - Move ttMove, move; - Depth ext, newDepth; - Value bestValue, refinedValue, nullValue, value, futilityValueScaled; - bool isCheck, singleEvasion, moveIsCheck, captureOrPromotion, dangerous; - bool mateThreat = false; - int moveCount = 0; - refinedValue = bestValue = value = -VALUE_INFINITE; - - if (depth < OnePly) - return qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID); - - // Step 1. Initialize node and poll - // Polling can abort search. - init_node(ss, ply, threadID); - - // Step 2. Check for aborted search and immediate draw - if (AbortSearch || TM.thread_should_stop(threadID)) - return Value(0); - - if (pos.is_draw() || ply >= PLY_MAX - 1) - return VALUE_DRAW; - - // Step 3. Mate distance pruning - if (value_mated_in(ply) >= beta) - return beta; - - if (value_mate_in(ply + 1) < beta) - return beta - 1; - - // Step 4. Transposition table lookup - - // We don't want the score of a partial search to overwrite a previous full search - // TT value, so we use a different position key in case of an excluded move exists. - Key posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key(); - - tte = TT.retrieve(posKey); - ttMove = (tte ? tte->move() : MOVE_NONE); - - if (tte && ok_to_use_TT(tte, depth, beta, ply, allowNullmove)) - { ss[ply].currentMove = ttMove; // Can be MOVE_NONE return value_from_tt(tte->value(), ply); } // Step 5. Evaluate the position statically + // At PV nodes we do this only to update gain statistics isCheck = pos.is_check(); - if (!isCheck) { - if (tte && (tte->type() & VALUE_TYPE_EVAL)) + if (!PvNode && tte && (tte->type() & VALUE_TYPE_EVAL)) ss[ply].eval = value_from_tt(tte->value(), ply); else ss[ply].eval = evaluate(pos, ei, threadID); @@ -1319,8 +1108,9 @@ namespace { update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval); } - // Step 6. Razoring - if ( refinedValue < beta - razor_margin(depth) + // Step 6. Razoring (is omitted in PV nodes) + if ( !PvNode + && refinedValue < beta - razor_margin(depth) && ttMove == MOVE_NONE && ss[ply - 1].currentMove != MOVE_NULL && depth < RazorDepth @@ -1336,10 +1126,11 @@ namespace { return v; } - // Step 7. Static null move pruning + // Step 7. Static null move pruning (is omitted in PV nodes) // 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 ( allowNullmove + if ( !PvNode + && allowNullmove && depth < RazorDepth && !isCheck && !value_is_mate(beta) @@ -1347,11 +1138,12 @@ namespace { && refinedValue >= beta + futility_margin(depth, 0)) return refinedValue - futility_margin(depth, 0); - // Step 8. Null move search with verification search + // Step 8. Null move search with verification search (is omitted in PV nodes) // When we jump directly to qsearch() we do a null move only if static value is // at least beta. Otherwise we do a null move if static value is not more than // NullMoveMargin under beta. - if ( allowNullmove + if ( !PvNode + && allowNullmove && depth > OnePly && !isCheck && !value_is_mate(beta) @@ -1369,7 +1161,7 @@ namespace { pos.do_null_move(st); - nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID); + nullValue = -search(pos, ss, -beta, -alpha, depth-R*OnePly, ply+1, false, threadID); pos.undo_null_move(); @@ -1379,20 +1171,13 @@ namespace { if (nullValue >= value_mate_in(PLY_MAX)) nullValue = beta; - // Do zugzwang verification search for high depths, don't store in TT - // if search was stopped. - if ( ( depth < 6 * OnePly - || search(pos, ss, beta, depth-5*OnePly, ply, false, threadID) >= beta) - && !AbortSearch - && !TM.thread_should_stop(threadID)) - { - assert(value_to_tt(nullValue, ply) == nullValue); + if (depth < 6 * OnePly) + return nullValue; - // Special flag null values that are not zugzwang checked - ValueType vt = (depth < 6 * OnePly ? VALUE_TYPE_NS_LO : VALUE_TYPE_LOWER); - TT.store(posKey, nullValue, vt, depth, MOVE_NONE); + // Do zugzwang verification search + Value v = search(pos, ss, alpha, beta, depth-5*OnePly, ply, false, threadID); + if (v >= beta) return nullValue; - } } else { // The null move failed low, which means that we may be faced with // some kind of threat. If the previous move was reduced, check if @@ -1412,18 +1197,33 @@ namespace { } // Step 9. Internal iterative deepening - if ( depth >= IIDDepthAtNonPVNodes + // We have different rules for PV nodes and non-pv nodes + if ( PvNode + && depth >= IIDDepthAtPVNodes + && ttMove == MOVE_NONE) + { + search(pos, ss, alpha, beta, depth-2*OnePly, ply, false, threadID); + ttMove = ss[ply].pv[ply]; + tte = TT.retrieve(posKey); + } + + if ( !PvNode + && depth >= IIDDepthAtNonPVNodes && ttMove == MOVE_NONE && !isCheck && ss[ply].eval >= beta - IIDMargin) { - search(pos, ss, beta, depth/2, ply, false, threadID); + search(pos, ss, alpha, beta, depth/2, ply, false, threadID); ttMove = ss[ply].pv[ply]; tte = TT.retrieve(posKey); } + // Expensive mate threat detection (only for PV nodes) + if (PvNode) + mateThreat = pos.has_mate_threat(opposite_color(pos.side_to_move())); + // Initialize a MovePicker object for the current position - MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply], beta); + MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply], (PvNode ? -VALUE_INFINITE : beta)); CheckInfo ci(pos); // Step 10. Loop through moves @@ -1437,17 +1237,17 @@ namespace { if (move == excludedMove) continue; - moveIsCheck = pos.move_is_check(move, ci); singleEvasion = (isCheck && mp.number_of_evasions() == 1); + moveIsCheck = pos.move_is_check(move, ci); captureOrPromotion = pos.move_is_capture_or_promotion(move); // Step 11. Decide the new search depth - ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous); + ext = extension(pos, move, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous); // Singular extension search. We extend the TT move if its value is much better than // its siblings. To verify this we do a reduced search on all the other moves but the // ttMove, if result is lower then ttValue minus a margin then we extend ttMove. - if ( depth >= SingularExtensionDepthAtNonPVNodes + if ( depth >= SingularExtensionDepth[PvNode] && tte && move == tte->move() && !excludedMove // Do not allow recursive singular extension search @@ -1459,7 +1259,7 @@ namespace { if (abs(ttValue) < VALUE_KNOWN_WIN) { - Value excValue = search(pos, ss, ttValue - SingularExtensionMargin, depth / 2, ply, false, threadID, move); + Value excValue = search(pos, ss, ttValue - SingularExtensionMargin - 1, ttValue - SingularExtensionMargin, depth / 2, ply, false, threadID, move); if (excValue < ttValue - SingularExtensionMargin) ext = OnePly; @@ -1471,8 +1271,9 @@ namespace { // Update current move (this must be done after singular extension search) movesSearched[moveCount++] = ss[ply].currentMove = move; - // Step 12. Futility pruning - if ( !isCheck + // Step 12. Futility pruning (is omitted in PV nodes) + if ( !PvNode + && !isCheck && !dangerous && !captureOrPromotion && !move_is_castle(move) @@ -1485,9 +1286,9 @@ namespace { continue; // Value based pruning - Depth predictedDepth = newDepth - nonpv_reduction(depth, moveCount); // We illogically ignore reduction condition depth >= 3*OnePly + Depth predictedDepth = newDepth - reduction(depth, moveCount); // We illogically ignore reduction condition depth >= 3*OnePly futilityValueScaled = ss[ply].eval + futility_margin(predictedDepth, moveCount) - + H.gain(pos.piece_on(move_from(move)), move_to(move)) + 45; + + H.gain(pos.piece_on(move_from(move)), move_to(move)); if (futilityValueScaled < beta) { @@ -1500,29 +1301,40 @@ namespace { // Step 13. Make the move pos.do_move(move, st, ci, moveIsCheck); - // Step 14. Reduced search, if the move fails high - // will be re-searched at full depth. - bool doFullDepthSearch = true; - - if ( depth >= 3*OnePly - && !dangerous - && !captureOrPromotion - && !move_is_castle(move) - && !move_is_killer(move, ss[ply])) + // Step extra. pv search (only in PV nodes) + // The first move in list is the expected PV + if (PvNode && moveCount == 1) + value = -search(pos, ss, -beta, -alpha, newDepth, ply+1, false, threadID); + else { - ss[ply].reduction = nonpv_reduction(depth, moveCount); - if (ss[ply].reduction) - { - value = -search(pos, ss, -(beta-1), newDepth-ss[ply].reduction, ply+1, true, threadID); - doFullDepthSearch = (value >= beta); - } - } + // Step 14. Reduced search + // if the move fails high will be re-searched at full depth. + bool doFullDepthSearch = true; - // Step 15. Full depth search - if (doFullDepthSearch) - { - ss[ply].reduction = Depth(0); - value = -search(pos, ss, -(beta-1), newDepth, ply+1, true, threadID); + if ( depth >= 3 * OnePly + && !dangerous + && !captureOrPromotion + && !move_is_castle(move) + && !move_is_killer(move, ss[ply])) + { + ss[ply].reduction = reduction(depth, moveCount); + if (ss[ply].reduction) + { + value = -search(pos, ss, -(alpha+1), -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID); + doFullDepthSearch = (value > alpha); + } + } + + // Step 15. Full depth search + if (doFullDepthSearch) + { + ss[ply].reduction = Depth(0); + value = -search(pos, ss, -(alpha+1), -alpha, newDepth, ply+1, true, threadID); + + // Step extra. pv search (only in PV nodes) + if (PvNode && value > alpha && value < beta) + value = -search(pos, ss, -beta, -alpha, newDepth, ply+1, false, threadID); + } } // Step 16. Undo move @@ -1534,11 +1346,13 @@ namespace { if (value > bestValue) { bestValue = value; - if (value >= beta) + if (value > alpha) + { + alpha = value; update_pv(ss, ply); - - if (value == value_mate_in(ply + 1)) - ss[ply].mateKiller = move; + if (value == value_mate_in(ply + 1)) + ss[ply].mateKiller = move; + } } // Step 18. Check for split @@ -1549,8 +1363,8 @@ namespace { && TM.available_thread_exists(threadID) && !AbortSearch && !TM.thread_should_stop(threadID) - && TM.split(pos, ss, ply, NULL, beta, &bestValue, - depth, mateThreat, &moveCount, &mp, threadID, false)) + && TM.split(pos, ss, ply, &alpha, beta, &bestValue, + depth, mateThreat, &moveCount, &mp, threadID, PvNode)) break; } @@ -1559,7 +1373,7 @@ namespace { // no legal moves, it must be mate or stalemate. // If one move was excluded return fail low score. if (!moveCount) - return excludedMove ? beta - 1 : (isCheck ? value_mated_in(ply) : VALUE_DRAW); + return excludedMove ? oldAlpha : (isCheck ? value_mated_in(ply) : VALUE_DRAW); // Step 20. Update tables // If the search is not aborted, update the transposition table, @@ -1567,9 +1381,10 @@ namespace { if (AbortSearch || TM.thread_should_stop(threadID)) return bestValue; - if (bestValue < beta) + if (bestValue <= oldAlpha) TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE); - else + + else if (bestValue >= beta) { TM.incrementBetaCounter(pos.side_to_move(), depth, threadID); move = ss[ply].pv[ply]; @@ -1579,8 +1394,9 @@ namespace { update_history(pos, move, depth, movesSearched, moveCount); update_killers(move, ss[ply]); } - } + else + TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, depth, ss[ply].pv[ply]); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1627,7 +1443,7 @@ namespace { tte = TT.retrieve(pos.get_key()); ttMove = (tte ? tte->move() : MOVE_NONE); - if (!pvNode && tte && ok_to_use_TT(tte, depth, beta, ply, true)) + if (!pvNode && tte && ok_to_use_TT(tte, depth, beta, ply)) { assert(tte->type() != VALUE_TYPE_EVAL); @@ -1658,7 +1474,7 @@ namespace { if (bestValue >= beta) { // Store the score to avoid a future costly evaluation() call - if (!isCheck && !tte && ei.futilityMargin[pos.side_to_move()] == 0) + if (!isCheck && !tte && ei.kingDanger[pos.side_to_move()] == 0) TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EV_LO, Depth(-127*OnePly), MOVE_NONE); return bestValue; @@ -1677,7 +1493,7 @@ namespace { 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[pos.side_to_move()]; + futilityBase = staticValue + FutilityMarginQS + ei.kingDanger[pos.side_to_move()]; // Loop through the moves until no moves remain or a beta cutoff occurs while ( alpha < beta @@ -1714,7 +1530,7 @@ namespace { // Detect blocking evasions that are candidate to be pruned evasionPrunable = isCheck - && bestValue != -VALUE_INFINITE + && bestValue > value_mated_in(PLY_MAX) && !pos.move_is_capture(move) && pos.type_of_piece_on(move_from(move)) != KING && !pos.can_castle(pos.side_to_move()); @@ -1757,7 +1573,7 @@ namespace { { // If bestValue isn't changed it means it is still the static evaluation // of the node, so keep this info to avoid a future evaluation() call. - ValueType type = (bestValue == staticValue && !ei.futilityMargin[pos.side_to_move()] ? VALUE_TYPE_EV_UP : VALUE_TYPE_UPPER); + ValueType type = (bestValue == staticValue && !ei.kingDanger[pos.side_to_move()] ? VALUE_TYPE_EV_UP : VALUE_TYPE_UPPER); TT.store(pos.get_key(), value_to_tt(bestValue, ply), type, d, MOVE_NONE); } else if (bestValue >= beta) @@ -1821,7 +1637,7 @@ namespace { captureOrPromotion = pos.move_is_capture_or_promotion(move); // Step 11. Decide the new search depth - ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous); + ext = extension(pos, move, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous); newDepth = sp->depth - OnePly + ext; // Update current move @@ -1843,9 +1659,9 @@ namespace { } // Value based pruning - Depth predictedDepth = newDepth - nonpv_reduction(sp->depth, moveCount); + Depth predictedDepth = newDepth - reduction(sp->depth, moveCount); futilityValueScaled = ss[sp->ply].eval + futility_margin(predictedDepth, moveCount) - + H.gain(pos.piece_on(move_from(move)), move_to(move)) + 45; + + H.gain(pos.piece_on(move_from(move)), move_to(move)); if (futilityValueScaled < sp->beta) { @@ -1869,10 +1685,10 @@ namespace { && !move_is_castle(move) && !move_is_killer(move, ss[sp->ply])) { - ss[sp->ply].reduction = nonpv_reduction(sp->depth, moveCount); + ss[sp->ply].reduction = reduction(sp->depth, moveCount); if (ss[sp->ply].reduction) { - value = -search(pos, ss, -(sp->beta-1), newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID); + value = -search(pos, ss, -(sp->alpha+1), -(sp->alpha), newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID); doFullDepthSearch = (value >= sp->beta && !TM.thread_should_stop(threadID)); } } @@ -1881,7 +1697,7 @@ namespace { if (doFullDepthSearch) { ss[sp->ply].reduction = Depth(0); - value = -search(pos, ss, -(sp->beta - 1), newDepth, sp->ply+1, true, threadID); + value = -search(pos, ss, -(sp->alpha+1), -(sp->alpha), newDepth, sp->ply+1, true, threadID); } // Step 16. Undo move @@ -1954,7 +1770,7 @@ namespace { captureOrPromotion = pos.move_is_capture_or_promotion(move); // Step 11. Decide the new search depth - ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous); + ext = extension(pos, move, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous); newDepth = sp->depth - OnePly + ext; // Update current move @@ -1974,11 +1790,11 @@ namespace { && !move_is_castle(move) && !move_is_killer(move, ss[sp->ply])) { - ss[sp->ply].reduction = pv_reduction(sp->depth, moveCount); + ss[sp->ply].reduction = reduction(sp->depth, moveCount); if (ss[sp->ply].reduction) { Value localAlpha = sp->alpha; - value = -search(pos, ss, -localAlpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID); + value = -search(pos, ss, -(localAlpha+1), -localAlpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID); doFullDepthSearch = (value > localAlpha && !TM.thread_should_stop(threadID)); } } @@ -1988,7 +1804,7 @@ namespace { { Value localAlpha = sp->alpha; ss[sp->ply].reduction = Depth(0); - value = -search(pos, ss, -localAlpha, newDepth, sp->ply+1, true, threadID); + value = -search(pos, ss, -(localAlpha+1), -localAlpha, newDepth, sp->ply+1, true, threadID); if (value > localAlpha && value < sp->beta && !TM.thread_should_stop(threadID)) { @@ -1996,7 +1812,7 @@ namespace { // 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); + value = -search(pos, ss, -sp->beta, -localAlpha, newDepth, sp->ply+1, false, threadID); } } @@ -2036,7 +1852,7 @@ namespace { // init_node() is called at the beginning of all the search functions - // (search(), search_pv(), qsearch(), and so on) and initializes the + // (search() qsearch(), and so on) and initializes the // search stack object corresponding to the current node. Once every // NodesBetweenPolls nodes, init_node() also calls poll(), which polls // for user input and checks whether it is time to stop the search. @@ -2188,9 +2004,9 @@ namespace { // any case are marked as 'dangerous'. Note that also if a move is not // extended, as example because the corresponding UCI option is set to zero, // the move is marked as 'dangerous' so, at least, we avoid to prune it. - - Depth extension(const Position& pos, Move m, bool pvNode, bool captureOrPromotion, - bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous) { + template + Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, + bool singleEvasion, bool mateThreat, bool* dangerous) { assert(m != MOVE_NONE); @@ -2200,13 +2016,13 @@ namespace { if (*dangerous) { if (moveIsCheck) - result += CheckExtension[pvNode]; + result += CheckExtension[PvNode]; if (singleEvasion) - result += SingleEvasionExtension[pvNode]; + result += SingleEvasionExtension[PvNode]; if (mateThreat) - result += MateThreatExtension[pvNode]; + result += MateThreatExtension[PvNode]; } if (pos.type_of_piece_on(move_from(m)) == PAWN) @@ -2214,12 +2030,12 @@ namespace { Color c = pos.side_to_move(); if (relative_rank(c, move_to(m)) == RANK_7) { - result += PawnPushTo7thExtension[pvNode]; + result += PawnPushTo7thExtension[PvNode]; *dangerous = true; } if (pos.pawn_is_passed(c, move_to(m))) { - result += PassedPawnExtension[pvNode]; + result += PassedPawnExtension[PvNode]; *dangerous = true; } } @@ -2231,11 +2047,11 @@ namespace { && !move_is_promotion(m) && !move_is_ep(m)) { - result += PawnEndgameExtension[pvNode]; + result += PawnEndgameExtension[PvNode]; *dangerous = true; } - if ( pvNode + if ( PvNode && captureOrPromotion && pos.type_of_piece_on(move_to(m)) != PAWN && pos.see_sign(m) >= 0) @@ -2308,18 +2124,14 @@ namespace { } - // ok_to_use_TT() returns true if a transposition table score can be used at a - // given point in search. To avoid zugzwang issues TT cutoffs at the root node - // of a null move verification search are not allowed if the TT value was found - // by a null search, this is implemented testing allowNullmove and TT entry type. + // ok_to_use_TT() returns true if a transposition table score + // can be used at a given point in search. - bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply, bool allowNullmove) { + bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) { Value v = value_from_tt(tte->value(), ply); - return (allowNullmove || !(tte->type() & VALUE_TYPE_NULL)) - - && ( tte->depth() >= depth + return ( tte->depth() >= depth || v >= Max(value_mate_in(PLY_MAX), beta) || v < Min(value_mated_in(PLY_MAX), beta)) @@ -2644,10 +2456,10 @@ namespace { // idle_loop() is where the threads are parked when they have no work to do. - // The parameter "waitSp", if non-NULL, is a pointer to an active SplitPoint + // The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint // object for which the current thread is the master. - void ThreadsManager::idle_loop(int threadID, SplitPoint* waitSp) { + void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) { assert(threadID >= 0 && threadID < MAX_THREADS); @@ -2657,7 +2469,7 @@ namespace { // master should exit as last one. if (AllThreadsShouldExit) { - assert(!waitSp); + assert(!sp); threads[threadID].state = THREAD_TERMINATED; return; } @@ -2666,7 +2478,7 @@ namespace { // instead of wasting CPU time polling for work. while (AllThreadsShouldSleep || threadID >= ActiveThreads) { - assert(!waitSp); + assert(!sp); assert(threadID != 0); threads[threadID].state = THREAD_SLEEPING; @@ -2703,8 +2515,13 @@ namespace { // If this thread is the master of a split point and all threads have // finished their work at this split point, return from the idle loop. - if (waitSp != NULL && waitSp->cpus == 0) + if (sp && sp->cpus == 0) { + // Because sp->cpus is decremented under lock protection, + // be sure sp->lock has been released before to proceed. + lock_grab(&(sp->lock)); + lock_release(&(sp->lock)); + assert(threads[threadID].state == THREAD_AVAILABLE); threads[threadID].state = THREAD_SEARCHING; @@ -2775,7 +2592,7 @@ namespace { } // Wait until the thread has finished launching and is gone to sleep - while (threads[i].state != THREAD_SLEEPING); + while (threads[i].state != THREAD_SLEEPING) {} } } @@ -2816,7 +2633,7 @@ namespace { SplitPoint* sp; - for (sp = threads[threadID].splitPoint; sp && !sp->stopRequest; sp = sp->parent); + for (sp = threads[threadID].splitPoint; sp && !sp->stopRequest; sp = sp->parent) {} return sp != NULL; } @@ -2925,7 +2742,7 @@ namespace { splitPoint->ply = ply; splitPoint->depth = depth; splitPoint->mateThreat = mateThreat; - splitPoint->alpha = pvNode ? *alpha : beta - 1; + splitPoint->alpha = *alpha; splitPoint->beta = beta; splitPoint->pvNode = pvNode; splitPoint->bestValue = *bestValue; @@ -2980,12 +2797,10 @@ namespace { idle_loop(master, splitPoint); // We have returned from the idle loop, which means that all threads are - // finished. Update alpha, beta and bestValue, and return. + // finished. Update alpha and bestValue, and return. lock_grab(&MPLock); - if (pvNode) - *alpha = splitPoint->alpha; - + *alpha = splitPoint->alpha; *bestValue = splitPoint->bestValue; threads[master].activeSplitPoints--; threads[master].splitPoint = splitPoint->parent;