X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fmovepick.cpp;h=3fe09bb7391260bdf94f6eee465c86dee3f82374;hp=44ce291214facb04d7d05c7ff232b68c88fb48cb;hb=59f64fda4fffe595d53183caae94b1d9a2062f32;hpb=519b2fe849760d3cab5cce9ef9dc3cd076bd300d diff --git a/src/movepick.cpp b/src/movepick.cpp index 44ce2912..3fe09bb7 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -35,7 +35,7 @@ namespace { STOP }; - // Our insertion sort, which is guaranteed (and also needed) to be stable + // Our insertion sort, which is guaranteed to be stable, as it should be void insertion_sort(ExtMove* begin, ExtMove* end) { ExtMove tmp, *p, *q; @@ -49,14 +49,15 @@ namespace { } } - // 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) + // 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. + Move pick_best(ExtMove* begin, ExtMove* end) { std::swap(*begin, *std::max_element(begin, end)); - return begin; + return *begin; } + } // namespace @@ -66,14 +67,13 @@ namespace { /// search captures, promotions and some checks) and how important good move /// ordering is at the current node. -MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats& h, - Move* cm, Move* fm, Search::Stack* s) : pos(p), history(h), depth(d) { +MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats& h, const CounterMovesHistoryStats& cmh, + Move cm, Search::Stack* s) : pos(p), history(h), counterMovesHistory(cmh), depth(d) { assert(d > DEPTH_ZERO); endBadCaptures = moves + MAX_MOVES - 1; - countermoves = cm; - followupmoves = fm; + countermove = cm; ss = s; if (pos.checkers()) @@ -86,8 +86,8 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats& endMoves += (ttMove != MOVE_NONE); } -MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats& h, - Square s) : pos(p), history(h) { +MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats& h, const CounterMovesHistoryStats& cmh, + Square s) : pos(p), history(h), counterMovesHistory(cmh) { assert(d <= DEPTH_ZERO); @@ -111,8 +111,8 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats& endMoves += (ttMove != MOVE_NONE); } -MovePicker::MovePicker(const Position& p, Move ttm, const HistoryStats& h, PieceType pt) - : pos(p), history(h) { +MovePicker::MovePicker(const Position& p, Move ttm, const HistoryStats& h, const CounterMovesHistoryStats& cmh, PieceType pt) + : pos(p), history(h), counterMovesHistory(cmh) { assert(!pos.checkers()); @@ -134,10 +134,10 @@ MovePicker::MovePicker(const Position& p, Move ttm, const HistoryStats& h, Piece /// highest values will be picked first. template<> void MovePicker::score() { - // Winning and equal captures in the main search are ordered by MVV/LVA. + // Winning and equal captures in the main search are ordered by MVV. // Suprisingly, this appears to perform slightly better than SEE based // move ordering. The reason is probably that in a position with a winning - // capture, capturing a more valuable (but sufficiently defended) piece + // capture, capturing a valuable (but sufficiently defended) piece // first usually doesn't hurt. The opponent will have to recapture, and // the hanging piece will still be hanging (except in the unusual cases // where it is possible to recapture with the hanging piece). Exchanging @@ -147,22 +147,20 @@ 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) - if (type_of(m) == ENPASSANT) - m.value = PieceValue[MG][PAWN] - Value(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))); + for (auto& m : *this){ + m.value = PieceValue[MG][pos.piece_on(to_sq(m))] - 200*relative_rank(pos.side_to_move(), to_sq(m)); + } } template<> void MovePicker::score() { + + Square prevSq = to_sq((ss-1)->currentMove); + const HistoryStats& cmh = counterMovesHistory[pos.piece_on(prevSq)][prevSq]; + for (auto& m : *this) - m.value = history[pos.moved_piece(m)][to_sq(m)]; + m.value = history[pos.moved_piece(m)][to_sq(m)] + + cmh[pos.moved_piece(m)][to_sq(m)] * 3; } template<> @@ -196,72 +194,59 @@ void MovePicker::generate_next_stage() { case CAPTURES_S1: case CAPTURES_S3: case CAPTURES_S4: case CAPTURES_S5: case CAPTURES_S6: endMoves = generate(pos, moves); score(); - return; + break; case KILLERS_S1: cur = killers; endMoves = cur + 2; - 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; - - // 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. + killers[0] = ss->killers[0]; + killers[1] = ss->killers[1]; + killers[2].move = MOVE_NONE; // Be sure countermoves are different from killers - for (int i = 0; i < 2; ++i) - if ( countermoves[i] != (cur+0)->move - && countermoves[i] != (cur+1)->move) - (endMoves++)->move = countermoves[i]; - - // Be sure followupmoves are different from killers and countermoves - for (int i = 0; i < 2; ++i) - if ( followupmoves[i] != (cur+0)->move - && followupmoves[i] != (cur+1)->move - && followupmoves[i] != (cur+2)->move - && followupmoves[i] != (cur+3)->move) - (endMoves++)->move = followupmoves[i]; - return; + if ( countermove != killers[0] + && countermove != killers[1]) + *endMoves++ = countermove; + break; case QUIETS_1_S1: endQuiets = endMoves = generate(pos, moves); score(); endMoves = std::partition(cur, endMoves, [](const ExtMove& m) { return m.value > VALUE_ZERO; }); insertion_sort(cur, endMoves); - return; + break; case QUIETS_2_S1: cur = endMoves; endMoves = endQuiets; if (depth >= 3 * ONE_PLY) insertion_sort(cur, endMoves); - return; + break; case BAD_CAPTURES_S1: // Just pick them in reverse order to get MVV/LVA ordering cur = moves + MAX_MOVES - 1; endMoves = endBadCaptures; - return; + break; case EVASIONS_S2: endMoves = generate(pos, moves); - if (endMoves > moves + 1) + if (endMoves - moves > 1) score(); - return; + break; case QUIET_CHECKS_S3: endMoves = generate(pos, moves); - return; + break; case EVASION: case QSEARCH_0: case QSEARCH_1: case PROBCUT: case RECAPTURE: stage = STOP; /* Fall through */ case STOP: - endMoves = cur + 1; // Avoid another next_phase() call - return; + endMoves = cur + 1; // Avoid another generate_next_stage() call + break; default: assert(false); @@ -290,19 +275,19 @@ Move MovePicker::next_move() { return ttMove; case CAPTURES_S1: - move = pick_best(cur++, endMoves)->move; + move = pick_best(cur++, endMoves); if (move != ttMove) { if (pos.see_sign(move) >= VALUE_ZERO) return move; // Losing capture, move it to the tail of the array - (endBadCaptures--)->move = move; + *endBadCaptures-- = move; } break; case KILLERS_S1: - move = (cur++)->move; + move = *cur++; if ( move != MOVE_NONE && move != ttMove && pos.pseudo_legal(move) @@ -311,40 +296,37 @@ Move MovePicker::next_move() { break; case QUIETS_1_S1: case QUIETS_2_S1: - move = (cur++)->move; + move = *cur++; if ( move != ttMove - && move != killers[0].move - && move != killers[1].move - && move != killers[2].move - && move != killers[3].move - && move != killers[4].move - && move != killers[5].move) + && move != killers[0] + && move != killers[1] + && move != killers[2]) return move; break; case BAD_CAPTURES_S1: - return (cur--)->move; + return *cur--; case EVASIONS_S2: case CAPTURES_S3: case CAPTURES_S4: - move = pick_best(cur++, endMoves)->move; + move = pick_best(cur++, endMoves); if (move != ttMove) return move; break; case CAPTURES_S5: - move = pick_best(cur++, endMoves)->move; + move = pick_best(cur++, endMoves); if (move != ttMove && pos.see(move) > captureThreshold) return move; break; case CAPTURES_S6: - move = pick_best(cur++, endMoves)->move; + move = pick_best(cur++, endMoves); if (to_sq(move) == recaptureSquare) return move; break; case QUIET_CHECKS_S3: - move = (cur++)->move; + move = *cur++; if (move != ttMove) return move; break;