X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=f1ab80f29294e20401fb93e9736b3b2b679668de;hp=21756824b815bfa58f37f1f4f948277466dab7a8;hb=b9768b8bc5ec9e814faedccf557d0304997d8aaf;hpb=ecd07e51d0f03ccd3e41e5634518b299989254dd diff --git a/src/search.cpp b/src/search.cpp index 21756824..f1ab80f2 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -63,12 +63,10 @@ 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] 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)]; + inline Value futility_margin(Depth d) { + return Value(100 * int(d)); } // Reduction lookup tables (initialized at startup) and their access function @@ -84,6 +82,7 @@ namespace { double BestMoveChanges; Value DrawValue[COLOR_NB]; HistoryStats History; + GainsStats Gains; CountermovesStats Countermoves; template @@ -144,10 +143,6 @@ void Search::init() { Reductions[0][0][hd][mc] += ONE_PLY / 2; } - // 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); - // Init futility move count array for (d = 0; d < 32; ++d) { @@ -299,6 +294,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 +303,7 @@ namespace { TT.new_search(); History.clear(); + Gains.clear(); Countermoves.clear(); PVSize = Options["MultiPV"]; @@ -331,7 +328,7 @@ namespace { RootMoves[i].prevScore = RootMoves[i].score; // MultiPV loop. We perform a full root search for each PV line - for (PVIdx = 0; PVIdx < PVSize; ++PVIdx) + for (PVIdx = 0; PVIdx < PVSize && !Signals.stop; ++PVIdx) { // Reset aspiration window starting size if (depth >= 5) @@ -360,11 +357,11 @@ namespace { for (size_t i = 0; i <= PVIdx; ++i) RootMoves[i].insert_pv_in_tt(pos); - // If search has been stopped return immediately. Sorting and + // If search has been stopped break immediately. Sorting and // writing PV back to TT is safe becuase RootMoves is still // valid, although refers to previous iteration. if (Signals.stop) - return; + break; // When failing high/low give some update (without cluttering // the UI) before to research. @@ -421,7 +418,7 @@ namespace { Signals.stop = true; // Do we have time for the next iteration? Can we stop searching now? - if (Limits.use_time_management() && !Signals.stopOnPonderhit) + if (Limits.use_time_management() && !Signals.stop && !Signals.stopOnPonderhit) { bool stop = false; // Local variable, not the volatile Signals.stop @@ -493,9 +490,8 @@ namespace { SplitPoint* splitPoint; Key posKey; Move ttMove, move, excludedMove, bestMove, threatMove; - Depth ext, newDepth; - Value bestValue, value, ttValue; - Value eval, nullValue; + Depth ext, newDepth, predictedDepth; + Value bestValue, value, ttValue, eval, nullValue, futilityValue; bool inCheck, givesCheck, pvMove, singularExtensionNode, improving; bool captureOrPromotion, dangerous, doFullDepthSearch; int moveCount, quietCount; @@ -523,7 +519,6 @@ namespace { bestValue = -VALUE_INFINITE; ss->currentMove = threatMove = (ss+1)->excludedMove = bestMove = MOVE_NONE; ss->ply = (ss-1)->ply + 1; - ss->futilityMoveCount = 0; (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO; (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; @@ -608,6 +603,16 @@ namespace { TT.store(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, ss->staticEval); } + 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) if ( !PvNode && depth < 4 * ONE_PLY @@ -624,15 +629,15 @@ namespace { return v; } - // Step 7. post-Futility pruning (skipped when in check) + // Step 7. Futility pruning: child node (skipped when in check) if ( !PvNode && !ss->skipNullMove && depth < 7 * ONE_PLY - && eval - futility_margin(depth, (ss-1)->futilityMoveCount) >= beta + && eval - futility_margin(depth) >= beta && abs(beta) < VALUE_MATE_IN_MAX_PLY && abs(eval) < VALUE_KNOWN_WIN && pos.non_pawn_material(pos.side_to_move())) - return eval - futility_margin(depth, (ss-1)->futilityMoveCount); + return eval - futility_margin(depth); // Step 8. Null move search with verification search (is omitted in PV nodes) if ( !PvNode @@ -834,13 +839,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) + // Step 13. Pruning at shallow depth (exclude 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,9 +859,30 @@ moves_loop: // When in check and at SpNode search starts from here continue; } + predictedDepth = newDepth - reduction(improving, depth, moveCount); + + // Futility pruning: parent node + if (predictedDepth < 7 * ONE_PLY) + { + futilityValue = ss->staticEval + futility_margin(predictedDepth) + + Value(128) + Gains[pos.moved_piece(move)][to_sq(move)]; + + if (futilityValue <= alpha) + { + 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) + if (predictedDepth < 4 * ONE_PLY && pos.see_sign(move) < 0) { if (SpNode) splitPoint->mutex.lock(); @@ -864,17 +890,12 @@ moves_loop: // When in check and at SpNode search starts from here continue; } - // We have not pruned the move that will be searched, but remember how - // far in the move list we are to be more aggressive in the child node. - ss->futilityMoveCount = moveCount; } - else - ss->futilityMoveCount = 0; // Check for legality only before to do the move if (!RootNode && !SpNode && !pos.legal(move, ci.pinned)) { - --moveCount; + moveCount--; continue; } @@ -1322,7 +1343,7 @@ moves_loop: // When in check and at SpNode search starts from here // We exclude the trivial case where a sliding piece does in two moves what // it could do in one move: eg. Ra1a2, Ra2a3. if ( m2to == m1from - || (m1to == m2from && !squares_aligned(m1from, m2from, m2to))) + || (m1to == m2from && !aligned(m1from, m2from, m2to))) return true; // Second one moves through the square vacated by first one @@ -1507,7 +1528,7 @@ void RootMove::extract_pv_from_tt(Position& pos) { } while ( tte && pos.pseudo_legal(m = tte->move()) // Local copy, TT could change - && pos.legal(m, pos.pinned_pieces()) + && pos.legal(m, pos.pinned_pieces(pos.side_to_move())) && ply < MAX_PLY && (!pos.is_draw() || ply < 2));