X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=b465a5b12f7a35125d12251d0c2441fb8509f514;hp=0de9e8f9c85da4d7800ccdd32086eb831f0a0454;hb=343544f3f7fe780a4231b78646ab2fd61760e294;hpb=13d1f0ae4301b86c610a58332c3c19d9101704da diff --git a/src/search.cpp b/src/search.cpp index 0de9e8f9..b465a5b1 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -63,12 +63,13 @@ namespace { inline Value razor_margin(Depth d) { return Value(512 + 16 * int(d)); } // Futility lookup tables (initialized at startup) and their access functions - Value FutilityMargins[14][64]; // [depth][moveNumber] + Value FutilityMargins[16][64]; // [depth][moveNumber] int FutilityMoveCounts[2][32]; // [improving][depth] inline Value futility_margin(Depth d, int mn) { - assert(DEPTH_ZERO <= d && d < 7 * ONE_PLY); - return FutilityMargins[d][std::min(mn, 63)]; + + return d < 7 * ONE_PLY ? FutilityMargins[std::max(int(d), 1)][std::min(mn, 63)] + : 2 * VALUE_INFINITE; } // Reduction lookup tables (initialized at startup) and their access function @@ -84,6 +85,7 @@ namespace { double BestMoveChanges; Value DrawValue[COLOR_NB]; HistoryStats History; + GainsStats Gains; CountermovesStats Countermoves; template @@ -145,8 +147,8 @@ void Search::init() { } // Init futility margins array - for (d = 0; d < 14; ++d) for (mc = 0; mc < 64; ++mc) - FutilityMargins[d][mc] = Value(112 * int(2.9 * log(d >= 1 ? double(d) : 1.0)) - 8 * mc + 45); + for (d = 1; d < 16; ++d) for (mc = 0; mc < 64; ++mc) + FutilityMargins[d][mc] = Value(112 * int(2.9 * log(double(d))) - 8 * mc + 45); // Init futility move count array for (d = 0; d < 32; ++d) @@ -299,6 +301,7 @@ namespace { Value bestValue, alpha, beta, delta; std::memset(ss-2, 0, 5 * sizeof(Stack)); + (ss-1)->currentMove = MOVE_NULL; // Hack to skip update gains depth = 0; BestMoveChanges = 0; @@ -307,6 +310,7 @@ namespace { TT.new_search(); History.clear(); + Gains.clear(); Countermoves.clear(); PVSize = Options["MultiPV"]; @@ -495,7 +499,7 @@ namespace { Move ttMove, move, excludedMove, bestMove, threatMove; Depth ext, newDepth; Value bestValue, value, ttValue; - Value eval, nullValue; + Value eval, nullValue, futilityValue; bool inCheck, givesCheck, pvMove, singularExtensionNode, improving; bool captureOrPromotion, dangerous, doFullDepthSearch; int moveCount, quietCount; @@ -587,15 +591,16 @@ namespace { // Step 5. Evaluate the position statically and update parent's gain statistics if (inCheck) { - ss->staticEval = eval = VALUE_NONE; + ss->staticEval = ss->evalMargin = eval = VALUE_NONE; goto moves_loop; } else if (tte) { // Never assume anything on values stored in TT - if ((ss->staticEval = eval = tte->eval_value()) == VALUE_NONE) - eval = ss->staticEval = evaluate(pos); + if ( (ss->staticEval = eval = tte->eval_value()) == VALUE_NONE + ||(ss->evalMargin = tte->eval_margin()) == VALUE_NONE) + eval = ss->staticEval = evaluate(pos, ss->evalMargin); // Can ttValue be used as a better position evaluation? if (ttValue != VALUE_NONE) @@ -604,8 +609,21 @@ namespace { } else { - eval = ss->staticEval = evaluate(pos); - TT.store(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, ss->staticEval); + eval = ss->staticEval = evaluate(pos, ss->evalMargin); + TT.store(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, + ss->staticEval, ss->evalMargin); + } + + // Update gain for the parent non-capture move given the static position + // evaluation before and after the move. + if ( !pos.captured_piece_type() + && ss->staticEval != VALUE_NONE + && (ss-1)->staticEval != VALUE_NONE + && (move = (ss-1)->currentMove) != MOVE_NULL + && type_of(move) == NORMAL) + { + Square to = to_sq(move); + Gains.update(pos.piece_on(to), to, -(ss-1)->staticEval - ss->staticEval); } // Step 6. Razoring (skipped when in check) @@ -624,10 +642,12 @@ namespace { return v; } - // Step 7. post-Futility pruning (skipped when in check) + // Step 7. Static null move pruning (skipped when in check) + // We're betting that the opponent doesn't have a move that will reduce + // the score by more than futility_margin(depth) if we do a null move. if ( !PvNode && !ss->skipNullMove - && depth < 7 * ONE_PLY + && depth < 4 * ONE_PLY && eval - futility_margin(depth, (ss-1)->futilityMoveCount) >= beta && abs(beta) < VALUE_MATE_IN_MAX_PLY && abs(eval) < VALUE_KNOWN_WIN @@ -834,13 +854,13 @@ moves_loop: // When in check and at SpNode search starts from here // Update current move (this must be done after singular extension search) newDepth = depth - ONE_PLY + ext; - Depth predictedDepth = newDepth - reduction(improving, depth, moveCount); // Step 13. Futility pruning (is omitted in PV nodes) if ( !PvNode && !captureOrPromotion && !inCheck && !dangerous + /* && move != ttMove Already implicit in the next condition */ && bestValue > VALUE_MATED_IN_MAX_PLY) { // Move count based pruning @@ -854,6 +874,26 @@ moves_loop: // When in check and at SpNode search starts from here continue; } + // Value based pruning + // We illogically ignore reduction condition depth >= 3*ONE_PLY for predicted depth, + // but fixing this made program slightly weaker. + Depth predictedDepth = newDepth - reduction(improving, depth, moveCount); + futilityValue = ss->staticEval + ss->evalMargin + futility_margin(predictedDepth, moveCount) + + Gains[pos.moved_piece(move)][to_sq(move)]; + + if (futilityValue < beta) + { + bestValue = std::max(bestValue, futilityValue); + + if (SpNode) + { + splitPoint->mutex.lock(); + if (bestValue > splitPoint->bestValue) + splitPoint->bestValue = bestValue; + } + continue; + } + // Prune moves with negative SEE at low depths if ( predictedDepth < 4 * ONE_PLY && pos.see_sign(move) < 0) @@ -1039,7 +1079,7 @@ moves_loop: // When in check and at SpNode search starts from here TT.store(posKey, value_to_tt(bestValue, ss->ply), bestValue >= beta ? BOUND_LOWER : PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER, - depth, bestMove, ss->staticEval); + depth, bestMove, ss->staticEval, ss->evalMargin); // Quiet best move: update killers, history and countermoves if ( bestValue >= beta @@ -1132,7 +1172,7 @@ moves_loop: // When in check and at SpNode search starts from here // Evaluate the position statically if (InCheck) { - ss->staticEval = VALUE_NONE; + ss->staticEval = ss->evalMargin = VALUE_NONE; bestValue = futilityBase = -VALUE_INFINITE; } else @@ -1140,8 +1180,9 @@ moves_loop: // When in check and at SpNode search starts from here if (tte) { // Never assume anything on values stored in TT - if ((ss->staticEval = bestValue = tte->eval_value()) == VALUE_NONE) - ss->staticEval = bestValue = evaluate(pos); + if ( (ss->staticEval = bestValue = tte->eval_value()) == VALUE_NONE + ||(ss->evalMargin = tte->eval_margin()) == VALUE_NONE) + ss->staticEval = bestValue = evaluate(pos, ss->evalMargin); // Can ttValue be used as a better position evaluation? if (ttValue != VALUE_NONE) @@ -1149,14 +1190,14 @@ moves_loop: // When in check and at SpNode search starts from here bestValue = ttValue; } else - ss->staticEval = bestValue = evaluate(pos); + ss->staticEval = bestValue = evaluate(pos, ss->evalMargin); // Stand pat. Return immediately if static value is at least beta if (bestValue >= beta) { if (!tte) TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER, - DEPTH_NONE, MOVE_NONE, ss->staticEval); + DEPTH_NONE, MOVE_NONE, ss->staticEval, ss->evalMargin); return bestValue; } @@ -1164,7 +1205,7 @@ moves_loop: // When in check and at SpNode search starts from here if (PvNode && bestValue > alpha) alpha = bestValue; - futilityBase = bestValue + Value(128); + futilityBase = bestValue + ss->evalMargin + Value(128); } // Initialize a MovePicker object for the current position, and prepare @@ -1253,7 +1294,7 @@ moves_loop: // When in check and at SpNode search starts from here else // Fail high { TT.store(posKey, value_to_tt(value, ss->ply), BOUND_LOWER, - ttDepth, move, ss->staticEval); + ttDepth, move, ss->staticEval, ss->evalMargin); return value; } @@ -1268,7 +1309,7 @@ moves_loop: // When in check and at SpNode search starts from here TT.store(posKey, value_to_tt(bestValue, ss->ply), PvNode && bestValue > oldAlpha ? BOUND_EXACT : BOUND_UPPER, - ttDepth, bestMove, ss->staticEval); + ttDepth, bestMove, ss->staticEval, ss->evalMargin); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1531,7 +1572,7 @@ void RootMove::insert_pv_in_tt(Position& pos) { tte = TT.probe(pos.key()); if (!tte || tte->move() != pv[ply]) // Don't overwrite correct entries - TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply], VALUE_NONE); + TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply], VALUE_NONE, VALUE_NONE); assert(MoveList(pos).contains(pv[ply]));