X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=38e445b343d13440803ddd1de84c5182f63d5e0e;hp=f5e1a00002b2fc1fc21035d3835c710632132ca7;hb=47f5560e2dccfad9aa64afc7a002ce049b7504d3;hpb=6ed409eceeb8caa81604c107b5ce0713b88bbae2 diff --git a/src/search.cpp b/src/search.cpp index f5e1a000..38e445b3 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -77,9 +77,11 @@ namespace { void init_threads(); void exit_threads(); - int active_threads() const { return ActiveThreads; } - void set_active_threads(int newActiveThreads) { ActiveThreads = newActiveThreads; } + int min_split_depth() const { return minimumSplitDepth; } + int active_threads() const { return activeThreads; } + void set_active_threads(int cnt) { activeThreads = cnt; } + void read_uci_options(); bool available_thread_exists(int master) const; bool thread_is_available(int slave, int master) const; bool thread_should_stop(int threadID) const; @@ -91,11 +93,14 @@ namespace { Depth depth, Move threatMove, bool mateThreat, int moveCount, MovePicker* mp, bool pvNode); private: - int ActiveThreads; - volatile bool AllThreadsShouldExit; + Depth minimumSplitDepth; + int maxThreadsPerSplitPoint; + bool useSleepingThreads; + int activeThreads; + volatile bool allThreadsShouldExit; Thread threads[MAX_THREADS]; - Lock MPLock, WaitLock; - WaitCondition WaitCond[MAX_THREADS]; + Lock mpLock, sleepLock[MAX_THREADS]; + WaitCondition sleepCond[MAX_THREADS]; }; @@ -260,9 +265,7 @@ namespace { bool UseLogFile; std::ofstream LogFile; - // Multi-threads related variables - Depth MinimumSplitDepth; - int MaxThreadsPerSplitPoint; + // Multi-threads manager object ThreadsManager ThreadsMgr; // Node counters, used only by thread[0] but try to keep in different cache @@ -294,6 +297,8 @@ namespace { template Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous); + bool check_is_useless(Position &pos, Move move, Value eval, Value futilityBase, Value beta, Value *bValue); + Bitboard attacks(const Piece P, const Square sq, const Bitboard occ); bool connected_moves(const Position& pos, Move m1, Move m2); bool value_is_mate(Value value); Value value_to_tt(Value v, int ply); @@ -347,7 +352,7 @@ void init_search() { // Init reductions array for (hd = 1; hd < 64; hd++) for (mc = 1; mc < 64; mc++) { - double pvRed = 0.33 + log(double(hd)) * log(double(mc)) / 4.5; + double pvRed = log(double(hd)) * log(double(mc)) / 3.0; double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25; ReductionMatrix[PV][hd][mc] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(ONE_PLY)) : 0); ReductionMatrix[NonPV][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(ONE_PLY)) : 0); @@ -450,11 +455,8 @@ bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[ PawnEndgameExtension[0] = Options["Pawn Endgame Extension (non-PV nodes)"].value(); MateThreatExtension[1] = Options["Mate Threat Extension (PV nodes)"].value(); MateThreatExtension[0] = Options["Mate Threat Extension (non-PV nodes)"].value(); - - MinimumSplitDepth = Options["Minimum Split Depth"].value() * ONE_PLY; - MaxThreadsPerSplitPoint = Options["Maximum Number of Threads per Split Point"].value(); - MultiPV = Options["MultiPV"].value(); - UseLogFile = Options["Use Search Log"].value(); + MultiPV = Options["MultiPV"].value(); + UseLogFile = Options["Use Search Log"].value(); if (UseLogFile) LogFile.open(Options["Search Log Filename"].value().c_str(), std::ios::out | std::ios::app); @@ -462,15 +464,11 @@ bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[ read_weights(pos.side_to_move()); // Set the number of active threads - int newActiveThreads = Options["Threads"].value(); - if (newActiveThreads != ThreadsMgr.active_threads()) - { - ThreadsMgr.set_active_threads(newActiveThreads); - init_eval(ThreadsMgr.active_threads()); - } + ThreadsMgr.read_uci_options(); + init_eval(ThreadsMgr.active_threads()); // Wake up needed threads - for (int i = 1; i < newActiveThreads; i++) + for (int i = 1; i < ThreadsMgr.active_threads(); i++) ThreadsMgr.wake_sleeping_thread(i); // Set thinking time @@ -1070,7 +1068,6 @@ namespace { && !isCheck && refinedValue < beta - razor_margin(depth) && ttMove == MOVE_NONE - && (ss-1)->currentMove != MOVE_NULL && !value_is_mate(beta) && !pos.has_pawn_on_7th(pos.side_to_move())) { @@ -1287,6 +1284,17 @@ split_point_start: // At split points actual search starts from here continue; } + + // Prune neg. see moves at low depths + if ( predictedDepth < 2 * ONE_PLY + && bestValue > value_mated_in(PLY_MAX) + && pos.see_sign(move) < 0) + { + if (SpNode) + lock_grab(&(sp->lock)); + + continue; + } } // Step 13. Make the move @@ -1391,7 +1399,7 @@ split_point_start: // At split points actual search starts from here // Step 18. Check for split if ( !SpNode - && depth >= MinimumSplitDepth + && depth >= ThreadsMgr.min_split_depth() && ThreadsMgr.active_threads() > 1 && bestValue < beta && ThreadsMgr.available_thread_exists(threadID) @@ -1442,7 +1450,6 @@ split_point_start: // At split points actual search starts from here return bestValue; } - // qsearch() is the quiescence search function, which is called by the main // search function when the remaining depth is zero (or, to be more precise, // less than ONE_PLY). @@ -1460,7 +1467,7 @@ split_point_start: // At split points actual search starts from here StateInfo st; Move ttMove, move; Value bestValue, value, evalMargin, futilityValue, futilityBase; - bool isCheck, deepChecks, enoughMaterial, moveIsCheck, evasionPrunable; + bool isCheck, enoughMaterial, moveIsCheck, evasionPrunable; const TTEntry* tte; Value oldAlpha = alpha; @@ -1470,25 +1477,32 @@ split_point_start: // At split points actual search starts from here if (pos.is_draw() || ply >= PLY_MAX - 1) return VALUE_DRAW; + // Decide whether or not to include checks + isCheck = pos.is_check(); + + Depth d; + if (isCheck || depth >= -ONE_PLY) + d = DEPTH_ZERO; + else + d = DEPTH_ZERO - ONE_PLY; + // Transposition table lookup. At PV nodes, we don't use the TT for // pruning, but only for move ordering. tte = TT.retrieve(pos.get_key()); ttMove = (tte ? tte->move() : MOVE_NONE); - if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply)) + if (!PvNode && tte && ok_to_use_TT(tte, d, beta, ply)) { ss->bestMove = ttMove; // Can be MOVE_NONE return value_from_tt(tte->value(), ply); } - isCheck = pos.is_check(); - // Evaluate the position statically if (isCheck) { bestValue = futilityBase = -VALUE_INFINITE; ss->eval = evalMargin = VALUE_NONE; - deepChecks = enoughMaterial = false; + enoughMaterial = false; } else { @@ -1516,9 +1530,6 @@ split_point_start: // At split points actual search starts from here if (PvNode && bestValue > alpha) alpha = bestValue; - // If we are near beta then try to get a cutoff pushing checks a bit further - deepChecks = (depth == -ONE_PLY && bestValue >= beta - PawnValueMidgame / 8); - // Futility pruning parameters, not needed when in check futilityBase = ss->eval + evalMargin + FutilityMarginQS; enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame; @@ -1528,7 +1539,7 @@ split_point_start: // At split points actual search starts from here // to search the moves. Because the depth is <= 0 here, only captures, // queen promotions and checks (only if depth == 0 or depth == -ONE_PLY // and we are near beta) will be generated. - MovePicker mp = MovePicker(pos, ttMove, deepChecks ? DEPTH_ZERO : depth, H); + MovePicker mp = MovePicker(pos, ttMove, d, H); CheckInfo ci(pos); // Loop through the moves until no moves remain or a beta cutoff occurs @@ -1574,6 +1585,16 @@ split_point_start: // At split points actual search starts from here && pos.see_sign(move) < 0) continue; + // Don't search useless checks + if ( !PvNode + && !isCheck + && moveIsCheck + && move != ttMove + && !pos.move_is_capture(move) + && !move_is_promotion(move) + && check_is_useless(pos, move, ss->eval, futilityBase, beta, &bestValue)) + continue; + // Update current move ss->currentMove = move; @@ -1602,7 +1623,6 @@ split_point_start: // At split points actual search starts from here return value_mated_in(ply); // Update transposition table - Depth d = (depth == DEPTH_ZERO ? DEPTH_ZERO : DEPTH_ZERO - ONE_PLY); ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT); TT.store(pos.get_key(), value_to_tt(bestValue, ply), vt, d, ss->bestMove, ss->eval, evalMargin); @@ -1611,6 +1631,94 @@ split_point_start: // At split points actual search starts from here return bestValue; } + // check_is_useless() tests if a checking move can be pruned in qsearch(). + // bestValue is updated when necesary. + + bool check_is_useless(Position &pos, Move move, Value eval, Value futilityBase, Value beta, Value *bValue) + { + Value bestValue = *bValue; + + /// Rule 1. Using checks to reposition pieces when close to beta + if (eval + PawnValueMidgame / 4 < beta) + { + if (eval + PawnValueMidgame / 4 > bestValue) + bestValue = eval + PawnValueMidgame / 4; + } + else + return false; + + Square from = move_from(move); + Square to = move_to(move); + Color oppColor = opposite_color(pos.side_to_move()); + Square oppKing = pos.king_square(oppColor); + + Bitboard occ = pos.occupied_squares() & ~(1ULL << from) & ~(1ULL <= beta && pos.see_sign(make_move(from, victimSq)) >= 0) + return false; + + if (futilityValue > bestValue) + bestValue = futilityValue; + } + + *bValue = bestValue; + return true; + } + + // attacks() returns attacked squares. + + Bitboard attacks(const Piece P, const Square sq, const Bitboard occ) + { + switch(P) + { + case WP: + case BP: + case WN: + case BN: + case WK: + case BK: + return StepAttackBB[P][sq]; + case WB: + case BB: + return bishop_attacks_bb(sq, occ); + case WR: + case BR: + return rook_attacks_bb(sq, occ); + case WQ: + case BQ: + return bishop_attacks_bb(sq, occ) | rook_attacks_bb(sq, occ); + default: + assert(false); + return 0ULL; + } + } // connected_moves() tests whether two moves are 'connected' in the sense // that the first move somehow made the second move possible (for instance @@ -2181,6 +2289,19 @@ split_point_start: // At split points actual search starts from here /// The ThreadsManager class + // read_uci_options() updates number of active threads and other internal + // parameters according to the UCI options values. It is called before + // to start a new search. + + void ThreadsManager::read_uci_options() { + + maxThreadsPerSplitPoint = Options["Maximum Number of Threads per Split Point"].value(); + minimumSplitDepth = Options["Minimum Split Depth"].value() * ONE_PLY; + useSleepingThreads = Options["Use Sleeping Threads"].value(); + activeThreads = Options["Threads"].value(); + } + + // idle_loop() is where the threads are parked when they have no work to do. // The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint // object for which the current thread is the master. @@ -2189,11 +2310,14 @@ split_point_start: // At split points actual search starts from here assert(threadID >= 0 && threadID < MAX_THREADS); + int i; + bool allFinished = false; + while (true) { // Slave threads can exit as soon as AllThreadsShouldExit raises, // master should exit as last one. - if (AllThreadsShouldExit) + if (allThreadsShouldExit) { assert(!sp); threads[threadID].state = THREAD_TERMINATED; @@ -2202,28 +2326,39 @@ split_point_start: // At split points actual search starts from here // If we are not thinking, wait for a condition to be signaled // instead of wasting CPU time polling for work. - while (threadID >= ActiveThreads || threads[threadID].state == THREAD_INITIALIZING) + while ( threadID >= activeThreads || threads[threadID].state == THREAD_INITIALIZING + || (useSleepingThreads && threads[threadID].state == THREAD_AVAILABLE)) { - assert(!sp); - assert(threadID != 0); + assert(!sp || useSleepingThreads); + assert(threadID != 0 || useSleepingThreads); - if (AllThreadsShouldExit) - break; + if (threads[threadID].state == THREAD_INITIALIZING) + threads[threadID].state = THREAD_AVAILABLE; - threads[threadID].state = THREAD_AVAILABLE; + // Grab the lock to avoid races with wake_sleeping_thread() + lock_grab(&sleepLock[threadID]); + + // If we are master and all slaves have finished do not go to sleep + for (i = 0; sp && i < activeThreads && !sp->slaves[i]; i++) {} + allFinished = (i == activeThreads); - lock_grab(&WaitLock); + if (allFinished || allThreadsShouldExit) + { + lock_release(&sleepLock[threadID]); + break; + } - if (threadID >= ActiveThreads || threads[threadID].state == THREAD_INITIALIZING) - cond_wait(&WaitCond[threadID], &WaitLock); + // Do sleep here after retesting sleep conditions + if (threadID >= activeThreads || threads[threadID].state == THREAD_AVAILABLE) + cond_wait(&sleepCond[threadID], &sleepLock[threadID]); - lock_release(&WaitLock); + lock_release(&sleepLock[threadID]); } // If this thread has been assigned work, launch a search if (threads[threadID].state == THREAD_WORKISWAITING) { - assert(!AllThreadsShouldExit); + assert(!allThreadsShouldExit); threads[threadID].state = THREAD_SEARCHING; @@ -2235,20 +2370,25 @@ split_point_start: // At split points actual search starts from here if (tsp->pvNode) search(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply); - else { + else search(pos, ss, tsp->alpha, tsp->beta, tsp->depth, tsp->ply); - } + assert(threads[threadID].state == THREAD_SEARCHING); threads[threadID].state = THREAD_AVAILABLE; + + // Wake up master thread so to allow it to return from the idle loop in + // case we are the last slave of the split point. + if (useSleepingThreads && threadID != tsp->master && threads[tsp->master].state == THREAD_AVAILABLE) + wake_sleeping_thread(tsp->master); } // If this thread is the master of a split point and all slaves have // finished their work at this split point, return from the idle loop. - int i = 0; - for ( ; sp && i < ActiveThreads && !sp->slaves[i]; i++) {} + for (i = 0; sp && i < activeThreads && !sp->slaves[i]; i++) {} + allFinished = (i == activeThreads); - if (i == ActiveThreads) + if (allFinished) { // Because sp->slaves[] is reset under lock protection, // be sure sp->lock has been released before to return. @@ -2276,11 +2416,13 @@ split_point_start: // At split points actual search starts from here bool ok; // Initialize global locks - lock_init(&MPLock); - lock_init(&WaitLock); + lock_init(&mpLock); for (i = 0; i < MAX_THREADS; i++) - cond_init(&WaitCond[i]); + { + lock_init(&sleepLock[i]); + cond_init(&sleepCond[i]); + } // Initialize splitPoints[] locks for (i = 0; i < MAX_THREADS; i++) @@ -2288,10 +2430,10 @@ split_point_start: // At split points actual search starts from here lock_init(&(threads[i].splitPoints[j].lock)); // Will be set just before program exits to properly end the threads - AllThreadsShouldExit = false; + allThreadsShouldExit = false; // Threads will be put all threads to sleep as soon as created - ActiveThreads = 1; + activeThreads = 1; // All threads except the main thread should be initialized to THREAD_INITIALIZING threads[0].state = THREAD_SEARCHING; @@ -2327,7 +2469,7 @@ split_point_start: // At split points actual search starts from here void ThreadsManager::exit_threads() { - AllThreadsShouldExit = true; // Let the woken up threads to exit idle_loop() + allThreadsShouldExit = true; // Let the woken up threads to exit idle_loop() // Wake up all the threads and waits for termination for (int i = 1; i < MAX_THREADS; i++) @@ -2341,12 +2483,14 @@ split_point_start: // At split points actual search starts from here for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++) lock_destroy(&(threads[i].splitPoints[j].lock)); - lock_destroy(&WaitLock); - lock_destroy(&MPLock); + lock_destroy(&mpLock); // Now we can safely destroy the wait conditions for (int i = 0; i < MAX_THREADS; i++) - cond_destroy(&WaitCond[i]); + { + lock_destroy(&sleepLock[i]); + cond_destroy(&sleepCond[i]); + } } @@ -2356,7 +2500,7 @@ split_point_start: // At split points actual search starts from here bool ThreadsManager::thread_should_stop(int threadID) const { - assert(threadID >= 0 && threadID < ActiveThreads); + assert(threadID >= 0 && threadID < activeThreads); SplitPoint* sp = threads[threadID].splitPoint; @@ -2375,9 +2519,9 @@ split_point_start: // At split points actual search starts from here bool ThreadsManager::thread_is_available(int slave, int master) const { - assert(slave >= 0 && slave < ActiveThreads); - assert(master >= 0 && master < ActiveThreads); - assert(ActiveThreads > 1); + assert(slave >= 0 && slave < activeThreads); + assert(master >= 0 && master < activeThreads); + assert(activeThreads > 1); if (threads[slave].state != THREAD_AVAILABLE || slave == master) return false; @@ -2387,7 +2531,7 @@ split_point_start: // At split points actual search starts from here // No active split points means that the thread is available as // a slave for any other thread. - if (localActiveSplitPoints == 0 || ActiveThreads == 2) + if (localActiveSplitPoints == 0 || activeThreads == 2) return true; // Apply the "helpful master" concept if possible. Use localActiveSplitPoints @@ -2405,10 +2549,10 @@ split_point_start: // At split points actual search starts from here bool ThreadsManager::available_thread_exists(int master) const { - assert(master >= 0 && master < ActiveThreads); - assert(ActiveThreads > 1); + assert(master >= 0 && master < activeThreads); + assert(activeThreads > 1); - for (int i = 0; i < ActiveThreads; i++) + for (int i = 0; i < activeThreads; i++) if (thread_is_available(i, master)) return true; @@ -2436,20 +2580,20 @@ split_point_start: // At split points actual search starts from here assert(*alpha < beta); assert(beta <= VALUE_INFINITE); assert(depth > DEPTH_ZERO); - assert(pos.thread() >= 0 && pos.thread() < ActiveThreads); - assert(ActiveThreads > 1); + assert(pos.thread() >= 0 && pos.thread() < activeThreads); + assert(activeThreads > 1); int i, master = pos.thread(); Thread& masterThread = threads[master]; - lock_grab(&MPLock); + 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) || masterThread.activeSplitPoints >= MAX_ACTIVE_SPLIT_POINTS) { - lock_release(&MPLock); + lock_release(&mpLock); return; } @@ -2458,6 +2602,7 @@ split_point_start: // At split points actual search starts from here // Initialize the split point object splitPoint.parent = masterThread.splitPoint; + splitPoint.master = master; splitPoint.stopRequest = false; splitPoint.ply = ply; splitPoint.depth = depth; @@ -2472,7 +2617,7 @@ split_point_start: // At split points actual search starts from here splitPoint.pos = &pos; splitPoint.nodes = 0; splitPoint.parentSstack = ss; - for (i = 0; i < ActiveThreads; i++) + for (i = 0; i < activeThreads; i++) splitPoint.slaves[i] = 0; masterThread.splitPoint = &splitPoint; @@ -2483,7 +2628,7 @@ split_point_start: // At split points actual search starts from here int workersCnt = 1; // At least the master is included // Allocate available threads setting state to THREAD_BOOKED - for (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; @@ -2495,11 +2640,11 @@ split_point_start: // At split points actual search starts from here assert(Fake || workersCnt > 1); // We can release the lock because slave threads are already booked and master is not available - lock_release(&MPLock); + lock_release(&mpLock); // 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 (i = 0; i < ActiveThreads; i++) + for (i = 0; i < activeThreads; i++) if (i == master || splitPoint.slaves[i]) { memcpy(splitPoint.sstack[i], ss - 1, 4 * sizeof(SearchStack)); @@ -2507,6 +2652,9 @@ split_point_start: // At split points actual search starts from here assert(i == master || threads[i].state == THREAD_BOOKED); threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop() + + if (useSleepingThreads && i != master) + wake_sleeping_thread(i); } // Everything is set up. The master thread enters the idle loop, from @@ -2518,7 +2666,7 @@ split_point_start: // At split points actual search starts from here // We have returned from the idle loop, which means that all threads are // finished. Update alpha and bestValue, and return. - lock_grab(&MPLock); + lock_grab(&mpLock); *alpha = splitPoint.alpha; *bestValue = splitPoint.bestValue; @@ -2526,18 +2674,18 @@ split_point_start: // At split points actual search starts from here masterThread.splitPoint = splitPoint.parent; pos.set_nodes_searched(pos.nodes_searched() + splitPoint.nodes); - lock_release(&MPLock); + lock_release(&mpLock); } - // wake_sleeping_thread() wakes up all sleeping threads when it is time - // to start a new search from the root. + // wake_sleeping_thread() wakes up the thread with the given threadID + // when it is time to start a new search. void ThreadsManager::wake_sleeping_thread(int threadID) { - lock_grab(&WaitLock); - cond_signal(&WaitCond[threadID]); - lock_release(&WaitLock); + lock_grab(&sleepLock[threadID]); + cond_signal(&sleepCond[threadID]); + lock_release(&sleepLock[threadID]); }