X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=847fc762e53644abb7959622e211a1c3966b3f03;hp=763a6ac31194a8ae8b8a6e92bbbf0700894373a7;hb=ec6aab01366ba1d2de27084d3cc7415a31aa5a24;hpb=aedebe35cfa38b543041bae97e91e8194738b202 diff --git a/src/search.cpp b/src/search.cpp index 763a6ac3..847fc762 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -40,7 +40,6 @@ namespace Search { SignalsType Signals; LimitsType Limits; - StateStackPtr SetupStates; } namespace Tablebases { @@ -127,6 +126,35 @@ namespace { Move pv[3]; }; + // Set of rows with half bits set to 1 and half to 0. It is used to allocate + // the search depths across the threads. + typedef std::vector Row; + + const Row HalfDensity[] = { + {0, 1}, + {1, 0}, + {0, 0, 1, 1}, + {0, 1, 1, 0}, + {1, 1, 0, 0}, + {1, 0, 0, 1}, + {0, 0, 0, 1, 1, 1}, + {0, 0, 1, 1, 1, 0}, + {0, 1, 1, 1, 0, 0}, + {1, 1, 1, 0, 0, 0}, + {1, 1, 0, 0, 0, 1}, + {1, 0, 0, 0, 1, 1}, + {0, 0, 0, 0, 1, 1, 1, 1}, + {0, 0, 0, 1, 1, 1, 1, 0}, + {0, 0, 1, 1, 1, 1, 0 ,0}, + {0, 1, 1, 1, 1, 0, 0 ,0}, + {1, 1, 1, 1, 0, 0, 0 ,0}, + {1, 1, 1, 0, 0, 0, 0 ,1}, + {1, 1, 0, 0, 0, 0, 1 ,1}, + {1, 0, 0, 0, 0, 1, 1 ,1}, + }; + + const size_t HalfDensitySize = std::extent::value; + EasyMoveManager EasyMove; Value DrawValue[COLOR_NB]; CounterMoveHistoryStats CounterMoveHistory; @@ -150,22 +178,21 @@ namespace { void Search::init() { - const double K[][2] = {{ 0.799, 2.281 }, { 0.484, 3.023 }}; - - 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]; + for (int imp = 0; imp <= 1; ++imp) + for (int d = 1; d < 64; ++d) + for (int mc = 1; mc < 64; ++mc) + { + double r = log(d) * log(mc) / 2; + if (r < 0.80) + continue; - if (r >= 1.5) - Reductions[pv][imp][d][mc] = int(r) * ONE_PLY; + 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); - // 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; - } + // 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; + } for (int d = 0; d < 16; ++d) { @@ -289,16 +316,8 @@ void MainThread::search() { } for (Thread* th : Threads) - { - th->maxPly = 0; - th->rootDepth = DEPTH_ZERO; if (th != this) - { - th->rootPos = Position(rootPos, th); - th->rootMoves = rootMoves; th->start_searching(); - } - } Thread::search(); // Let's start searching! } @@ -331,7 +350,8 @@ void MainThread::search() { Thread* bestThread = this; if ( !this->easyMovePlayed && Options["MultiPV"] == 1 - && !Skill(Options["Skill Level"]).enabled()) + && !Skill(Options["Skill Level"]).enabled() + && rootMoves[0].pv[0] != MOVE_NONE) { for (Thread* th : Threads) if ( th->completedDepth > bestThread->completedDepth @@ -353,33 +373,6 @@ void MainThread::search() { std::cout << sync_endl; } -const int halfDensityMap[][9] = -{ - {2, 0, 1}, - {2, 1, 0}, - - {4, 0, 0, 1, 1}, - {4, 0, 1, 1, 0}, - {4, 1, 1, 0, 0}, - {4, 1, 0, 0, 1}, - - {6, 0, 0, 0, 1, 1, 1}, - {6, 0, 0, 1, 1, 1, 0}, - {6, 0, 1, 1, 1, 0, 0}, - {6, 1, 1, 1, 0, 0, 0}, - {6, 1, 1, 0, 0, 0, 1}, - {6, 1, 0, 0, 0, 1, 1}, - - {8, 0, 0, 0, 0, 1, 1, 1, 1}, - {8, 0, 0, 0, 1, 1, 1, 1, 0}, - {8, 0, 0, 1, 1, 1, 1, 0 ,0}, - {8, 0, 1, 1, 1, 1, 0, 0 ,0}, - {8, 1, 1, 1, 1, 0, 0, 0 ,0}, - {8, 1, 1, 1, 0, 0, 0, 0 ,1}, - {8, 1, 1, 0, 0, 0, 0, 1 ,1}, - {8, 1, 0, 0, 0, 0, 1, 1 ,1}, -}; - // Thread::search() is the main iterative deepening loop. It calls search() // repeatedly with increasing depth until the allocated thinking time has been @@ -387,12 +380,12 @@ const int halfDensityMap[][9] = void Thread::search() { - Stack stack[MAX_PLY+4], *ss = stack+2; // To allow referencing (ss-2) and (ss+2) + Stack stack[MAX_PLY+7], *ss = stack+5; // To allow referencing (ss-5) and (ss+2) Value bestValue, alpha, beta, delta; Move easyMove = MOVE_NONE; MainThread* mainThread = (this == Threads.main() ? Threads.main() : nullptr); - std::memset(ss-2, 0, 5 * sizeof(Stack)); + std::memset(ss-5, 0, 8 * sizeof(Stack)); bestValue = delta = alpha = -VALUE_INFINITE; beta = VALUE_INFINITE; @@ -424,8 +417,8 @@ void Thread::search() { // 2nd ply (using a half-density matrix). if (!mainThread) { - int row = (idx - 1) % 20; - if (halfDensityMap[row][(rootDepth + rootPos.game_ply()) % halfDensityMap[row][0] + 1]) + const Row& row = HalfDensity[(idx - 1) % HalfDensitySize]; + if (row[(rootDepth + rootPos.game_ply()) % row.size()]) continue; } @@ -664,6 +657,7 @@ namespace { assert(0 <= ss->ply && ss->ply < MAX_PLY); ss->currentMove = (ss+1)->excludedMove = bestMove = MOVE_NONE; + ss->counterMoves = nullptr; (ss+1)->skipEarlyPruning = false; (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; @@ -787,6 +781,7 @@ namespace { && pos.non_pawn_material(pos.side_to_move())) { ss->currentMove = MOVE_NULL; + ss->counterMoves = nullptr; assert(eval - beta >= 0); @@ -835,13 +830,14 @@ namespace { assert((ss-1)->currentMove != MOVE_NONE); assert((ss-1)->currentMove != MOVE_NULL); - MovePicker mp(pos, ttMove, thisThread->history, PieceValue[MG][pos.captured_piece_type()]); + MovePicker mp(pos, ttMove, PieceValue[MG][pos.captured_piece_type()]); CheckInfo ci(pos); while ((move = mp.next_move()) != MOVE_NONE) if (pos.legal(move, ci.pinned)) { ss->currentMove = move; + ss->counterMoves = &CounterMoveHistory[pos.moved_piece(move)][to_sq(move)]; pos.do_move(move, st, pos.gives_check(move, ci)); value = -search(pos, ss+1, -rbeta, -rbeta+1, rdepth, !cutNode); pos.undo_move(move); @@ -867,10 +863,9 @@ namespace { moves_loop: // When in check search starts from here Square prevSq = to_sq((ss-1)->currentMove); - Move cm = thisThread->counterMoves[pos.piece_on(prevSq)][prevSq]; const CounterMoveStats& cmh = CounterMoveHistory[pos.piece_on(prevSq)][prevSq]; - MovePicker mp(pos, ttMove, depth, thisThread->history, cmh, cm, ss); + MovePicker mp(pos, ttMove, depth, ss); CheckInfo ci(pos); value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc improving = ss->staticEval >= (ss-2)->staticEval @@ -967,7 +962,7 @@ moves_loop: // When in check search starts from here && cmh[pos.moved_piece(move)][to_sq(move)] < VALUE_ZERO) continue; - predictedDepth = newDepth - reduction(improving, depth, moveCount); + predictedDepth = std::max(newDepth - reduction(improving, depth, moveCount), DEPTH_ZERO); // Futility pruning: parent node if (predictedDepth < 7 * ONE_PLY) @@ -997,6 +992,7 @@ moves_loop: // When in check search starts from here } ss->currentMove = move; + ss->counterMoves = &CounterMoveHistory[pos.moved_piece(move)][to_sq(move)]; // Step 14. Make the move pos.do_move(move, st, givesCheck); @@ -1008,16 +1004,16 @@ moves_loop: // When in check search starts from here && !captureOrPromotion) { Depth r = reduction(improving, depth, moveCount); + Value hValue = thisThread->history[pos.piece_on(to_sq(move))][to_sq(move)]; + Value cmhValue = cmh[pos.piece_on(to_sq(move))][to_sq(move)]; // Increase reduction for cut nodes and moves with a bad history if ( (!PvNode && cutNode) - || ( thisThread->history[pos.piece_on(to_sq(move))][to_sq(move)] < VALUE_ZERO - && cmh[pos.piece_on(to_sq(move))][to_sq(move)] <= VALUE_ZERO)) + || (hValue < VALUE_ZERO && cmhValue <= VALUE_ZERO)) r += ONE_PLY; // Decrease/increase reduction for moves with a good/bad history - int rHist = ( thisThread->history[pos.piece_on(to_sq(move))][to_sq(move)] - + cmh[pos.piece_on(to_sq(move))][to_sq(move)]) / 14980; + int rHist = (hValue + cmhValue) / 14980; r = std::max(DEPTH_ZERO, r - rHist * ONE_PLY); // Decrease reduction for moves that escape a capture. Filter out @@ -1158,13 +1154,17 @@ moves_loop: // When in check search starts from here && !bestMove && !inCheck && !pos.captured_piece_type() - && is_ok((ss - 1)->currentMove) - && is_ok((ss - 2)->currentMove)) + && is_ok((ss-1)->currentMove)) { Value bonus = Value((depth / ONE_PLY) * (depth / ONE_PLY) + depth / ONE_PLY - 1); - Square prevPrevSq = to_sq((ss - 2)->currentMove); - CounterMoveStats& prevCmh = CounterMoveHistory[pos.piece_on(prevPrevSq)][prevPrevSq]; - prevCmh.update(pos.piece_on(prevSq), prevSq, bonus); + if ((ss-2)->counterMoves) + (ss-2)->counterMoves->update(pos.piece_on(prevSq), prevSq, bonus); + + if ((ss-3)->counterMoves) + (ss-3)->counterMoves->update(pos.piece_on(prevSq), prevSq, bonus); + + if ((ss-5)->counterMoves) + (ss-5)->counterMoves->update(pos.piece_on(prevSq), prevSq, bonus); } tte->save(posKey, value_to_tt(bestValue, ss->ply), @@ -1285,7 +1285,7 @@ moves_loop: // When in check search starts from here // to search the moves. Because the depth is <= 0 here, only captures, // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will // be generated. - MovePicker mp(pos, ttMove, depth, pos.this_thread()->history, to_sq((ss-1)->currentMove)); + 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 @@ -1424,8 +1424,8 @@ moves_loop: // When in check search starts from here } - // update_stats() updates killers, history, countermove and countermove - // history when a new quiet best move is found. + // update_stats() updates killers, history, countermove and countermove plus + // follow-up move history when a new quiet best move is found. void update_stats(const Position& pos, Stack* ss, Move move, Depth depth, Move* quiets, int quietsCnt) { @@ -1439,34 +1439,51 @@ moves_loop: // When in check search starts from here Value bonus = Value((depth / ONE_PLY) * (depth / ONE_PLY) + depth / ONE_PLY - 1); Square prevSq = to_sq((ss-1)->currentMove); - CounterMoveStats& cmh = CounterMoveHistory[pos.piece_on(prevSq)][prevSq]; + CounterMoveStats* cmh = (ss-1)->counterMoves; + CounterMoveStats* fmh = (ss-2)->counterMoves; + CounterMoveStats* fmh2 = (ss-4)->counterMoves; Thread* thisThread = pos.this_thread(); thisThread->history.update(pos.moved_piece(move), to_sq(move), bonus); - if (is_ok((ss-1)->currentMove)) + if (cmh) { thisThread->counterMoves.update(pos.piece_on(prevSq), prevSq, move); - cmh.update(pos.moved_piece(move), to_sq(move), bonus); + cmh->update(pos.moved_piece(move), to_sq(move), bonus); } + if (fmh) + fmh->update(pos.moved_piece(move), to_sq(move), bonus); + + if (fmh2) + fmh2->update(pos.moved_piece(move), to_sq(move), bonus); + // Decrease all the other played quiet moves for (int i = 0; i < quietsCnt; ++i) { thisThread->history.update(pos.moved_piece(quiets[i]), to_sq(quiets[i]), -bonus); - if (is_ok((ss-1)->currentMove)) - cmh.update(pos.moved_piece(quiets[i]), to_sq(quiets[i]), -bonus); + if (cmh) + cmh->update(pos.moved_piece(quiets[i]), to_sq(quiets[i]), -bonus); + + if (fmh) + fmh->update(pos.moved_piece(quiets[i]), to_sq(quiets[i]), -bonus); + + if (fmh2) + fmh2->update(pos.moved_piece(quiets[i]), to_sq(quiets[i]), -bonus); } // Extra penalty for a quiet TT move in previous ply when it gets refuted - if ( (ss-1)->moveCount == 1 - && !pos.captured_piece_type() - && is_ok((ss-2)->currentMove)) + if ((ss-1)->moveCount == 1 && !pos.captured_piece_type()) { - Square prevPrevSq = to_sq((ss-2)->currentMove); - CounterMoveStats& prevCmh = CounterMoveHistory[pos.piece_on(prevPrevSq)][prevPrevSq]; - prevCmh.update(pos.piece_on(prevSq), prevSq, -bonus - 2 * (depth + 1) / ONE_PLY); + if ((ss-2)->counterMoves) + (ss-2)->counterMoves->update(pos.piece_on(prevSq), prevSq, -bonus - 2 * (depth + 1) / ONE_PLY); + + if ((ss-3)->counterMoves) + (ss-3)->counterMoves->update(pos.piece_on(prevSq), prevSq, -bonus - 2 * (depth + 1) / ONE_PLY); + + if ((ss-5)->counterMoves) + (ss-5)->counterMoves->update(pos.piece_on(prevSq), prevSq, -bonus - 2 * (depth + 1) / ONE_PLY); } } @@ -1476,7 +1493,7 @@ moves_loop: // When in check search starts from here Move Skill::pick_best(size_t multiPV) { - const Search::RootMoveVector& rootMoves = Threads.main()->rootMoves; + const RootMoves& rootMoves = Threads.main()->rootMoves; static PRNG rng(now()); // PRNG sequence should be non-deterministic // RootMoves are already sorted by score in descending order @@ -1541,7 +1558,7 @@ string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) { std::stringstream ss; int elapsed = Time.elapsed() + 1; - const Search::RootMoveVector& rootMoves = pos.this_thread()->rootMoves; + 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();