X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=0ed6b191b8bbe7e16d5585a68b85662c0c363616;hp=ff31e0360a76c2c5201cd13e8944024054980fc0;hb=b915fdc889e7e154e030189d277b5242433407b4;hpb=1ee2838214fcbadc352fb17c8c6fa1142ae5dcb0 diff --git a/src/search.cpp b/src/search.cpp index ff31e036..0ed6b191 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -29,6 +29,7 @@ #include "misc.h" #include "movegen.h" #include "movepick.h" +#include "position.h" #include "search.h" #include "timeman.h" #include "thread.h" @@ -45,7 +46,6 @@ namespace Search { namespace Tablebases { int Cardinality; - uint64_t Hits; bool RootInTB; bool UseRule50; Depth ProbeDepth; @@ -157,7 +157,6 @@ namespace { EasyMoveManager EasyMove; Value DrawValue[COLOR_NB]; - CounterMoveHistoryStats CounterMoveHistory; template Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode); @@ -184,8 +183,6 @@ void Search::init() { for (int mc = 1; mc < 64; ++mc) { double r = log(d) * log(mc) / 2; - if (r < 0.80) - continue; Reductions[NonPV][imp][d][mc] = int(std::round(r)); Reductions[PV][imp][d][mc] = std::max(Reductions[NonPV][imp][d][mc] - 1, 0); @@ -208,13 +205,13 @@ void Search::init() { void Search::clear() { TT.clear(); - CounterMoveHistory.clear(); for (Thread* th : Threads) { th->history.clear(); th->counterMoves.clear(); th->fromTo.clear(); + th->counterMoveHistory.clear(); } Threads.main()->previousScore = VALUE_INFINITE; @@ -462,11 +459,7 @@ void Thread::search() { if (!mainThread) continue; - if (Signals.stop) - sync_cout << "info nodes " << Threads.nodes_searched() - << " time " << Time.elapsed() << sync_endl; - - else if (PVIdx + 1 == multiPV || Time.elapsed() > 3000) + if (Signals.stop || PVIdx + 1 == multiPV || Time.elapsed() > 3000) sync_cout << UCI::pv(rootPos, rootDepth, alpha, beta) << sync_endl; } @@ -506,7 +499,7 @@ void Thread::search() { if ( rootMoves.size() == 1 || Time.elapsed() > Time.optimum() * unstablePvFactor * improvingFactor / 628 - || (mainThread->easyMovePlayed = doEasyMove)) + || (mainThread->easyMovePlayed = doEasyMove, doEasyMove)) { // If we are allowed to ponder do not stop the search now but // keep pondering until the GUI sends "ponderhit" or "stop". @@ -560,7 +553,7 @@ namespace { TTEntry* tte; Key posKey; Move ttMove, move, excludedMove, bestMove; - Depth extension, newDepth, predictedDepth; + Depth extension, newDepth; Value bestValue, value, ttValue, eval, nullValue; bool ttHit, inCheck, givesCheck, singularExtensionNode, improving; bool captureOrPromotion, doFullDepthSearch, moveCountPruning; @@ -571,6 +564,7 @@ namespace { Thread* thisThread = pos.this_thread(); inCheck = pos.checkers(); moveCount = quietCount = ss->moveCount = 0; + ss->history = VALUE_ZERO; bestValue = -VALUE_INFINITE; ss->ply = (ss-1)->ply + 1; @@ -622,7 +616,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] @@ -636,8 +630,6 @@ namespace { && (ttValue >= beta ? (tte->bound() & BOUND_LOWER) : (tte->bound() & BOUND_UPPER))) { - ss->currentMove = ttMove; // Can be MOVE_NONE - // If ttMove is quiet, update killers, history, counter move on TT hit if (ttValue >= beta && ttMove) { @@ -650,7 +642,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); @@ -670,11 +662,12 @@ namespace { && pos.rule50_count() == 0 && !pos.can_castle(ANY_CASTLING)) { - int found, v = Tablebases::probe_wdl(pos, &found); + TB::ProbeState err; + TB::WDLScore v = Tablebases::probe_wdl(pos, &err); - if (found) + if (err != TB::ProbeState::FAIL) { - TB::Hits++; + thisThread->tbHits++; int drawScore = TB::UseRule50 ? 1 : 0; @@ -725,11 +718,10 @@ namespace { // Step 6. Razoring (skipped when in check) if ( !PvNode && depth < 4 * ONE_PLY - && eval + razor_margin[depth / ONE_PLY] <= 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) + if (depth <= ONE_PLY) return qsearch(pos, ss, alpha, beta, DEPTH_ZERO); Value ralpha = alpha - razor_margin[depth / ONE_PLY]; @@ -744,7 +736,7 @@ namespace { && eval - futility_margin(depth) >= beta && eval < VALUE_KNOWN_WIN // Do not return unproven wins && pos.non_pawn_material(pos.side_to_move())) - return eval - futility_margin(depth); + return eval; // Step 8. Null move search with verification search (is omitted in PV nodes) if ( !PvNode @@ -788,9 +780,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) @@ -802,13 +793,13 @@ namespace { assert((ss-1)->currentMove != MOVE_NONE); assert((ss-1)->currentMove != MOVE_NULL); - MovePicker mp(pos, ttMove, PieceValue[MG][pos.captured_piece_type()]); + MovePicker mp(pos, ttMove, rbeta - ss->staticEval); while ((move = mp.next_move()) != MOVE_NONE) if (pos.legal(move)) { ss->currentMove = move; - ss->counterMoves = &CounterMoveHistory[pos.moved_piece(move)][to_sq(move)]; + ss->counterMoves = &thisThread->counterMoveHistory[pos.moved_piece(move)][to_sq(move)]; pos.do_move(move, st, pos.gives_check(move)); value = -search(pos, ss+1, -rbeta, -rbeta+1, rdepth, !cutNode); pos.undo_move(move); @@ -846,8 +837,7 @@ moves_loop: // When in check search starts from here singularExtensionNode = !rootNode && depth >= 8 * ONE_PLY && ttMove != MOVE_NONE - /* && ttValue != VALUE_NONE Already implicit in the next condition */ - && abs(ttValue) < VALUE_KNOWN_WIN + && ttValue != VALUE_NONE && !excludedMove // Recursive singular search is not allowed && (tte->bound() & BOUND_LOWER) && tte->depth() >= depth - 3 * ONE_PLY; @@ -892,7 +882,7 @@ moves_loop: // When in check search starts from here // Step 12. Extend checks if ( givesCheck && !moveCountPruning - && pos.see_sign(move) >= VALUE_ZERO) + && pos.see_ge(move, VALUE_ZERO)) extension = ONE_PLY; // Singular extension search. If all moves but one fail low on a search of @@ -905,7 +895,7 @@ moves_loop: // When in check search starts from here && !extension && pos.legal(move)) { - Value rBeta = ttValue - 2 * depth / ONE_PLY; + Value rBeta = std::max(ttValue - 2 * depth / ONE_PLY, -VALUE_MATE); Depth d = (depth / (2 * ONE_PLY)) * ONE_PLY; ss->excludedMove = move; ss->skipEarlyPruning = true; @@ -921,42 +911,42 @@ 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 + && 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); + // Reduced depth of the next LMR search + int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount), DEPTH_ZERO) / ONE_PLY; - // 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; - - // Futility pruning: parent node - if ( predictedDepth < 7 * ONE_PLY - && ss->staticEval + 256 + 200 * predictedDepth / ONE_PLY <= alpha) - continue; + // Countermoves based pruning + if ( lmrDepth < 3 + && (!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; - // 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; + // Futility pruning: parent node + if ( lmrDepth < 7 + && !inCheck + && ss->staticEval + 256 + 200 * lmrDepth <= alpha) + continue; - if (pos.see_sign(move) < see_v) + // Prune moves with negative SEE + if ( lmrDepth < 8 + && !pos.see_ge(move, Value(-35 * lmrDepth * lmrDepth))) continue; } + else if ( depth < 7 * ONE_PLY + && !extension + && !pos.see_ge(move, Value(-35 * depth / ONE_PLY * depth / ONE_PLY))) + continue; } // Speculative prefetch as early as possible @@ -970,7 +960,7 @@ moves_loop: // When in check search starts from here } ss->currentMove = move; - ss->counterMoves = &CounterMoveHistory[moved_piece][to_sq(move)]; + ss->counterMoves = &thisThread->counterMoveHistory[moved_piece][to_sq(move)]; // Step 14. Make the move pos.do_move(move, st, givesCheck); @@ -997,17 +987,25 @@ moves_loop: // When in check search starts from here // because the destination square is empty. else if ( type_of(move) == NORMAL && type_of(pos.piece_on(to_sq(move))) != PAWN - && pos.see(make_move(to_sq(move), from_sq(move))) < VALUE_ZERO) + && !pos.see_ge(make_move(to_sq(move), from_sq(move)), VALUE_ZERO)) r -= 2 * ONE_PLY; + ss->history = 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) + - 8000; // Correction factor + + // Decrease/increase reduction by comparing opponent's stat score + if (ss->history > VALUE_ZERO && (ss-1)->history < VALUE_ZERO) + r -= ONE_PLY; + + else if (ss->history < VALUE_ZERO && (ss-1)->history > VALUE_ZERO) + r += 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 / ONE_PLY - rHist) * ONE_PLY); + r = std::max(DEPTH_ZERO, (r / ONE_PLY - ss->history / 20000) * ONE_PLY); } Depth d = std::max(newDepth - r, ONE_PLY); @@ -1125,6 +1123,9 @@ moves_loop: // When in check search starts from here // All legal moves have been searched and if there are no legal moves, it // must be a mate or a stalemate. If we are in a singular extension search then // return a fail low score. + + assert(moveCount || !inCheck || excludedMove || !MoveList(pos).size()); + if (!moveCount) bestValue = excludedMove ? alpha : inCheck ? mated_in(ss->ply) : DrawValue[pos.side_to_move()]; @@ -1140,7 +1141,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); @@ -1149,7 +1150,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; @@ -1228,10 +1229,7 @@ moves_loop: // When in check search starts from here && ttValue != VALUE_NONE // Only in case of TT access race && (ttValue >= beta ? (tte->bound() & BOUND_LOWER) : (tte->bound() & BOUND_UPPER))) - { - ss->currentMove = ttMove; // Can be MOVE_NONE return ttValue; - } // Evaluate the position statically if (InCheck) @@ -1304,7 +1302,7 @@ moves_loop: // When in check search starts from here continue; } - if (futilityBase <= alpha && pos.see(move) <= VALUE_ZERO) + if (futilityBase <= alpha && !pos.see_ge(move, VALUE_ZERO + 1)) { bestValue = std::max(bestValue, futilityBase); continue; @@ -1319,7 +1317,7 @@ moves_loop: // When in check search starts from here // Don't search moves with negative SEE values if ( (!InCheck || evasionPrunable) && type_of(move) != PROMOTION - && pos.see_sign(move) < VALUE_ZERO) + && !pos.see_ge(move, VALUE_ZERO)) continue; // Speculative prefetch as early as possible @@ -1524,7 +1522,7 @@ moves_loop: // When in check search starts from here if ( (Limits.use_time_management() && elapsed > Time.maximum() - 10) || (Limits.movetime && elapsed >= Limits.movetime) - || (Limits.nodes && Threads.nodes_searched() >= Limits.nodes)) + || (Limits.nodes && Threads.nodes_searched() >= (uint64_t)Limits.nodes)) Signals.stop = true; } @@ -1541,7 +1539,8 @@ string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) { const RootMoves& rootMoves = pos.this_thread()->rootMoves; size_t PVIdx = pos.this_thread()->PVIdx; size_t multiPV = std::min((size_t)Options["MultiPV"], rootMoves.size()); - uint64_t nodes_searched = Threads.nodes_searched(); + uint64_t nodesSearched = Threads.nodes_searched(); + uint64_t tbHits = Threads.tb_hits() + (TB::RootInTB ? rootMoves.size() : 0); for (size_t i = 0; i < multiPV; ++i) { @@ -1568,13 +1567,13 @@ string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) { if (!tb && i == PVIdx) ss << (v >= beta ? " lowerbound" : v <= alpha ? " upperbound" : ""); - ss << " nodes " << nodes_searched - << " nps " << nodes_searched * 1000 / elapsed; + ss << " nodes " << nodesSearched + << " nps " << nodesSearched * 1000 / elapsed; if (elapsed > 1000) // Earlier makes little sense ss << " hashfull " << TT.hashfull(); - ss << " tbhits " << TB::Hits + ss << " tbhits " << tbHits << " time " << elapsed << " pv"; @@ -1591,13 +1590,16 @@ string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) { /// fail high at root. We try hard to have a ponder move to return to the GUI, /// otherwise in case of 'ponder on' we have nothing to think on. -bool RootMove::extract_ponder_from_tt(Position& pos) -{ +bool RootMove::extract_ponder_from_tt(Position& pos) { + StateInfo st; bool ttHit; assert(pv.size() == 1); + if (!pv[0]) + return false; + pos.do_move(pv[0], st, pos.gives_check(pv[0])); TTEntry* tte = TT.probe(pos.key(), ttHit); @@ -1614,7 +1616,6 @@ bool RootMove::extract_ponder_from_tt(Position& pos) void Tablebases::filter_root_moves(Position& pos, Search::RootMoves& rootMoves) { - Hits = 0; RootInTB = false; UseRule50 = Options["Syzygy50MoveRule"]; ProbeDepth = Options["SyzygyProbeDepth"] * ONE_PLY; @@ -1643,17 +1644,12 @@ 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; } - if (RootInTB) - { - Hits = rootMoves.size(); - - if (!UseRule50) - TB::Score = TB::Score > VALUE_DRAW ? VALUE_MATE - MAX_PLY - 1 - : TB::Score < VALUE_DRAW ? -VALUE_MATE + MAX_PLY + 1 - : VALUE_DRAW; - } + if (RootInTB && !UseRule50) + TB::Score = TB::Score > VALUE_DRAW ? VALUE_MATE - MAX_PLY - 1 + : TB::Score < VALUE_DRAW ? -VALUE_MATE + MAX_PLY + 1 + : VALUE_DRAW; }