X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=3985ad3049c6ba3d747c4285fceabbd6c5382cdb;hp=f24f33b91cfb48d63eb1ec60e81c7d90caff663b;hb=110644d91834fbf44859aa9aad63c23ed1dafc56;hpb=62d38f0196b077a6f67213f5fbbbb28eb60e7d92 diff --git a/src/search.cpp b/src/search.cpp index f24f33b9..3985ad30 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -100,6 +100,7 @@ namespace { Value value_to_tt(Value v, int ply); Value value_from_tt(Value v, int ply); bool check_is_dangerous(const Position& pos, Move move, Value futilityBase, Value beta); + bool allows(const Position& pos, Move first, Move second); bool refutes(const Position& pos, Move first, Move second); string uci_pv(const Position& pos, int depth, Value alpha, Value beta); @@ -152,7 +153,7 @@ void Search::init() { /// Search::perft() is our utility to verify move generation. All the leaf nodes /// up to the given depth are generated and counted and the sum returned. -size_t Search::perft(Position& pos, Depth depth) { +static size_t perft(Position& pos, Depth depth) { StateInfo st; size_t cnt = 0; @@ -162,12 +163,15 @@ size_t Search::perft(Position& pos, Depth depth) { for (MoveList it(pos); *it; ++it) { pos.do_move(*it, st, ci, pos.move_gives_check(*it, ci)); - cnt += leaf ? MoveList(pos).size() : perft(pos, depth - ONE_PLY); + cnt += leaf ? MoveList(pos).size() : ::perft(pos, depth - ONE_PLY); pos.undo_move(*it); } return cnt; } +size_t Search::perft(Position& pos, Depth depth) { + return depth > ONE_PLY ? ::perft(pos, depth) : MoveList(pos).size(); +} /// Search::think() is the external interface to Stockfish's search, and is /// called by the main thread when the program receives the UCI 'go' command. It @@ -211,7 +215,7 @@ void Search::think() { else DrawValue[WHITE] = DrawValue[BLACK] = VALUE_DRAW; - if (Options["Use Search Log"]) + if (Options["Write Search Log"]) { Log log(Options["Search Log Filename"]); log << "\nSearching: " << RootPos.fen() @@ -227,7 +231,7 @@ void Search::think() { for (size_t i = 0; i < Threads.size(); i++) Threads[i]->maxPly = 0; - Threads.sleepWhileIdle = Options["Use Sleeping Threads"]; + Threads.sleepWhileIdle = Options["Idle Threads Sleep"]; // Set best timer interval to avoid lagging under time pressure. Timer is // used to check for remaining available thinking time. @@ -243,7 +247,7 @@ void Search::think() { Threads.timer->msec = 0; // Stop the timer Threads.sleepWhileIdle = true; // Send idle threads to sleep - if (Options["Use Search Log"]) + if (Options["Write Search Log"]) { Time::point elapsed = Time::now() - SearchTime + 1; @@ -294,7 +298,7 @@ namespace { int depth, prevBestMoveChanges; Value bestValue, alpha, beta, delta; - memset(ss-1, 0, 4 * sizeof(Stack)); + std::memset(ss-1, 0, 4 * sizeof(Stack)); (ss-1)->currentMove = MOVE_NULL; // Hack to skip update gains depth = BestMoveChanges = 0; @@ -363,6 +367,12 @@ namespace { if (Signals.stop) return; + // When failing high/low give some update (without cluttering + // the UI) before to research. + if ( (bestValue <= alpha || bestValue >= beta) + && Time::now() - SearchTime > 3000) + sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl; + // In case of failing low/high increase aspiration window and // research, otherwise exit the loop. if (bestValue <= alpha) @@ -381,10 +391,6 @@ namespace { delta += delta / 2; assert(alpha >= -VALUE_INFINITE && beta <= VALUE_INFINITE); - - // Give some update (without cluttering the UI) before to research - if (Time::now() - SearchTime > 3000) - sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl; } // Sort the PV lines searched so far and update the GUI @@ -398,7 +404,7 @@ namespace { if (skill.enabled() && skill.time_to_pick(depth)) skill.pick_move(); - if (Options["Use Search Log"]) + if (Options["Write Search Log"]) { RootMove& rm = RootMoves[0]; if (skill.best != MOVE_NONE) @@ -496,7 +502,6 @@ namespace { // Step 1. Initialize node Thread* thisThread = pos.this_thread(); - moveCount = quietCount = 0; inCheck = pos.checkers(); if (SpNode) @@ -511,9 +516,10 @@ namespace { assert(splitPoint->bestValue > -VALUE_INFINITE && splitPoint->moveCount > 0); - goto split_point_start; + goto moves_loop; } + moveCount = quietCount = 0; bestValue = -VALUE_INFINITE; ss->currentMove = threatMove = (ss+1)->excludedMove = bestMove = MOVE_NONE; ss->ply = (ss-1)->ply + 1; @@ -582,7 +588,7 @@ namespace { if (inCheck) { ss->staticEval = ss->evalMargin = eval = VALUE_NONE; - goto iid_start; + goto moves_loop; } else if (tte) @@ -617,7 +623,7 @@ namespace { Gains.update(pos.piece_on(to), to, -(ss-1)->staticEval - ss->staticEval); } - // Step 6. Razoring (is omitted in PV nodes) + // Step 6. Razoring (skipped when in check) if ( !PvNode && depth < 4 * ONE_PLY && eval + razor_margin(depth) < beta @@ -633,7 +639,7 @@ namespace { return v; } - // Step 7. Static null move pruning (is omitted in PV nodes) + // Step 7. Static null move pruning (skipped when in check) // We're betting that the opponent doesn't have a move that will reduce // the score by more than futility_margin(depth) if we do a null move. if ( !PvNode @@ -689,19 +695,22 @@ namespace { else { // The null move failed low, which means that we may be faced with - // some kind of threat. If the previous move was reduced return a fail + // 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). + threatMove = (ss+1)->currentMove; + if ( depth < 5 * ONE_PLY && (ss-1)->reduction - && nullValue < beta - Value(128)) + && threatMove != MOVE_NONE + && allows(pos, (ss-1)->currentMove, threatMove)) return alpha; - - threatMove = (ss+1)->currentMove; } } - // Step 9. ProbCut (is omitted in PV nodes) + // Step 9. ProbCut (skipped when in check) // If we have a very good capture (i.e. SEE > seeValues[captured_piece_type]) // and a reduced search returns a value much above beta, we can (almost) safely // prune the previous move. @@ -732,12 +741,10 @@ namespace { } } -iid_start: // When in check we skip early cut tests - - // Step 10. Internal iterative deepening + // Step 10. Internal iterative deepening (skipped when in check) if ( depth >= (PvNode ? 5 * ONE_PLY : 8 * ONE_PLY) && ttMove == MOVE_NONE - && (PvNode || (!inCheck && ss->staticEval + Value(256) >= beta))) + && (PvNode || ss->staticEval + Value(256) >= beta)) { Depth d = depth - 2 * ONE_PLY - (PvNode ? DEPTH_ZERO : depth / 4); @@ -749,7 +756,7 @@ iid_start: // When in check we skip early cut tests ttMove = tte ? tte->move() : MOVE_NONE; } -split_point_start: // At split points actual search starts from here +moves_loop: // When in check and at SpNode search starts from here Square prevMoveSq = to_sq((ss-1)->currentMove); Move countermoves[] = { Countermoves[pos.piece_on(prevMoveSq)][prevMoveSq].first, @@ -1119,7 +1126,7 @@ split_point_start: // At split points actual search starts from here Key posKey; Move ttMove, move, bestMove; Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha; - bool givesCheck, enoughMaterial, evasionPrunable; + bool givesCheck, evasionPrunable; Depth ttDepth; // To flag BOUND_EXACT a node with eval above alpha and no available moves @@ -1161,7 +1168,6 @@ split_point_start: // At split points actual search starts from here { ss->staticEval = ss->evalMargin = VALUE_NONE; bestValue = futilityBase = -VALUE_INFINITE; - enoughMaterial = false; } else { @@ -1189,7 +1195,6 @@ split_point_start: // At split points actual search starts from here alpha = bestValue; futilityBase = ss->staticEval + ss->evalMargin + Value(128); - enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMg; } // Initialize a MovePicker object for the current position, and prepare @@ -1211,7 +1216,6 @@ split_point_start: // At split points actual search starts from here && !InCheck && !givesCheck && move != ttMove - && enoughMaterial && type_of(move) != PROMOTION && !pos.is_passed_pawn_push(move)) { @@ -1236,8 +1240,7 @@ split_point_start: // At split points actual search starts from here } // Detect non-capture evasions that are candidate to be pruned - evasionPrunable = !PvNode - && InCheck + evasionPrunable = InCheck && bestValue > VALUE_MATED_IN_MAX_PLY && !pos.is_capture(move) && !pos.can_castle(pos.side_to_move()); @@ -1373,6 +1376,47 @@ split_point_start: // At split points actual search starts from here } + // allows() tests whether the 'first' move at previous ply somehow makes the + // 'second' move possible, for instance if the moving piece is the same in + // both moves. Normally the second move is the threat (the best move returned + // from a null search that fails low). + + bool allows(const Position& pos, Move first, Move second) { + + 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 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 second's destination was vacated by the first move + if (m1to == m2from || m2to == m1from) + return true; + + // Second one moves through the square vacated by first one + if (between_bb(m2from, m2to) & m1from) + return true; + + // 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; + + // Second move gives a discovered check through the first's checking piece + if (m1att & pos.king_square(pos.side_to_move())) + { + assert(between_bb(m1to, pos.king_square(pos.side_to_move())) & m2from); + return true; + } + + return false; + } + + // refutes() tests whether a 'first' move is able to defend against a 'second' // opponent's move. In this case will not be pruned. Normally the second move // is the threat (the best move returned from a null search that fails low). @@ -1410,7 +1454,7 @@ split_point_start: // At split points actual search starts from here | (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)))) + if (unlikely(xray) && (xray & ~pos.attacks_from(m2to))) return true; } @@ -1621,6 +1665,7 @@ void Thread::idle_loop() { Threads.mutex.lock(); assert(searching); + assert(activeSplitPoint); SplitPoint* sp = activeSplitPoint; Threads.mutex.unlock(); @@ -1628,7 +1673,7 @@ void Thread::idle_loop() { Stack stack[MAX_PLY_PLUS_2], *ss = stack+1; // To allow referencing (ss-1) Position pos(*sp->pos, this); - memcpy(ss-1, sp->ss-1, 4 * sizeof(Stack)); + std::memcpy(ss-1, sp->ss-1, 4 * sizeof(Stack)); ss->splitPoint = sp; sp->mutex.lock();