X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=f981664dbb9255fd2efb75c7ef13b11e3d90e112;hp=a052ea18f8828d3c56c8dc8cee94c0cde34bcbcc;hb=7bcd97933a20b649964bf96eb840a6190e777428;hpb=3c31776a20370cad008e1d4b0203c7b02b1b8ec6 diff --git a/src/search.cpp b/src/search.cpp index a052ea18..f981664d 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -72,7 +72,6 @@ namespace { void set_active_threads(int newActiveThreads) { ActiveThreads = newActiveThreads; } void incrementNodeCounter(int threadID) { threads[threadID].nodes++; } void incrementBetaCounter(Color us, Depth d, int threadID) { threads[threadID].betaCutOffs[us] += unsigned(d); } - void print_current_line(SearchStack ss[], int ply, int threadID); void resetNodeCounters(); void resetBetaCounters(); @@ -85,17 +84,17 @@ 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, - const Value futilityValue, Depth depth, int* moves, MovePicker* mp, int master, bool pvNode); + Depth depth, int* moves, MovePicker* mp, int master, bool pvNode); private: - friend void poll(); + friend void poll(SearchStack ss[], int ply); int ActiveThreads; volatile bool AllThreadsShouldExit, AllThreadsShouldSleep; Thread threads[MAX_THREADS]; SplitPoint SplitPointStack[MAX_THREADS][ACTIVE_SPLIT_POINTS_MAX]; - Lock MPLock, IOLock; + Lock MPLock; #if !defined(_MSC_VER) pthread_cond_t WaitCond; @@ -288,7 +287,7 @@ namespace { int current_search_time(); int nps(); - void poll(); + void poll(SearchStack ss[], int ply); void ponderhit(); void wait_for_stop_or_ponderhit(); void init_ss_array(SearchStack ss[]); @@ -1219,7 +1218,7 @@ namespace { && TM.available_thread_exists(threadID) && !AbortSearch && !TM.thread_should_stop(threadID) - && TM.split(pos, ss, ply, &alpha, beta, &bestValue, VALUE_NONE, + && TM.split(pos, ss, ply, &alpha, beta, &bestValue, depth, &moveCount, &mp, threadID, true)) break; } @@ -1272,11 +1271,11 @@ namespace { const TTEntry* tte; Move ttMove, move; Depth ext, newDepth; - Value bestValue, staticValue, nullValue, value, futilityValue, futilityValueScaled; + Value bestValue, refinedValue, nullValue, value, futilityValueScaled; bool isCheck, singleEvasion, moveIsCheck, captureOrPromotion, dangerous; bool mateThreat = false; int moveCount = 0; - futilityValue = staticValue = bestValue = value = -VALUE_INFINITE; + refinedValue = bestValue = value = -VALUE_INFINITE; if (depth < OnePly) return qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID); @@ -1302,7 +1301,7 @@ namespace { // Step 4. Transposition table lookup // We don't want the score of a partial search to overwrite a previous full search - // TT value, so we use a different position key in case of an excluded move exsists. + // TT value, so we use a different position key in case of an excluded move exists. Key posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key(); tte = TT.retrieve(posKey); @@ -1320,13 +1319,11 @@ namespace { if (!isCheck) { if (tte && (tte->type() & VALUE_TYPE_EVAL)) - staticValue = value_from_tt(tte->value(), ply); + ss[ply].eval = value_from_tt(tte->value(), ply); else - staticValue = evaluate(pos, ei, threadID); + ss[ply].eval = evaluate(pos, ei, threadID); - ss[ply].eval = staticValue; - futilityValue = staticValue + futility_margin(depth, 0); //FIXME: Remove me, only for split - staticValue = refine_eval(tte, staticValue, ply); // Enhance accuracy with TT value if possible + refinedValue = refine_eval(tte, ss[ply].eval, ply); // Enhance accuracy with TT value if possible update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval); } @@ -1334,7 +1331,7 @@ namespace { if ( !value_is_mate(beta) && !isCheck && depth < RazorDepth - && staticValue < beta - (0x200 + 16 * depth) + && refinedValue < beta - (0x200 + 16 * depth) && ss[ply - 1].currentMove != MOVE_NULL && ttMove == MOVE_NONE && !pos.has_pawn_on_7th(pos.side_to_move())) @@ -1351,8 +1348,8 @@ namespace { if ( !isCheck && allowNullmove && depth < RazorDepth - && staticValue - futility_margin(depth, 0) >= beta) - return staticValue - futility_margin(depth, 0); + && refinedValue - futility_margin(depth, 0) >= beta) + return refinedValue - futility_margin(depth, 0); // Step 8. Null move search with verification search // When we jump directly to qsearch() we do a null move only if static value is @@ -1363,7 +1360,7 @@ namespace { && !isCheck && !value_is_mate(beta) && ok_to_do_nullmove(pos) - && staticValue >= beta - (depth >= 4 * OnePly ? NullMoveMargin : 0)) + && refinedValue >= beta - (depth >= 4 * OnePly ? NullMoveMargin : 0)) { ss[ply].currentMove = MOVE_NULL; @@ -1373,7 +1370,7 @@ namespace { int R = 3 + (depth >= 5 * OnePly ? depth / 8 : 0); // Null move dynamic reduction based on value - if (staticValue - beta > PawnValueMidgame) + if (refinedValue - beta > PawnValueMidgame) R++; nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID); @@ -1544,7 +1541,7 @@ namespace { && TM.available_thread_exists(threadID) && !AbortSearch && !TM.thread_should_stop(threadID) - && TM.split(pos, ss, ply, NULL, beta, &bestValue, futilityValue, //FIXME: SMP & futilityValue + && TM.split(pos, ss, ply, NULL, beta, &bestValue, depth, &moveCount, &mp, threadID, false)) break; } @@ -1790,15 +1787,17 @@ namespace { Position pos(*sp->pos); CheckInfo ci(pos); SearchStack* ss = sp->sstack[threadID]; + StateInfo st; Value value = -VALUE_INFINITE; Move move; int moveCount; bool isCheck = pos.is_check(); - bool useFutilityPruning = sp->depth < 7 * OnePly //FIXME: sync with search - && !isCheck; - while ( lock_grab_bool(&(sp->lock)) - && sp->bestValue < sp->beta + // Step 10. Loop through moves + // Loop through all legal moves until no moves remain or a beta cutoff occurs + lock_grab(&(sp->lock)); + + while ( sp->bestValue < sp->beta && !TM.thread_should_stop(threadID) && (move = sp->mp->get_next_move()) != MOVE_NONE) { @@ -1810,45 +1809,48 @@ namespace { bool moveIsCheck = pos.move_is_check(move, ci); bool captureOrPromotion = pos.move_is_capture_or_promotion(move); - ss[sp->ply].currentMove = move; - - // Decide the new search depth + // Step 11. Decide the new search depth bool dangerous; Depth ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, false, false, &dangerous); Depth newDepth = sp->depth - OnePly + ext; - // Prune? - if ( useFutilityPruning + // Update current move + ss[sp->ply].currentMove = move; + + // Step 12. Futility pruning + if ( !isCheck && !dangerous - && !captureOrPromotion) + && !captureOrPromotion + && !move_is_castle(move)) { // Move count based pruning if ( moveCount >= futility_move_count(sp->depth) && ok_to_prune(pos, move, ss[sp->ply].threatMove) && sp->bestValue > value_mated_in(PLY_MAX)) + { + lock_grab(&(sp->lock)); continue; + } // Value based pruning - Value futilityValueScaled = sp->futilityValue - moveCount * 8; //FIXME: sync with search + Depth predictedDepth = newDepth - nonpv_reduction(sp->depth, moveCount); + Value futilityValueScaled = ss[sp->ply].eval + futility_margin(predictedDepth, moveCount) + + H.gain(pos.piece_on(move_from(move)), move_to(move)) + 45; if (futilityValueScaled < sp->beta) { - if (futilityValueScaled > sp->bestValue) // Less then 1% of cases - { - lock_grab(&(sp->lock)); - if (futilityValueScaled > sp->bestValue) - sp->bestValue = futilityValueScaled; - lock_release(&(sp->lock)); - } + lock_grab(&(sp->lock)); + + if (futilityValueScaled > sp->bestValue) + sp->bestValue = futilityValueScaled; continue; } } - // Make and search the move. - StateInfo st; + // Step 13. Make the move pos.do_move(move, st, ci, moveIsCheck); - // Try to reduce non-pv search depth by one ply if move seems not problematic, + // Step 14. Reduced search // if the move fails high will be re-searched at full depth. bool doFullDepthSearch = true; @@ -1865,36 +1867,36 @@ namespace { } } - if (doFullDepthSearch) // Go with full depth non-pv search + // Step 15. Full depth search + if (doFullDepthSearch) { ss[sp->ply].reduction = Depth(0); value = -search(pos, ss, -(sp->beta - 1), newDepth, sp->ply+1, true, threadID); } + + // Step 16. Undo move pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - // New best move? - if (value > sp->bestValue) // Less then 2% of cases + // Step 17. Check for new best move + lock_grab(&(sp->lock)); + + if (value > sp->bestValue && !TM.thread_should_stop(threadID)) { - lock_grab(&(sp->lock)); - if (value > sp->bestValue && !TM.thread_should_stop(threadID)) + sp->bestValue = value; + if (sp->bestValue >= sp->beta) { - sp->bestValue = value; - if (sp->bestValue >= sp->beta) - { - sp->stopRequest = true; - sp_update_pv(sp->parentSstack, ss, sp->ply); - } + sp->stopRequest = true; + sp_update_pv(sp->parentSstack, ss, sp->ply); } - lock_release(&(sp->lock)); } } /* Here we have the lock still grabbed */ - sp->cpus--; sp->slaves[threadID] = 0; + sp->cpus--; lock_release(&(sp->lock)); } @@ -1916,12 +1918,16 @@ namespace { Position pos(*sp->pos); CheckInfo ci(pos); SearchStack* ss = sp->sstack[threadID]; + StateInfo st; Value value = -VALUE_INFINITE; int moveCount; Move move; - while ( lock_grab_bool(&(sp->lock)) - && sp->alpha < sp->beta + // Step 10. Loop through moves + // Loop through all legal moves until no moves remain or a beta cutoff occurs + lock_grab(&(sp->lock)); + + while ( sp->alpha < sp->beta && !TM.thread_should_stop(threadID) && (move = sp->mp->get_next_move()) != MOVE_NONE) { @@ -1933,18 +1939,20 @@ namespace { bool moveIsCheck = pos.move_is_check(move, ci); bool captureOrPromotion = pos.move_is_capture_or_promotion(move); - ss[sp->ply].currentMove = move; - - // Decide the new search depth + // Step 11. Decide the new search depth bool dangerous; Depth ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous); Depth newDepth = sp->depth - OnePly + ext; - // Make and search the move. - StateInfo st; + // Update current move + ss[sp->ply].currentMove = move; + + // Step 12. Futility pruning (is omitted in PV nodes) + + // Step 13. Make the move pos.do_move(move, st, ci, moveIsCheck); - // Try to reduce non-pv search depth by one ply if move seems not problematic, + // Step 14. Reduced search // if the move fails high will be re-searched at full depth. bool doFullDepthSearch = true; @@ -1962,7 +1970,8 @@ namespace { } } - if (doFullDepthSearch) // Go with full depth non-pv search + // Step 15. Full depth search + if (doFullDepthSearch) { Value localAlpha = sp->alpha; ss[sp->ply].reduction = Depth(0); @@ -1977,38 +1986,37 @@ namespace { value = -search_pv(pos, ss, -sp->beta, -localAlpha, newDepth, sp->ply+1, threadID); } } + + // Step 16. Undo move pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - // New best move? - if (value > sp->bestValue) // Less then 2% of cases + // Step 17. Check for new best move + lock_grab(&(sp->lock)); + + if (value > sp->bestValue && !TM.thread_should_stop(threadID)) { - lock_grab(&(sp->lock)); - if (value > sp->bestValue && !TM.thread_should_stop(threadID)) + sp->bestValue = value; + if (value > sp->alpha) { - sp->bestValue = value; - if (value > sp->alpha) - { - // Ask threads to stop before to modify sp->alpha - if (value >= sp->beta) - sp->stopRequest = true; - - sp->alpha = value; - - sp_update_pv(sp->parentSstack, ss, sp->ply); - if (value == value_mate_in(sp->ply + 1)) - ss[sp->ply].mateKiller = move; - } + // Ask threads to stop before to modify sp->alpha + if (value >= sp->beta) + sp->stopRequest = true; + + sp->alpha = value; + + sp_update_pv(sp->parentSstack, ss, sp->ply); + if (value == value_mate_in(sp->ply + 1)) + ss[sp->ply].mateKiller = move; } - lock_release(&(sp->lock)); } } /* Here we have the lock still grabbed */ - sp->cpus--; sp->slaves[threadID] = 0; + sp->cpus--; lock_release(&(sp->lock)); } @@ -2032,13 +2040,12 @@ namespace { NodesSincePoll++; if (NodesSincePoll >= NodesBetweenPolls) { - poll(); + poll(ss, ply); NodesSincePoll = 0; } } ss[ply].init(ply); ss[ply + 2].initKillers(); - TM.print_current_line(ss, ply, threadID); } @@ -2396,7 +2403,7 @@ namespace { // looks at the time consumed so far and decides if it's time to abort the // search. - void poll() { + void poll(SearchStack ss[], int ply) { static int lastInfoTime; int t = current_search_time(); @@ -2438,7 +2445,6 @@ namespace { else if (t - lastInfoTime >= 1000) { lastInfoTime = t; - lock_grab(&TM.IOLock); if (dbg_show_mean) dbg_print_mean(); @@ -2449,10 +2455,15 @@ namespace { cout << "info nodes " << TM.nodes_searched() << " nps " << nps() << " time " << t << " hashfull " << TT.full() << endl; - lock_release(&TM.IOLock); + // We only support current line printing in single thread mode + if (ShowCurrentLine && TM.active_threads() == 1) + { + cout << "info currline"; + for (int p = 0; p < ply; p++) + cout << " " << ss[p].currentMove; - if (ShowCurrentLine) - TM.threads[0].printCurrentLineRequest = true; + cout << endl; + } } // Should we stop the search? @@ -2681,7 +2692,6 @@ namespace { // Initialize global locks lock_init(&MPLock, NULL); - lock_init(&IOLock, NULL); // Initialize SplitPointStack locks for (i = 0; i < MAX_THREADS; i++) @@ -2839,7 +2849,7 @@ namespace { // splitPoint->cpus becomes 0), split() returns true. bool ThreadsManager::split(const Position& p, SearchStack* sstck, int ply, - Value* alpha, const Value beta, Value* bestValue, const Value futilityValue, + Value* alpha, const Value beta, Value* bestValue, Depth depth, int* moves, MovePicker* mp, int master, bool pvNode) { assert(p.is_ok()); @@ -2879,7 +2889,6 @@ namespace { splitPoint->beta = beta; splitPoint->pvNode = pvNode; splitPoint->bestValue = *bestValue; - splitPoint->futilityValue = futilityValue; splitPoint->master = master; splitPoint->mp = mp; splitPoint->moves = *moves; @@ -2984,47 +2993,8 @@ namespace { // This makes the threads to go to sleep AllThreadsShouldSleep = true; - - // Reset flags to a known state. - for (int i = 1; i < ActiveThreads; i++) - { - // This flag can be in a random state - threads[i].printCurrentLineRequest = false; - } } - // print_current_line() prints _once_ the current line of search for a - // given thread and then setup the print request for the next thread. - // Called when the UCI option UCI_ShowCurrLine is 'true'. - - void ThreadsManager::print_current_line(SearchStack ss[], int ply, int threadID) { - - assert(ply >= 0 && ply < PLY_MAX); - assert(threadID >= 0 && threadID < ActiveThreads); - - if (!threads[threadID].printCurrentLineRequest) - return; - - // One shot only - threads[threadID].printCurrentLineRequest = false; - - if (threads[threadID].state == THREAD_SEARCHING) - { - lock_grab(&IOLock); - cout << "info currline " << (threadID + 1); - for (int p = 0; p < ply; p++) - cout << " " << ss[p].currentMove; - - cout << endl; - lock_release(&IOLock); - } - - // Setup print request for the next thread ID - if (threadID + 1 < ActiveThreads) - threads[threadID + 1].printCurrentLineRequest = true; - } - - /// The RootMoveList class // RootMoveList c'tor