X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=3f4ad24ca17652319456568ef0169d1ab1ecd7e4;hp=97ed196acede459112754e6892f2b88fba8a75cc;hb=18677852315b960132b0e8daa220c83b1c3c17cd;hpb=e7bad2687a26655e128fec04b58bbcdaaaf910cd diff --git a/src/search.cpp b/src/search.cpp index 97ed196a..3f4ad24c 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -238,19 +238,20 @@ 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); void sp_update_pv(SearchStack *pss, SearchStack ss[], int ply); bool connected_moves(const Position &pos, Move m1, Move m2); - Depth extension(const Position &pos, Move m, bool pvNode, bool check, - bool singleReply, bool mateThreat); + bool move_is_killer(Move m, const SearchStack& ss); + Depth extension(const Position &pos, Move m, bool pvNode, bool check, bool singleReply, bool mateThreat); bool ok_to_do_nullmove(const Position &pos); bool ok_to_prune(const Position &pos, Move m, Move threat, Depth d); bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply); 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_history(const Position& pos, Move m, Depth depth, Move movesSearched[], int moveCount); + void update_killers(Move m, SearchStack& ss); bool fail_high_ply_1(); int current_search_time(); @@ -298,6 +299,9 @@ Lock IOLock; History H; // Should be made local? +// The empty search stack +SearchStack EmptySearchStack; + //// //// Functions @@ -426,8 +430,8 @@ void think(const Position &pos, bool infinite, bool ponder, int side_to_move, TimeAdvantage = myTime - oppTime; if (!movesToGo) // Sudden death time control - { - if (increment) + { + if (myIncrement) { MaxSearchTime = myTime / 30 + myIncrement; AbsoluteMaxSearchTime = Max(myTime / 4, myIncrement - 100); @@ -562,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); } @@ -788,7 +795,7 @@ namespace { if (Problem && StopOnPonderhit) StopOnPonderhit = false; - } + } else { value = -search(pos, ss, -alpha, newDepth, 1, true, 0); @@ -938,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; @@ -992,8 +998,7 @@ namespace { && !move_promotion(move) && !moveIsPassedPawnPush && !move_is_castle(move) - && move != ss[ply].killer1 - && move != ss[ply].killer2) + && !move_is_killer(move, ss[ply])) { ss[ply].reduction = OnePly; value = -search(pos, ss, -alpha, newDepth-OnePly, ply+1, true, threadID); @@ -1075,11 +1080,7 @@ 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) - { - ss[ply].killer2 = ss[ply].killer1; - ss[ply].killer1 = m; - } + update_killers(m, ss[ply]); } TT.store(pos, value_to_tt(bestValue, ply), depth, m, VALUE_TYPE_LOWER); } @@ -1197,8 +1198,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; @@ -1267,8 +1267,7 @@ namespace { && !move_promotion(move) && !moveIsPassedPawnPush && !move_is_castle(move) - && move != ss[ply].killer1 - && move != ss[ply].killer2) + && !move_is_killer(move, ss[ply])) { ss[ply].reduction = OnePly; value = -search(pos, ss, -(beta-1), newDepth-OnePly, ply+1, true, threadID); @@ -1327,11 +1326,7 @@ 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) - { - ss[ply].killer2 = ss[ply].killer1; - ss[ply].killer1 = m; - } + update_killers(m, ss[ply]); } TT.store(pos, value_to_tt(bestValue, ply), depth, m, VALUE_TYPE_LOWER); } @@ -1388,12 +1383,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. @@ -1414,8 +1410,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)), @@ -1431,7 +1427,7 @@ 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) && (pos.midgame_value_of_piece_on(move_from(move)) > @@ -1469,6 +1465,13 @@ 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 + update_killers(m, ss[ply]); + } return bestValue; } @@ -1537,8 +1540,7 @@ namespace { && !moveIsPassedPawnPush && !move_promotion(move) && !move_is_castle(move) - && move != ss[sp->ply].killer1 - && move != ss[sp->ply].killer2) + && !move_is_killer(move, ss[sp->ply])) { ss[sp->ply].reduction = OnePly; value = -search(pos, ss, -(sp->beta-1), newDepth - OnePly, sp->ply+1, true, threadID); @@ -1645,8 +1647,7 @@ namespace { && !moveIsPassedPawnPush && !move_promotion(move) && !move_is_castle(move) - && move != ss[sp->ply].killer1 - && move != ss[sp->ply].killer2) + && !move_is_killer(move, ss[sp->ply])) { ss[sp->ply].reduction = OnePly; value = -search(pos, ss, -sp->alpha, newDepth - OnePly, sp->ply+1, true, threadID); @@ -1877,17 +1878,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; } } @@ -1914,10 +1926,11 @@ 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].threatMove = MOVE_NONE; ss[ply].reduction = Depth(0); ss[ply].currentMoveCaptureValue = Value(0); + for (int j = 0; j < KILLER_MAX; j++) + ss[ply+2].killers[j] = MOVE_NONE; if(Threads[threadID].printCurrentLine) print_current_line(ss, ply, threadID); @@ -2020,6 +2033,20 @@ namespace { } + // move_is_killer() checks if the given move is among the + // killer moves of that ply. + + bool move_is_killer(Move m, const SearchStack& ss) { + + const Move* k = ss.killers; + for (int i = 0; i < KILLER_MAX; i++, k++) + if (*k == m) + return true; + + return false; + } + + // extension() decides whether a move should be searched with normal depth, // or with extended depth. Certain classes of moves (checking moves, in // particular) are searched with bigger depth than ordinary moves. @@ -2044,12 +2071,12 @@ 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]; - + if ( pvNode && pos.move_is_capture(m) && pos.type_of_piece_on(move_to(m)) != PAWN @@ -2143,13 +2170,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); } @@ -2162,8 +2187,26 @@ 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]); + } + } + + + // update_killers() add a good move that produced a beta-cutoff + // among the killer moves of that ply. + + void update_killers(Move m, SearchStack& ss) { + + if (m == ss.killers[0]) + return; + + for (int i = KILLER_MAX - 1; i > 0; i--) + ss.killers[i] = ss.killers[i - 1]; + + ss.killers[0] = m; } // fail_high_ply_1() checks if some thread is currently resolving a fail