X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=17e54e4cd3cbedc32a9656f314fa8ac1514790f2;hp=1eddff5813f2d5afc45f106f53dd8c1278b4b7a2;hb=f16c231bc9b239cc270e3103be93899f3204df76;hpb=c835ee88535e138a4a5870f18a1cebab96476cf7 diff --git a/src/search.cpp b/src/search.cpp index 1eddff58..17e54e4c 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -1,7 +1,7 @@ /* Stockfish, a UCI chess playing engine derived from Glaurung 2.1 Copyright (C) 2004-2008 Tord Romstad (Glaurung author) - Copyright (C) 2008-2009 Marco Costalba + Copyright (C) 2008-2010 Marco Costalba, Joona Kiiski, Tord Romstad Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -82,12 +82,12 @@ namespace { bool thread_should_stop(int threadID) const; void wake_sleeping_threads(); void put_threads_to_sleep(); - void idle_loop(int threadID, SplitPoint* waitSp); + void idle_loop(int threadID, SplitPoint* sp); bool split(const Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue, Depth depth, bool mateThreat, int* moves, MovePicker* mp, int master, bool pvNode); private: - friend void poll(SearchStack ss[], int ply); + friend void poll(); int ActiveThreads; volatile bool AllThreadsShouldExit, AllThreadsShouldSleep; @@ -259,9 +259,6 @@ namespace { bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit; bool FirstRootMove, AbortSearch, Quit, AspirationFailLow; - // Show current line? - bool ShowCurrentLine; - // Log file bool UseLogFile; std::ofstream LogFile; @@ -305,7 +302,7 @@ namespace { int current_search_time(); int nps(); - void poll(SearchStack ss[], int ply); + void poll(); void ponderhit(); void wait_for_stop_or_ponderhit(); void init_ss_array(SearchStack ss[]); @@ -390,7 +387,7 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, if (get_option_value_string("Book File") != OpeningBook.file_name()) OpeningBook.open(get_option_value_string("Book File")); - Move bookMove = OpeningBook.get_move(pos); + Move bookMove = OpeningBook.get_move(pos, get_option_value_bool("Best Book Move")); if (bookMove != MOVE_NONE) { if (PonderSearch) @@ -425,7 +422,6 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, MinimumSplitDepth = get_option_value_int("Minimum Split Depth") * OnePly; MaxThreadsPerSplitPoint = get_option_value_int("Maximum Number of Threads per Split Point"); - ShowCurrentLine = get_option_value_bool("UCI_ShowCurrLine"); MultiPV = get_option_value_int("MultiPV"); Chess960 = get_option_value_bool("UCI_Chess960"); UseLogFile = get_option_value_bool("Use Search Log"); @@ -441,10 +437,6 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, { TM.set_active_threads(newActiveThreads); init_eval(TM.active_threads()); - // HACK: init_eval() destroys the static castleRightsMask[] array in the - // Position class. The below line repairs the damage. - Position p(pos.to_fen()); - assert(pos.is_ok()); } // Wake up sleeping threads @@ -568,7 +560,7 @@ void init_search() { for (int j = 0; j < 64; j++) // j == moveNumber { // FIXME: test using log instead of BSR - FutilityMarginsMatrix[i][j] = (i < 2 ? 0 : 112 * bitScanReverse32(i * i / 2)) - 8 * j; + FutilityMarginsMatrix[i][j] = (i < 2 ? 0 : 112 * bitScanReverse32(i * i / 2)) - 8 * j + 45; } // Init futility move count array @@ -931,8 +923,8 @@ namespace { print_pv_info(pos, ss, alpha, beta, value); // Prepare for a research after a fail high, each time with a wider window - researchCountFH++; *betaPtr = beta = Min(beta + AspirationDelta * (1 << researchCountFH), VALUE_INFINITE); + researchCountFH++; } // End of fail high loop @@ -1017,8 +1009,8 @@ namespace { break; // Prepare for a research after a fail low, each time with a wider window - researchCountFL++; *alphaPtr = alpha = Max(alpha - AspirationDelta * (1 << researchCountFL), -VALUE_INFINITE); + researchCountFL++; } // Fail low loop @@ -1105,14 +1097,13 @@ namespace { tte = TT.retrieve(pos.get_key()); } - // Step 10. Loop through moves - // Loop through all legal moves until no moves remain or a beta cutoff occurs - // Initialize a MovePicker object for the current position mateThreat = pos.has_mate_threat(opposite_color(pos.side_to_move())); MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]); CheckInfo ci(pos); + // Step 10. Loop through moves + // Loop through all legal moves until no moves remain or a beta cutoff occurs while ( alpha < beta && (move = mp.get_next_move()) != MOVE_NONE && !TM.thread_should_stop(threadID)) @@ -1310,6 +1301,9 @@ namespace { if (tte && ok_to_use_TT(tte, depth, beta, ply)) { + // Refresh tte entry to avoid aging + TT.store(posKey, tte->value(), tte->type(), tte->depth(), ttMove); + ss[ply].currentMove = ttMove; // Can be MOVE_NONE return value_from_tt(tte->value(), ply); } @@ -1329,12 +1323,12 @@ namespace { } // Step 6. Razoring - if ( !value_is_mate(beta) + if ( refinedValue < beta - razor_margin(depth) + && ttMove == MOVE_NONE + && ss[ply - 1].currentMove != MOVE_NULL + && depth < RazorDepth && !isCheck - && depth < RazorDepth - && refinedValue < beta - razor_margin(depth) - && ss[ply - 1].currentMove != MOVE_NULL - && ttMove == MOVE_NONE + && !value_is_mate(beta) && !pos.has_pawn_on_7th(pos.side_to_move())) { Value rbeta = beta - razor_margin(depth); @@ -1347,11 +1341,13 @@ namespace { // Step 7. Static null move pruning // We're betting that the opponent doesn't have a move that will reduce - // the score by more than fuility_margin(depth) if we do a null move. - if ( !isCheck - && allowNullmove - && depth < RazorDepth - && refinedValue - futility_margin(depth, 0) >= beta) + // the score by more than futility_margin(depth) if we do a null move. + if ( allowNullmove + && depth < RazorDepth + && !isCheck + && !value_is_mate(beta) + && ok_to_do_nullmove(pos) + && refinedValue >= beta + futility_margin(depth, 0)) return refinedValue - futility_margin(depth, 0); // Step 8. Null move search with verification search @@ -1367,8 +1363,6 @@ namespace { { ss[ply].currentMove = MOVE_NULL; - pos.do_null_move(st); - // Null move dynamic reduction based on depth int R = 3 + (depth >= 5 * OnePly ? depth / 8 : 0); @@ -1376,19 +1370,25 @@ namespace { if (refinedValue - beta > PawnValueMidgame) R++; + pos.do_null_move(st); + nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID); pos.undo_null_move(); if (nullValue >= beta) { + // Do not return unproven mate scores + if (nullValue >= value_mate_in(PLY_MAX)) + nullValue = beta; + if (depth < 6 * OnePly) - return beta; + return nullValue; // Do zugzwang verification search Value v = search(pos, ss, beta, depth-5*OnePly, ply, false, threadID); if (v >= beta) - return beta; + return nullValue; } else { // The null move failed low, which means that we may be faced with // some kind of threat. If the previous move was reduced, check if @@ -1418,13 +1418,12 @@ namespace { tte = TT.retrieve(posKey); } - // Step 10. Loop through moves - // Loop through all legal moves until no moves remain or a beta cutoff occurs - // Initialize a MovePicker object for the current position MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply], beta); CheckInfo ci(pos); + // Step 10. Loop through moves + // Loop through all legal moves until no moves remain or a beta cutoff occurs while ( bestValue < beta && (move = mp.get_next_move()) != MOVE_NONE && !TM.thread_should_stop(threadID)) @@ -1447,7 +1446,7 @@ namespace { if ( depth >= SingularExtensionDepthAtNonPVNodes && tte && move == tte->move() - && !excludedMove // Do not allow recursive single-reply search + && !excludedMove // Do not allow recursive singular extension search && ext < OnePly && is_lower_bound(tte->type()) && tte->depth() >= depth - 3 * OnePly) @@ -1484,7 +1483,7 @@ namespace { // Value based pruning Depth predictedDepth = newDepth - nonpv_reduction(depth, moveCount); // We illogically ignore reduction condition depth >= 3*OnePly futilityValueScaled = ss[ply].eval + futility_margin(predictedDepth, moveCount) - + H.gain(pos.piece_on(move_from(move)), move_to(move)) + 45; + + H.gain(pos.piece_on(move_from(move)), move_to(move)); if (futilityValueScaled < beta) { @@ -1497,8 +1496,8 @@ namespace { // Step 13. Make the move pos.do_move(move, st, ci, moveIsCheck); - // Step 14. Reduced search - // if the move fails high will be re-searched at full depth. + // Step 14. Reduced search, if the move fails high + // will be re-searched at full depth. bool doFullDepthSearch = true; if ( depth >= 3*OnePly @@ -1552,11 +1551,11 @@ namespace { } // Step 19. Check for mate and stalemate - // All legal moves have been searched and if there were + // All legal moves have been searched and if there are // no legal moves, it must be mate or stalemate. - // If one move was excluded return fail low. + // If one move was excluded return fail low score. if (!moveCount) - return excludedMove ? beta - 1 : (pos.is_check() ? value_mated_in(ply) : VALUE_DRAW); + return excludedMove ? beta - 1 : (isCheck ? value_mated_in(ply) : VALUE_DRAW); // Step 20. Update tables // If the search is not aborted, update the transposition table, @@ -1665,7 +1664,7 @@ namespace { alpha = bestValue; // If we are near beta then try to get a cutoff pushing checks a bit further - bool deepChecks = depth == -OnePly && staticValue >= beta - PawnValueMidgame / 8; + bool deepChecks = (depth == -OnePly && staticValue >= beta - PawnValueMidgame / 8); // Initialize a MovePicker object for the current position, and prepare // to search the moves. Because the depth is <= 0 here, only captures, @@ -1676,8 +1675,7 @@ namespace { enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame; futilityBase = staticValue + FutilityMarginQS + ei.futilityMargin[pos.side_to_move()]; - // Loop through the moves until no moves remain or a beta cutoff - // occurs. + // Loop through the moves until no moves remain or a beta cutoff occurs while ( alpha < beta && (move = mp.get_next_move()) != MOVE_NONE) { @@ -1712,7 +1710,7 @@ namespace { // Detect blocking evasions that are candidate to be pruned evasionPrunable = isCheck - && bestValue != -VALUE_INFINITE + && bestValue > value_mated_in(PLY_MAX) && !pos.move_is_capture(move) && pos.type_of_piece_on(move_from(move)) != KING && !pos.can_castle(pos.side_to_move()); @@ -1746,7 +1744,7 @@ namespace { // All legal moves have been searched. A special case: If we're in check // and no legal moves were found, it is checkmate. - if (!moveCount && pos.is_check()) // Mate! + if (!moveCount && isCheck) // Mate! return value_mated_in(ply); // Update transposition table @@ -1843,7 +1841,7 @@ namespace { // Value based pruning Depth predictedDepth = newDepth - nonpv_reduction(sp->depth, moveCount); futilityValueScaled = ss[sp->ply].eval + futility_margin(predictedDepth, moveCount) - + H.gain(pos.piece_on(move_from(move)), move_to(move)) + 45; + + H.gain(pos.piece_on(move_from(move)), move_to(move)); if (futilityValueScaled < sp->beta) { @@ -2051,7 +2049,7 @@ namespace { NodesSincePoll++; if (NodesSincePoll >= NodesBetweenPolls) { - poll(ss, ply); + poll(); NodesSincePoll = 0; } } @@ -2414,7 +2412,7 @@ namespace { // looks at the time consumed so far and decides if it's time to abort the // search. - void poll(SearchStack ss[], int ply) { + void poll() { static int lastInfoTime; int t = current_search_time(); @@ -2465,16 +2463,6 @@ namespace { cout << "info nodes " << TM.nodes_searched() << " nps " << nps() << " time " << t << " hashfull " << TT.full() << endl; - - // We only support current line printing in single thread mode - if (ShowCurrentLine && TM.active_threads() == 1) - { - cout << "info currline"; - for (int p = 0; p < ply; p++) - cout << " " << ss[p].currentMove; - - cout << endl; - } } // Should we stop the search? @@ -2648,10 +2636,10 @@ namespace { // idle_loop() is where the threads are parked when they have no work to do. - // The parameter "waitSp", if non-NULL, is a pointer to an active SplitPoint + // The parameter 'sp', if non-NULL, is a pointer to an active SplitPoint // object for which the current thread is the master. - void ThreadsManager::idle_loop(int threadID, SplitPoint* waitSp) { + void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) { assert(threadID >= 0 && threadID < MAX_THREADS); @@ -2661,7 +2649,7 @@ namespace { // master should exit as last one. if (AllThreadsShouldExit) { - assert(!waitSp); + assert(!sp); threads[threadID].state = THREAD_TERMINATED; return; } @@ -2670,7 +2658,7 @@ namespace { // instead of wasting CPU time polling for work. while (AllThreadsShouldSleep || threadID >= ActiveThreads) { - assert(!waitSp); + assert(!sp); assert(threadID != 0); threads[threadID].state = THREAD_SLEEPING; @@ -2707,8 +2695,13 @@ namespace { // If this thread is the master of a split point and all threads have // finished their work at this split point, return from the idle loop. - if (waitSp != NULL && waitSp->cpus == 0) + if (sp && sp->cpus == 0) { + // Because sp->cpus is decremented under lock protection, + // be sure sp->lock has been released before to proceed. + lock_grab(&(sp->lock)); + lock_release(&(sp->lock)); + assert(threads[threadID].state == THREAD_AVAILABLE); threads[threadID].state = THREAD_SEARCHING; @@ -2779,7 +2772,7 @@ namespace { } // Wait until the thread has finished launching and is gone to sleep - while (threads[i].state != THREAD_SLEEPING); + while (threads[i].state != THREAD_SLEEPING) {} } } @@ -2820,7 +2813,7 @@ namespace { SplitPoint* sp; - for (sp = threads[threadID].splitPoint; sp && !sp->stopRequest; sp = sp->parent); + for (sp = threads[threadID].splitPoint; sp && !sp->stopRequest; sp = sp->parent) {} return sp != NULL; }