X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=e853b6ee73e2518490c590283ef10b926efea42c;hp=9649c2da76b269d00ae9380e1fbfd4c018883fbb;hb=dee878082960be198fdb1493940b3d8a2be0bd58;hpb=d607febb38e65668ffb70e55db40a827b037d8e6 diff --git a/src/search.cpp b/src/search.cpp index 9649c2da..e853b6ee 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -59,6 +59,10 @@ namespace { // Used for debugging SMP code. const bool FakeSplit = false; + // Fast lookup table of sliding pieces indexed by Piece + const bool Slidings[18] = { 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1 }; + inline bool piece_is_slider(Piece p) { return Slidings[p]; } + // ThreadsManager class is used to handle all the threads related stuff in search, // init, starting, parking and, the most important, launching a slave thread at a // split point are what this class does. All the access to shared thread data is @@ -73,12 +77,14 @@ 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; + bool cutoff_at_splitpoint(int threadID) const; void wake_sleeping_thread(int threadID); void idle_loop(int threadID, SplitPoint* sp); @@ -87,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; - WaitCondition WaitCond[MAX_THREADS]; + Lock mpLock, sleepLock[MAX_THREADS]; + WaitCondition sleepCond[MAX_THREADS]; }; @@ -228,7 +237,10 @@ namespace { const Value EasyMoveMargin = Value(0x200); - /// Global variables + /// Namespace variables + + // Book object + Book OpeningBook; // Iteration counter int Iteration; @@ -253,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 @@ -287,6 +297,7 @@ namespace { template Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous); + bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bValue); bool connected_moves(const Position& pos, Move m1, Move m2); bool value_is_mate(Value value); Value value_to_tt(Value v, int ply); @@ -340,7 +351,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); @@ -407,12 +418,12 @@ bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[ UseTimeManagement = !ExactMaxTime && !MaxDepth && !MaxNodes && !InfiniteSearch; // Look for a book move, only during games, not tests - if (UseTimeManagement && get_option_value_bool("OwnBook")) + if (UseTimeManagement && Options["OwnBook"].value()) { - if (get_option_value_string("Book File") != OpeningBook.file_name()) - OpeningBook.open(get_option_value_string("Book File")); + if (Options["Book File"].value() != OpeningBook.file_name()) + OpeningBook.open(Options["Book File"].value()); - Move bookMove = OpeningBook.get_move(pos, get_option_value_bool("Best Book Move")); + Move bookMove = OpeningBook.get_move(pos, Options["Best Book Move"].value()); if (bookMove != MOVE_NONE) { if (PonderSearch) @@ -424,40 +435,40 @@ bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[ } // Read UCI option values - TT.set_size(get_option_value_int("Hash")); - if (button_was_pressed("Clear Hash")) + TT.set_size(Options["Hash"].value()); + if (Options["Clear Hash"].value()) + { + Options["Clear Hash"].set_value("false"); TT.clear(); + } - CheckExtension[1] = Depth(get_option_value_int("Check Extension (PV nodes)")); - CheckExtension[0] = Depth(get_option_value_int("Check Extension (non-PV nodes)")); - SingleEvasionExtension[1] = Depth(get_option_value_int("Single Evasion Extension (PV nodes)")); - SingleEvasionExtension[0] = Depth(get_option_value_int("Single Evasion Extension (non-PV nodes)")); - PawnPushTo7thExtension[1] = Depth(get_option_value_int("Pawn Push to 7th Extension (PV nodes)")); - PawnPushTo7thExtension[0] = Depth(get_option_value_int("Pawn Push to 7th Extension (non-PV nodes)")); - PassedPawnExtension[1] = Depth(get_option_value_int("Passed Pawn Extension (PV nodes)")); - PassedPawnExtension[0] = Depth(get_option_value_int("Passed Pawn Extension (non-PV nodes)")); - PawnEndgameExtension[1] = Depth(get_option_value_int("Pawn Endgame Extension (PV nodes)")); - PawnEndgameExtension[0] = Depth(get_option_value_int("Pawn Endgame Extension (non-PV nodes)")); - MateThreatExtension[1] = Depth(get_option_value_int("Mate Threat Extension (PV nodes)")); - MateThreatExtension[0] = Depth(get_option_value_int("Mate Threat Extension (non-PV nodes)")); - - MinimumSplitDepth = get_option_value_int("Minimum Split Depth") * ONE_PLY; - MaxThreadsPerSplitPoint = get_option_value_int("Maximum Number of Threads per Split Point"); - MultiPV = get_option_value_int("MultiPV"); - UseLogFile = get_option_value_bool("Use Search Log"); + CheckExtension[1] = Options["Check Extension (PV nodes)"].value(); + CheckExtension[0] = Options["Check Extension (non-PV nodes)"].value(); + SingleEvasionExtension[1] = Options["Single Evasion Extension (PV nodes)"].value(); + SingleEvasionExtension[0] = Options["Single Evasion Extension (non-PV nodes)"].value(); + PawnPushTo7thExtension[1] = Options["Pawn Push to 7th Extension (PV nodes)"].value(); + PawnPushTo7thExtension[0] = Options["Pawn Push to 7th Extension (non-PV nodes)"].value(); + PassedPawnExtension[1] = Options["Passed Pawn Extension (PV nodes)"].value(); + PassedPawnExtension[0] = Options["Passed Pawn Extension (non-PV nodes)"].value(); + PawnEndgameExtension[1] = Options["Pawn Endgame Extension (PV nodes)"].value(); + 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(); + MultiPV = Options["MultiPV"].value(); + UseLogFile = Options["Use Search Log"].value(); if (UseLogFile) - LogFile.open(get_option_value_string("Search Log Filename").c_str(), std::ios::out | std::ios::app); + LogFile.open(Options["Search Log Filename"].value().c_str(), std::ios::out | std::ios::app); read_weights(pos.side_to_move()); // Set the number of active threads - int newActiveThreads = get_option_value_int("Threads"); - 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 < ThreadsMgr.active_threads(); i++) + ThreadsMgr.wake_sleeping_thread(i); // Set thinking time int myTime = time[pos.side_to_move()]; @@ -491,6 +502,9 @@ bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[ if (UseLogFile) LogFile.close(); + // This makes all the threads to go to sleep + ThreadsMgr.set_active_threads(1); + return !Quit; } @@ -644,7 +658,7 @@ namespace { << " time " << current_search_time() << endl; // Print the best move and the ponder move to the standard output - if (pv[0] == MOVE_NONE) + if (pv[0] == MOVE_NONE || MultiPV > 1) { pv[0] = rml.move(0); pv[1] = MOVE_NONE; @@ -979,7 +993,8 @@ namespace { threatMove = sp->threatMove; mateThreat = sp->mateThreat; goto split_point_start; - } else {} // Hack to fix icc's "statement is unreachable" warning + } + else {} // Hack to fix icc's "statement is unreachable" warning // Step 1. Initialize node and poll. Polling can abort search ss->currentMove = ss->bestMove = threatMove = MOVE_NONE; @@ -992,8 +1007,10 @@ namespace { } // Step 2. Check for aborted search and immediate draw - if ( AbortSearch || ThreadsMgr.thread_should_stop(threadID) - || pos.is_draw() || ply >= PLY_MAX - 1) + if ( AbortSearch + || ThreadsMgr.cutoff_at_splitpoint(threadID) + || pos.is_draw() + || ply >= PLY_MAX - 1) return VALUE_DRAW; // Step 3. Mate distance pruning @@ -1053,7 +1070,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())) { @@ -1132,6 +1148,7 @@ namespace { threatMove = (ss+1)->bestMove; if ( depth < ThreatDepth && (ss-1)->reduction + && threatMove != MOVE_NONE && connected_moves(pos, (ss-1)->currentMove, threatMove)) return beta - 1; } @@ -1183,7 +1200,7 @@ split_point_start: // At split points actual search starts from here // Loop through all legal moves until no moves remain or a beta cutoff occurs while ( bestValue < beta && (move = mp.get_next_move()) != MOVE_NONE - && !ThreadsMgr.thread_should_stop(threadID)) + && !ThreadsMgr.cutoff_at_splitpoint(threadID)) { assert(move_is_ok(move)); @@ -1270,6 +1287,17 @@ split_point_start: // At split points actual search starts from here continue; } + + // Prune moves with negative SEE 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 @@ -1277,7 +1305,7 @@ split_point_start: // At split points actual search starts from here // Step extra. pv search (only in PV nodes) // The first move in list is the expected PV - if (!SpNode && PvNode && moveCount == 1) + if (PvNode && moveCount == 1) value = -search(pos, ss+1, -beta, -alpha, newDepth, ply+1); else { @@ -1289,9 +1317,11 @@ split_point_start: // At split points actual search starts from here && !captureOrPromotion && !dangerous && !move_is_castle(move) - && !(ss->killers[0] == move || ss->killers[1] == move)) + && ss->killers[0] != move + && ss->killers[1] != move) { ss->reduction = reduction(depth, moveCount); + if (ss->reduction) { alpha = SpNode ? sp->alpha : alpha; @@ -1343,7 +1373,7 @@ split_point_start: // At split points actual search starts from here alpha = sp->alpha; } - if (value > bestValue && !(SpNode && ThreadsMgr.thread_should_stop(threadID))) + if (value > bestValue && !(SpNode && ThreadsMgr.cutoff_at_splitpoint(threadID))) { bestValue = value; @@ -1352,15 +1382,15 @@ split_point_start: // At split points actual search starts from here if (value > alpha) { - if (SpNode && (!PvNode || value >= beta)) - sp->stopRequest = true; - if (PvNode && value < beta) // We want always alpha < beta { alpha = value; + if (SpNode) sp->alpha = value; } + else if (SpNode) + sp->betaCutoff = true; if (value == value_mate_in(ply + 1)) ss->mateKiller = move; @@ -1374,12 +1404,12 @@ 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) && !AbortSearch - && !ThreadsMgr.thread_should_stop(threadID) + && !ThreadsMgr.cutoff_at_splitpoint(threadID) && Iteration <= 99) ThreadsMgr.split(pos, ss, ply, &alpha, beta, &bestValue, depth, threatMove, mateThreat, moveCount, &mp, PvNode); @@ -1395,7 +1425,7 @@ split_point_start: // At split points actual search starts from here // Step 20. Update tables // If the search is not aborted, update the transposition table, // history counters, and killer moves. - if (!SpNode && !AbortSearch && !ThreadsMgr.thread_should_stop(threadID)) + if (!SpNode && !AbortSearch && !ThreadsMgr.cutoff_at_splitpoint(threadID)) { move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove; vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER @@ -1425,7 +1455,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). @@ -1443,8 +1472,9 @@ 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; + Depth ttDepth; Value oldAlpha = alpha; ss->bestMove = ss->currentMove = MOVE_NONE; @@ -1453,25 +1483,29 @@ 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, this fixes also the type of + // TT entry depth that we are going to use. Note that in qsearch we use + // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS. + isCheck = pos.is_check(); + ttDepth = (isCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS); + // 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, ttDepth, 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 { @@ -1499,9 +1533,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; @@ -1509,9 +1540,9 @@ split_point_start: // At split points actual search starts from here // Initialize a MovePicker object for the current position, and prepare // 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); + // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will + // be generated. + MovePicker mp = MovePicker(pos, ttMove, depth, H); CheckInfo ci(pos); // Loop through the moves until no moves remain or a beta cutoff occurs @@ -1557,6 +1588,21 @@ 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_or_promotion(move) + && ss->eval + PawnValueMidgame / 4 < beta + && !check_is_dangerous(pos, move, futilityBase, beta, &bestValue)) + { + if (ss->eval + PawnValueMidgame / 4 > bestValue) + bestValue = ss->eval + PawnValueMidgame / 4; + + continue; + } + // Update current move ss->currentMove = move; @@ -1585,9 +1631,8 @@ 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); + TT.store(pos.get_key(), value_to_tt(bestValue, ply), vt, ttDepth, ss->bestMove, ss->eval, evalMargin); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1595,6 +1640,63 @@ split_point_start: // At split points actual search starts from here } + // check_is_dangerous() tests if a checking move can be pruned in qsearch(). + // bestValue is updated only when returning false because in that case move + // will be pruned. + + bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bestValue) + { + Bitboard b, occ, oldAtt, newAtt, kingAtt; + Square from, to, ksq, victimSq; + Piece pc; + Color them; + Value futilityValue, bv = *bestValue; + + from = move_from(move); + to = move_to(move); + them = opposite_color(pos.side_to_move()); + ksq = pos.king_square(them); + kingAtt = pos.attacks_from(ksq); + pc = pos.piece_on(from); + + occ = pos.occupied_squares() & ~(1ULL << from) & ~(1ULL << ksq); + oldAtt = pos.attacks_from(pc, from, occ); + newAtt = pos.attacks_from(pc, to, occ); + + // Rule 1. Checks which give opponent's king at most one escape square are dangerous + b = kingAtt & ~pos.pieces_of_color(them) & ~newAtt & ~(1ULL << to); + + if (!(b && (b & (b - 1)))) + return true; + + // Rule 2. Queen contact check is very dangerous + if ( type_of_piece(pc) == QUEEN + && bit_is_set(kingAtt, to)) + return true; + + // Rule 3. Creating new double threats with checks + b = pos.pieces_of_color(them) & newAtt & ~oldAtt & ~(1ULL << ksq); + + while (b) + { + victimSq = pop_1st_bit(&b); + futilityValue = futilityBase + pos.endgame_value_of_piece_on(victimSq); + + // Note that here we generate illegal "double move"! + if ( futilityValue >= beta + && pos.see_sign(make_move(from, victimSq)) >= 0) + return true; + + if (futilityValue > bv) + bv = futilityValue; + } + + // Update bestValue only if check is not dangerous (because we will prune the move) + *bestValue = bv; + return false; + } + + // connected_moves() tests whether two moves are 'connected' in the sense // that the first move somehow made the second move possible (for instance // if the moving piece is the same in both moves). The first move is assumed @@ -1606,11 +1708,8 @@ split_point_start: // At split points actual search starts from here Square f1, t1, f2, t2; Piece p; - assert(move_is_ok(m1)); - assert(move_is_ok(m2)); - - if (m2 == MOVE_NONE) - return false; + assert(m1 && move_is_ok(m1)); + assert(m2 && move_is_ok(m2)); // Case 1: The moving piece is the same in both moves f2 = move_from(m2); @@ -1924,7 +2023,7 @@ split_point_start: // At split points actual search starts from here int t = current_search_time(); // Poll for input - if (Bioskey()) + if (data_available()) { // We are line oriented, don't read single chars std::string command; @@ -2164,6 +2263,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. @@ -2172,11 +2284,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; @@ -2185,37 +2300,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 - || (!sp && threads[threadID].state == THREAD_AVAILABLE)) + 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; - lock_grab(&MPLock); + // Grab the lock to avoid races with wake_sleeping_thread() + lock_grab(&sleepLock[threadID]); - // Retest condition under lock protection - if (!( threadID >= ActiveThreads - || threads[threadID].state == THREAD_INITIALIZING - || (!sp && threads[threadID].state == THREAD_AVAILABLE))) + // 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); + + if (allFinished || allThreadsShouldExit) { - lock_release(&MPLock); - continue; + lock_release(&sleepLock[threadID]); + break; } - // Put thread to sleep - threads[threadID].state = THREAD_AVAILABLE; - cond_wait(&WaitCond[threadID], &MPLock); - lock_release(&MPLock); + // Do sleep here after retesting sleep conditions + if (threadID >= activeThreads || threads[threadID].state == THREAD_AVAILABLE) + cond_wait(&sleepCond[threadID], &sleepLock[threadID]); + + 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; @@ -2227,20 +2344,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. @@ -2268,10 +2390,13 @@ split_point_start: // At split points actual search starts from here bool ok; // Initialize global locks - lock_init(&MPLock); + 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++) @@ -2279,10 +2404,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; @@ -2304,7 +2429,7 @@ split_point_start: // At split points actual search starts from here if (!ok) { cout << "Failed to create thread number " << i << endl; - Application::exit_with_failure(); + exit(EXIT_FAILURE); } // Wait until the thread has finished launching and is gone to sleep @@ -2318,7 +2443,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++) @@ -2332,25 +2457,28 @@ 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(&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]); + } } - // thread_should_stop() checks whether the thread should stop its search. - // This can happen if a beta cutoff has occurred in the thread's currently - // active split point, or in some ancestor of the current split point. + // cutoff_at_splitpoint() checks whether a beta cutoff has occurred in + // the thread's currently active split point, or in some ancestor of + // the current split point. - bool ThreadsManager::thread_should_stop(int threadID) const { + bool ThreadsManager::cutoff_at_splitpoint(int threadID) const { - assert(threadID >= 0 && threadID < ActiveThreads); + assert(threadID >= 0 && threadID < activeThreads); SplitPoint* sp = threads[threadID].splitPoint; - for ( ; sp && !sp->stopRequest; sp = sp->parent) {} + for ( ; sp && !sp->betaCutoff; sp = sp->parent) {} return sp != NULL; } @@ -2365,9 +2493,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; @@ -2377,7 +2505,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 @@ -2395,10 +2523,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; @@ -2426,20 +2554,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; } @@ -2448,7 +2576,8 @@ split_point_start: // At split points actual search starts from here // Initialize the split point object splitPoint.parent = masterThread.splitPoint; - splitPoint.stopRequest = false; + splitPoint.master = master; + splitPoint.betaCutoff = false; splitPoint.ply = ply; splitPoint.depth = depth; splitPoint.threatMove = threatMove; @@ -2462,7 +2591,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; @@ -2473,7 +2602,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; @@ -2485,11 +2614,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)); @@ -2497,7 +2626,8 @@ 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 (i != master) + + if (useSleepingThreads && i != master) wake_sleeping_thread(i); } @@ -2510,7 +2640,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; @@ -2518,18 +2648,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(&MPLock); - cond_signal(&WaitCond[threadID]); - lock_release(&MPLock); + lock_grab(&sleepLock[threadID]); + cond_signal(&sleepCond[threadID]); + lock_release(&sleepLock[threadID]); }