X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=7249a113862f87ebe8cd6563f0bb3fa08e937ddb;hp=7699a74658acbab8207b9b66172696f816f05354;hb=1322ab97c737fe761bd6ae8786f852851b8f019f;hpb=adb43cc0cca109c1d95fa8032e717762faa01563 diff --git a/src/search.cpp b/src/search.cpp index 7699a746..7249a113 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); @@ -348,14 +342,14 @@ void init_search() { // Init reductions array for (hd = 1; hd < 64; hd++) for (mc = 1; mc < 64; mc++) { - double pvRed = log(double(hd)) * log(double(mc)) / 3.0; - double nonPVRed = log(double(hd)) * log(double(mc)) / 1.5; + double pvRed = 0.33 + log(double(hd)) * log(double(mc)) / 4.5; + double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25; ReductionMatrix[PV][hd][mc] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(OnePly)) : 0); ReductionMatrix[NonPV][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(OnePly)) : 0); } // 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 @@ -370,7 +364,6 @@ void SearchStack::init() { currentMove = threatMove = bestMove = MOVE_NONE; reduction = Depth(0); - eval = VALUE_NONE; } // SearchStack::initKillers() initializes killers for a search stack entry @@ -417,9 +410,8 @@ int perft(Position& pos, Depth depth) /// search-related global variables, and calls root_search(). It returns false /// when a quit command is received during the search. -bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, - int time[], int increment[], int movesToGo, int maxDepth, - int maxNodes, int maxTime, Move searchMoves[]) { +bool think(const Position& pos, bool infinite, bool ponder, int time[], int increment[], + int movesToGo, int maxDepth, int maxNodes, int maxTime, Move searchMoves[]) { // Initialize global search variables StopOnPonderhit = AbortSearch = Quit = AspirationFailLow = false; @@ -451,10 +443,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")) @@ -496,8 +484,8 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, TM.wake_sleeping_threads(); // Set thinking time - int myTime = time[side_to_move]; - int myIncrement = increment[side_to_move]; + int myTime = time[pos.side_to_move()]; + int myIncrement = increment[pos.side_to_move()]; if (UseTimeManagement) { if (!movesToGo) // Sudden death time control @@ -554,36 +542,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 +585,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 +701,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) @@ -811,8 +770,7 @@ namespace { // Step 5. Evaluate the position statically // At root we do this only to get reference value for child nodes - if (!isCheck) - ss->eval = evaluate(pos, ei); + ss->eval = isCheck ? VALUE_NONE : evaluate(pos, ei); // Step 6. Razoring (omitted at root) // Step 7. Static null move pruning (omitted at root) @@ -937,9 +895,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 +935,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 +960,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 +1021,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(); @@ -1139,6 +1095,8 @@ namespace { refinedValue = refine_eval(tte, ss->eval, ply); // Enhance accuracy with TT value if possible update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval); } + else + ss->eval = VALUE_NONE; // Step 6. Razoring (is omitted in PV nodes) if ( !PvNode @@ -1209,12 +1167,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 +1219,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 +1237,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 +1261,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 +1373,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; } } @@ -1491,7 +1450,6 @@ namespace { TM.incrementNodeCounter(pos.thread()); ss->bestMove = ss->currentMove = MOVE_NONE; - ss->eval = VALUE_NONE; // Check for an instant draw or maximum ply reached if (pos.is_draw() || ply >= PLY_MAX - 1) @@ -1514,6 +1472,7 @@ namespace { if (isCheck) { bestValue = futilityBase = -VALUE_INFINITE; + ss->eval = VALUE_NONE; deepChecks = enoughMaterial = false; } else @@ -1617,7 +1576,7 @@ namespace { if (value > alpha) { alpha = value; - update_pv(ss); + ss->bestMove = move; } } } @@ -1798,7 +1757,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 +1769,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 +1826,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 +1838,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 +2084,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 +2161,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 +2252,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 +2443,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 +2500,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 +2554,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 +2601,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 +2659,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 +2674,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); } @@ -2770,6 +2753,8 @@ namespace { // Find a quick score for the move init_ss_array(ss, PLY_MAX_PLUS_2); + ss[0].eval = VALUE_NONE; + ss[0].currentMove = cur->move; pos.do_move(cur->move, st); moves[count].move = cur->move; moves[count].score = -qsearch(pos, ss+1, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1);