X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=085d124ee66b994819a1e8e71e20bf99eb3532cd;hp=253311ae11c9ff122a4f40db5ab4e3bc07ef81e5;hb=db097921bc0f631d770c3437569f105579823471;hpb=a5b1f4774f44e29ad32a93b524ad43fa2d790e1a diff --git a/src/search.cpp b/src/search.cpp index 253311ae..085d124e 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -99,8 +99,8 @@ namespace { Value value_to_tt(Value v, int ply); Value value_from_tt(Value v, int ply); bool check_is_dangerous(Position& pos, Move move, Value futilityBase, Value beta); - bool yields_to_threat(const Position& pos, Move move, Move threat); - bool prevents_threat(const Position& pos, Move move, Move threat); + bool allows_move(const Position& pos, Move first, Move second); + bool prevents_move(const Position& pos, Move first, Move second); string uci_pv(const Position& pos, int depth, Value alpha, Value beta); struct Skill { @@ -188,7 +188,7 @@ void Search::think() { { RootMoves.push_back(MOVE_NONE); sync_cout << "info depth 0 score " - << score_to_uci(RootPos.in_check() ? -VALUE_MATE : VALUE_DRAW) + << score_to_uci(RootPos.checkers() ? -VALUE_MATE : VALUE_DRAW) << sync_endl; goto finalize; @@ -208,7 +208,7 @@ void Search::think() { if (Options["Contempt Factor"] && !Options["UCI_AnalyseMode"]) { int cf = Options["Contempt Factor"] * PawnValueMg / 100; // From centipawns - cf = cf * MaterialTable::game_phase(RootPos) / PHASE_MIDGAME; // Scale down with phase + cf = cf * Material::game_phase(RootPos) / PHASE_MIDGAME; // Scale down with phase DrawValue[ RootColor] = VALUE_DRAW - Value(cf); DrawValue[~RootColor] = VALUE_DRAW + Value(cf); } @@ -218,7 +218,7 @@ void Search::think() { if (Options["Use Search Log"]) { Log log(Options["Search Log Filename"]); - log << "\nSearching: " << RootPos.to_fen() + log << "\nSearching: " << RootPos.fen() << "\ninfinite: " << Limits.infinite << " ponder: " << Limits.ponder << " time: " << Limits.time[RootColor] @@ -391,7 +391,8 @@ namespace { // Sort the PV lines searched so far and update the GUI sort(RootMoves.begin(), RootMoves.begin() + PVIdx + 1); - sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl; + if (PVIdx + 1 == PVSize || Time::now() - SearchTime > 3000) + sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl; } // Do we need to pick now the sub-optimal best move ? @@ -484,13 +485,14 @@ namespace { Value bestValue, value, ttValue; Value eval, nullValue, futilityValue; bool inCheck, givesCheck, pvMove, singularExtensionNode; - bool captureOrPromotion, dangerous, doFullDepthSearch; + bool captureOrPromotion, dangerous, doFullDepthSearch, threatExtension; int moveCount, playedMoveCount; // Step 1. Initialize node Thread* thisThread = pos.this_thread(); moveCount = playedMoveCount = 0; - inCheck = pos.in_check(); + threatExtension = false; + inCheck = pos.checkers(); if (SpNode) { @@ -573,31 +575,17 @@ namespace { // Step 5. Evaluate the position statically and update parent's gain statistics if (inCheck) ss->staticEval = ss->evalMargin = eval = VALUE_NONE; - - else if (tte) + else { - // Following asserts are valid only in single thread condition because - // TT access is always racy and its contents cannot be trusted. - assert(tte->static_value() != VALUE_NONE || Threads.size() > 1); - assert(ttValue != VALUE_NONE || tte->type() == BOUND_NONE || Threads.size() > 1); - - ss->staticEval = eval = tte->static_value(); - ss->evalMargin = tte->static_value_margin(); - - if (eval == VALUE_NONE || ss->evalMargin == VALUE_NONE) // Due to a race - eval = ss->staticEval = evaluate(pos, ss->evalMargin); + eval = ss->staticEval = evaluate(pos, ss->evalMargin); // Can ttValue be used as a better position evaluation? - if (ttValue != VALUE_NONE) + if (tte && ttValue != VALUE_NONE) + { if ( ((tte->type() & BOUND_LOWER) && ttValue > eval) || ((tte->type() & BOUND_UPPER) && ttValue < eval)) eval = ttValue; - } - else - { - eval = ss->staticEval = evaluate(pos, ss->evalMargin); - TT.store(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, - ss->staticEval, ss->evalMargin); + } } // Update gain for the parent non-capture move given the static position @@ -688,16 +676,15 @@ namespace { // The null move failed low, which means that we may be faced with // some kind of threat. If the previous move was reduced, check if // the move that refuted the null move was somehow connected to the - // move which was reduced. If a connection is found, return a fail - // low score (which will cause the reduced move to fail high in the - // parent node, which will trigger a re-search with full depth). + // move which was reduced. If a connection is found extend moves that + // defend against threat. threatMove = (ss+1)->currentMove; if ( depth < 5 * ONE_PLY && (ss-1)->reduction && threatMove != MOVE_NONE - && yields_to_threat(pos, (ss-1)->currentMove, threatMove)) - return beta - 1; + && allows_move(pos, (ss-1)->currentMove, threatMove)) + threatExtension = true; } } @@ -793,7 +780,7 @@ split_point_start: // At split points actual search starts from here { Signals.firstRootMove = (moveCount == 1); - if (thisThread == Threads.main_thread() && Time::now() - SearchTime > 2000) + if (thisThread == Threads.main_thread() && Time::now() - SearchTime > 3000) sync_cout << "info depth " << depth / ONE_PLY << " currmove " << move_to_uci(move, pos.is_chess960()) << " currmovenumber " << moveCount + PVIdx << sync_endl; @@ -815,6 +802,9 @@ split_point_start: // At split points actual search starts from here if (PvNode && dangerous) ext = ONE_PLY; + else if (threatExtension && prevents_move(pos, move, threatMove)) + ext = ONE_PLY; + else if (givesCheck && pos.see_sign(move) >= 0) ext = ONE_PLY / 2; @@ -857,7 +847,7 @@ split_point_start: // At split points actual search starts from here // Move count based pruning if ( depth < 16 * ONE_PLY && moveCount >= FutilityMoveCounts[depth] - && (!threatMove || !prevents_threat(pos, move, threatMove))) + && (!threatMove || !prevents_move(pos, move, threatMove))) { if (SpNode) sp->mutex.lock(); @@ -892,7 +882,7 @@ split_point_start: // At split points actual search starts from here } // Check for legality only before to do the move - if (!pos.pl_move_is_legal(move, ci.pinned)) + if (!RootNode && !SpNode && !pos.pl_move_is_legal(move, ci.pinned)) { moveCount--; continue; @@ -1003,8 +993,10 @@ split_point_start: // At split points actual search starts from here alpha = value; // Update alpha here! Always alpha < beta if (SpNode) sp->alpha = value; } - else // Fail high + else { + assert(value >= beta); // Fail high + if (SpNode) sp->cutoff = true; break; } @@ -1014,9 +1006,10 @@ split_point_start: // At split points actual search starts from here // Step 19. Check for splitting the search if ( !SpNode && depth >= Threads.min_split_depth() - && bestValue < beta && Threads.available_slave_exists(thisThread)) { + assert(bestValue < beta); + bestValue = Threads.split(pos, ss, alpha, beta, bestValue, &bestMove, depth, threatMove, moveCount, mp, NT); if (bestValue >= beta) @@ -1048,8 +1041,7 @@ split_point_start: // At split points actual search starts from here if (bestValue >= beta) // Failed high { - TT.store(posKey, value_to_tt(bestValue, ss->ply), BOUND_LOWER, depth, - bestMove, ss->staticEval, ss->evalMargin); + TT.store(posKey, value_to_tt(bestValue, ss->ply), BOUND_LOWER, depth, bestMove); if (!pos.is_capture_or_promotion(bestMove) && !inCheck) { @@ -1074,7 +1066,7 @@ split_point_start: // At split points actual search starts from here else // Failed low or PV search TT.store(posKey, value_to_tt(bestValue, ss->ply), PvNode && bestMove != MOVE_NONE ? BOUND_EXACT : BOUND_UPPER, - depth, bestMove, ss->staticEval, ss->evalMargin); + depth, bestMove); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1092,7 +1084,7 @@ split_point_start: // At split points actual search starts from here const bool PvNode = (NT == PV); assert(NT == PV || NT == NonPV); - assert(InCheck == pos.in_check()); + assert(InCheck == !!pos.checkers()); assert(alpha >= -VALUE_INFINITE && alpha < beta && beta <= VALUE_INFINITE); assert(PvNode || (alpha == beta - 1)); assert(depth <= DEPTH_ZERO); @@ -1101,12 +1093,17 @@ split_point_start: // At split points actual search starts from here const TTEntry* tte; Key posKey; Move ttMove, move, bestMove; - Value bestValue, value, ttValue, futilityValue, futilityBase; - bool givesCheck, enoughMaterial, evasionPrunable; + Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha; + bool givesCheck, enoughMaterial, evasionPrunable, fromNull; Depth ttDepth; + // To flag BOUND_EXACT a node with eval above alpha and no available moves + if (PvNode) + oldAlpha = alpha; + ss->currentMove = bestMove = MOVE_NONE; ss->ply = (ss-1)->ply + 1; + fromNull = (ss-1)->currentMove == MOVE_NULL; // Check for an instant draw or maximum ply reached if (pos.is_draw() || ss->ply > MAX_PLY) @@ -1144,15 +1141,11 @@ split_point_start: // At split points actual search starts from here } else { - if (tte) + if (fromNull) { - assert(tte->static_value() != VALUE_NONE || Threads.size() > 1); - - ss->staticEval = bestValue = tte->static_value(); - ss->evalMargin = tte->static_value_margin(); - - if (ss->staticEval == VALUE_NONE || ss->evalMargin == VALUE_NONE) // Due to a race - ss->staticEval = bestValue = evaluate(pos, ss->evalMargin); + // Approximated score. Real one is slightly higher due to tempo + ss->staticEval = bestValue = -(ss-1)->staticEval; + ss->evalMargin = VALUE_ZERO; } else ss->staticEval = bestValue = evaluate(pos, ss->evalMargin); @@ -1161,8 +1154,7 @@ split_point_start: // At split points actual search starts from here if (bestValue >= beta) { if (!tte) - TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER, - DEPTH_NONE, MOVE_NONE, ss->staticEval, ss->evalMargin); + TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER, DEPTH_NONE, MOVE_NONE); return bestValue; } @@ -1191,6 +1183,7 @@ split_point_start: // At split points actual search starts from here // Futility pruning if ( !PvNode && !InCheck + && !fromNull && !givesCheck && move != ttMove && enoughMaterial @@ -1203,9 +1196,7 @@ split_point_start: // At split points actual search starts from here if (futilityValue < beta) { - if (futilityValue > bestValue) - bestValue = futilityValue; - + bestValue = std::max(bestValue, futilityValue); continue; } @@ -1213,7 +1204,10 @@ split_point_start: // At split points actual search starts from here if ( futilityBase < beta && depth < DEPTH_ZERO && pos.see(move) <= 0) + { + bestValue = std::max(bestValue, futilityBase); continue; + } } // Detect non-capture evasions that are candidate to be pruned @@ -1269,9 +1263,7 @@ split_point_start: // At split points actual search starts from here } else // Fail high { - TT.store(posKey, value_to_tt(value, ss->ply), BOUND_LOWER, - ttDepth, move, ss->staticEval, ss->evalMargin); - + TT.store(posKey, value_to_tt(value, ss->ply), BOUND_LOWER, ttDepth, move); return value; } } @@ -1284,8 +1276,8 @@ split_point_start: // At split points actual search starts from here return mated_in(ss->ply); // Plies to mate from the root TT.store(posKey, value_to_tt(bestValue, ss->ply), - PvNode && bestMove != MOVE_NONE ? BOUND_EXACT : BOUND_UPPER, - ttDepth, bestMove, ss->staticEval, ss->evalMargin); + PvNode && bestValue > oldAlpha ? BOUND_EXACT : BOUND_UPPER, + ttDepth, bestMove); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1354,39 +1346,40 @@ split_point_start: // At split points actual search starts from here } - // yields_to_threat() tests whether the move at previous ply yields to the so - // called threat move (the best move returned from a null search that fails - // low). Here 'yields to' means that the move somehow made the threat possible - // for instance if the moving piece is the same in both moves. + // allows_move() tests whether the move at previous ply (first) somehow makes a + // second move possible, for instance if the moving piece is the same in both + // moves. Normally the second move is the threat move (the best move returned + // from a null search that fails low). - bool yields_to_threat(const Position& pos, Move move, Move threat) { + bool allows_move(const Position& pos, Move first, Move second) { - assert(is_ok(move)); - assert(is_ok(threat)); - assert(color_of(pos.piece_on(from_sq(threat))) == ~pos.side_to_move()); + assert(is_ok(first)); + assert(is_ok(second)); + assert(color_of(pos.piece_on(from_sq(second))) == ~pos.side_to_move()); + assert(color_of(pos.piece_on(to_sq(first))) == ~pos.side_to_move()); - Square mfrom = from_sq(move); - Square mto = to_sq(move); - Square tfrom = from_sq(threat); - Square tto = to_sq(threat); + Square m1from = from_sq(first); + Square m2from = from_sq(second); + Square m1to = to_sq(first); + Square m2to = to_sq(second); - // The piece is the same or threat's destination was vacated by the move - if (mto == tfrom || tto == mfrom) + // The piece is the same or second's destination was vacated by the first move + if (m1to == m2from || m2to == m1from) return true; - // Threat moves through the vacated square - if (between_bb(tfrom, tto) & mfrom) + // Second one moves through the square vacated by first one + if (between_bb(m2from, m2to) & m1from) return true; - // Threat's destination is defended by the move's piece - Bitboard matt = pos.attacks_from(pos.piece_on(mto), mto, pos.pieces() ^ tfrom); - if (matt & tto) + // Second's destination is defended by the first move's piece + Bitboard m1att = pos.attacks_from(pos.piece_on(m1to), m1to, pos.pieces() ^ m2from); + if (m1att & m2to) return true; - // Threat gives a discovered check through the move's checking piece - if (matt & pos.king_square(pos.side_to_move())) + // Second move gives a discovered check through the first's checking piece + if (m1att & pos.king_square(pos.side_to_move())) { - assert(between_bb(mto, pos.king_square(pos.side_to_move())) & tfrom); + assert(between_bb(m1to, pos.king_square(pos.side_to_move())) & m2from); return true; } @@ -1394,51 +1387,52 @@ split_point_start: // At split points actual search starts from here } - // prevents_threat() tests whether a move is able to defend against the so - // called threat move (the best move returned from a null search that fails - // low). In this case will not be pruned. + // prevents_move() tests whether a move (first) is able to defend against an + // opponent's move (second). In this case will not be pruned. Normally the + // second move is the threat move (the best move returned from a null search + // that fails low). - bool prevents_threat(const Position& pos, Move move, Move threat) { + bool prevents_move(const Position& pos, Move first, Move second) { - assert(is_ok(move)); - assert(is_ok(threat)); - assert(!pos.is_capture_or_promotion(move)); - assert(!pos.is_passed_pawn_push(move)); + assert(is_ok(first)); + assert(is_ok(second)); + assert(!pos.is_capture_or_promotion(first)); + assert(!pos.is_passed_pawn_push(first)); - Square mfrom = from_sq(move); - Square mto = to_sq(move); - Square tfrom = from_sq(threat); - Square tto = to_sq(threat); + Square m1from = from_sq(first); + Square m2from = from_sq(second); + Square m1to = to_sq(first); + Square m2to = to_sq(second); // Don't prune moves of the threatened piece - if (mfrom == tto) + if (m1from == m2to) return true; // If the threatened piece has value less than or equal to the value of the // threat piece, don't prune moves which defend it. - if ( pos.is_capture(threat) - && ( PieceValue[MG][pos.piece_on(tfrom)] >= PieceValue[MG][pos.piece_on(tto)] - || type_of(pos.piece_on(tfrom)) == KING)) + if ( pos.is_capture(second) + && ( PieceValue[MG][pos.piece_on(m2from)] >= PieceValue[MG][pos.piece_on(m2to)] + || type_of(pos.piece_on(m2from)) == KING)) { // Update occupancy as if the piece and the threat are moving - Bitboard occ = pos.pieces() ^ mfrom ^ mto ^ tfrom; - Piece piece = pos.piece_on(mfrom); + Bitboard occ = pos.pieces() ^ m1from ^ m1to ^ m2from; + Piece piece = pos.piece_on(m1from); // The moved piece attacks the square 'tto' ? - if (pos.attacks_from(piece, mto, occ) & tto) + if (pos.attacks_from(piece, m1to, occ) & m2to) return true; // Scan for possible X-ray attackers behind the moved piece - Bitboard xray = (attacks_bb< ROOK>(tto, occ) & pos.pieces(color_of(piece), QUEEN, ROOK)) - | (attacks_bb(tto, occ) & pos.pieces(color_of(piece), QUEEN, BISHOP)); + 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)); // Verify attackers are triggered by our move and not already existing - if (xray && (xray ^ (xray & pos.attacks_from(tto)))) + if (xray && (xray ^ (xray & pos.attacks_from(m2to)))) return true; } // Don't prune safe moves which block the threat path - if ((between_bb(tfrom, tto) & mto) && pos.see_sign(move) >= 0) + if ((between_bb(m2from, m2to) & m1to) && pos.see_sign(first) >= 0) return true; return false; @@ -1551,7 +1545,8 @@ void RootMove::extract_pv_from_tt(Position& pos) { do { pv.push_back(m); - assert(pos.move_is_legal(pv[ply])); + assert(MoveList(pos).contains(pv[ply])); + pos.do_move(pv[ply++], *st++); tte = TT.probe(pos.key()); @@ -1576,22 +1571,15 @@ void RootMove::insert_pv_in_tt(Position& pos) { StateInfo state[MAX_PLY_PLUS_2], *st = state; TTEntry* tte; int ply = 0; - Value v, m; do { tte = TT.probe(pos.key()); if (!tte || tte->move() != pv[ply]) // Don't overwrite correct entries - { - if (pos.in_check()) - v = m = VALUE_NONE; - else - v = evaluate(pos, m); + TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply]); - TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply], v, m); - } + assert(MoveList(pos).contains(pv[ply])); - assert(pos.move_is_legal(pv[ply])); pos.do_move(pv[ply++], *st++); } while (pv[ply] != MOVE_NONE);