X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=3f9e29da0485763dbd40221008a1d977479d2794;hp=e773a36a72af9b40915dfede7c9a79ed45a9c5b1;hb=dc130042831cdb52994aa8165b1cf8f49eef8640;hpb=f6f1d2422303923927c0c088dee1d6df22dc4b98 diff --git a/src/search.cpp b/src/search.cpp index e773a36a..3f9e29da 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -66,22 +66,29 @@ namespace { // Different node types, used as template parameter enum NodeType { Root, PV, NonPV }; - // Dynamic razoring margin based on depth + // Razoring and futility margin based on depth inline Value razor_margin(Depth d) { return Value(512 + 32 * d); } + inline Value futility_margin(Depth d) { return Value(200 * d); } - // Futility lookup tables (initialized at startup) and their access functions - int FutilityMoveCounts[2][16]; // [improving][depth] + // Futility and reductions lookup tables, initialized at startup + int FutilityMoveCounts[2][16]; // [improving][depth] + Depth Reductions[2][2][64][64]; // [pv][improving][depth][moveNumber] - inline Value futility_margin(Depth d) { - return Value(200 * d); + template inline Depth reduction(bool i, Depth d, int mn) { + return Reductions[PvNode][i][std::min(d, 63 * ONE_PLY)][std::min(mn, 63)]; } - // Reduction lookup tables (initialized at startup) and their access function - int8_t Reductions[2][2][64][64]; // [pv][improving][depth][moveNumber] + // Skill struct is used to implement strength limiting + struct Skill { + Skill(int l) : level(l) {} + bool enabled() const { return level < 20; } + bool time_to_pick(Depth depth) const { return depth / ONE_PLY == 1 + level; } + Move best_move(size_t multiPV) { return best ? best : pick_best(multiPV); } + Move pick_best(size_t multiPV); - template inline Depth reduction(bool i, Depth d, int mn) { - return (Depth) Reductions[PvNode][i][std::min(int(d), 63)][std::min(mn, 63)]; - } + int level; + Move best = MOVE_NONE; + }; size_t PVIdx; TimeManager TimeMgr; @@ -102,18 +109,6 @@ namespace { Value value_from_tt(Value v, int ply); void update_pv(Move* pv, Move move, Move* childPv); void update_stats(const Position& pos, Stack* ss, Move move, Depth depth, Move* quiets, int quietsCnt); - string uci_pv(const Position& pos, Depth depth, Value alpha, Value beta); - - struct Skill { - Skill(int l) : level(l) {} - bool enabled() const { return level < 20; } - bool time_to_pick(Depth depth) const { return depth / ONE_PLY == 1 + level; } - Move best_move(size_t multiPV) { return best ? best : pick_best(multiPV); } - Move pick_best(size_t multiPV); - - int level; - Move best = MOVE_NONE; - }; } // namespace @@ -122,25 +117,23 @@ namespace { void Search::init() { - // Init reductions array - for (int d = 1; d < 64; ++d) - for (int mc = 1; mc < 64; ++mc) - { - double pvRed = 0.00 + log(double(d)) * log(double(mc)) / 3.00; - double nonPVRed = 0.33 + log(double(d)) * log(double(mc)) / 2.25; + const double K[][2] = {{ 0.83, 2.25 }, { 0.50, 3.00 }}; - Reductions[1][1][d][mc] = int8_t( pvRed >= 1.0 ? pvRed + 0.5: 0); - Reductions[0][1][d][mc] = int8_t(nonPVRed >= 1.0 ? nonPVRed + 0.5: 0); + for (int pv = 0; pv <= 1; ++pv) + for (int imp = 0; imp <= 1; ++imp) + for (int d = 1; d < 64; ++d) + for (int mc = 1; mc < 64; ++mc) + { + double r = K[pv][0] + log(d) * log(mc) / K[pv][1]; - Reductions[1][0][d][mc] = Reductions[1][1][d][mc]; - Reductions[0][0][d][mc] = Reductions[0][1][d][mc]; + if (r >= 1.5) + Reductions[pv][imp][d][mc] = int(r) * ONE_PLY; - // Increase reduction when eval is not improving - if (Reductions[0][0][d][mc] >= 2) - Reductions[0][0][d][mc] += 1; - } + // Increase reduction when eval is not improving + if (!pv && !imp && Reductions[pv][imp][d][mc] >= 2 * ONE_PLY) + Reductions[pv][imp][d][mc] += ONE_PLY; + } - // Init futility move count array for (int d = 0; d < 16; ++d) { FutilityMoveCounts[0][d] = int(2.4 + 0.773 * pow(d + 0.00, 1.8)); @@ -159,19 +152,19 @@ uint64_t Search::perft(Position& pos, Depth depth) { CheckInfo ci(pos); const bool leaf = (depth == 2 * ONE_PLY); - for (const ExtMove& ms : MoveList(pos)) + for (const auto& m : MoveList(pos)) { if (Root && depth <= ONE_PLY) cnt = 1, nodes++; else { - pos.do_move(ms.move, st, ci, pos.gives_check(ms.move, ci)); + pos.do_move(m, st, pos.gives_check(m, ci)); cnt = leaf ? MoveList(pos).size() : perft(pos, depth - ONE_PLY); nodes += cnt; - pos.undo_move(ms.move); + pos.undo_move(m); } if (Root) - sync_cout << UCI::move(ms.move, pos.is_chess960()) << ": " << cnt << sync_endl; + sync_cout << UCI::move(m, pos.is_chess960()) << ": " << cnt << sync_endl; } return nodes; } @@ -206,7 +199,7 @@ void Search::think() { if (RootMoves.empty()) { - RootMoves.push_back(MOVE_NONE); + RootMoves.push_back(RootMove(MOVE_NONE)); sync_cout << "info depth 0 score " << UCI::value(RootPos.checkers() ? -VALUE_MATE : VALUE_DRAW) << sync_endl; @@ -363,7 +356,7 @@ namespace { if ( multiPV == 1 && (bestValue <= alpha || bestValue >= beta) && Time::now() - SearchTime > 3000) - sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl; + sync_cout << UCI::pv(pos, depth, alpha, beta) << sync_endl; // In case of failing low/high increase aspiration window and // re-search, otherwise exit the loop. @@ -396,7 +389,7 @@ namespace { << " time " << Time::now() - SearchTime << sync_endl; else if (PVIdx + 1 == multiPV || Time::now() - SearchTime > 3000) - sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl; + sync_cout << UCI::pv(pos, depth, alpha, beta) << sync_endl; } // If skill level is enabled and time is up, pick a sub-optimal best move @@ -701,7 +694,7 @@ namespace { if (pos.legal(move, ci.pinned)) { ss->currentMove = move; - pos.do_move(move, st, ci, pos.gives_check(move, ci)); + pos.do_move(move, st, pos.gives_check(move, ci)); value = -search(pos, ss+1, -rbeta, -rbeta+1, rdepth, !cutNode); pos.undo_move(move); if (value >= rbeta) @@ -879,7 +872,7 @@ moves_loop: // When in check and at SpNode search starts from here } // Speculative prefetch as early as possible - prefetch((char*)TT.first_entry(pos.key_after(move))); + prefetch(TT.first_entry(pos.key_after(move))); // Check for legality just before making the move if (!RootNode && !SpNode && !pos.legal(move, ci.pinned)) @@ -893,7 +886,7 @@ moves_loop: // When in check and at SpNode search starts from here quietsSearched[quietCount++] = move; // Step 14. Make the move - pos.do_move(move, st, ci, givesCheck); + pos.do_move(move, st, givesCheck); // Step 15. Reduced depth search (LMR). If the move fails high it will be // re-searched at full depth. @@ -1245,7 +1238,7 @@ moves_loop: // When in check and at SpNode search starts from here continue; // Speculative prefetch as early as possible - prefetch((char*)TT.first_entry(pos.key_after(move))); + prefetch(TT.first_entry(pos.key_after(move))); // Check for legality just before making the move if (!pos.legal(move, ci.pinned)) @@ -1254,7 +1247,7 @@ moves_loop: // When in check and at SpNode search starts from here ss->currentMove = move; // Make and search the move - pos.do_move(move, st, ci, givesCheck); + pos.do_move(move, st, givesCheck); value = givesCheck ? -qsearch(pos, ss+1, -beta, -alpha, depth - ONE_PLY) : -qsearch(pos, ss+1, -beta, -alpha, depth - ONE_PLY); pos.undo_move(move); @@ -1351,6 +1344,7 @@ moves_loop: // When in check and at SpNode search starts from here // played quiet moves. Value bonus = Value((depth / ONE_PLY) * (depth / ONE_PLY)); History.update(pos.moved_piece(move), to_sq(move), bonus); + for (int i = 0; i < quietsCnt; ++i) { Move m = quiets[i]; @@ -1389,75 +1383,77 @@ moves_loop: // When in check and at SpNode search starts from here // then we choose the move with the resulting highest score. for (size_t i = 0; i < multiPV; ++i) { - int score = RootMoves[i].score; - // This is our magic formula - score += ( weakness * int(RootMoves[0].score - score) - + variance * (rng.rand() % weakness)) / 128; + int push = ( weakness * int(RootMoves[0].score - RootMoves[i].score) + + variance * (rng.rand() % weakness)) / 128; - if (score > maxScore) + if (RootMoves[i].score + push > maxScore) { - maxScore = score; + maxScore = RootMoves[i].score + push; best = RootMoves[i].pv[0]; } } return best; } +} // namespace - // uci_pv() formats PV information according to the UCI protocol. UCI - // requires that all (if any) unsearched PV lines are sent using a previous - // search score. - string uci_pv(const Position& pos, Depth depth, Value alpha, Value beta) { +/// UCI::pv() formats PV information according to the UCI protocol. UCI requires +/// that all (if any) unsearched PV lines are sent using a previous search score. - std::stringstream ss; - Time::point elapsed = Time::now() - SearchTime + 1; - size_t uciPVSize = std::min((size_t)Options["MultiPV"], RootMoves.size()); - int selDepth = 0; +string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) { - for (Thread* th : Threads) - if (th->maxPly > selDepth) - selDepth = th->maxPly; + std::stringstream ss; + Time::point elapsed = Time::now() - SearchTime + 1; + size_t multiPV = std::min((size_t)Options["MultiPV"], RootMoves.size()); + int selDepth = 0; - for (size_t i = 0; i < uciPVSize; ++i) - { - bool updated = (i <= PVIdx); + for (Thread* th : Threads) + if (th->maxPly > selDepth) + selDepth = th->maxPly; - if (depth == ONE_PLY && !updated) - continue; + for (size_t i = 0; i < multiPV; ++i) + { + bool updated = (i <= PVIdx); - Depth d = updated ? depth : depth - ONE_PLY; - Value v = updated ? RootMoves[i].score : RootMoves[i].previousScore; + if (depth == ONE_PLY && !updated) + continue; - bool tb = TB::RootInTB && abs(v) < VALUE_MATE - MAX_PLY; - v = tb ? TB::Score : v; + Depth d = updated ? depth : depth - ONE_PLY; + Value v = updated ? RootMoves[i].score : RootMoves[i].previousScore; - if (ss.rdbuf()->in_avail()) // Not at first line - ss << "\n"; + bool tb = TB::RootInTB && abs(v) < VALUE_MATE - MAX_PLY; + v = tb ? TB::Score : v; - ss << "info depth " << d / ONE_PLY - << " seldepth " << selDepth - << " multipv " << i + 1 - << " score " << UCI::value(v); + if (ss.rdbuf()->in_avail()) // Not at first line + ss << "\n"; - if (!tb && i == PVIdx) - ss << (v >= beta ? " lowerbound" : v <= alpha ? " upperbound" : ""); + ss << "info" + << " depth " << d / ONE_PLY + << " seldepth " << selDepth + << " multipv " << i + 1 + << " score " << UCI::value(v); - ss << " nodes " << pos.nodes_searched() - << " nps " << pos.nodes_searched() * 1000 / elapsed - << " tbhits " << TB::Hits - << " time " << elapsed - << " pv"; + if (!tb && i == PVIdx) + ss << (v >= beta ? " lowerbound" : v <= alpha ? " upperbound" : ""); - for (size_t j = 0; j < RootMoves[i].pv.size(); ++j) - ss << " " << UCI::move(RootMoves[i].pv[j], pos.is_chess960()); - } + ss << " nodes " << pos.nodes_searched() + << " nps " << pos.nodes_searched() * 1000 / elapsed; - return ss.str(); + if (elapsed > 1000) // Earlier makes little sense + ss << " hashfull " << TT.hashfull(); + + ss << " tbhits " << TB::Hits + << " time " << elapsed + << " pv"; + + for (Move m : RootMoves[i].pv) + ss << " " << UCI::move(m, pos.is_chess960()); } -} // namespace + return ss.str(); +} /// RootMove::insert_pv_in_tt() is called at the end of a search iteration, and @@ -1467,22 +1463,22 @@ moves_loop: // When in check and at SpNode search starts from here void RootMove::insert_pv_in_tt(Position& pos) { StateInfo state[MAX_PLY], *st = state; - size_t idx = 0; + bool ttHit; - for ( ; idx < pv.size(); ++idx) + for (Move m : pv) { - bool ttHit; - TTEntry* tte = TT.probe(pos.key(), ttHit); + assert(MoveList(pos).contains(m)); - if (!ttHit || tte->move() != pv[idx]) // Don't overwrite correct entries - tte->save(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[idx], VALUE_NONE, TT.generation()); + TTEntry* tte = TT.probe(pos.key(), ttHit); - assert(MoveList(pos).contains(pv[idx])); + if (!ttHit || tte->move() != m) // Don't overwrite correct entries + tte->save(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, m, VALUE_NONE, TT.generation()); - pos.do_move(pv[idx], *st++); + pos.do_move(m, *st++); } - while (idx) pos.undo_move(pv[--idx]); + for (size_t i = pv.size(); i > 0; ) + pos.undo_move(pv[--i]); } @@ -1491,22 +1487,25 @@ void RootMove::insert_pv_in_tt(Position& pos) { /// 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. -Move RootMove::extract_ponder_from_tt(Position& pos) +bool RootMove::extract_ponder_from_tt(Position& pos) { StateInfo st; - bool found; + bool ttHit; assert(pv.size() == 1); pos.do_move(pv[0], st); - TTEntry* tte = TT.probe(pos.key(), found); - Move m = found ? tte->move() : MOVE_NONE; - if (!MoveList(pos).contains(m)) - m = MOVE_NONE; - + TTEntry* tte = TT.probe(pos.key(), ttHit); pos.undo_move(pv[0]); - pv.push_back(m); - return m; + + if (ttHit) + { + Move m = tte->move(); // Local copy to be SMP safe + if (MoveList(pos).contains(m)) + return pv.push_back(m), true; + } + + return false; }