X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fmovepick.cpp;h=edee8179e2d7d3795446b628df14316925a72ae8;hb=856a5f3aaaf8b9d53599963decacd4476b55c034;hp=44ce291214facb04d7d05c7ff232b68c88fb48cb;hpb=519b2fe849760d3cab5cce9ef9dc3cd076bd300d;p=stockfish diff --git a/src/movepick.cpp b/src/movepick.cpp index 44ce2912..edee8179 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -49,6 +49,10 @@ namespace { } } + // 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. @@ -71,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; @@ -83,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); @@ -108,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()); @@ -126,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); } @@ -147,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<> @@ -170,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)]; + } } @@ -194,13 +213,13 @@ 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(); return; case KILLERS_S1: cur = killers; - endMoves = cur + 2; + end = cur + 2; killers[0].move = ss->killers[0]; killers[1].move = ss->killers[1]; @@ -214,7 +233,7 @@ void MovePicker::generate_next_stage() { for (int i = 0; i < 2; ++i) if ( countermoves[i] != (cur+0)->move && countermoves[i] != (cur+1)->move) - (endMoves++)->move = countermoves[i]; + (end++)->move = countermoves[i]; // Be sure followupmoves are different from killers and countermoves for (int i = 0; i < 2; ++i) @@ -222,37 +241,37 @@ void MovePicker::generate_next_stage() { && followupmoves[i] != (cur+1)->move && followupmoves[i] != (cur+2)->move && followupmoves[i] != (cur+3)->move) - (endMoves++)->move = followupmoves[i]; + (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); + 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); + 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; + end = endBadCaptures; return; case EVASIONS_S2: - endMoves = generate(pos, moves); - if (endMoves > moves + 1) + end = generate(pos, moves); + if (end > moves + 1) score(); return; case QUIET_CHECKS_S3: - endMoves = generate(pos, moves); + end = generate(pos, moves); return; case EVASION: case QSEARCH_0: case QSEARCH_1: case PROBCUT: case RECAPTURE: @@ -260,7 +279,7 @@ void MovePicker::generate_next_stage() { /* Fall through */ case STOP: - endMoves = cur + 1; // Avoid another next_phase() call + end = cur + 1; // Avoid another next_phase() call return; default: @@ -280,7 +299,7 @@ Move MovePicker::next_move() { while (true) { - while (cur == endMoves) + while (cur == end) generate_next_stage(); switch (stage) { @@ -290,7 +309,7 @@ Move MovePicker::next_move() { return ttMove; case CAPTURES_S1: - move = pick_best(cur++, endMoves)->move; + move = pick_best(cur++, end)->move; if (move != ttMove) { if (pos.see_sign(move) >= VALUE_ZERO) @@ -326,19 +345,19 @@ Move MovePicker::next_move() { return (cur--)->move; case EVASIONS_S2: case CAPTURES_S3: case CAPTURES_S4: - move = pick_best(cur++, endMoves)->move; + move = pick_best(cur++, end)->move; if (move != ttMove) return move; break; case CAPTURES_S5: - move = pick_best(cur++, endMoves)->move; + 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; + move = pick_best(cur++, end)->move; if (to_sq(move) == recaptureSquare) return move; break;