X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=f4f411c56d18f266f110d69ba5d4aa0b8c9707ad;hp=15f09bc92743de1cc2eab9fcdfabfd76a4cba82b;hb=e215a88cddd16e09cd77618bd3b793957dea7dc1;hpb=0d68b523a390e2f5c37f211316869d798e852289 diff --git a/src/search.cpp b/src/search.cpp index 15f09bc9..f4f411c5 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -44,7 +44,6 @@ namespace Search { Color RootColor; Time::point SearchTime; StateStackPtr SetupStates; - MovesVectPtr SetupMoves; } using std::string; @@ -87,11 +86,12 @@ namespace { TimeManager TimeMgr; int BestMoveChanges; Value DrawValue[COLOR_NB]; - History Hist; - Gains Gain; + HistoryStats History; + GainsStats Gains; + CountermovesStats Countermoves; template - Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth); + Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode); template Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth); @@ -146,7 +146,7 @@ void Search::init() { // Init futility move count array for (d = 0; d < 32; d++) - FutilityMoveCounts[d] = int(3.001 + 0.25 * pow(double(d), 2.0)); + FutilityMoveCounts[d] = int(3.001 + 0.3 * pow(double(d), 1.8)); } @@ -155,21 +155,17 @@ void Search::init() { size_t Search::perft(Position& pos, Depth depth) { - // At the last ply just return the number of legal moves (leaf nodes) - if (depth == ONE_PLY) - return MoveList(pos).size(); - StateInfo st; size_t cnt = 0; CheckInfo ci(pos); + const bool leaf = depth == 2 * ONE_PLY; - for (MoveList ml(pos); !ml.end(); ++ml) + for (MoveList it(pos); *it; ++it) { - pos.do_move(ml.move(), st, ci, pos.move_gives_check(ml.move(), ci)); - cnt += perft(pos, depth - ONE_PLY); - pos.undo_move(ml.move()); + pos.do_move(*it, st, ci, pos.move_gives_check(*it, ci)); + cnt += leaf ? MoveList(pos).size() : perft(pos, depth - ONE_PLY); + pos.undo_move(*it); } - return cnt; } @@ -265,6 +261,10 @@ void Search::think() { finalize: + // When search is stopped this info is not printed + sync_cout << "info nodes " << RootPos.nodes_searched() + << " time " << Time::now() - SearchTime + 1 << sync_endl; + // When we reach max depth we arrive here even without Signals.stop is raised, // but if we are pondering or in infinite search, according to UCI protocol, // we shouldn't print the best move before the GUI sends a "stop" or "ponderhit" @@ -291,18 +291,18 @@ namespace { void id_loop(Position& pos) { - Stack ss[MAX_PLY_PLUS_2]; + Stack stack[MAX_PLY_PLUS_2], *ss = stack+1; // To allow referencing (ss-1) int depth, prevBestMoveChanges; Value bestValue, alpha, beta, delta; - bool bestMoveNeverChanged = true; - memset(ss, 0, 4 * sizeof(Stack)); + memset(ss-1, 0, 4 * sizeof(Stack)); depth = BestMoveChanges = 0; bestValue = delta = -VALUE_INFINITE; - ss->currentMove = MOVE_NULL; // Hack to skip update gains + (ss-1)->currentMove = MOVE_NULL; // Hack to skip update gains TT.new_search(); - Hist.clear(); - Gain.clear(); + History.clear(); + Gains.clear(); + Countermoves.clear(); PVSize = Options["MultiPV"]; Skill skill(Options["Skill Level"]); @@ -345,9 +345,7 @@ namespace { // research with bigger window until not failing high/low anymore. while (true) { - // Search starts from ss+1 to allow referencing (ss-1). This is - // needed by update gains and ss copy when splitting at Root. - bestValue = search(pos, ss+1, alpha, beta, depth * ONE_PLY); + bestValue = search(pos, ss, alpha, beta, depth * ONE_PLY, false); // Bring to front the best move. It is critical that sorting is // done with a stable algorithm because all the values but the first @@ -412,15 +410,15 @@ namespace { if (Options["Use Search Log"]) { + RootMove& rm = RootMoves[0]; + if (skill.best != MOVE_NONE) + rm = *std::find(RootMoves.begin(), RootMoves.end(), skill.best); + Log log(Options["Search Log Filename"]); - log << pretty_pv(pos, depth, bestValue, Time::now() - SearchTime, &RootMoves[0].pv[0]) + log << pretty_pv(pos, depth, rm.score, Time::now() - SearchTime, &rm.pv[0]) << std::endl; } - // Filter out startup noise when monitoring best move stability - if (depth > 2 && BestMoveChanges) - bestMoveNeverChanged = false; - // Do we have found a "mate in x"? if ( Limits.mate && bestValue >= VALUE_MATE_IN_MAX_PLY @@ -446,15 +444,16 @@ namespace { if ( depth >= 12 && !stop && PVSize == 1 - && ( (bestMoveNeverChanged && pos.captured_piece_type()) - || Time::now() - SearchTime > (TimeMgr.available_time() * 40) / 100)) + && bestValue > VALUE_MATED_IN_MAX_PLY + && ( RootMoves.size() == 1 + || Time::now() - SearchTime > (TimeMgr.available_time() * 20) / 100)) { Value rBeta = bestValue - 2 * PawnValueMg; - (ss+1)->excludedMove = RootMoves[0].pv[0]; - (ss+1)->skipNullMove = true; - Value v = search(pos, ss+1, rBeta - 1, rBeta, (depth - 3) * ONE_PLY); - (ss+1)->skipNullMove = false; - (ss+1)->excludedMove = MOVE_NONE; + ss->excludedMove = RootMoves[0].pv[0]; + ss->skipNullMove = true; + Value v = search(pos, ss, rBeta - 1, rBeta, (depth - 3) * ONE_PLY, true); + ss->skipNullMove = false; + ss->excludedMove = MOVE_NONE; if (v < rBeta) stop = true; @@ -482,7 +481,7 @@ namespace { // here: This is taken care of after we return from the split point. template - Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth) { + Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode) { const bool PvNode = (NT == PV || NT == Root || NT == SplitPointPV || NT == SplitPointRoot); const bool SpNode = (NT == SplitPointPV || NT == SplitPointNonPV || NT == SplitPointRoot); @@ -528,6 +527,7 @@ namespace { bestValue = -VALUE_INFINITE; ss->currentMove = threatMove = (ss+1)->excludedMove = bestMove = MOVE_NONE; ss->ply = (ss-1)->ply + 1; + ss->futilityMoveCount = 0; (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO; (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; @@ -538,7 +538,7 @@ namespace { if (!RootNode) { // Step 2. Check for aborted search and immediate draw - if (Signals.stop || pos.is_draw() || ss->ply > MAX_PLY) + if (Signals.stop || pos.is_draw() || ss->ply > MAX_PLY) return DrawValue[pos.side_to_move()]; // Step 3. Mate distance pruning. Even if we mate at the next move our score @@ -621,7 +621,7 @@ namespace { && type_of(move) == NORMAL) { Square to = to_sq(move); - Gain.update(pos.piece_on(to), to, -(ss-1)->staticEval - ss->staticEval); + Gains.update(pos.piece_on(to), to, -(ss-1)->staticEval - ss->staticEval); } // Step 6. Razoring (is omitted in PV nodes) @@ -648,10 +648,11 @@ namespace { && !ss->skipNullMove && depth < 4 * ONE_PLY && !inCheck - && eval - FutilityMargins[depth][0] >= beta + && eval - futility_margin(depth, (ss-1)->futilityMoveCount) >= beta && abs(beta) < VALUE_MATE_IN_MAX_PLY + && abs(eval) < VALUE_KNOWN_WIN && pos.non_pawn_material(pos.side_to_move())) - return eval - FutilityMargins[depth][0]; + return eval - futility_margin(depth, (ss-1)->futilityMoveCount); // Step 8. Null move search with verification search (is omitted in PV nodes) if ( !PvNode @@ -674,7 +675,7 @@ namespace { pos.do_null_move(st); (ss+1)->skipNullMove = true; nullValue = depth-R < ONE_PLY ? -qsearch(pos, ss+1, -beta, -alpha, DEPTH_ZERO) - : - search(pos, ss+1, -beta, -alpha, depth-R); + : - search(pos, ss+1, -beta, -alpha, depth-R, !cutNode); (ss+1)->skipNullMove = false; pos.undo_null_move(); @@ -684,12 +685,12 @@ namespace { if (nullValue >= VALUE_MATE_IN_MAX_PLY) nullValue = beta; - if (depth < 6 * ONE_PLY) + if (depth < 12 * ONE_PLY) return nullValue; // Do verification search at high depths ss->skipNullMove = true; - Value v = search(pos, ss, alpha, beta, depth-R); + Value v = search(pos, ss, alpha, beta, depth-R, false); ss->skipNullMove = false; if (v >= beta) @@ -709,7 +710,7 @@ namespace { && (ss-1)->reduction && threatMove != MOVE_NONE && allows(pos, (ss-1)->currentMove, threatMove)) - return beta - 1; + return alpha; } } @@ -721,7 +722,6 @@ namespace { && depth >= 5 * ONE_PLY && !inCheck && !ss->skipNullMove - && excludedMove == MOVE_NONE && abs(beta) < VALUE_MATE_IN_MAX_PLY) { Value rbeta = beta + 200; @@ -731,7 +731,7 @@ namespace { assert((ss-1)->currentMove != MOVE_NONE); assert((ss-1)->currentMove != MOVE_NULL); - MovePicker mp(pos, ttMove, Hist, pos.captured_piece_type()); + MovePicker mp(pos, ttMove, History, pos.captured_piece_type()); CheckInfo ci(pos); while ((move = mp.next_move()) != MOVE_NONE) @@ -739,7 +739,7 @@ namespace { { ss->currentMove = move; pos.do_move(move, st, ci, pos.move_gives_check(move, ci)); - value = -search(pos, ss+1, -rbeta, -rbeta+1, rdepth); + value = -search(pos, ss+1, -rbeta, -rbeta+1, rdepth, !cutNode); pos.undo_move(move); if (value >= rbeta) return value; @@ -751,10 +751,10 @@ namespace { && ttMove == MOVE_NONE && (PvNode || (!inCheck && ss->staticEval + Value(256) >= beta))) { - Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2); + Depth d = depth - 2 * ONE_PLY - (PvNode ? DEPTH_ZERO : depth / 4); ss->skipNullMove = true; - search(pos, ss, alpha, beta, d); + search(pos, ss, alpha, beta, d, true); ss->skipNullMove = false; tte = TT.probe(posKey); @@ -763,7 +763,11 @@ namespace { split_point_start: // At split points actual search starts from here - MovePicker mp(pos, ttMove, depth, Hist, ss, PvNode ? -VALUE_INFINITE : beta); + Square prevMoveSq = to_sq((ss-1)->currentMove); + Move countermoves[] = { Countermoves[pos.piece_on(prevMoveSq)][prevMoveSq].first, + Countermoves[pos.piece_on(prevMoveSq)][prevMoveSq].second }; + + MovePicker mp(pos, ttMove, depth, History, countermoves, ss, PvNode ? -VALUE_INFINITE : beta); CheckInfo ci(pos); value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc singularExtensionNode = !RootNode @@ -846,7 +850,7 @@ split_point_start: // At split points actual search starts from here Value rBeta = ttValue - int(depth); ss->excludedMove = move; ss->skipNullMove = true; - value = search(pos, ss, rBeta - 1, rBeta, depth / 2); + value = search(pos, ss, rBeta - 1, rBeta, depth / 2, cutNode); ss->skipNullMove = false; ss->excludedMove = MOVE_NONE; @@ -858,14 +862,15 @@ split_point_start: // At split points actual search starts from here newDepth = depth - ONE_PLY + ext; // Step 13. Futility pruning (is omitted in PV nodes) - if ( !captureOrPromotion + if ( !PvNode + && !captureOrPromotion && !inCheck && !dangerous - && move != ttMove) + /* && move != ttMove Already implicit in the next condition */ + && bestValue > VALUE_MATED_IN_MAX_PLY) { // Move count based pruning - if ( !PvNode - && depth < 16 * ONE_PLY + if ( depth < 16 * ONE_PLY && moveCount >= FutilityMoveCounts[depth] && (!threatMove || !refutes(pos, move, threatMove))) { @@ -880,18 +885,23 @@ split_point_start: // At split points actual search starts from here // but fixing this made program slightly weaker. Depth predictedDepth = newDepth - reduction(depth, moveCount); futilityValue = ss->staticEval + ss->evalMargin + futility_margin(predictedDepth, moveCount) - + Gain[pos.piece_moved(move)][to_sq(move)]; + + Gains[pos.piece_moved(move)][to_sq(move)]; - if (!PvNode && futilityValue < beta) + if (futilityValue < beta) { + bestValue = std::max(bestValue, futilityValue); + if (SpNode) + { splitPoint->mutex.lock(); - + if (bestValue > splitPoint->bestValue) + splitPoint->bestValue = bestValue; + } continue; } // Prune moves with negative SEE at low depths - if ( predictedDepth < 2 * ONE_PLY + if ( predictedDepth < 4 * ONE_PLY && pos.see_sign(move) < 0) { if (SpNode) @@ -899,7 +909,13 @@ split_point_start: // At split points actual search starts from here continue; } + + // We have not pruned the move that will be searched, but remember how + // far in the move list we are to be more aggressive in the child node. + ss->futilityMoveCount = moveCount; } + else + ss->futilityMoveCount = 0; // Check for legality only before to do the move if (!RootNode && !SpNode && !pos.pl_move_is_legal(move, ci.pinned)) @@ -927,11 +943,18 @@ split_point_start: // At split points actual search starts from here && move != ss->killers[1]) { ss->reduction = reduction(depth, moveCount); + + if (!PvNode && cutNode) + ss->reduction += ONE_PLY; + + if (move == countermoves[0] || move == countermoves[1]) + ss->reduction = std::max(DEPTH_ZERO, ss->reduction-ONE_PLY); + Depth d = std::max(newDepth - ss->reduction, ONE_PLY); if (SpNode) alpha = splitPoint->alpha; - value = -search(pos, ss+1, -(alpha+1), -alpha, d); + value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); doFullDepthSearch = (value > alpha && ss->reduction != DEPTH_ZERO); ss->reduction = DEPTH_ZERO; @@ -948,7 +971,7 @@ split_point_start: // At split points actual search starts from here value = newDepth < ONE_PLY ? givesCheck ? -qsearch(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO) : -qsearch(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO) - : - search(pos, ss+1, -(alpha+1), -alpha, newDepth); + : - search(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode); } // Only for PV nodes do a full PV search on the first move or after a fail @@ -958,7 +981,7 @@ split_point_start: // At split points actual search starts from here value = newDepth < ONE_PLY ? givesCheck ? -qsearch(pos, ss+1, -beta, -alpha, DEPTH_ZERO) : -qsearch(pos, ss+1, -beta, -alpha, DEPTH_ZERO) - : - search(pos, ss+1, -beta, -alpha, newDepth); + : - search(pos, ss+1, -beta, -alpha, newDepth, false); // Step 17. Undo move pos.undo_move(move); @@ -1033,7 +1056,7 @@ split_point_start: // At split points actual search starts from here assert(bestValue < beta); thisThread->split(pos, ss, alpha, beta, &bestValue, &bestMove, - depth, threatMove, moveCount, &mp, NT); + depth, threatMove, moveCount, &mp, NT, cutNode); if (bestValue >= beta) break; } @@ -1076,13 +1099,15 @@ split_point_start: // At split points actual search starts from here // Increase history value of the cut-off move Value bonus = Value(int(depth) * int(depth)); - Hist.update(pos.piece_moved(bestMove), to_sq(bestMove), bonus); + History.update(pos.piece_moved(bestMove), to_sq(bestMove), bonus); + if (is_ok((ss-1)->currentMove)) + Countermoves.update(pos.piece_on(prevMoveSq), prevMoveSq, bestMove); // Decrease history of all the other played non-capture moves for (int i = 0; i < playedMoveCount - 1; i++) { Move m = movesSearched[i]; - Hist.update(pos.piece_moved(m), to_sq(m), -bonus); + History.update(pos.piece_moved(m), to_sq(m), -bonus); } } } @@ -1128,9 +1153,15 @@ split_point_start: // At split points actual search starts from here ss->ply = (ss-1)->ply + 1; // Check for an instant draw or maximum ply reached - if (pos.is_draw() || ss->ply > MAX_PLY) + if (pos.is_draw() || ss->ply > MAX_PLY) return DrawValue[pos.side_to_move()]; + // Decide whether or not to include checks, this fixes also the type of + // TT entry depth that we are going to use. Note that in qsearch we use + // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS. + ttDepth = InCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS + : DEPTH_QS_NO_CHECKS; + // Transposition table lookup. At PV nodes, we don't use the TT for // pruning, but only for move ordering. posKey = pos.key(); @@ -1138,11 +1169,6 @@ split_point_start: // At split points actual search starts from here ttMove = tte ? tte->move() : MOVE_NONE; ttValue = tte ? value_from_tt(tte->value(),ss->ply) : VALUE_NONE; - // Decide whether or not to include checks, this fixes also the type of - // TT entry depth that we are going to use. Note that in qsearch we use - // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS. - ttDepth = InCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS - : DEPTH_QS_NO_CHECKS; if ( tte && tte->depth() >= ttDepth && ttValue != VALUE_NONE // Only in case of TT access race @@ -1194,7 +1220,7 @@ split_point_start: // At split points actual 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, Hist, to_sq((ss-1)->currentMove)); + MovePicker mp(pos, ttMove, depth, History, to_sq((ss-1)->currentMove)); CheckInfo ci(pos); // Loop through the moves until no moves remain or a beta cutoff occurs @@ -1223,10 +1249,10 @@ split_point_start: // At split points actual search starts from here continue; } - // Prune moves with negative or equal SEE + // Prune moves with negative or equal SEE and also moves with positive + // SEE where capturing piece loses a tempo and SEE < beta - futilityBase. if ( futilityBase < beta - && depth < DEPTH_ZERO - && pos.see(move) <= 0) + && pos.see(move, beta - futilityBase) <= 0) { bestValue = std::max(bestValue, futilityBase); continue; @@ -1438,15 +1464,15 @@ split_point_start: // At split points actual search starts from here { // Update occupancy as if the piece and the threat are moving Bitboard occ = pos.pieces() ^ m1from ^ m1to ^ m2from; - Piece piece = pos.piece_on(m1from); + Piece pc = pos.piece_on(m1from); // The moved piece attacks the square 'tto' ? - if (pos.attacks_from(piece, m1to, occ) & m2to) + if (pos.attacks_from(pc, m1to, occ) & m2to) return true; // Scan for possible X-ray attackers behind the moved piece - Bitboard xray = (attacks_bb< ROOK>(m2to, occ) & pos.pieces(color_of(piece), QUEEN, ROOK)) - | (attacks_bb(m2to, occ) & pos.pieces(color_of(piece), QUEEN, BISHOP)); + Bitboard xray = (attacks_bb< ROOK>(m2to, occ) & pos.pieces(color_of(pc), QUEEN, ROOK)) + | (attacks_bb(m2to, occ) & pos.pieces(color_of(pc), QUEEN, BISHOP)); // Verify attackers are triggered by our move and not already existing if (xray && (xray ^ (xray & pos.attacks_from(m2to)))) @@ -1510,7 +1536,7 @@ split_point_start: // At split points actual search starts from here string uci_pv(const Position& pos, int depth, Value alpha, Value beta) { std::stringstream s; - Time::point elaspsed = Time::now() - SearchTime + 1; + Time::point elapsed = Time::now() - SearchTime + 1; size_t uciPVSize = std::min((size_t)Options["MultiPV"], RootMoves.size()); int selDepth = 0; @@ -1535,8 +1561,8 @@ split_point_start: // At split points actual search starts from here << " seldepth " << selDepth << " score " << (i == PVIdx ? score_to_uci(v, alpha, beta) : score_to_uci(v)) << " nodes " << pos.nodes_searched() - << " nps " << pos.nodes_searched() * 1000 / elaspsed - << " time " << elaspsed + << " nps " << pos.nodes_searched() * 1000 / elapsed + << " time " << elapsed << " multipv " << i + 1 << " pv"; @@ -1576,7 +1602,7 @@ void RootMove::extract_pv_from_tt(Position& pos) { && pos.is_pseudo_legal(m = tte->move()) // Local copy, TT could change && pos.pl_move_is_legal(m, pos.pinned_pieces()) && ply < MAX_PLY - && (!pos.is_draw() || ply < 2)); + && (!pos.is_draw() || ply < 2)); pv.push_back(MOVE_NONE); // Must be zero-terminating @@ -1616,13 +1642,11 @@ void Thread::idle_loop() { // Pointer 'this_sp' is not null only if we are called from split(), and not // at the thread creation. So it means we are the split point's master. - const SplitPoint* this_sp = splitPointsSize ? activeSplitPoint : NULL; + SplitPoint* this_sp = splitPointsSize ? activeSplitPoint : NULL; assert(!this_sp || (this_sp->masterThread == this && searching)); - // If this thread is the master of a split point and all slaves have finished - // their work at this split point, return from the idle loop. - while (!this_sp || this_sp->slavesMask) + while (true) { // If we are not searching, wait for a condition to be signaled instead of // wasting CPU time polling for work. @@ -1666,11 +1690,11 @@ void Thread::idle_loop() { Threads.mutex.unlock(); - Stack ss[MAX_PLY_PLUS_2]; + Stack stack[MAX_PLY_PLUS_2], *ss = stack+1; // To allow referencing (ss-1) Position pos(*sp->pos, this); - memcpy(ss, sp->ss - 1, 4 * sizeof(Stack)); - (ss+1)->splitPoint = sp; + memcpy(ss-1, sp->ss-1, 4 * sizeof(Stack)); + ss->splitPoint = sp; sp->mutex.lock(); @@ -1680,13 +1704,13 @@ void Thread::idle_loop() { switch (sp->nodeType) { case Root: - search(pos, ss+1, sp->alpha, sp->beta, sp->depth); + search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); break; case PV: - search(pos, ss+1, sp->alpha, sp->beta, sp->depth); + search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); break; case NonPV: - search(pos, ss+1, sp->alpha, sp->beta, sp->depth); + search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); break; default: assert(false); @@ -1715,6 +1739,17 @@ void Thread::idle_loop() { // unsafe because if we are exiting there is a chance are already freed. sp->mutex.unlock(); } + + // If this thread is the master of a split point and all slaves have finished + // their work at this split point, return from the idle loop. + if (this_sp && !this_sp->slavesMask) + { + this_sp->mutex.lock(); + bool finished = !this_sp->slavesMask; // Retest under lock protection + this_sp->mutex.unlock(); + if (finished) + return; + } } }