X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=dc488c2b8922df283d51ba1c525e452b83cab7e4;hp=0ccf326698ee3bc9a1a676e8831ba3e8001d39b2;hb=29b5842da8d5477c0aea924cfd364c9e619456a2;hpb=28933a580eeb4b9a2d717f06c789a6c13dfef19c diff --git a/src/search.cpp b/src/search.cpp index 0ccf3266..dc488c2b 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -127,6 +127,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 +179,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) { @@ -256,8 +284,9 @@ void MainThread::search() { } else { - if (TB::Cardinality >= rootPos.count(WHITE) - + rootPos.count(BLACK)) + if ( TB::Cardinality >= rootPos.count(WHITE) + + rootPos.count(BLACK) + && !rootPos.can_castle(ANY_CASTLING)) { // If the current root position is in the tablebases, then RootMoves // contains only moves that preserve the draw or the win. @@ -393,27 +422,12 @@ void Thread::search() { while (++rootDepth < DEPTH_MAX && !Signals.stop && (!Limits.depth || rootDepth <= Limits.depth)) { // Set up the new depths for the helper threads skipping on average every - // 2nd ply (using a half-density map similar to a Hadamard matrix). + // 2nd ply (using a half-density matrix). if (!mainThread) { - int d = rootDepth + rootPos.game_ply(); - - if (idx <= 6 || idx > 24) - { - if (((d + idx) >> (msb(idx + 1) - 1)) % 2) - continue; - } - else - { - // Table of values of 6 bits with 3 of them set - static const int HalfDensityMap[] = { - 0x07, 0x0b, 0x0d, 0x0e, 0x13, 0x16, 0x19, 0x1a, 0x1c, - 0x23, 0x25, 0x26, 0x29, 0x2c, 0x31, 0x32, 0x34, 0x38 - }; - - if ((HalfDensityMap[idx - 7] >> (d % 6)) & 1) - continue; - } + const Row& row = HalfDensity[(idx - 1) % HalfDensitySize]; + if (row[(rootDepth + rootPos.game_ply()) % row.size()]) + continue; } // Age out PV variability metric @@ -531,10 +545,6 @@ void Thread::search() { { if (!Signals.stop && !Signals.stopOnPonderhit) { - // Take some extra time if the best move has changed - if (rootDepth > 4 * ONE_PLY && multiPV == 1) - Time.pv_instability(mainThread->bestMoveChanges); - // Stop the search if only one legal move is available, or if all // of the available time has been used, or if we matched an easyMove // from the previous search and just did a fast verification. @@ -542,13 +552,14 @@ void Thread::search() { bestValue >= mainThread->previousScore }; int improvingFactor = 640 - 160*F[0] - 126*F[1] - 124*F[0]*F[1]; + double unstablePvFactor = 1 + mainThread->bestMoveChanges; bool doEasyMove = rootMoves[0].pv[0] == easyMove && mainThread->bestMoveChanges < 0.03 - && Time.elapsed() > Time.available() * 25 / 206; + && Time.elapsed() > Time.optimum() * 25 / 204; if ( rootMoves.size() == 1 - || Time.elapsed() > Time.available() * improvingFactor / 640 + || Time.elapsed() > Time.optimum() * unstablePvFactor * improvingFactor / 634 || (mainThread->easyMovePlayed = doEasyMove)) { // If we are allowed to ponder do not stop the search now but @@ -691,7 +702,8 @@ namespace { if ( piecesCnt <= TB::Cardinality && (piecesCnt < TB::Cardinality || depth >= TB::ProbeDepth) - && pos.rule50_count() == 0) + && pos.rule50_count() == 0 + && !pos.can_castle(ANY_CASTLING)) { int found, v = Tablebases::probe_wdl(pos, &found); @@ -856,10 +868,12 @@ namespace { moves_loop: // When in check search starts from here Square prevSq = to_sq((ss-1)->currentMove); + Square ownPrevSq = to_sq((ss-2)->currentMove); Move cm = thisThread->counterMoves[pos.piece_on(prevSq)][prevSq]; const CounterMoveStats& cmh = CounterMoveHistory[pos.piece_on(prevSq)][prevSq]; + const CounterMoveStats& fmh = CounterMoveHistory[pos.piece_on(ownPrevSq)][ownPrevSq]; - MovePicker mp(pos, ttMove, depth, thisThread->history, cmh, cm, ss); + MovePicker mp(pos, ttMove, depth, thisThread->history, cmh, fmh, cm, ss); CheckInfo ci(pos); value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc improving = ss->staticEval >= (ss-2)->staticEval @@ -956,7 +970,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,16 +1011,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 @@ -1413,8 +1427,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) { @@ -1428,7 +1442,9 @@ 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); + Square ownPrevSq = to_sq((ss-2)->currentMove); CounterMoveStats& cmh = CounterMoveHistory[pos.piece_on(prevSq)][prevSq]; + CounterMoveStats& fmh = CounterMoveHistory[pos.piece_on(ownPrevSq)][ownPrevSq]; Thread* thisThread = pos.this_thread(); thisThread->history.update(pos.moved_piece(move), to_sq(move), bonus); @@ -1439,6 +1455,9 @@ moves_loop: // When in check search starts from here cmh.update(pos.moved_piece(move), to_sq(move), bonus); } + if (is_ok((ss-2)->currentMove)) + fmh.update(pos.moved_piece(move), to_sq(move), bonus); + // Decrease all the other played quiet moves for (int i = 0; i < quietsCnt; ++i) { @@ -1446,6 +1465,9 @@ moves_loop: // When in check search starts from here if (is_ok((ss-1)->currentMove)) cmh.update(pos.moved_piece(quiets[i]), to_sq(quiets[i]), -bonus); + + if (is_ok((ss-2)->currentMove)) + fmh.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