X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=17a1aeab984884b261c08bd858556bcdb8884614;hp=23fe8ce7eb2f5f61cc0f0fbda48d2b695686f98c;hb=da948cc94ebef4988199c90389a5099b087d2088;hpb=e217407450a65282ecc92f0985ff111b93110516 diff --git a/src/search.cpp b/src/search.cpp index 23fe8ce7..17a1aeab 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -28,7 +28,6 @@ #include #include -#include "bitcount.h" #include "book.h" #include "evaluate.h" #include "history.h" @@ -193,16 +192,6 @@ namespace { /// Variables initialized by UCI options - // Adjustable playing strength - int Slowdown = 0; - const int SlowdownArray[32] = { - 19, 41, 70, 110, 160, 230, 320, 430, 570, 756, 1000, 1300, 1690, 2197, - 2834, 3600, 4573, 5809, 7700, 9863, 12633, 16181, 20726, 26584, 34005, - 43557, 55792, 71463, 91536, 117247, 150180, 192363 - }; - int Strength; - const int MaxStrength = 25; - // Minimum number of full depth (i.e. non-reduced) moves at PV and non-PV nodes int LMRPVMoves, LMRNonPVMoves; // heavy SMP read access for the latter @@ -289,7 +278,7 @@ namespace { Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID); void sp_search(SplitPoint* sp, int threadID); void sp_search_pv(SplitPoint* sp, int threadID); - void init_node(const Position& pos, SearchStack ss[], int ply, int threadID); + void init_node(SearchStack ss[], int ply, int threadID); void update_pv(SearchStack ss[], int ply); void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply); bool connected_moves(const Position& pos, Move m1, Move m2); @@ -302,7 +291,6 @@ namespace { bool ok_to_history(const Position& pos, Move m); void update_history(const Position& pos, Move m, Depth depth, Move movesSearched[], int moveCount); void update_killers(Move m, SearchStack& ss); - void slowdown(const Position& pos); bool fail_high_ply_1(); int current_search_time(); @@ -311,6 +299,7 @@ namespace { void ponderhit(); void print_current_line(SearchStack ss[], int ply, int threadID); void wait_for_stop_or_ponderhit(); + void init_ss_array(SearchStack ss[]); void idle_loop(int threadID, SplitPoint* waitSp); void init_split_point_stack(); @@ -423,10 +412,8 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, read_weights(pos.side_to_move()); - // Set the number of active threads. If UCI_LimitStrength is enabled, never - // use more than one thread. - int newActiveThreads = - get_option_value_bool("UCI_LimitStrength")? 1 : get_option_value_int("Threads"); + // Set the number of active threads + int newActiveThreads = get_option_value_int("Threads"); if (newActiveThreads != ActiveThreads) { ActiveThreads = newActiveThreads; @@ -439,19 +426,6 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, for (int i = 1; i < ActiveThreads; i++) assert(thread_is_available(i, 0)); - // Set playing strength - if (get_option_value_bool("UCI_LimitStrength")) - { - Strength = (get_option_value_int("UCI_Elo") - 2100) / 25; - Slowdown = - (Strength == MaxStrength)? 0 : SlowdownArray[Max(0, 31-Strength)]; - } - else - { - Strength = MaxStrength; - Slowdown = 0; - } - // Set thinking time int myTime = time[side_to_move]; int myIncrement = increment[side_to_move]; @@ -496,13 +470,6 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, NodesBetweenPolls = Min(MaxNodes, 30000); InfiniteSearch = true; // HACK } - else if (Slowdown) { - if (Slowdown > 50000) NodesBetweenPolls = 30; - else if (Slowdown > 10000) NodesBetweenPolls = 100; - else if (Slowdown > 1000) NodesBetweenPolls = 500; - else if (Slowdown > 100) NodesBetweenPolls = 3000; - else NodesBetweenPolls = 15000; - } else NodesBetweenPolls = 30000; @@ -523,9 +490,9 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, { Value v = id_loop(pos, searchMoves); loseOnTime = ( UseLSNFiltering - && myTime < LSNTime - && myIncrement == 0 - && v < -LSNValue); + && myTime < LSNTime + && myIncrement == 0 + && v < -LSNValue); } else { @@ -658,14 +625,19 @@ namespace { // searchMoves are verified, copied, scored and sorted RootMoveList rml(p, searchMoves); + // Print RootMoveList c'tor startup scoring to the standard output, + // so that we print information also for iteration 1. + std::cout << "info depth " << 1 << "\ninfo depth " << 1 + << " score " << value_to_string(rml.get_move_score(0)) + << " time " << current_search_time() + << " nodes " << nodes_searched() + << " nps " << nps() + << " pv " << rml.get_move(0) << "\n"; + // Initialize TT.new_search(); H.clear(); - for (int i = 0; i < 3; i++) - { - ss[i].init(i); - ss[i].initKillers(); - } + init_ss_array(ss); IterationInfo[1] = IterationInfoType(rml.get_move_score(0), rml.get_move_score(0)); Iteration = 1; @@ -916,7 +888,7 @@ namespace { else { if ( newDepth >= 3*OnePly - && i >= MultiPV + LMRPVMoves - 2 // Remove -2 and decrease LMRPVMoves instead ? + && i >= MultiPV + LMRPVMoves && !dangerous && !moveIsCapture && !move_is_promotion(move) @@ -972,7 +944,7 @@ namespace { // Update PV rml.set_move_score(i, value); update_pv(ss, 0); - TT.extract_pv(pos, ss[0].pv); + TT.extract_pv(pos, ss[0].pv, PLY_MAX); rml.set_move_pv(i, ss[0].pv); if (MultiPV == 1) @@ -1056,7 +1028,7 @@ namespace { // Initialize, and make an early exit in case of an aborted search, // an instant draw, maximum ply reached, etc. - init_node(pos, ss, ply, threadID); + init_node(ss, ply, threadID); // After init_node() that calls poll() if (AbortSearch || thread_should_stop(threadID)) @@ -1091,16 +1063,16 @@ namespace { // Initialize a MovePicker object for the current position, and prepare // to search all moves - MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]); - Move move, movesSearched[256]; int moveCount = 0; Value value, bestValue = -VALUE_INFINITE; - Bitboard dcCandidates = mp.discovered_check_candidates(); Color us = pos.side_to_move(); bool isCheck = pos.is_check(); bool mateThreat = pos.has_mate_threat(opposite_color(us)); + MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]); + Bitboard dcCandidates = mp.discovered_check_candidates(); + // Loop through all legal moves until no moves remain or a beta cutoff // occurs. while ( alpha < beta @@ -1109,7 +1081,7 @@ namespace { { assert(move_is_ok(move)); - bool singleReply = (isCheck && mp.number_of_moves() == 1); + bool singleReply = (isCheck && mp.number_of_evasions() == 1); bool moveIsCheck = pos.move_is_check(move, dcCandidates); bool moveIsCapture = pos.move_is_capture(move); @@ -1246,7 +1218,7 @@ namespace { // Initialize, and make an early exit in case of an aborted search, // an instant draw, maximum ply reached, etc. - init_node(pos, ss, ply, threadID); + init_node(ss, ply, threadID); // After init_node() that calls poll() if (AbortSearch || thread_should_stop(threadID)) @@ -1358,6 +1330,10 @@ namespace { bool useFutilityPruning = depth < SelectiveDepth && !isCheck; + // Avoid calling evaluate() if we already have the score in TT + if (tte && (tte->type() & VALUE_TYPE_EVAL)) + futilityValue = value_from_tt(tte->value(), ply) + FutilityMargins[int(depth) - 2]; + // Loop through all legal moves until no moves remain or a beta cutoff // occurs. while ( bestValue < beta @@ -1366,7 +1342,7 @@ namespace { { assert(move_is_ok(move)); - bool singleReply = (isCheck && mp.number_of_moves() == 1); + bool singleReply = (isCheck && mp.number_of_evasions() == 1); bool moveIsCheck = pos.move_is_check(move, dcCandidates); bool moveIsCapture = pos.move_is_capture(move); @@ -1502,7 +1478,7 @@ namespace { // Initialize, and make an early exit in case of an aborted search, // an instant draw, maximum ply reached, etc. - init_node(pos, ss, ply, threadID); + init_node(ss, ply, threadID); // After init_node() that calls poll() if (AbortSearch || thread_should_stop(threadID)) @@ -1535,7 +1511,7 @@ namespace { if (isCheck) staticValue = -VALUE_INFINITE; - else if (tte && tte->type() == VALUE_TYPE_EVAL) + else if (tte && (tte->type() & VALUE_TYPE_EVAL)) { // Use the cached evaluation score if possible assert(ei.futilityMargin == Value(0)); @@ -1556,7 +1532,7 @@ namespace { { // Store the score to avoid a future costly evaluation() call if (!isCheck && !tte && ei.futilityMargin == 0) - TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EVAL, Depth(-127*OnePly), MOVE_NONE); + TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EV_LO, Depth(-127*OnePly), MOVE_NONE); return bestValue; } @@ -1644,9 +1620,13 @@ namespace { Move m = ss[ply].pv[ply]; if (!pvNode) { + // If bestValue isn't changed it means it is still the static evaluation of + // the node, so keep this info to avoid a future costly evaluation() call. + ValueType type = (bestValue == staticValue && !ei.futilityMargin ? VALUE_TYPE_EV_UP : VALUE_TYPE_UPPER); Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1)); + if (bestValue < beta) - TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, d, MOVE_NONE); + TT.store(pos.get_key(), value_to_tt(bestValue, ply), type, d, MOVE_NONE); else TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, m); } @@ -1962,15 +1942,15 @@ namespace { bool includeAllMoves = (searchMoves[0] == MOVE_NONE); // Generate all legal moves - int lm_count = generate_legal_moves(pos, mlist); + MoveStack* last = generate_moves(pos, mlist); // Add each move to the moves[] array - for (int i = 0; i < lm_count; i++) + for (MoveStack* cur = mlist; cur != last; cur++) { bool includeMove = includeAllMoves; for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++) - includeMove = (searchMoves[k] == mlist[i].move); + includeMove = (searchMoves[k] == cur->move); if (!includeMove) continue; @@ -1978,8 +1958,9 @@ namespace { // Find a quick score for the move StateInfo st; SearchStack ss[PLY_MAX_PLUS_2]; + init_ss_array(ss); - moves[count].move = mlist[i].move; + moves[count].move = cur->move; pos.do_move(moves[count].move, st); moves[count].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1, 0); pos.undo_move(moves[count].move); @@ -2089,14 +2070,11 @@ namespace { // NodesBetweenPolls nodes, init_node() also calls poll(), which polls // for user input and checks whether it is time to stop the search. - void init_node(const Position& pos, SearchStack ss[], int ply, int threadID) { + void init_node(SearchStack ss[], int ply, int threadID) { assert(ply >= 0 && ply < PLY_MAX); assert(threadID >= 0 && threadID < ActiveThreads); - if (Slowdown && Iteration >= 3) - slowdown(pos); - Threads[threadID].nodes++; if (threadID == 0) @@ -2153,7 +2131,9 @@ namespace { // the second move is assumed to be a move from the current position. bool connected_moves(const Position& pos, Move m1, Move m2) { + Square f1, t1, f2, t2; + Piece p; assert(move_is_ok(m1)); assert(move_is_ok(m2)); @@ -2179,31 +2159,32 @@ namespace { return true; // Case 4: The destination square for m2 is attacked by the moving piece in m1 - if (pos.piece_attacks_square(pos.piece_on(t1), t1, t2)) + p = pos.piece_on(t1); + if (bit_is_set(pos.attacks_from(p, t1), t2)) return true; // Case 5: Discovered check, checking piece is the piece moved in m1 - if ( piece_is_slider(pos.piece_on(t1)) + if ( piece_is_slider(p) && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2) - && !bit_is_set(squares_between(t2, pos.king_square(pos.side_to_move())), t2)) + && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2)) { Bitboard occ = pos.occupied_squares(); Color us = pos.side_to_move(); Square ksq = pos.king_square(us); clear_bit(&occ, f2); - if (pos.type_of_piece_on(t1) == BISHOP) + if (type_of_piece(p) == BISHOP) { if (bit_is_set(bishop_attacks_bb(ksq, occ), t1)) return true; } - else if (pos.type_of_piece_on(t1) == ROOK) + else if (type_of_piece(p) == ROOK) { if (bit_is_set(rook_attacks_bb(ksq, occ), t1)) return true; } else { - assert(pos.type_of_piece_on(t1) == QUEEN); + assert(type_of_piece(p) == QUEEN); if (bit_is_set(queen_attacks_bb(ksq, occ), t1)) return true; } @@ -2431,20 +2412,6 @@ namespace { } - // slowdown() simply wastes CPU cycles doing nothing useful. It's used - // in strength handicap mode. - - void slowdown(const Position &pos) { - int i, n; - n = Slowdown; - for (i = 0; i < n; i++) { - Square s = Square(i&63); - if (count_1s(pos.attacks_to(s)) > 63) - std::cout << "This can't happen, but I put this string here anyway, in order to prevent the compiler from optimizing away the useless computation." << std::endl; - } - } - - // fail_high_ply_1() checks if some thread is currently resolving a fail // high at ply 1 at the node below the first root node. This information // is used for time managment. @@ -2591,6 +2558,18 @@ namespace { } + // init_ss_array() does a fast reset of the first entries of a SearchStack array + + void init_ss_array(SearchStack ss[]) { + + for (int i = 0; i < 3; i++) + { + ss[i].init(i); + ss[i].initKillers(); + } + } + + // wait_for_stop_or_ponderhit() is called when the maximum depth is reached // while the program is pondering. The point is to work around a wrinkle in // the UCI protocol: When pondering, the engine is not allowed to give a