X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=f8dd1361dea615e1f84cccb5a7ad347b10a80e4e;hp=aaff2f547dfd5c90c2cf9539a80957076728a2ef;hb=91ce930b28440e05f4c4b75e0ed7bcc2c58fa07c;hpb=f3809f2a18bd3a348ba80e1e07d014834603499b diff --git a/src/search.cpp b/src/search.cpp index aaff2f54..f8dd1361 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); @@ -104,13 +104,6 @@ namespace { }; - // FIXME: document me - - enum NullStatus { - ALLOW_NULLMOVE, - FORBID_NULLMOVE, - VERIFY_NULLMOVE - }; // RootMove struct is used for moves at the root at the tree. For each // root move, we store a score, a node count, and a PV (really a refutation @@ -201,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. @@ -287,8 +279,10 @@ 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, NullStatus nullStatus, 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); + 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); @@ -301,7 +295,7 @@ namespace { 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); @@ -556,8 +550,8 @@ 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; + double pvRed = log(double(i)) * log(double(j)) / 3.0; + double nonPVRed = log(double(i)) * log(double(j)) / 1.5; 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); } @@ -567,7 +561,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 @@ -876,7 +870,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 { @@ -893,7 +887,7 @@ namespace { if (ss[0].reduction) { // Reduced depth non-pv search using alpha as upperbound - value = -search(pos, ss, -alpha, newDepth-ss[0].reduction, 1, ALLOW_NULLMOVE, 0); + value = -search(pos, ss, -(alpha+1), -alpha, newDepth-ss[0].reduction, 1, true, 0); doFullDepthSearch = (value > alpha); } } @@ -903,12 +897,12 @@ namespace { { // Full depth non-pv search using alpha as upperbound ss[0].reduction = Depth(0); - value = -search(pos, ss, -alpha, newDepth, 1, ALLOW_NULLMOVE, 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); } } @@ -1030,8 +1024,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); @@ -1045,10 +1040,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); @@ -1065,13 +1062,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: // @@ -1079,245 +1083,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, FORBID_NULLMOVE, threadID, move); - - if (excValue < ttValue - SingularExtensionMargin) - ext = OnePly; - } - } - - newDepth = depth - OnePly + ext; - - // 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, ALLOW_NULLMOVE, threadID); - doFullDepthSearch = (value > alpha); - } - } - - // Step 15. Full depth search - if (doFullDepthSearch) - { - ss[ply].reduction = Depth(0); - value = -search(pos, ss, -alpha, newDepth, ply+1, ALLOW_NULLMOVE, 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); + // Refresh tte entry to avoid aging + TT.store(posKey, tte->value(), tte->type(), tte->depth(), ttMove); - // 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, NullStatus nullStatus, 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, nullStatus == ALLOW_NULLMOVE)) - { 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); @@ -1326,8 +1107,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 @@ -1343,10 +1125,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 ( nullStatus == ALLOW_NULLMOVE + if ( !PvNode + && allowNullmove && depth < RazorDepth && !isCheck && !value_is_mate(beta) @@ -1354,11 +1137,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 ( nullStatus == ALLOW_NULLMOVE + if ( !PvNode + && allowNullmove && depth > OnePly && !isCheck && !value_is_mate(beta) @@ -1376,7 +1160,7 @@ namespace { pos.do_null_move(st); - nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, FORBID_NULLMOVE, threadID); + nullValue = -search(pos, ss, -beta, -alpha, depth-R*OnePly, ply+1, false, threadID); pos.undo_null_move(); @@ -1386,18 +1170,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, FORBID_NULLMOVE, threadID) >= beta) - && !AbortSearch - && !TM.thread_should_stop(threadID)) - { - assert(value_to_tt(nullValue, ply) == nullValue); + if (depth < 6 * OnePly) + return nullValue; - TT.store(posKey, nullValue, VALUE_TYPE_NS_LO, 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 @@ -1417,18 +1196,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, FORBID_NULLMOVE, 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 @@ -1442,17 +1236,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, PvNode, 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 @@ -1464,7 +1258,7 @@ namespace { if (abs(ttValue) < VALUE_KNOWN_WIN) { - Value excValue = search(pos, ss, ttValue - SingularExtensionMargin, depth / 2, ply, FORBID_NULLMOVE, threadID, move); + Value excValue = search(pos, ss, ttValue - SingularExtensionMargin - 1, ttValue - SingularExtensionMargin, depth / 2, ply, false, threadID, move); if (excValue < ttValue - SingularExtensionMargin) ext = OnePly; @@ -1476,8 +1270,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) @@ -1492,7 +1287,7 @@ namespace { // Value based pruning Depth predictedDepth = newDepth - nonpv_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) { @@ -1505,29 +1300,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, ALLOW_NULLMOVE, 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, ALLOW_NULLMOVE, threadID); + if ( depth >= 3 * OnePly + && !dangerous + && !captureOrPromotion + && !move_is_castle(move) + && !move_is_killer(move, ss[ply])) + { + ss[ply].reduction = (PvNode ? pv_reduction(depth, moveCount) : nonpv_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 @@ -1539,11 +1345,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 @@ -1554,8 +1362,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; } @@ -1564,7 +1372,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, @@ -1572,9 +1380,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]; @@ -1584,8 +1393,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); @@ -1632,7 +1442,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); @@ -1663,7 +1473,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; @@ -1682,7 +1492,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 @@ -1762,7 +1572,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) @@ -1850,7 +1660,7 @@ namespace { // Value based pruning Depth predictedDepth = newDepth - nonpv_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) { @@ -1877,7 +1687,7 @@ namespace { ss[sp->ply].reduction = nonpv_reduction(sp->depth, moveCount); if (ss[sp->ply].reduction) { - value = -search(pos, ss, -(sp->beta-1), newDepth-ss[sp->ply].reduction, sp->ply+1, ALLOW_NULLMOVE, 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)); } } @@ -1886,7 +1696,7 @@ namespace { if (doFullDepthSearch) { ss[sp->ply].reduction = Depth(0); - value = -search(pos, ss, -(sp->beta - 1), newDepth, sp->ply+1, ALLOW_NULLMOVE, threadID); + value = -search(pos, ss, -(sp->alpha+1), -(sp->alpha), newDepth, sp->ply+1, true, threadID); } // Step 16. Undo move @@ -1983,7 +1793,7 @@ namespace { if (ss[sp->ply].reduction) { Value localAlpha = sp->alpha; - value = -search(pos, ss, -localAlpha, newDepth-ss[sp->ply].reduction, sp->ply+1, ALLOW_NULLMOVE, 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)); } } @@ -1993,7 +1803,7 @@ namespace { { Value localAlpha = sp->alpha; ss[sp->ply].reduction = Depth(0); - value = -search(pos, ss, -localAlpha, newDepth, sp->ply+1, ALLOW_NULLMOVE, 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)) { @@ -2001,7 +1811,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); } } @@ -2041,7 +1851,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. @@ -2313,18 +2123,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)) @@ -2649,10 +2455,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); @@ -2662,7 +2468,7 @@ namespace { // master should exit as last one. if (AllThreadsShouldExit) { - assert(!waitSp); + assert(!sp); threads[threadID].state = THREAD_TERMINATED; return; } @@ -2671,7 +2477,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; @@ -2708,8 +2514,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; @@ -2930,7 +2741,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; @@ -2985,12 +2796,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;