X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fmovepick.cpp;h=edee8179e2d7d3795446b628df14316925a72ae8;hp=b3f413bf1ffa0bd20255ccd5f25893839dfd1e45;hb=856a5f3aaaf8b9d53599963decacd4476b55c034;hpb=6fa6da3ee13d2b7bdbec3cd24ff8ca43233c74fb diff --git a/src/movepick.cpp b/src/movepick.cpp index b3f413bf..edee8179 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -35,7 +35,7 @@ namespace { STOP }; - // Our insertion sort, which is guaranteed to be stable, as it should be + // Our insertion sort, which is guaranteed (and also needed) to be stable void insertion_sort(ExtMove* begin, ExtMove* end) { ExtMove tmp, *p, *q; @@ -49,15 +49,18 @@ namespace { } } - // pick_best() finds the best move in the range (begin, end) and moves it to - // the front. It's faster than sorting all the moves in advance when there - // are few moves e.g. the possible captures. - inline Move pick_best(ExtMove* begin, ExtMove* end) + // Unary predicate used by std::partition to split positive values from remaining + // ones so as to sort the two sets separately, with the second sort delayed. + inline bool has_positive_value(const ExtMove& move) { return move.value > VALUE_ZERO; } + + // Picks the best move in the range (begin, end) and moves it to the front. + // It's faster than sorting all the moves in advance when there are few + // moves e.g. possible captures. + inline ExtMove* pick_best(ExtMove* begin, ExtMove* end) { std::swap(*begin, *std::max_element(begin, end)); - return *begin; + return begin; } - } // namespace @@ -72,6 +75,7 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats& assert(d > DEPTH_ZERO); + cur = end = moves; endBadCaptures = moves + MAX_MOVES - 1; countermoves = cm; followupmoves = fm; @@ -84,11 +88,11 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats& stage = MAIN_SEARCH; ttMove = (ttm && pos.pseudo_legal(ttm) ? ttm : MOVE_NONE); - endMoves += (ttMove != MOVE_NONE); + end += (ttMove != MOVE_NONE); } MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats& h, - Square s) : pos(p), history(h) { + Square s) : pos(p), history(h), cur(moves), end(moves) { assert(d <= DEPTH_ZERO); @@ -109,11 +113,11 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats& } ttMove = (ttm && pos.pseudo_legal(ttm) ? ttm : MOVE_NONE); - endMoves += (ttMove != MOVE_NONE); + end += (ttMove != MOVE_NONE); } MovePicker::MovePicker(const Position& p, Move ttm, const HistoryStats& h, PieceType pt) - : pos(p), history(h) { + : pos(p), history(h), cur(moves), end(moves) { assert(!pos.checkers()); @@ -127,7 +131,7 @@ MovePicker::MovePicker(const Position& p, Move ttm, const HistoryStats& h, Piece if (ttMove && (!pos.capture(ttMove) || pos.see(ttMove) <= captureThreshold)) ttMove = MOVE_NONE; - endMoves += (ttMove != MOVE_NONE); + end += (ttMove != MOVE_NONE); } @@ -148,22 +152,32 @@ void MovePicker::score() { // badCaptures[] array, but instead of doing it now we delay until the move // has been picked up in pick_move_from_list(). This way we save some SEE // calls in case we get a cutoff. - for (auto& m : *this) + Move m; + + for (ExtMove* it = moves; it != end; ++it) + { + m = it->move; + it->value = PieceValue[MG][pos.piece_on(to_sq(m))] + - Value(type_of(pos.moved_piece(m))); + if (type_of(m) == ENPASSANT) - m.value = PieceValue[MG][PAWN] - Value(PAWN); + it->value += PieceValue[MG][PAWN]; else if (type_of(m) == PROMOTION) - m.value = PieceValue[MG][pos.piece_on(to_sq(m))] - Value(PAWN) - + PieceValue[MG][promotion_type(m)] - PieceValue[MG][PAWN]; - else - m.value = PieceValue[MG][pos.piece_on(to_sq(m))] - - Value(type_of(pos.moved_piece(m))); + it->value += PieceValue[MG][promotion_type(m)] - PieceValue[MG][PAWN]; + } } template<> void MovePicker::score() { - for (auto& m : *this) - m.value = history[pos.moved_piece(m)][to_sq(m)]; + + Move m; + + for (ExtMove* it = moves; it != end; ++it) + { + m = it->move; + it->value = history[pos.moved_piece(m)][to_sq(m)]; + } } template<> @@ -171,17 +185,21 @@ void MovePicker::score() { // Try good captures ordered by MVV/LVA, then non-captures if destination square // is not under attack, ordered by history value, then bad-captures and quiet // moves with a negative SEE. This last group is ordered by the SEE value. + Move m; Value see; - for (auto& m : *this) + for (ExtMove* it = moves; it != end; ++it) + { + m = it->move; if ((see = pos.see_sign(m)) < VALUE_ZERO) - m.value = see - HistoryStats::Max; // At the bottom + it->value = see - HistoryStats::Max; // At the bottom else if (pos.capture(m)) - m.value = PieceValue[MG][pos.piece_on(to_sq(m))] - - Value(type_of(pos.moved_piece(m))) + HistoryStats::Max; + it->value = PieceValue[MG][pos.piece_on(to_sq(m))] + - Value(type_of(pos.moved_piece(m))) + HistoryStats::Max; else - m.value = history[pos.moved_piece(m)][to_sq(m)]; + it->value = history[pos.moved_piece(m)][to_sq(m)]; + } } @@ -195,73 +213,74 @@ void MovePicker::generate_next_stage() { switch (++stage) { case CAPTURES_S1: case CAPTURES_S3: case CAPTURES_S4: case CAPTURES_S5: case CAPTURES_S6: - endMoves = generate(pos, moves); + end = generate(pos, moves); score(); - break; + return; case KILLERS_S1: cur = killers; - endMoves = cur + 2; + end = cur + 2; - killers[0] = ss->killers[0]; - killers[1] = ss->killers[1]; + killers[0].move = ss->killers[0]; + killers[1].move = ss->killers[1]; killers[2].move = killers[3].move = MOVE_NONE; killers[4].move = killers[5].move = MOVE_NONE; - // In SMP case countermoves[] and followupmoves[] could have duplicated entries - // in rare cases (less than 1 out of a million). This is harmless. + // Please note that following code is racy and could yield to rare (less + // than 1 out of a million) duplicated entries in SMP case. This is harmless. - // Be sure countermoves and followupmoves are different from killers + // Be sure countermoves are different from killers for (int i = 0; i < 2; ++i) - if ( countermoves[i] != killers[0] - && countermoves[i] != killers[1]) - *endMoves++ = countermoves[i]; + if ( countermoves[i] != (cur+0)->move + && countermoves[i] != (cur+1)->move) + (end++)->move = countermoves[i]; + // Be sure followupmoves are different from killers and countermoves for (int i = 0; i < 2; ++i) - if ( followupmoves[i] != killers[0] - && followupmoves[i] != killers[1] - && followupmoves[i] != killers[2] - && followupmoves[i] != killers[3]) - *endMoves++ = followupmoves[i]; - break; + if ( followupmoves[i] != (cur+0)->move + && followupmoves[i] != (cur+1)->move + && followupmoves[i] != (cur+2)->move + && followupmoves[i] != (cur+3)->move) + (end++)->move = followupmoves[i]; + return; case QUIETS_1_S1: - endQuiets = endMoves = generate(pos, moves); + endQuiets = end = generate(pos, moves); score(); - endMoves = std::partition(cur, endMoves, [](const ExtMove& m) { return m.value > VALUE_ZERO; }); - insertion_sort(cur, endMoves); - break; + end = std::partition(cur, end, has_positive_value); + insertion_sort(cur, end); + return; case QUIETS_2_S1: - cur = endMoves; - endMoves = endQuiets; + cur = end; + end = endQuiets; if (depth >= 3 * ONE_PLY) - insertion_sort(cur, endMoves); - break; + insertion_sort(cur, end); + return; case BAD_CAPTURES_S1: // Just pick them in reverse order to get MVV/LVA ordering cur = moves + MAX_MOVES - 1; - endMoves = endBadCaptures; - break; + end = endBadCaptures; + return; case EVASIONS_S2: - endMoves = generate(pos, moves); - if (endMoves - moves > 1) + end = generate(pos, moves); + if (end > moves + 1) score(); - break; + return; case QUIET_CHECKS_S3: - endMoves = generate(pos, moves); - break; + end = generate(pos, moves); + return; case EVASION: case QSEARCH_0: case QSEARCH_1: case PROBCUT: case RECAPTURE: stage = STOP; /* Fall through */ case STOP: - endMoves = cur + 1; // Avoid another generate_next_stage() call - break; + end = cur + 1; // Avoid another next_phase() call + return; default: assert(false); @@ -280,7 +299,7 @@ Move MovePicker::next_move() { while (true) { - while (cur == endMoves) + while (cur == end) generate_next_stage(); switch (stage) { @@ -290,19 +309,19 @@ Move MovePicker::next_move() { return ttMove; case CAPTURES_S1: - move = pick_best(cur++, endMoves); + move = pick_best(cur++, end)->move; if (move != ttMove) { if (pos.see_sign(move) >= VALUE_ZERO) return move; // Losing capture, move it to the tail of the array - *endBadCaptures-- = move; + (endBadCaptures--)->move = move; } break; case KILLERS_S1: - move = *cur++; + move = (cur++)->move; if ( move != MOVE_NONE && move != ttMove && pos.pseudo_legal(move) @@ -311,40 +330,40 @@ Move MovePicker::next_move() { break; case QUIETS_1_S1: case QUIETS_2_S1: - move = *cur++; + move = (cur++)->move; if ( move != ttMove - && move != killers[0] - && move != killers[1] - && move != killers[2] - && move != killers[3] - && move != killers[4] - && move != killers[5]) + && move != killers[0].move + && move != killers[1].move + && move != killers[2].move + && move != killers[3].move + && move != killers[4].move + && move != killers[5].move) return move; break; case BAD_CAPTURES_S1: - return *cur--; + return (cur--)->move; case EVASIONS_S2: case CAPTURES_S3: case CAPTURES_S4: - move = pick_best(cur++, endMoves); + move = pick_best(cur++, end)->move; if (move != ttMove) return move; break; case CAPTURES_S5: - move = pick_best(cur++, endMoves); + move = pick_best(cur++, end)->move; if (move != ttMove && pos.see(move) > captureThreshold) return move; break; case CAPTURES_S6: - move = pick_best(cur++, endMoves); + move = pick_best(cur++, end)->move; if (to_sq(move) == recaptureSquare) return move; break; case QUIET_CHECKS_S3: - move = *cur++; + move = (cur++)->move; if (move != ttMove) return move; break;