X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=2b51a698b0de3e40c8208255251a92fc0149faf0;hp=b43ebd02ab848ae4f2675bd0eaba637b8f9532b8;hb=4e31c39a6494499ba85db0e0014bbbaac9770b1d;hpb=22715259a04497743afe7e33f5cf1e3b13bb097e diff --git a/src/search.cpp b/src/search.cpp index b43ebd02..2b51a698 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -100,7 +100,7 @@ namespace { Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth); void id_loop(Position& pos); - bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta); + bool check_is_dangerous(Position& pos, Move move, Value futilityBase, Value beta); bool connected_moves(const Position& pos, Move m1, Move m2); Value value_to_tt(Value v, int ply); Value value_from_tt(Value v, int ply); @@ -524,7 +524,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 @@ -553,13 +553,13 @@ namespace { // smooth experience in analysis mode. We don't probe at Root nodes otherwise // we should also update RootMoveList to avoid bogus output. if ( !RootNode - && tte && tte->depth() >= depth + && tte + && tte->depth() >= depth + && ttValue != VALUE_NONE // Only in case of TT access race && ( PvNode ? tte->type() == BOUND_EXACT : ttValue >= beta ? (tte->type() & BOUND_LOWER) : (tte->type() & BOUND_UPPER))) { - assert(ttValue != VALUE_NONE); // Due to depth > DEPTH_NONE - TT.refresh(tte); ss->currentMove = ttMove; // Can be MOVE_NONE @@ -580,16 +580,22 @@ namespace { else if (tte) { - assert(tte->static_value() != VALUE_NONE); - assert(ttValue != VALUE_NONE || tte->type() == BOUND_NONE); + // 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); + // Can ttValue be used as a better position evaluation? - if ( ((tte->type() & BOUND_LOWER) && ttValue > eval) - || ((tte->type() & BOUND_UPPER) && ttValue < eval)) - eval = ttValue; + if (ttValue != VALUE_NONE) + if ( ((tte->type() & BOUND_LOWER) && ttValue > eval) + || ((tte->type() & BOUND_UPPER) && ttValue < eval)) + eval = ttValue; } else { @@ -958,7 +964,7 @@ split_point_start: // At split points actual search starts from here // ran out of time. In this case, the return value of the search cannot // be trusted, and we don't update the best move and/or PV. if (Signals.stop || thisThread->cutoff_occurred()) - return bestValue; + return value; // To avoid returning VALUE_INFINITE if (RootNode) { @@ -1103,7 +1109,7 @@ 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()]; // Transposition table lookup. At PV nodes, we don't use the TT for @@ -1118,13 +1124,13 @@ split_point_start: // At split points actual search starts from here // 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 + if ( tte + && tte->depth() >= ttDepth + && ttValue != VALUE_NONE // Only in case of TT access race && ( PvNode ? tte->type() == BOUND_EXACT : ttValue >= beta ? (tte->type() & BOUND_LOWER) : (tte->type() & BOUND_UPPER))) { - assert(ttValue != VALUE_NONE); // Due to ttDepth > DEPTH_NONE - ss->currentMove = ttMove; // Can be MOVE_NONE return ttValue; } @@ -1140,10 +1146,13 @@ split_point_start: // At split points actual search starts from here { if (tte) { - assert(tte->static_value() != VALUE_NONE); + 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); } else ss->staticEval = bestValue = evaluate(pos, ss->evalMargin); @@ -1283,40 +1292,56 @@ split_point_start: // At split points actual search starts from here } - // check_is_dangerous() tests if a checking move can be pruned in qsearch(). - // bestValue is updated only when returning false because in that case move - // will be pruned. + // value_to_tt() adjusts a mate score from "plies to mate from the root" to + // "plies to mate from the current position". Non-mate scores are unchanged. + // The function is called before storing a value to the transposition table. + + Value value_to_tt(Value v, int ply) { + + assert(v != VALUE_NONE); + + return v >= VALUE_MATE_IN_MAX_PLY ? v + ply + : v <= VALUE_MATED_IN_MAX_PLY ? v - ply : v; + } + + + // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score + // from the transposition table (where refers to the plies to mate/be mated + // from current position) to "plies to mate/be mated from the root". + + Value value_from_tt(Value v, int ply) { + + return v == VALUE_NONE ? VALUE_NONE + : v >= VALUE_MATE_IN_MAX_PLY ? v - ply + : v <= VALUE_MATED_IN_MAX_PLY ? v + ply : v; + } + + + // check_is_dangerous() tests if a checking move can be pruned in qsearch() - bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta) + bool check_is_dangerous(Position& pos, Move move, Value futilityBase, Value beta) { - Bitboard b, occ, oldAtt, newAtt, kingAtt; - Square from, to, ksq; - Piece pc; - Color them; - - from = from_sq(move); - to = to_sq(move); - them = ~pos.side_to_move(); - ksq = pos.king_square(them); - kingAtt = pos.attacks_from(ksq); - pc = pos.piece_moved(move); - - occ = pos.pieces() ^ from ^ ksq; - oldAtt = pos.attacks_from(pc, from, occ); - newAtt = pos.attacks_from(pc, to, occ); - - // Rule 1. Checks which give opponent's king at most one escape square are dangerous - b = kingAtt & ~pos.pieces(them) & ~newAtt & ~(1ULL << to); - - if (!more_than_one(b)) + Piece pc = pos.piece_moved(move); + Square from = from_sq(move); + Square to = to_sq(move); + Color them = ~pos.side_to_move(); + Square ksq = pos.king_square(them); + Bitboard enemies = pos.pieces(them); + Bitboard kingAtt = pos.attacks_from(ksq); + Bitboard occ = pos.pieces() ^ from ^ ksq; + Bitboard oldAtt = pos.attacks_from(pc, from, occ); + Bitboard newAtt = pos.attacks_from(pc, to, occ); + + // Checks which give opponent's king at most one escape square are dangerous + if (!more_than_one(kingAtt & ~(enemies | newAtt | to))) return true; - // Rule 2. Queen contact check is very dangerous + // Queen contact check is very dangerous if (type_of(pc) == QUEEN && (kingAtt & to)) return true; - // Rule 3. Creating new double threats with checks - b = pos.pieces(them) & newAtt & ~oldAtt & ~(1ULL << ksq); + // Creating new double threats with checks is dangerous + Bitboard b = (enemies ^ ksq) & newAtt & ~oldAtt; while (b) { // Note that here we generate illegal "double move"! @@ -1376,31 +1401,6 @@ split_point_start: // At split points actual search starts from here } - // value_to_tt() adjusts a mate score from "plies to mate from the root" to - // "plies to mate from the current position". Non-mate scores are unchanged. - // The function is called before storing a value to the transposition table. - - Value value_to_tt(Value v, int ply) { - - assert(v != VALUE_NONE); - - return v >= VALUE_MATE_IN_MAX_PLY ? v + ply - : v <= VALUE_MATED_IN_MAX_PLY ? v - ply : v; - } - - - // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score - // from the transposition table (where refers to the plies to mate/be mated - // from current position) to "plies to mate/be mated from the root". - - Value value_from_tt(Value v, int ply) { - - return v == VALUE_NONE ? VALUE_NONE - : v >= VALUE_MATE_IN_MAX_PLY ? v - ply - : v <= VALUE_MATED_IN_MAX_PLY ? v + ply : v; - } - - // connected_threat() tests whether it is safe to forward prune a move or if // is somehow connected to the threat move returned by null search. @@ -1411,12 +1411,10 @@ split_point_start: // At split points actual search starts from here assert(!pos.is_capture_or_promotion(m)); assert(!pos.is_passed_pawn_push(m)); - Square mfrom, mto, tfrom, tto; - - mfrom = from_sq(m); - mto = to_sq(m); - tfrom = from_sq(threat); - tto = to_sq(threat); + Square mfrom = from_sq(m); + Square mto = to_sq(m); + Square tfrom = from_sq(threat); + Square tto = to_sq(threat); // Case 1: Don't prune moves which move the threatened piece if (mfrom == tto) @@ -1424,11 +1422,26 @@ split_point_start: // At split points actual search starts from here // Case 2: If the threatened piece has value less than or equal to the // value of the threatening piece, don't prune moves which defend it. - if ( pos.is_capture(threat) + if ( pos.is_capture(threat) && ( PieceValue[MG][pos.piece_on(tfrom)] >= PieceValue[MG][pos.piece_on(tto)] - || type_of(pos.piece_on(tfrom)) == KING) - && pos.move_attacks_square(m, tto)) - return true; + || type_of(pos.piece_on(tfrom)) == KING)) + { + // Update occupancy as if the piece is moving + Bitboard occ = pos.pieces() ^ mfrom ^ mto; + Piece piece = pos.piece_on(mfrom); + + // The moved piece attacks the square 'tto' ? + if (pos.attacks_from(piece, mto, occ) & tto) + 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)); + + // Verify attackers are triggered by our move and not already existing + if (xray && (xray ^ (xray & pos.attacks_from(tto)))) + return true; + } // Case 3: If the moving piece in the threatened move is a slider, don't // prune safe moves which block its ray. @@ -1491,23 +1504,24 @@ split_point_start: // At split points actual search starts from here std::stringstream s; Time::point elaspsed = Time::now() - SearchTime + 1; + size_t uciPVSize = std::min((size_t)Options["MultiPV"], RootMoves.size()); int selDepth = 0; for (size_t i = 0; i < Threads.size(); i++) if (Threads[i].maxPly > selDepth) selDepth = Threads[i].maxPly; - for (size_t i = 0; i < std::min((size_t)Options["MultiPV"], RootMoves.size()); i++) + for (size_t i = 0; i < uciPVSize; i++) { bool updated = (i <= PVIdx); if (depth == 1 && !updated) continue; - int d = (updated ? depth : depth - 1); - Value v = (updated ? RootMoves[i].score : RootMoves[i].prevScore); + int d = updated ? depth : depth - 1; + Value v = updated ? RootMoves[i].score : RootMoves[i].prevScore; - if (s.rdbuf()->in_avail()) + if (s.rdbuf()->in_avail()) // Not at first line s << "\n"; s << "info depth " << d @@ -1538,29 +1552,27 @@ void RootMove::extract_pv_from_tt(Position& pos) { StateInfo state[MAX_PLY_PLUS_2], *st = state; TTEntry* tte; - int ply = 1; + int ply = 0; Move m = pv[0]; - assert(m != MOVE_NONE && pos.is_pseudo_legal(m)); - pv.clear(); - pv.push_back(m); - pos.do_move(m, *st++); - - while ( (tte = TT.probe(pos.key())) != NULL - && (m = tte->move()) != MOVE_NONE // Local copy, TT entry could change - && pos.is_pseudo_legal(m) - && pos.pl_move_is_legal(m, pos.pinned_pieces()) - && ply < MAX_PLY - && (!pos.is_draw() || ply < 2)) - { + + do { pv.push_back(m); - pos.do_move(m, *st++); - ply++; - } - pv.push_back(MOVE_NONE); - do pos.undo_move(pv[--ply]); while (ply); + assert(pos.move_is_legal(pv[ply])); + pos.do_move(pv[ply++], *st++); + tte = TT.probe(pos.key()); + + } while ( tte + && 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)); + + pv.push_back(MOVE_NONE); // Must be zero-terminating + + while (ply) pos.undo_move(pv[--ply]); } @@ -1572,27 +1584,28 @@ void RootMove::insert_pv_in_tt(Position& pos) { StateInfo state[MAX_PLY_PLUS_2], *st = state; TTEntry* tte; - Key k; - Value v, m = VALUE_NONE; int ply = 0; - - assert(pv[ply] != MOVE_NONE && pos.is_pseudo_legal(pv[ply])); + Value v, m; do { - k = pos.key(); - tte = TT.probe(k); + tte = TT.probe(pos.key()); - // Don't overwrite existing correct entries - if (!tte || tte->move() != pv[ply]) + if (!tte || tte->move() != pv[ply]) // Don't overwrite correct entries { - v = (pos.in_check() ? VALUE_NONE : evaluate(pos, m)); - TT.store(k, VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply], v, m); + 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], v, m); } - pos.do_move(pv[ply], *st++); - } while (pv[++ply] != MOVE_NONE); + assert(pos.move_is_legal(pv[ply])); + pos.do_move(pv[ply++], *st++); + + } while (pv[ply] != MOVE_NONE); - do pos.undo_move(pv[--ply]); while (ply); + while (ply) pos.undo_move(pv[--ply]); }