X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=a4ea9aa4b36e455057c66aa6934b99896fe62dca;hp=02907a80f9d63dcc883a508c6791f76fd7660bfa;hb=93bc05cf693064b80bf70cb97c6d110ab8f0a015;hpb=55b6464d4096edae032c67d829acff69705b22a6 diff --git a/src/search.cpp b/src/search.cpp index 02907a80..a4ea9aa4 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -144,7 +144,7 @@ namespace { bool UseFutilityPruning = true; // Margins for futility pruning in the quiescence search, at frontier - // nodes, and at pre-frontier nodes: + // nodes, and at pre-frontier nodes Value FutilityMargin0 = Value(0x80); Value FutilityMargin1 = Value(0x100); Value FutilityMargin2 = Value(0x300); @@ -167,21 +167,22 @@ namespace { Depth PawnEndgameExtension[2] = {OnePly, OnePly}; Depth MateThreatExtension[2] = {Depth(0), Depth(0)}; - // Search depth at iteration 1: + // Search depth at iteration 1 const Depth InitialDepth = OnePly /*+ OnePly/2*/; // Node counters int NodesSincePoll; int NodesBetweenPolls = 30000; - // Iteration counter: + // Iteration counter int Iteration; + bool LastIterations; // Scores and number of times the best move changed for each iteration: Value ValueByIteration[PLY_MAX_PLUS_2]; int BestMoveChangesByIteration[PLY_MAX_PLUS_2]; - // MultiPV mode: + // MultiPV mode int MultiPV = 1; // Time managment variables @@ -237,6 +238,7 @@ namespace { Depth depth, int ply, int threadID); void sp_search(SplitPoint *sp, int threadID); void sp_search_pv(SplitPoint *sp, int threadID); + void init_search_stack(SearchStack ss); void init_search_stack(SearchStack ss[]); void init_node(const Position &pos, SearchStack ss[], int ply, int threadID); void update_pv(SearchStack ss[], int ply); @@ -297,6 +299,9 @@ Lock IOLock; History H; // Should be made local? +// The empty search stack +SearchStack EmptySearchStack; + //// //// Functions @@ -561,6 +566,9 @@ void init_threads() { // Wait until the thread has finished launching: while (!Threads[i].running); } + + // Init also the empty search stack + init_search_stack(EmptySearchStack); } @@ -617,6 +625,7 @@ namespace { ValueByIteration[0] = Value(0); ValueByIteration[1] = rml.get_move_score(0); Iteration = 1; + LastIterations = false; EasyMove = rml.scan_for_easy_move(); @@ -675,6 +684,9 @@ namespace { if (ExtraSearchTime > 0 && TimeAdvantage > 2 * MaxSearchTime) ExtraSearchTime += MaxSearchTime / 2; + // Try to guess if the current iteration is the last one or the last two + LastIterations = (current_search_time() > ((MaxSearchTime + ExtraSearchTime)*58) / 128); + // Stop search if most of MaxSearchTime is consumed at the end of the // iteration. We probably don't have enough time to search the first // move at the next iteration anyway. @@ -933,8 +945,7 @@ namespace { // Initialize a MovePicker object for the current position, and prepare // to search all moves - MovePicker mp = MovePicker(pos, true, ttMove, ss[ply].mateKiller, - ss[ply].killer1, ss[ply].killer2, depth); + MovePicker mp = MovePicker(pos, true, ttMove, ss[ply], depth); Move move, movesSearched[256]; int moveCount = 0; @@ -960,11 +971,11 @@ namespace { movesSearched[moveCount++] = ss[ply].currentMove = move; if (moveIsCapture) - ss[ply].currentMoveCaptureValue = pos.midgame_value_of_piece_on(move_to(move)); + ss[ply].currentMoveCaptureValue = pos.midgame_value_of_piece_on(move_to(move)); else if (move_is_ep(move)) - ss[ply].currentMoveCaptureValue = PawnValueMidgame; + ss[ply].currentMoveCaptureValue = PawnValueMidgame; else - ss[ply].currentMoveCaptureValue = Value(0); + ss[ply].currentMoveCaptureValue = Value(0); // Decide the new search depth Depth ext = extension(pos, move, true, moveIsCheck, singleReply, mateThreat); @@ -987,8 +998,8 @@ namespace { && !move_promotion(move) && !moveIsPassedPawnPush && !move_is_castle(move) - && move != ss[ply].killer1 - && move != ss[ply].killer2) + && move != ss[ply].killers[0] + && move != ss[ply].killers[1]) { ss[ply].reduction = OnePly; value = -search(pos, ss, -alpha, newDepth-OnePly, ply+1, true, threadID); @@ -1070,10 +1081,10 @@ namespace { if (ok_to_history(pos, m)) // Only non capture moves are considered { update_history(pos, m, depth, movesSearched, moveCount); - if (m != ss[ply].killer1) + if (m != ss[ply].killers[0]) { - ss[ply].killer2 = ss[ply].killer1; - ss[ply].killer1 = m; + ss[ply].killers[1] = ss[ply].killers[0]; + ss[ply].killers[0] = m; } } TT.store(pos, value_to_tt(bestValue, ply), depth, m, VALUE_TYPE_LOWER); @@ -1143,7 +1154,8 @@ namespace { UndoInfo u; pos.do_null_move(u); - Value nullValue = -search(pos, ss, -(beta-1), depth-4*OnePly, ply+1, false, threadID); + int R = (depth > 7 ? 4 : 3); + Value nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID); pos.undo_null_move(u); if (nullValue >= beta) @@ -1191,8 +1203,7 @@ namespace { // Initialize a MovePicker object for the current position, and prepare // to search all moves: - MovePicker mp = MovePicker(pos, false, ttMove, ss[ply].mateKiller, - ss[ply].killer1, ss[ply].killer2, depth); + MovePicker mp = MovePicker(pos, false, ttMove, ss[ply], depth); Move move, movesSearched[256]; int moveCount = 0; @@ -1261,8 +1272,8 @@ namespace { && !move_promotion(move) && !moveIsPassedPawnPush && !move_is_castle(move) - && move != ss[ply].killer1 - && move != ss[ply].killer2) + && move != ss[ply].killers[0] + && move != ss[ply].killers[1]) { ss[ply].reduction = OnePly; value = -search(pos, ss, -(beta-1), newDepth-OnePly, ply+1, true, threadID); @@ -1321,10 +1332,10 @@ namespace { if (ok_to_history(pos, m)) // Only non capture moves are considered { update_history(pos, m, depth, movesSearched, moveCount); - if (m != ss[ply].killer1) + if (m != ss[ply].killers[0]) { - ss[ply].killer2 = ss[ply].killer1; - ss[ply].killer1 = m; + ss[ply].killers[1] = ss[ply].killers[0]; + ss[ply].killers[0] = m; } } TT.store(pos, value_to_tt(bestValue, ply), depth, m, VALUE_TYPE_LOWER); @@ -1382,12 +1393,13 @@ namespace { // 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) will be generated. - MovePicker mp = MovePicker(pos, false, MOVE_NONE, MOVE_NONE, MOVE_NONE, - MOVE_NONE, depth); + MovePicker mp = MovePicker(pos, false, MOVE_NONE, EmptySearchStack, depth, &ei); Move move; int moveCount = 0; Bitboard dcCandidates = mp.discovered_check_candidates(); bool isCheck = pos.is_check(); + bool pvNode = (beta - alpha != 1); + bool enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame; // Loop through the moves until no moves remain or a beta cutoff // occurs. @@ -1408,8 +1420,8 @@ namespace { && !moveIsCheck && !move_promotion(move) && !moveIsPassedPawnPush - && beta - alpha == 1 - && pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame) + && !pvNode + && enoughMaterial) { Value futilityValue = staticValue + Max(pos.midgame_value_of_piece_on(move_to(move)), @@ -1425,9 +1437,10 @@ namespace { } } - // Don't search captures and checks with negative SEE values. + // Don't search captures and checks with negative SEE values if ( !isCheck && !move_promotion(move) + && !pvNode && (pos.midgame_value_of_piece_on(move_from(move)) > pos.midgame_value_of_piece_on(move_to(move))) && pos.see(move) < 0) @@ -1463,6 +1476,18 @@ namespace { // Update transposition table TT.store(pos, value_to_tt(bestValue, ply), depth, MOVE_NONE, VALUE_TYPE_EXACT); + // Update killers only for good check moves + Move m = ss[ply].currentMove; + if (alpha >= beta && ok_to_history(pos, m)) // Only non capture moves are considered + { + // Wrong to update history when depth is <= 0 + + if (m != ss[ply].killers[0]) + { + ss[ply].killers[1] = ss[ply].killers[0]; + ss[ply].killers[0] = m; + } + } return bestValue; } @@ -1531,8 +1556,8 @@ namespace { && !moveIsPassedPawnPush && !move_promotion(move) && !move_is_castle(move) - && move != ss[sp->ply].killer1 - && move != ss[sp->ply].killer2) + && move != ss[sp->ply].killers[0] + && move != ss[sp->ply].killers[1]) { ss[sp->ply].reduction = OnePly; value = -search(pos, ss, -(sp->beta-1), newDepth - OnePly, sp->ply+1, true, threadID); @@ -1639,8 +1664,8 @@ namespace { && !moveIsPassedPawnPush && !move_promotion(move) && !move_is_castle(move) - && move != ss[sp->ply].killer1 - && move != ss[sp->ply].killer2) + && move != ss[sp->ply].killers[0] + && move != ss[sp->ply].killers[1]) { ss[sp->ply].reduction = OnePly; value = -search(pos, ss, -sp->alpha, newDepth - OnePly, sp->ply+1, true, threadID); @@ -1871,17 +1896,28 @@ namespace { // init_search_stack() initializes a search stack at the beginning of a // new search from the root. + void init_search_stack(SearchStack ss) { + + ss.pv[0] = MOVE_NONE; + ss.pv[1] = MOVE_NONE; + ss.currentMove = MOVE_NONE; + ss.threatMove = MOVE_NONE; + ss.reduction = Depth(0); + for (int j = 0; j < KILLER_MAX; j++) + ss.killers[j] = MOVE_NONE; + } void init_search_stack(SearchStack ss[]) { - for(int i = 0; i < 3; i++) { - ss[i].pv[i] = MOVE_NONE; - ss[i].pv[i+1] = MOVE_NONE; - ss[i].currentMove = MOVE_NONE; - ss[i].mateKiller = MOVE_NONE; - ss[i].killer1 = MOVE_NONE; - ss[i].killer2 = MOVE_NONE; - ss[i].threatMove = MOVE_NONE; - ss[i].reduction = Depth(0); + + for (int i = 0; i < 3; i++) + { + ss[i].pv[i] = MOVE_NONE; + ss[i].pv[i+1] = MOVE_NONE; + ss[i].currentMove = MOVE_NONE; + ss[i].threatMove = MOVE_NONE; + ss[i].reduction = Depth(0); + for (int j = 0; j < KILLER_MAX; j++) + ss[i].killers[j] = MOVE_NONE; } } @@ -1908,7 +1944,7 @@ namespace { ss[ply].pv[ply] = ss[ply].pv[ply+1] = ss[ply].currentMove = MOVE_NONE; ss[ply+2].mateKiller = MOVE_NONE; - ss[ply+2].killer1 = ss[ply+2].killer2 = MOVE_NONE; + ss[ply+2].killers[0] = ss[ply+2].killers[1] = MOVE_NONE; ss[ply].threatMove = MOVE_NONE; ss[ply].reduction = Depth(0); ss[ply].currentMoveCaptureValue = Value(0); @@ -2038,9 +2074,9 @@ namespace { if (mateThreat) result += MateThreatExtension[pvNode]; - if ( pos.midgame_value_of_piece_on(move_to(m)) >= RookValueMidgame - && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK) - - pos.midgame_value_of_piece_on(move_to(m)) == Value(0)) + if ( pos.midgame_value_of_piece_on(move_to(m)) >= RookValueMidgame + && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK) + - pos.midgame_value_of_piece_on(move_to(m)) == Value(0)) && !move_promotion(m)) result += PawnEndgameExtension[pvNode]; @@ -2137,13 +2173,11 @@ namespace { // ok_to_history() returns true if a move m can be stored - // in history. Should be a non capturing move. + // in history. Should be a non capturing move nor a promotion. bool ok_to_history(const Position& pos, Move m) { - return pos.square_is_empty(move_to(m)) - && !move_promotion(m) - && !move_is_ep(m); + return !pos.move_is_capture(m) && !move_promotion(m); } @@ -2156,8 +2190,11 @@ namespace { H.success(pos.piece_on(move_from(m)), m, depth); for (int i = 0; i < moveCount - 1; i++) - if (ok_to_history(pos, movesSearched[i]) && m != movesSearched[i]) + { + assert(m != movesSearched[i]); + if (ok_to_history(pos, movesSearched[i])) H.failure(pos.piece_on(move_from(movesSearched[i])), movesSearched[i]); + } } // fail_high_ply_1() checks if some thread is currently resolving a fail