X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=fa544a1754ae4cb0f6b39ac5157d8afc59091985;hp=7699a74658acbab8207b9b66172696f816f05354;hb=bc0c1c8d7b1ef10bb917f3da8b5ba272ee6401fc;hpb=adb43cc0cca109c1d95fa8032e717762faa01563 diff --git a/src/search.cpp b/src/search.cpp index 7699a746..fa544a17 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -98,7 +98,6 @@ namespace { int ActiveThreads; volatile bool AllThreadsShouldExit, AllThreadsShouldSleep; Thread threads[MAX_THREADS]; - SplitPoint SplitPointStack[MAX_THREADS][ACTIVE_SPLIT_POINTS_MAX]; Lock MPLock, WaitLock; @@ -214,7 +213,7 @@ namespace { int32_t FutilityMarginsMatrix[16][64]; // [depth][moveNumber] int FutilityMoveCountArray[32]; // [depth] - inline Value futility_margin(Depth d, int mn) { return Value(d < 7 * OnePly ? FutilityMarginsMatrix[Max(d, 0)][Min(mn, 63)] : 2 * VALUE_INFINITE); } + inline Value futility_margin(Depth d, int mn) { return Value(d < 7 * OnePly ? FutilityMarginsMatrix[Max(d, 1)][Min(mn, 63)] : 2 * VALUE_INFINITE); } inline int futility_move_count(Depth d) { return d < 16 * OnePly ? FutilityMoveCountArray[d] : 512; } // Step 14. Reduced search @@ -234,12 +233,6 @@ namespace { // better than the second best move. const Value EasyMoveMargin = Value(0x200); - // Last seconds noise filtering (LSN) - const bool UseLSNFiltering = false; - const int LSNTime = 100; // In milliseconds - const Value LSNValue = value_from_centipawns(200); - bool loseOnTime = false; - /// Global variables @@ -296,10 +289,10 @@ namespace { template Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous); - void update_pv(SearchStack* ss); - void sp_update_pv(SearchStack* pss, SearchStack* ss); bool connected_moves(const Position& pos, Move m1, Move m2); bool value_is_mate(Value value); + Value value_to_tt(Value v, int ply); + Value value_from_tt(Value v, int ply); bool move_is_killer(Move m, SearchStack* ss); bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply); bool connected_threat(const Position& pos, Move m, Move threat); @@ -309,12 +302,13 @@ namespace { void update_gains(const Position& pos, Move move, Value before, Value after); int current_search_time(); + std::string value_to_uci(Value v); int nps(); void poll(); void ponderhit(); void wait_for_stop_or_ponderhit(); void init_ss_array(SearchStack* ss, int size); - void print_pv_info(const Position& pos, Move* ss, Value alpha, Value beta, Value value); + void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value); #if !defined(_MSC_VER) void *init_thread(void *threadID); @@ -355,7 +349,7 @@ void init_search() { } // Init futility margins array - for (d = 0; d < 16; d++) for (mc = 0; mc < 64; mc++) + for (d = 1; d < 16; d++) for (mc = 0; mc < 64; mc++) FutilityMarginsMatrix[d][mc] = 112 * int(log(double(d * d) / 2) / log(2.0) + 1.001) - 8 * mc + 45; // Init futility move count array @@ -451,10 +445,6 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, } } - // Reset loseOnTime flag at the beginning of a new game - if (button_was_pressed("New Game")) - loseOnTime = false; - // Read UCI option values TT.set_size(get_option_value_int("Hash")); if (button_was_pressed("Clear Hash")) @@ -554,36 +544,8 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, << " increment: " << myIncrement << " moves to go: " << movesToGo << endl; - // LSN filtering. Used only for developing purposes, disabled by default - if ( UseLSNFiltering - && loseOnTime) - { - // Step 2. If after last move we decided to lose on time, do it now! - while (SearchStartTime + myTime + 1000 > get_system_time()) - /* wait here */; - } - // We're ready to start thinking. Call the iterative deepening loop function - Value v = id_loop(pos, searchMoves); - - if (UseLSNFiltering) - { - // Step 1. If this is sudden death game and our position is hopeless, - // decide to lose on time. - if ( !loseOnTime // If we already lost on time, go to step 3. - && myTime < LSNTime - && myIncrement == 0 - && movesToGo == 0 - && v < -LSNValue) - { - loseOnTime = true; - } - else if (loseOnTime) - { - // Step 3. Now after stepping over the time limit, reset flag for next match. - loseOnTime = false; - } - } + id_loop(pos, searchMoves); if (UseLogFile) LogFile.close(); @@ -625,7 +587,7 @@ namespace { // so to output information also for iteration 1. cout << "info depth " << 1 << "\ninfo depth " << 1 - << " score " << value_to_string(rml.get_move_score(0)) + << " score " << value_to_uci(rml.get_move_score(0)) << " time " << current_search_time() << " nodes " << TM.nodes_searched() << " nps " << nps() @@ -741,8 +703,7 @@ namespace { // Print final search statistics cout << "info nodes " << TM.nodes_searched() << " nps " << nps() - << " time " << current_search_time() - << " hashfull " << TT.full() << endl; + << " time " << current_search_time() << endl; // Print the best move and the ponder move to the standard output if (pv[0] == MOVE_NONE) @@ -937,9 +898,8 @@ namespace { // We are failing high and going to do a research. It's important to update // the score before research in case we run out of time while researching. rml.set_move_score(i, value); - update_pv(ss); - pv[0] = ss->bestMove; - TT.extract_pv(pos, pv, PLY_MAX); + ss->bestMove = move; + TT.extract_pv(pos, move, pv, PLY_MAX); rml.set_move_pv(i, pv); // Print information to the standard output @@ -978,9 +938,8 @@ namespace { // Update PV rml.set_move_score(i, value); - update_pv(ss); - pv[0] = ss->bestMove; - TT.extract_pv(pos, pv, PLY_MAX); + ss->bestMove = move; + TT.extract_pv(pos, move, pv, PLY_MAX); rml.set_move_pv(i, pv); if (MultiPV == 1) @@ -1004,7 +963,7 @@ namespace { for (int j = 0; j < Min(MultiPV, rml.move_count()); j++) { cout << "info multipv " << j + 1 - << " score " << value_to_string(rml.get_move_score(j)) + << " score " << value_to_uci(rml.get_move_score(j)) << " depth " << (j <= i ? Iteration : Iteration - 1) << " time " << current_search_time() << " nodes " << TM.nodes_searched() @@ -1065,7 +1024,7 @@ namespace { Depth ext, newDepth; Value bestValue, value, oldAlpha; Value refinedValue, nullValue, futilityValueScaled; // Non-PV specific - bool isCheck, singleEvasion, moveIsCheck, captureOrPromotion, dangerous; + bool isCheck, singleEvasion, singularExtensionNode, moveIsCheck, captureOrPromotion, dangerous; bool mateThreat = false; int moveCount = 0; int threadID = pos.thread(); @@ -1209,12 +1168,12 @@ namespace { if (nullValue >= value_mate_in(PLY_MAX)) nullValue = beta; - // Do zugzwang verification search at high depths if (depth < 6 * OnePly) return nullValue; + // Do verification search at high depths ss->skipNullMove = true; - Value v = search(pos, ss, alpha, beta, depth-5*OnePly, ply); + Value v = search(pos, ss, alpha, beta, depth-R*OnePly, ply); ss->skipNullMove = false; if (v >= beta) @@ -1261,11 +1220,12 @@ namespace { // Initialize a MovePicker object for the current position MovePicker mp = MovePicker(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta)); CheckInfo ci(pos); - bool singularExtensionNode = depth >= SingularExtensionDepth[PvNode] - && tte && tte->move() - && !excludedMove // Do not allow recursive singular extension search - && is_lower_bound(tte->type()) - && tte->depth() >= depth - 3 * OnePly; + singleEvasion = isCheck && mp.number_of_evasions() == 1; + singularExtensionNode = depth >= SingularExtensionDepth[PvNode] + && tte && tte->move() + && !excludedMove // Do not allow recursive singular extension search + && is_lower_bound(tte->type()) + && tte->depth() >= depth - 3 * OnePly; // Step 10. Loop through moves // Loop through all legal moves until no moves remain or a beta cutoff occurs @@ -1278,16 +1238,16 @@ namespace { if (move == excludedMove) continue; - singleEvasion = (isCheck && mp.number_of_evasions() == 1); moveIsCheck = pos.move_is_check(move, ci); captureOrPromotion = pos.move_is_capture_or_promotion(move); // Step 11. Decide the new search depth ext = extension(pos, move, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous); - // Singular extension search. We extend the TT move if its value is much better than - // its siblings. To verify this we do a reduced search on all the other moves but the - // ttMove, if result is lower then ttValue minus a margin then we extend ttMove. + // Singular extension search. If all moves but one fail low on a search of (alpha-s, beta-s), + // and just one fails high on (alpha, beta), then that move is singular and should be extended. + // To verify this we do a reduced search on all the other moves but the ttMove, if result is + // lower then ttValue minus a margin then we extend ttMove. if ( singularExtensionNode && move == tte->move() && ext < OnePly) @@ -1302,7 +1262,7 @@ namespace { Value v = search(pos, ss, b - 1, b, depth / 2, ply); ss->skipNullMove = false; ss->excludedMove = MOVE_NONE; - if (v < ttValue - SingularExtensionMargin) + if (v < b) ext = OnePly; } } @@ -1414,10 +1374,10 @@ namespace { if (PvNode && value < beta) // This guarantees that always: alpha < beta alpha = value; - update_pv(ss); - if (value == value_mate_in(ply + 1)) ss->mateKiller = move; + + ss->bestMove = move; } } @@ -1617,7 +1577,7 @@ namespace { if (value > alpha) { alpha = value; - update_pv(ss); + ss->bestMove = move; } } } @@ -1798,7 +1758,7 @@ namespace { if (PvNode && value < sp->beta) // This guarantees that always: sp->alpha < sp->beta sp->alpha = value; - sp_update_pv(sp->parentSstack, ss); + sp->parentSstack->bestMove = ss->bestMove = move; } } } @@ -1810,25 +1770,6 @@ namespace { lock_release(&(sp->lock)); } - // update_pv() is called whenever a search returns a value > alpha. - // It updates the PV in the SearchStack object corresponding to the - // current node. - - void update_pv(SearchStack* ss) { - - ss->bestMove = ss->currentMove; - } - - - // sp_update_pv() is a variant of update_pv for use at split points. The - // difference between the two functions is that sp_update_pv also updates - // the PV at the parent node. - - void sp_update_pv(SearchStack* pss, SearchStack* ss) { - - pss->bestMove = ss->bestMove = ss->currentMove; - } - // connected_moves() tests whether two moves are 'connected' in the sense // that the first move somehow made the second move possible (for instance @@ -1886,8 +1827,8 @@ namespace { } - // value_is_mate() checks if the given value is a mate one - // eventually compensated for the ply. + // value_is_mate() checks if the given value is a mate one eventually + // compensated for the ply. bool value_is_mate(Value value) { @@ -1898,8 +1839,38 @@ namespace { } - // move_is_killer() checks if the given move is among the - // killer moves of that ply. + // value_to_tt() adjusts a mate score from "plies to mate from the root" to + // "plies to mate from the current ply". 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) { + + if (v >= value_mate_in(PLY_MAX)) + return v + ply; + + if (v <= value_mated_in(PLY_MAX)) + return v - ply; + + return v; + } + + + // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score from + // the transposition table to a mate score corrected for the current ply. + + Value value_from_tt(Value v, int ply) { + + if (v >= value_mate_in(PLY_MAX)) + return v - ply; + + if (v <= value_mated_in(PLY_MAX)) + return v + ply; + + return v; + } + + + // move_is_killer() checks if the given move is among the killer moves bool move_is_killer(Move m, SearchStack* ss) { @@ -2114,6 +2085,20 @@ namespace { } + // value_to_uci() converts a value to a string suitable for use with the UCI protocol + + std::string value_to_uci(Value v) { + + std::stringstream s; + + if (abs(v) < VALUE_MATE - PLY_MAX * OnePly) + s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to pawn = 100 + else + s << "mate " << (v > 0 ? (VALUE_MATE - v + 1) / 2 : -(VALUE_MATE + v) / 2 ); + + return s.str(); + } + // nps() computes the current nodes/second count. int nps() { @@ -2177,7 +2162,7 @@ namespace { dbg_print_hit_rate(); cout << "info nodes " << TM.nodes_searched() << " nps " << nps() - << " time " << t << " hashfull " << TT.full() << endl; + << " time " << t << endl; } // Should we stop the search? @@ -2268,29 +2253,28 @@ namespace { // print_pv_info() prints to standard output and eventually to log file information on // the current PV line. It is called at each iteration or after a new pv is found. - void print_pv_info(const Position& pos, Move* pv, Value alpha, Value beta, Value value) { + void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value) { cout << "info depth " << Iteration - << " score " << value_to_string(value) - << ((value >= beta) ? " lowerbound" : - ((value <= alpha)? " upperbound" : "")) + << " score " << value_to_uci(value) + << (value >= beta ? " lowerbound" : value <= alpha ? " upperbound" : "") << " time " << current_search_time() << " nodes " << TM.nodes_searched() << " nps " << nps() << " pv "; - for (int j = 0; pv[j] != MOVE_NONE && j < PLY_MAX; j++) - cout << pv[j] << " "; + for (Move* m = pv; *m != MOVE_NONE; m++) + cout << *m << " "; cout << endl; if (UseLogFile) { - ValueType type = (value >= beta ? VALUE_TYPE_LOWER - : (value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT)); + ValueType t = value >= beta ? VALUE_TYPE_LOWER : + value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT; LogFile << pretty_pv(pos, current_search_time(), Iteration, - TM.nodes_searched(), value, type, pv) << endl; + TM.nodes_searched(), value, t, pv) << endl; } } @@ -2460,10 +2444,10 @@ namespace { SitIdleEvent[i] = CreateEvent(0, FALSE, FALSE, 0); #endif - // Initialize SplitPointStack locks + // Initialize splitPoints[] locks for (i = 0; i < MAX_THREADS; i++) - for (int j = 0; j < ACTIVE_SPLIT_POINTS_MAX; j++) - lock_init(&(SplitPointStack[i][j].lock), NULL); + for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++) + lock_init(&(threads[i].splitPoints[j].lock), NULL); // Will be set just before program exits to properly end the threads AllThreadsShouldExit = false; @@ -2517,8 +2501,8 @@ namespace { // Now we can safely destroy the locks for (int i = 0; i < MAX_THREADS; i++) - for (int j = 0; j < ACTIVE_SPLIT_POINTS_MAX; j++) - lock_destroy(&(SplitPointStack[i][j].lock)); + for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++) + lock_destroy(&(threads[i].splitPoints[j].lock)); lock_destroy(&WaitLock); lock_destroy(&MPLock); @@ -2571,7 +2555,7 @@ namespace { // Apply the "helpful master" concept if possible. Use localActiveSplitPoints // that is known to be > 0, instead of threads[slave].activeSplitPoints that // could have been set to 0 by another thread leading to an out of bound access. - if (SplitPointStack[slave][localActiveSplitPoints - 1].slaves[master]) + if (threads[slave].splitPoints[localActiveSplitPoints - 1].slaves[master]) return true; return false; @@ -2618,54 +2602,54 @@ namespace { assert(p.thread() >= 0 && p.thread() < ActiveThreads); assert(ActiveThreads > 1); - int master = p.thread(); + int i, master = p.thread(); + Thread& masterThread = threads[master]; lock_grab(&MPLock); // If no other thread is available to help us, or if we have too many // active split points, don't split. if ( !available_thread_exists(master) - || threads[master].activeSplitPoints >= ACTIVE_SPLIT_POINTS_MAX) + || masterThread.activeSplitPoints >= MAX_ACTIVE_SPLIT_POINTS) { lock_release(&MPLock); return; } // Pick the next available split point object from the split point stack - SplitPoint* splitPoint = &SplitPointStack[master][threads[master].activeSplitPoints]; + SplitPoint& splitPoint = masterThread.splitPoints[masterThread.activeSplitPoints++]; // Initialize the split point object - splitPoint->parent = threads[master].splitPoint; - splitPoint->stopRequest = false; - splitPoint->ply = ply; - splitPoint->depth = depth; - splitPoint->mateThreat = mateThreat; - splitPoint->alpha = *alpha; - splitPoint->beta = beta; - splitPoint->pvNode = pvNode; - splitPoint->bestValue = *bestValue; - splitPoint->mp = mp; - splitPoint->moveCount = *moveCount; - splitPoint->pos = &p; - splitPoint->parentSstack = ss; - for (int i = 0; i < ActiveThreads; i++) - splitPoint->slaves[i] = 0; - - threads[master].splitPoint = splitPoint; - threads[master].activeSplitPoints++; + splitPoint.parent = masterThread.splitPoint; + splitPoint.stopRequest = false; + splitPoint.ply = ply; + splitPoint.depth = depth; + splitPoint.mateThreat = mateThreat; + splitPoint.alpha = *alpha; + splitPoint.beta = beta; + splitPoint.pvNode = pvNode; + splitPoint.bestValue = *bestValue; + splitPoint.mp = mp; + splitPoint.moveCount = *moveCount; + splitPoint.pos = &p; + splitPoint.parentSstack = ss; + for (i = 0; i < ActiveThreads; i++) + splitPoint.slaves[i] = 0; + + masterThread.splitPoint = &splitPoint; // If we are here it means we are not available - assert(threads[master].state != THREAD_AVAILABLE); + assert(masterThread.state != THREAD_AVAILABLE); int workersCnt = 1; // At least the master is included // Allocate available threads setting state to THREAD_BOOKED - for (int i = 0; !Fake && i < ActiveThreads && workersCnt < MaxThreadsPerSplitPoint; i++) + for (i = 0; !Fake && i < ActiveThreads && workersCnt < MaxThreadsPerSplitPoint; i++) if (thread_is_available(i, master)) { threads[i].state = THREAD_BOOKED; - threads[i].splitPoint = splitPoint; - splitPoint->slaves[i] = 1; + threads[i].splitPoint = &splitPoint; + splitPoint.slaves[i] = 1; workersCnt++; } @@ -2676,10 +2660,10 @@ namespace { // Tell the threads that they have work to do. This will make them leave // their idle loop. But before copy search stack tail for each thread. - for (int i = 0; i < ActiveThreads; i++) - if (i == master || splitPoint->slaves[i]) + for (i = 0; i < ActiveThreads; i++) + if (i == master || splitPoint.slaves[i]) { - memcpy(splitPoint->sstack[i], ss - 1, 4 * sizeof(SearchStack)); + memcpy(splitPoint.sstack[i], ss - 1, 4 * sizeof(SearchStack)); assert(i == master || threads[i].state == THREAD_BOOKED); @@ -2691,16 +2675,16 @@ namespace { // THREAD_WORKISWAITING. We send the split point as a second parameter to the // idle loop, which means that the main thread will return from the idle // loop when all threads have finished their work at this split point. - idle_loop(master, splitPoint); + idle_loop(master, &splitPoint); // We have returned from the idle loop, which means that all threads are // finished. Update alpha and bestValue, and return. lock_grab(&MPLock); - *alpha = splitPoint->alpha; - *bestValue = splitPoint->bestValue; - threads[master].activeSplitPoints--; - threads[master].splitPoint = splitPoint->parent; + *alpha = splitPoint.alpha; + *bestValue = splitPoint.bestValue; + masterThread.activeSplitPoints--; + masterThread.splitPoint = splitPoint.parent; lock_release(&MPLock); }