X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=6182d9c57068b59b071fa0336bd2830211ae97f9;hp=8f0bb76364e661656a5c8341c91c91b08480cb59;hb=d909d10f33df023be46a2633608bdf655d1f5a62;hpb=9bd856e28ec93a16a5db78b24f9579c607541def diff --git a/src/search.cpp b/src/search.cpp index 8f0bb763..6182d9c5 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -65,14 +65,14 @@ namespace { // Razoring and futility margin based on depth const int razor_margin[4] = { 483, 570, 603, 554 }; - Value futility_margin(Depth d) { return Value(150 * d); } + Value futility_margin(Depth d) { return Value(150 * d / ONE_PLY); } // Futility and reductions lookup tables, initialized at startup - int FutilityMoveCounts[2][16]; // [improving][depth] - Depth Reductions[2][2][64][64]; // [pv][improving][depth][moveNumber] + int FutilityMoveCounts[2][16]; // [improving][depth] + int Reductions[2][2][64][64]; // [pv][improving][depth][moveNumber] template Depth reduction(bool i, Depth d, int mn) { - return Reductions[PvNode][i][std::min(d, 63 * ONE_PLY)][std::min(mn, 63)]; + return Reductions[PvNode][i][std::min(d / ONE_PLY, 63)][std::min(mn, 63)] * ONE_PLY; } // Skill structure is used to implement strength limit @@ -113,8 +113,8 @@ namespace { std::copy(newPv.begin(), newPv.begin() + 3, pv); StateInfo st[2]; - pos.do_move(newPv[0], st[0], pos.gives_check(newPv[0], CheckInfo(pos))); - pos.do_move(newPv[1], st[1], pos.gives_check(newPv[1], CheckInfo(pos))); + pos.do_move(newPv[0], st[0], pos.gives_check(newPv[0])); + pos.do_move(newPv[1], st[1], pos.gives_check(newPv[1])); expectedPosKey = pos.key(); pos.undo_move(newPv[1]); pos.undo_move(newPv[0]); @@ -187,12 +187,12 @@ void Search::init() { if (r < 0.80) continue; - Reductions[NonPV][imp][d][mc] = int(std::round(r)) * ONE_PLY; - Reductions[PV][imp][d][mc] = std::max(Reductions[NonPV][imp][d][mc] - ONE_PLY, DEPTH_ZERO); + Reductions[NonPV][imp][d][mc] = int(std::round(r)); + Reductions[PV][imp][d][mc] = std::max(Reductions[NonPV][imp][d][mc] - 1, 0); // Increase reduction for non-PV nodes when eval is not improving - if (!imp && Reductions[NonPV][imp][d][mc] >= 2 * ONE_PLY) - Reductions[NonPV][imp][d][mc] += ONE_PLY; + if (!imp && Reductions[NonPV][imp][d][mc] >= 2) + Reductions[NonPV][imp][d][mc]++; } for (int d = 0; d < 16; ++d) @@ -228,7 +228,6 @@ uint64_t Search::perft(Position& pos, Depth depth) { StateInfo st; uint64_t cnt, nodes = 0; - CheckInfo ci(pos); const bool leaf = (depth == 2 * ONE_PLY); for (const auto& m : MoveList(pos)) @@ -237,7 +236,7 @@ uint64_t Search::perft(Position& pos, Depth depth) { cnt = 1, nodes++; else { - pos.do_move(m, st, pos.gives_check(m, ci)); + pos.do_move(m, st, pos.gives_check(m)); cnt = leaf ? MoveList(pos).size() : perft(pos, depth - ONE_PLY); nodes += cnt; pos.undo_move(m); @@ -368,15 +367,17 @@ void Thread::search() { multiPV = std::min(multiPV, rootMoves.size()); - // Iterative deepening loop until requested to stop or the target depth is reached. - while (++rootDepth < DEPTH_MAX && !Signals.stop && (!Limits.depth || Threads.main()->rootDepth <= Limits.depth)) + // Iterative deepening loop until requested to stop or the target depth is reached + while ( (rootDepth += ONE_PLY) < DEPTH_MAX + && !Signals.stop + && (!Limits.depth || Threads.main()->rootDepth / ONE_PLY <= Limits.depth)) { // Set up the new depths for the helper threads skipping on average every // 2nd ply (using a half-density matrix). if (!mainThread) { const Row& row = HalfDensity[(idx - 1) % HalfDensitySize]; - if (row[(rootDepth + rootPos.game_ply()) % row.size()]) + if (row[(rootDepth / ONE_PLY + rootPos.game_ply()) % row.size()]) continue; } @@ -552,6 +553,7 @@ namespace { assert(PvNode || (alpha == beta - 1)); assert(DEPTH_ZERO < depth && depth < DEPTH_MAX); assert(!(PvNode && cutNode)); + assert(depth / ONE_PLY * ONE_PLY == depth); Move pv[MAX_PLY+1], quietsSearched[64]; StateInfo st; @@ -620,7 +622,7 @@ namespace { // search to overwrite a previous full search TT value, so we use a different // position key in case of an excluded move. excludedMove = ss->excludedMove; - posKey = excludedMove ? pos.exclusion_key() : pos.key(); + posKey = pos.key() ^ Key(excludedMove); tte = TT.probe(posKey, ttHit); ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; ttMove = rootNode ? thisThread->rootMoves[thisThread->PVIdx].pv[0] @@ -648,7 +650,7 @@ namespace { } // Extra penalty for a quiet TT move in previous ply when it gets refuted - if ((ss-1)->moveCount == 1 && !pos.captured_piece_type()) + if ((ss-1)->moveCount == 1 && !pos.captured_piece()) { Value penalty = Value(d * d + 4 * d + 1); Square prevSq = to_sq((ss-1)->currentMove); @@ -723,14 +725,14 @@ namespace { // Step 6. Razoring (skipped when in check) if ( !PvNode && depth < 4 * ONE_PLY - && eval + razor_margin[depth] <= alpha - && ttMove == MOVE_NONE) + && ttMove == MOVE_NONE + && eval + razor_margin[depth / ONE_PLY] <= alpha) { if ( depth <= ONE_PLY && eval + razor_margin[3 * ONE_PLY] <= alpha) return qsearch(pos, ss, alpha, beta, DEPTH_ZERO); - Value ralpha = alpha - razor_margin[depth]; + Value ralpha = alpha - razor_margin[depth / ONE_PLY]; Value v = qsearch(pos, ss, ralpha, ralpha+1, DEPTH_ZERO); if (v <= ralpha) return v; @@ -756,7 +758,7 @@ namespace { assert(eval - beta >= 0); // Null move dynamic reduction based on depth and value - Depth R = ((823 + 67 * depth) / 256 + std::min((eval - beta) / PawnValueMg, 3)) * ONE_PLY; + Depth R = ((823 + 67 * depth / ONE_PLY) / 256 + std::min((eval - beta) / PawnValueMg, 3)) * ONE_PLY; pos.do_null_move(st); (ss+1)->skipEarlyPruning = true; @@ -786,9 +788,8 @@ namespace { } // Step 9. ProbCut (skipped when in check) - // If we have a very good capture (i.e. SEE > seeValues[captured_piece_type]) - // and a reduced search returns a value much above beta, we can (almost) - // safely prune the previous move. + // If we have a good enough capture and a reduced search returns a value + // much above beta, we can (almost) safely prune the previous move. if ( !PvNode && depth >= 5 * ONE_PLY && abs(beta) < VALUE_MATE_IN_MAX_PLY) @@ -800,15 +801,14 @@ namespace { assert((ss-1)->currentMove != MOVE_NONE); assert((ss-1)->currentMove != MOVE_NULL); - MovePicker mp(pos, ttMove, PieceValue[MG][pos.captured_piece_type()]); - CheckInfo ci(pos); + MovePicker mp(pos, ttMove, rbeta - ss->staticEval); while ((move = mp.next_move()) != MOVE_NONE) - if (pos.legal(move, ci.pinned)) + if (pos.legal(move)) { ss->currentMove = move; ss->counterMoves = &CounterMoveHistory[pos.moved_piece(move)][to_sq(move)]; - pos.do_move(move, st, pos.gives_check(move, ci)); + pos.do_move(move, st, pos.gives_check(move)); value = -search(pos, ss+1, -rbeta, -rbeta+1, rdepth, !cutNode); pos.undo_move(move); if (value >= rbeta) @@ -821,8 +821,9 @@ namespace { && !ttMove && (PvNode || ss->staticEval + 256 >= beta)) { + Depth d = (3 * depth / (4 * ONE_PLY) - 2) * ONE_PLY; ss->skipEarlyPruning = true; - search(pos, ss, alpha, beta, 3 * depth / 4 - 2 * ONE_PLY, cutNode); + search(pos, ss, alpha, beta, d, cutNode); ss->skipEarlyPruning = false; tte = TT.probe(posKey, ttHit); @@ -836,7 +837,6 @@ moves_loop: // When in check search starts from here const CounterMoveStats* fmh2 = (ss-4)->counterMoves; MovePicker mp(pos, ttMove, depth, ss); - CheckInfo ci(pos); value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc improving = ss->staticEval >= (ss-2)->staticEval /* || ss->staticEval == VALUE_NONE Already implicit in the previous condition */ @@ -881,12 +881,12 @@ moves_loop: // When in check search starts from here captureOrPromotion = pos.capture_or_promotion(move); moved_piece = pos.moved_piece(move); - givesCheck = type_of(move) == NORMAL && !ci.dcCandidates - ? ci.checkSquares[type_of(pos.piece_on(from_sq(move)))] & to_sq(move) - : pos.gives_check(move, ci); + givesCheck = type_of(move) == NORMAL && !pos.discovered_check_candidates() + ? pos.check_squares(type_of(pos.piece_on(from_sq(move)))) & to_sq(move) + : pos.gives_check(move); moveCountPruning = depth < 16 * ONE_PLY - && moveCount >= FutilityMoveCounts[improving][depth]; + && moveCount >= FutilityMoveCounts[improving][depth / ONE_PLY]; // Step 12. Extend checks if ( givesCheck @@ -902,12 +902,13 @@ moves_loop: // When in check search starts from here if ( singularExtensionNode && move == ttMove && !extension - && pos.legal(move, ci.pinned)) + && pos.legal(move)) { Value rBeta = ttValue - 2 * depth / ONE_PLY; + Depth d = (depth / (2 * ONE_PLY)) * ONE_PLY; ss->excludedMove = move; ss->skipEarlyPruning = true; - value = search(pos, ss, rBeta - 1, rBeta, depth / 2, cutNode); + value = search(pos, ss, rBeta - 1, rBeta, d, cutNode); ss->skipEarlyPruning = false; ss->excludedMove = MOVE_NONE; @@ -919,49 +920,53 @@ moves_loop: // When in check search starts from here newDepth = depth - ONE_PLY + extension; // Step 13. Pruning at shallow depth - if ( !rootNode - && !captureOrPromotion - && !inCheck - && !givesCheck - && !pos.advanced_pawn_push(move) - && bestValue > VALUE_MATED_IN_MAX_PLY) + if ( !rootNode + && !inCheck + && bestValue > VALUE_MATED_IN_MAX_PLY) { - // Move count based pruning - if (moveCountPruning) - continue; + if ( !captureOrPromotion + && !givesCheck + && !pos.advanced_pawn_push(move)) + { + // Move count based pruning + if (moveCountPruning) + continue; - predictedDepth = std::max(newDepth - reduction(improving, depth, moveCount), DEPTH_ZERO); + predictedDepth = std::max(newDepth - reduction(improving, depth, moveCount), DEPTH_ZERO); - // Countermoves based pruning - if ( predictedDepth < 3 * ONE_PLY - && move != ss->killers[0] - && (!cmh || (*cmh )[moved_piece][to_sq(move)] < VALUE_ZERO) - && (!fmh || (*fmh )[moved_piece][to_sq(move)] < VALUE_ZERO) - && (!fmh2 || (*fmh2)[moved_piece][to_sq(move)] < VALUE_ZERO || (cmh && fmh))) - continue; + // Countermoves based pruning + if ( predictedDepth < 3 * ONE_PLY + && (!cmh || (*cmh )[moved_piece][to_sq(move)] < VALUE_ZERO) + && (!fmh || (*fmh )[moved_piece][to_sq(move)] < VALUE_ZERO) + && (!fmh2 || (*fmh2)[moved_piece][to_sq(move)] < VALUE_ZERO || (cmh && fmh))) + continue; - // Futility pruning: parent node - if ( predictedDepth < 7 * ONE_PLY - && ss->staticEval + 256 + 200 * predictedDepth / ONE_PLY <= alpha) - continue; + // Futility pruning: parent node + if ( predictedDepth < 7 * ONE_PLY + && ss->staticEval + 256 + 200 * predictedDepth / ONE_PLY <= alpha) + continue; - // Prune moves with negative SEE at low depths and below a decreasing - // threshold at higher depths. - if (predictedDepth < 8 * ONE_PLY) - { - Value see_v = predictedDepth < 4 * ONE_PLY ? VALUE_ZERO - : -PawnValueMg * 2 * int(predictedDepth - 3 * ONE_PLY); + // Prune moves with negative SEE at low depths and below a decreasing + // threshold at higher depths. + if (predictedDepth < 8 * ONE_PLY) + { + Value see_v = predictedDepth < 4 * ONE_PLY ? VALUE_ZERO + : -PawnValueMg * 2 * int(predictedDepth - 3 * ONE_PLY) / ONE_PLY; - if (pos.see_sign(move) < see_v) - continue; + if (pos.see_sign(move) < see_v) + continue; + } } + else if ( depth < 3 * ONE_PLY + && pos.see_sign(move) < VALUE_ZERO) + continue; } // Speculative prefetch as early as possible prefetch(TT.first_entry(pos.key_after(move))); // Check for legality just before making the move - if (!rootNode && !pos.legal(move, ci.pinned)) + if (!rootNode && !pos.legal(move)) { ss->moveCount = --moveCount; continue; @@ -985,12 +990,6 @@ moves_loop: // When in check search starts from here r -= r ? ONE_PLY : DEPTH_ZERO; else { - Value val = thisThread->history[moved_piece][to_sq(move)] - + (cmh ? (*cmh )[moved_piece][to_sq(move)] : VALUE_ZERO) - + (fmh ? (*fmh )[moved_piece][to_sq(move)] : VALUE_ZERO) - + (fmh2 ? (*fmh2)[moved_piece][to_sq(move)] : VALUE_ZERO) - + thisThread->fromTo.get(~pos.side_to_move(), move); - // Increase reduction for cut nodes if (cutNode) r += 2 * ONE_PLY; @@ -1005,8 +1004,13 @@ moves_loop: // When in check search starts from here r -= 2 * ONE_PLY; // Decrease/increase reduction for moves with a good/bad history + Value val = thisThread->history[moved_piece][to_sq(move)] + + (cmh ? (*cmh )[moved_piece][to_sq(move)] : VALUE_ZERO) + + (fmh ? (*fmh )[moved_piece][to_sq(move)] : VALUE_ZERO) + + (fmh2 ? (*fmh2)[moved_piece][to_sq(move)] : VALUE_ZERO) + + thisThread->fromTo.get(~pos.side_to_move(), move); int rHist = (val - 8000) / 20000; - r = std::max(DEPTH_ZERO, r - rHist * ONE_PLY); + r = std::max(DEPTH_ZERO, (r / ONE_PLY - rHist) * ONE_PLY); } Depth d = std::max(newDepth - r, ONE_PLY); @@ -1139,7 +1143,7 @@ moves_loop: // When in check search starts from here } // Extra penalty for a quiet TT move in previous ply when it gets refuted - if ((ss-1)->moveCount == 1 && !pos.captured_piece_type()) + if ((ss-1)->moveCount == 1 && !pos.captured_piece()) { Value penalty = Value(d * d + 4 * d + 1); Square prevSq = to_sq((ss-1)->currentMove); @@ -1148,7 +1152,7 @@ moves_loop: // When in check search starts from here } // Bonus for prior countermove that caused the fail low else if ( depth >= 3 * ONE_PLY - && !pos.captured_piece_type() + && !pos.captured_piece() && is_ok((ss-1)->currentMove)) { int d = depth / ONE_PLY; @@ -1181,6 +1185,7 @@ moves_loop: // When in check search starts from here assert(alpha >= -VALUE_INFINITE && alpha < beta && beta <= VALUE_INFINITE); assert(PvNode || (alpha == beta - 1)); assert(depth <= DEPTH_ZERO); + assert(depth / ONE_PLY * ONE_PLY == depth); Move pv[MAX_PLY+1]; StateInfo st; @@ -1276,16 +1281,15 @@ moves_loop: // When in check search starts from here // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will // be generated. MovePicker mp(pos, ttMove, depth, to_sq((ss-1)->currentMove)); - CheckInfo ci(pos); // Loop through the moves until no moves remain or a beta cutoff occurs while ((move = mp.next_move()) != MOVE_NONE) { assert(is_ok(move)); - givesCheck = type_of(move) == NORMAL && !ci.dcCandidates - ? ci.checkSquares[type_of(pos.piece_on(from_sq(move)))] & to_sq(move) - : pos.gives_check(move, ci); + givesCheck = type_of(move) == NORMAL && !pos.discovered_check_candidates() + ? pos.check_squares(type_of(pos.piece_on(from_sq(move)))) & to_sq(move) + : pos.gives_check(move); // Futility pruning if ( !InCheck @@ -1325,7 +1329,7 @@ moves_loop: // When in check search starts from here prefetch(TT.first_entry(pos.key_after(move))); // Check for legality just before making the move - if (!pos.legal(move, ci.pinned)) + if (!pos.legal(move)) continue; ss->currentMove = move; @@ -1597,7 +1601,7 @@ bool RootMove::extract_ponder_from_tt(Position& pos) assert(pv.size() == 1); - pos.do_move(pv[0], st, pos.gives_check(pv[0], CheckInfo(pos))); + pos.do_move(pv[0], st, pos.gives_check(pv[0])); TTEntry* tte = TT.probe(pos.key(), ttHit); if (ttHit) @@ -1642,7 +1646,7 @@ void Tablebases::filter_root_moves(Position& pos, Search::RootMoves& rootMoves) RootInTB = root_probe_wdl(pos, rootMoves, TB::Score); // Only probe during search if winning - if (TB::Score <= VALUE_DRAW) + if (RootInTB && TB::Score <= VALUE_DRAW) Cardinality = 0; }