X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=515787c1042da05329220c2737b866be0f3d2da2;hp=82ecd913f8ddfec988f58f638fd52247d9c9e7f1;hb=55f0d6377f7828fb43428ed643a99780053dd589;hpb=a303bde26c166abf6a14846f841694fa81d8d0a3 diff --git a/src/search.cpp b/src/search.cpp index 82ecd913..515787c1 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -84,7 +84,7 @@ namespace { void put_threads_to_sleep(); void idle_loop(int threadID, SplitPoint* waitSp); bool split(const Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue, - Depth depth, int* moves, MovePicker* mp, int master, bool pvNode); + Depth depth, bool mateThreat, int* moves, MovePicker* mp, int master, bool pvNode); private: friend void poll(SearchStack ss[], int ply); @@ -645,7 +645,6 @@ namespace { while (Iteration < PLY_MAX) { // Initialize iteration - rml.sort(); Iteration++; BestMoveChangesByIteration[Iteration] = 0; if (Iteration <= 5) @@ -666,7 +665,7 @@ namespace { beta = Min(ValueByIteration[Iteration - 1] + AspirationDelta, VALUE_INFINITE); } - // Search to the current depth + // Search to the current depth, rml is updated and sorted value = root_search(p, ss, rml, alpha, beta); // Write PV to transposition table, in case the relevant entries have @@ -733,8 +732,6 @@ namespace { break; } - rml.sort(); - // If we are pondering or in infinite search, we shouldn't print the // best move before we are told to do so. if (!AbortSearch && (PonderSearch || InfiniteSearch)) @@ -803,23 +800,34 @@ namespace { alpha = oldAlpha; isCheck = pos.is_check(); - // Evaluate the position statically - ss[0].eval = !isCheck ? evaluate(pos, ei, 0) : VALUE_NONE; + // Step 1. Initialize node and poll (omitted at root, but I can see no good reason for this, FIXME) + // Step 2. Check for aborted search (omitted at root, because we do not initialize root node) + // Step 3. Mate distance pruning (omitted at root) + // Step 4. Transposition table lookup (omitted at root) + + // Step 5. Evaluate the position statically + // At root we do this only to get reference value for child nodes + if (!isCheck) + ss[0].eval = evaluate(pos, ei, 0); + else + ss[0].eval = VALUE_NONE; // HACK because we do not initialize root node - while (1) // Fail low loop + // Step 6. Razoring (omitted at root) + // Step 7. Static null move pruning (omitted at root) + // Step 8. Null move search with verification search (omitted at root) + // Step 9. Internal iterative deepening (omitted at root) + + // Step extra. Fail low loop + // We start with small aspiration window and in case of fail low, we research + // with bigger window until we are not failing low anymore. + while (1) { - // Loop through all the moves in the root move list + // Sort the moves before to (re)search + rml.sort(); + + // Step 10. Loop through all moves in the root move list for (int i = 0; i < rml.move_count() && !AbortSearch; i++) { - if (alpha >= beta) - { - // We failed high, invalidate and skip next moves, leave node-counters - // and beta-counters as they are and quickly return, we will try to do - // a research at the next iteration with a bigger aspiration window. - rml.set_move_score(i, -VALUE_INFINITE); - continue; - } - // This is used by time management and starts from 1 RootMoveNumber = i + 1; @@ -837,21 +845,29 @@ namespace { cout << "info currmove " << move << " currmovenumber " << RootMoveNumber << endl; - // Decide search depth for this move moveIsCheck = pos.move_is_check(move); captureOrPromotion = pos.move_is_capture_or_promotion(move); + + // Step 11. Decide the new search depth depth = (Iteration - 2) * OnePly + InitialDepth; ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous); newDepth = depth + ext; - // Reset value before the search + // Step 12. Futility pruning (omitted at root) + + // Step extra. Fail high loop + // If move fails high, we research with bigger window until we are not failing + // high anymore. value = - VALUE_INFINITE; - while (1) // Fail high loop + while (1) { - // Make the move, and search it + // Step 13. Make the move pos.do_move(move, st, ci, moveIsCheck); + // Step extra. pv search + // We do pv search for first moves (i < MultiPV) + // and for fail high research (value > alpha) if (i < MultiPV || value > alpha) { // Aspiration window is disabled in multi-pv case @@ -863,11 +879,11 @@ namespace { } else { - // Try to reduce non-pv search depth by one ply if move seems not problematic, - // if the move fails high will be re-searched at full depth. + // Step 14. Reduced search + // if the move fails high will be re-searched at full depth bool doFullDepthSearch = true; - if ( depth >= 3 * OnePly // FIXME was newDepth + if ( depth >= 3 * OnePly && !dangerous && !captureOrPromotion && !move_is_castle(move)) @@ -881,6 +897,7 @@ namespace { } } + // Step 15. Full depth search if (doFullDepthSearch) { // Full depth non-pv search using alpha as upperbound @@ -894,6 +911,7 @@ namespace { } } + // Step 16. Undo move pos.undo_move(move); // Can we exit fail high loop ? @@ -925,7 +943,7 @@ namespace { break; // Remember beta-cutoff and searched nodes counts for this move. The - // info is used to sort the root moves at the next iteration. + // info is used to sort the root moves for the next iteration. int64_t our, their; TM.get_beta_counters(pos.side_to_move(), our, their); rml.set_beta_counters(i, our, their); @@ -933,6 +951,7 @@ namespace { assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE); + // Step 17. Check for new best move if (value <= alpha && i >= MultiPV) rml.set_move_score(i, -VALUE_INFINITE); else @@ -1002,6 +1021,9 @@ namespace { } // Fail low loop + // Sort the moves before to return + rml.sort(); + return alpha; } @@ -1197,7 +1219,7 @@ namespace { && !AbortSearch && !TM.thread_should_stop(threadID) && TM.split(pos, ss, ply, &alpha, beta, &bestValue, - depth, &moveCount, &mp, threadID, true)) + depth, mateThreat, &moveCount, &mp, threadID, true)) break; } @@ -1317,7 +1339,9 @@ namespace { Value rbeta = beta - razor_margin(depth); Value v = qsearch(pos, ss, rbeta-1, rbeta, Depth(0), ply, threadID); if (v < rbeta) - return v; //FIXME: Logically should be: return (v + razor_margin(depth)); + // Logically we should return (v + razor_margin(depth)), but + // surprisingly this did slightly weaker in tests. + return v; } // Step 7. Static null move pruning @@ -1522,7 +1546,7 @@ namespace { && !AbortSearch && !TM.thread_should_stop(threadID) && TM.split(pos, ss, ply, NULL, beta, &bestValue, - depth, &moveCount, &mp, threadID, false)) + depth, mateThreat, &moveCount, &mp, threadID, false)) break; } @@ -1758,7 +1782,6 @@ namespace { // splitting, we don't have to repeat all this work in sp_search(). We // also don't need to store anything to the hash table here: This is taken // care of after we return from the split point. - // FIXME: We are currently ignoring mateThreat flag here void sp_search(SplitPoint* sp, int threadID) { @@ -1795,7 +1818,7 @@ namespace { captureOrPromotion = pos.move_is_capture_or_promotion(move); // Step 11. Decide the new search depth - ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, false, false, &dangerous); + ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous); newDepth = sp->depth - OnePly + ext; // Update current move @@ -1893,7 +1916,6 @@ namespace { // don't have to repeat all this work in sp_search_pv(). We also don't // need to store anything to the hash table here: This is taken care of // after we return from the split point. - // FIXME: We are ignoring mateThreat flag! void sp_search_pv(SplitPoint* sp, int threadID) { @@ -1929,7 +1951,7 @@ namespace { captureOrPromotion = pos.move_is_capture_or_promotion(move); // Step 11. Decide the new search depth - ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous); + ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous); newDepth = sp->depth - OnePly + ext; // Update current move @@ -2870,7 +2892,7 @@ namespace { bool ThreadsManager::split(const Position& p, SearchStack* sstck, int ply, Value* alpha, const Value beta, Value* bestValue, - Depth depth, int* moves, MovePicker* mp, int master, bool pvNode) { + Depth depth, bool mateThreat, int* moves, MovePicker* mp, int master, bool pvNode) { assert(p.is_ok()); assert(sstck != NULL); @@ -2905,6 +2927,7 @@ namespace { splitPoint->stopRequest = false; splitPoint->ply = ply; splitPoint->depth = depth; + splitPoint->mateThreat = mateThreat; splitPoint->alpha = pvNode ? *alpha : beta - 1; splitPoint->beta = beta; splitPoint->pvNode = pvNode;