X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fmovepick.cpp;h=025f5b82cdeb2ae808d23c0e75a955862b48524b;hb=bae019b53e5c2bfcf0d69b4ebfc52b4f4de762eb;hp=eb686f7938837d23acb86e0812ea52e1f442d72d;hpb=5a0581498cde3d0904924d8ef7ed25ea1a2c855a;p=stockfish diff --git a/src/movepick.cpp b/src/movepick.cpp index eb686f79..025f5b82 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -1,14 +1,14 @@ /* Stockfish, a UCI chess playing engine derived from Glaurung 2.1 Copyright (C) 2004-2008 Tord Romstad (Glaurung author) - Copyright (C) 2008 Marco Costalba + Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad + Copyright (C) 2015-2020 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. - Stockfish is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the @@ -18,519 +18,254 @@ along with this program. If not, see . */ - -//// -//// Includes -//// - #include -#include "history.h" -#include "evaluate.h" -#include "movegen.h" #include "movepick.h" -#include "search.h" -#include "value.h" - - -//// -//// Local definitions -//// namespace { - /// Variables - - MovePicker::MovegenPhase PhaseTable[32]; - int MainSearchPhaseIndex; - int EvasionsPhaseIndex; - int QsearchWithChecksPhaseIndex; - int QsearchNoCapturesPhaseIndex; - int QsearchWithoutChecksPhaseIndex; - int NoMovesPhaseIndex; - -} - - + enum Stages { + MAIN_TT, CAPTURE_INIT, GOOD_CAPTURE, REFUTATION, QUIET_INIT, QUIET, BAD_CAPTURE, + EVASION_TT, EVASION_INIT, EVASION, + PROBCUT_TT, PROBCUT_INIT, PROBCUT, + QSEARCH_TT, QCAPTURE_INIT, QCAPTURE, QCHECK_INIT, QCHECK + }; -//// -//// Functions -//// + // partial_insertion_sort() sorts moves in descending order up to and including + // a given limit. The order of moves smaller than the limit is left unspecified. + void partial_insertion_sort(ExtMove* begin, ExtMove* end, int limit) { - -/// Constructor for the MovePicker class. Apart from the position for which -/// it is asked to pick legal moves, MovePicker also wants some information -/// to help it to return the presumably good moves first, to decide which -/// moves to return (in the quiescence search, for instance, we only want to -/// search captures, promotions and some checks) and about how important good -/// move ordering is at the current node. - -MovePicker::MovePicker(const Position& p, bool pv, Move ttm, - const SearchStack& ss, Depth d) : pos(p) { - pvNode = pv; - ttMove = ttm; - mateKiller = (ss.mateKiller == ttm)? MOVE_NONE : ss.mateKiller; - killer1 = ss.killers[0]; - killer2 = ss.killers[1]; - depth = d; - movesPicked = 0; - numOfMoves = 0; - numOfBadCaptures = 0; - - // With EvalInfo we are able to know how many captures are possible before - // generating them. So avoid generating in case we know are zero. - Color us = pos.side_to_move(); - Color them = opposite_color(us); - - if (p.is_check()) - phaseIndex = EvasionsPhaseIndex; - else if (depth > Depth(0)) - phaseIndex = MainSearchPhaseIndex; - else if (depth == Depth(0)) - phaseIndex = QsearchWithChecksPhaseIndex; - else - phaseIndex = QsearchWithoutChecksPhaseIndex; - - dc = p.discovered_check_candidates(us); - pinned = p.pinned_pieces(us); - - finished = false; -} - - -/// MovePicker::get_next_move() is the most important method of the MovePicker -/// class. It returns a new legal move every time it is called, until there -/// are no more moves left of the types we are interested in. - -Move MovePicker::get_next_move() { - - Move move; - - while (true) - { - // If we already have a list of generated moves, pick the best move from - // the list, and return it. - move = pick_move_from_list(); - if (move != MOVE_NONE) - { - assert(move_is_ok(move)); - return move; - } - - // Next phase - phaseIndex++; - switch (PhaseTable[phaseIndex]) { - - case PH_TT_MOVE: - if (ttMove != MOVE_NONE) + for (ExtMove *sortedEnd = begin, *p = begin + 1; p < end; ++p) + if (p->value >= limit) { - assert(move_is_ok(ttMove)); - if (move_is_legal(pos, ttMove, pinned)) - return ttMove; + ExtMove tmp = *p, *q; + *p = *++sortedEnd; + for (q = sortedEnd; q != begin && *(q - 1) < tmp; --q) + *q = *(q - 1); + *q = tmp; } - break; - - case PH_MATE_KILLER: - if (mateKiller != MOVE_NONE) - { - assert(move_is_ok(mateKiller)); - if (move_is_legal(pos, mateKiller, pinned)) - return mateKiller; - } - break; - - case PH_GOOD_CAPTURES: - numOfMoves = generate_captures(pos, moves); - score_captures(); - movesPicked = 0; - break; - - case PH_BAD_CAPTURES: - movesPicked = 0; - break; - - case PH_NONCAPTURES: - numOfMoves = generate_noncaptures(pos, moves); - score_noncaptures(); - movesPicked = 0; - break; - - case PH_EVASIONS: - assert(pos.is_check()); - numOfMoves = generate_evasions(pos, moves, pinned); - score_evasions(); - movesPicked = 0; - break; - - case PH_QCAPTURES: - numOfMoves = generate_captures(pos, moves); - score_qcaptures(); - movesPicked = 0; - break; - - case PH_QCHECKS: - numOfMoves = generate_checks(pos, moves, dc); - movesPicked = 0; - break; - - case PH_STOP: - return MOVE_NONE; - - default: - assert(false); - return MOVE_NONE; - } } -} - -/// A variant of get_next_move() which takes a lock as a parameter, used to -/// prevent multiple threads from picking the same move at a split point. +} // namespace -Move MovePicker::get_next_move(Lock &lock) { - lock_grab(&lock); - if (finished) - { - lock_release(&lock); - return MOVE_NONE; - } - Move m = get_next_move(); - if (m == MOVE_NONE) - finished = true; +/// Constructors of the MovePicker class. As arguments we pass information +/// to help it to return the (presumably) good moves first, to decide which +/// moves to return (in the quiescence search, for instance, we only want to +/// search captures, promotions, and some checks) and how important good move +/// ordering is at the current node. - lock_release(&lock); - return m; -} +/// MovePicker constructor for the main search +MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const ButterflyHistory* mh, + const CapturePieceToHistory* cph, const PieceToHistory** ch, Move cm, Move* killers) + : pos(p), mainHistory(mh), captureHistory(cph), continuationHistory(ch), + refutations{{killers[0], 0}, {killers[1], 0}, {cm, 0}}, depth(d) { + assert(d > 0); -/// MovePicker::score_captures(), MovePicker::score_noncaptures(), -/// MovePicker::score_evasions() and MovePicker::score_qcaptures() assign a -/// numerical move ordering score to each move in a move list. The moves -/// with highest scores will be picked first by pick_move_from_list(). - -void MovePicker::score_captures() { - // Winning and equal captures in the main search are ordered by MVV/LVA. - // 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 - // 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 - // big pieces before capturing a hanging piece probably helps to reduce - // the subtree size. - // While scoring captures it moves all captures with negative SEE values - // to the badCaptures[] array. - Move m; - int seeValue; - - for (int i = 0; i < numOfMoves; i++) - { - m = moves[i].move; - seeValue = pos.see(m); - if (seeValue >= 0) - { - if (move_promotion(m)) - moves[i].score = QueenValueMidgame; - else - moves[i].score = int(pos.midgame_value_of_piece_on(move_to(m))) - -int(pos.type_of_piece_on(move_from(m))); - } - else - { - // Losing capture, move it to the badCaptures[] array - assert(numOfBadCaptures < 63); - moves[i].score = seeValue; - badCaptures[numOfBadCaptures++] = moves[i]; - moves[i--] = moves[--numOfMoves]; - } - } + stage = pos.checkers() ? EVASION_TT : MAIN_TT; + ttMove = ttm && pos.pseudo_legal(ttm) ? ttm : MOVE_NONE; + stage += (ttMove == MOVE_NONE); } -void MovePicker::score_noncaptures() { - // First score by history, when no history is available then use - // piece/square tables values. This seems to be better then a - // random choice when we don't have an history for any move. - Move m; - int hs; +/// MovePicker constructor for quiescence search +MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const ButterflyHistory* mh, + const CapturePieceToHistory* cph, const PieceToHistory** ch, Square rs) + : pos(p), mainHistory(mh), captureHistory(cph), continuationHistory(ch), recaptureSquare(rs), depth(d) { - for (int i = 0; i < numOfMoves; i++) - { - m = moves[i].move; - - if (m == killer1) - hs = HistoryMax + 2; - else if (m == killer2) - hs = HistoryMax + 1; - else - hs = H.move_ordering_score(pos.piece_on(move_from(m)), m); + assert(d <= 0); - // Ensure history is always preferred to pst - if (hs > 0) - hs += 1000; - - // pst based scoring - moves[i].score = hs + pos.mg_pst_delta(m); - } + stage = pos.checkers() ? EVASION_TT : QSEARCH_TT; + ttMove = ttm + && (depth > DEPTH_QS_RECAPTURES || to_sq(ttm) == recaptureSquare) + && pos.pseudo_legal(ttm) ? ttm : MOVE_NONE; + stage += (ttMove == MOVE_NONE); } -void MovePicker::score_evasions() { +/// MovePicker constructor for ProbCut: we generate captures with SEE greater +/// than or equal to the given threshold. +MovePicker::MovePicker(const Position& p, Move ttm, Value th, const CapturePieceToHistory* cph) + : pos(p), captureHistory(cph), threshold(th) { - for (int i = 0; i < numOfMoves; i++) - { - Move m = moves[i].move; - if (m == ttMove) - moves[i].score = 2*HistoryMax; - else if (!pos.square_is_empty(move_to(m))) - { - int seeScore = pos.see(m); - moves[i].score = (seeScore >= 0)? seeScore + HistoryMax : seeScore; - } else - moves[i].score = H.move_ordering_score(pos.piece_on(move_from(m)), m); - } -} - -void MovePicker::score_qcaptures() { + assert(!pos.checkers()); - // Use MVV/LVA ordering - for (int i = 0; i < numOfMoves; i++) - { - Move m = moves[i].move; - if (move_promotion(m)) - moves[i].score = QueenValueMidgame; - else - moves[i].score = int(pos.midgame_value_of_piece_on(move_to(m))) - -int(pos.type_of_piece_on(move_from(m))); - } + stage = PROBCUT_TT; + ttMove = ttm + && pos.capture(ttm) + && pos.pseudo_legal(ttm) + && pos.see_ge(ttm, threshold) ? ttm : MOVE_NONE; + stage += (ttMove == MOVE_NONE); } +/// MovePicker::score() assigns a numerical value to each move in a list, used +/// for sorting. Captures are ordered by Most Valuable Victim (MVV), preferring +/// captures with a good history. Quiets moves are ordered using the histories. +template +void MovePicker::score() { -/// find_best_index() loops across the moves and returns index of -/// the highest scored one. There is also a second version that -/// lowers the priority of moves that attack the same square, -/// so that if the best move that attack a square fails the next -/// move picked attacks a different square if any, not the same one. - -int MovePicker::find_best_index() { + static_assert(Type == CAPTURES || Type == QUIETS || Type == EVASIONS, "Wrong type"); - assert(movesPicked < numOfMoves); + for (auto& m : *this) + if (Type == CAPTURES) + m.value = int(PieceValue[MG][pos.piece_on(to_sq(m))]) * 6 + + (*captureHistory)[pos.moved_piece(m)][to_sq(m)][type_of(pos.piece_on(to_sq(m)))]; - int bestIndex = movesPicked, bestScore = moves[movesPicked].score; + else if (Type == QUIETS) + m.value = (*mainHistory)[pos.side_to_move()][from_to(m)] + + 2 * (*continuationHistory[0])[pos.moved_piece(m)][to_sq(m)] + + 2 * (*continuationHistory[1])[pos.moved_piece(m)][to_sq(m)] + + 2 * (*continuationHistory[3])[pos.moved_piece(m)][to_sq(m)] + + (*continuationHistory[5])[pos.moved_piece(m)][to_sq(m)]; - for (int i = movesPicked + 1; i < numOfMoves; i++) - if (moves[i].score > bestScore) + else // Type == EVASIONS { - bestIndex = i; - bestScore = moves[i].score; + if (pos.capture(m)) + m.value = PieceValue[MG][pos.piece_on(to_sq(m))] + - Value(type_of(pos.moved_piece(m))); + else + m.value = (*mainHistory)[pos.side_to_move()][from_to(m)] + + (*continuationHistory[0])[pos.moved_piece(m)][to_sq(m)] + - (1 << 28); } - return bestIndex; } -int MovePicker::find_best_index(Bitboard* squares, int values[]) { - - assert(movesPicked < numOfMoves); +/// MovePicker::select() returns the next move satisfying a predicate function. +/// It never returns the TT move. +template +Move MovePicker::select(Pred filter) { - int hs; - Move m; - Square to; - int bestScore = -10000000, bestIndex = -1; - - for (int i = movesPicked; i < numOfMoves; i++) + while (cur < endMoves) { - m = moves[i].move; - to = move_to(m); + if (T == Best) + std::swap(*cur, *std::max_element(cur, endMoves)); - if (!bit_is_set(*squares, to)) - { - // Init at first use - set_bit(squares, to); - values[to] = 0; - } + if (*cur != ttMove && filter()) + return *cur++; - hs = moves[i].score - values[to]; - if (hs > bestScore) - { - bestIndex = i; - bestScore = hs; - } + cur++; } - - if (bestIndex != -1) - { - // Raise value of the picked square, so next attack - // to the same square will get low priority. - to = move_to(moves[bestIndex].move); - values[to] += 0xB00; - } - return bestIndex; + return MOVE_NONE; } +/// MovePicker::next_move() is the most important method of the MovePicker class. It +/// returns a new pseudo legal move every time it is called until there are no more +/// moves left, picking the move with the highest score from a list of generated moves. +Move MovePicker::next_move(bool skipQuiets) { + +top: + switch (stage) { + + case MAIN_TT: + case EVASION_TT: + case QSEARCH_TT: + case PROBCUT_TT: + ++stage; + return ttMove; + + case CAPTURE_INIT: + case PROBCUT_INIT: + case QCAPTURE_INIT: + cur = endBadCaptures = moves; + endMoves = generate(pos, cur); + + score(); + ++stage; + goto top; + + case GOOD_CAPTURE: + if (select([&](){ + return pos.see_ge(*cur, Value(-55 * cur->value / 1024)) ? + // Move losing capture to endBadCaptures to be tried later + true : (*endBadCaptures++ = *cur, false); })) + return *(cur - 1); + + // Prepare the pointers to loop over the refutations array + cur = std::begin(refutations); + endMoves = std::end(refutations); + + // If the countermove is the same as a killer, skip it + if ( refutations[0].move == refutations[2].move + || refutations[1].move == refutations[2].move) + --endMoves; + + ++stage; + /* fallthrough */ + + case REFUTATION: + if (select([&](){ return *cur != MOVE_NONE + && !pos.capture(*cur) + && pos.pseudo_legal(*cur); })) + return *(cur - 1); + ++stage; + /* fallthrough */ + + case QUIET_INIT: + if (!skipQuiets) + { + cur = endBadCaptures; + endMoves = generate(pos, cur); -/// MovePicker::pick_move_from_list() picks the move with the biggest score -/// from a list of generated moves (moves[] or badCaptures[], depending on -/// the current move generation phase). It takes care not to return the -/// transposition table move if that has already been serched previously. + score(); + partial_insertion_sort(cur, endMoves, -3000 * depth); + } -Move MovePicker::pick_move_from_list() { + ++stage; + /* fallthrough */ - int bestIndex; - Move move; + case QUIET: + if ( !skipQuiets + && select([&](){return *cur != refutations[0].move + && *cur != refutations[1].move + && *cur != refutations[2].move;})) + return *(cur - 1); - switch (PhaseTable[phaseIndex]) { + // Prepare the pointers to loop over the bad captures + cur = moves; + endMoves = endBadCaptures; - case PH_GOOD_CAPTURES: - assert(!pos.is_check()); - assert(movesPicked >= 0); + ++stage; + /* fallthrough */ - while (movesPicked < numOfMoves) - { - bestIndex = find_best_index(); - move = moves[bestIndex].move; - moves[bestIndex] = moves[movesPicked++]; - if ( move != ttMove - && move != mateKiller - && pos.pl_move_is_legal(move, pinned)) - return move; - } - break; + case BAD_CAPTURE: + return select([](){ return true; }); - case PH_NONCAPTURES: - assert(!pos.is_check()); - assert(movesPicked >= 0); + case EVASION_INIT: + cur = moves; + endMoves = generate(pos, cur); - while (movesPicked < numOfMoves) - { - // If this is a PV node or we have only picked a few moves, scan - // the entire move list for the best move. If many moves have already - // been searched and it is not a PV node, we are probably failing low - // anyway, so we just pick the first move from the list. - bestIndex = (pvNode || movesPicked < 12) ? find_best_index() : movesPicked; - move = moves[bestIndex].move; - moves[bestIndex] = moves[movesPicked++]; - if ( move != ttMove - && move != mateKiller - && pos.pl_move_is_legal(move, pinned)) - return move; - } - break; + score(); + ++stage; + /* fallthrough */ - case PH_EVASIONS: - assert(pos.is_check()); - assert(movesPicked >= 0); + case EVASION: + return select([](){ return true; }); - while (movesPicked < numOfMoves) - { - bestIndex = find_best_index(); - move = moves[bestIndex].move; - moves[bestIndex] = moves[movesPicked++]; - return move; - } - break; - - case PH_BAD_CAPTURES: - assert(!pos.is_check()); - assert(movesPicked >= 0); - // It's probably a good idea to use SEE move ordering here, instead - // of just picking the first move. FIXME - while (movesPicked < numOfBadCaptures) - { - move = badCaptures[movesPicked++].move; - if ( move != ttMove - && move != mateKiller - && pos.pl_move_is_legal(move, pinned)) - return move; - } - break; + case PROBCUT: + return select([&](){ return pos.see_ge(*cur, threshold); }); - case PH_QCAPTURES: - assert(!pos.is_check()); - assert(movesPicked >= 0); - while (movesPicked < numOfMoves) - { - bestIndex = (movesPicked < 4 ? find_best_index() : movesPicked); - move = moves[bestIndex].move; - moves[bestIndex] = moves[movesPicked++]; - // Remember to change the line below if we decide to hash the qsearch! - // Maybe also postpone the legality check until after futility pruning? - if (/* move != ttMove && */ pos.pl_move_is_legal(move, pinned)) - return move; - } - break; - - case PH_QCHECKS: - assert(!pos.is_check()); - assert(movesPicked >= 0); - // Perhaps we should do something better than just picking the first - // move here? FIXME - while (movesPicked < numOfMoves) - { - move = moves[movesPicked++].move; - // Remember to change the line below if we decide to hash the qsearch! - if (/* move != ttMove && */ pos.pl_move_is_legal(move, pinned)) - return move; - } - break; + case QCAPTURE: + if (select([&](){ return depth > DEPTH_QS_RECAPTURES + || to_sq(*cur) == recaptureSquare; })) + return *(cur - 1); - default: - break; - } - return MOVE_NONE; -} + // If we did not find any move and we do not try checks, we have finished + if (depth != DEPTH_QS_CHECKS) + return MOVE_NONE; + ++stage; + /* fallthrough */ -/// MovePicker::current_move_type() returns the type of the just -/// picked next move. It can be used in search to further differentiate -/// according to the current move type: capture, non capture, escape, etc. -MovePicker::MovegenPhase MovePicker::current_move_type() const { + case QCHECK_INIT: + cur = moves; + endMoves = generate(pos, cur); - return PhaseTable[phaseIndex]; -} + ++stage; + /* fallthrough */ + case QCHECK: + return select([](){ return true; }); + } -/// MovePicker::init_phase_table() initializes the PhaseTable[], -/// MainSearchPhaseIndex, EvasionPhaseIndex, QsearchWithChecksPhaseIndex -/// QsearchNoCapturesPhaseIndex, QsearchWithoutChecksPhaseIndex and -/// NoMovesPhaseIndex variables. It is only called once during program -/// startup, and never again while the program is running. - -void MovePicker::init_phase_table() { - - int i = 0; - - // Main search - MainSearchPhaseIndex = i - 1; - PhaseTable[i++] = PH_TT_MOVE; - PhaseTable[i++] = PH_MATE_KILLER; - PhaseTable[i++] = PH_GOOD_CAPTURES; - // PH_KILLER_1 and PH_KILLER_2 are not yet used. - // PhaseTable[i++] = PH_KILLER_1; - // PhaseTable[i++] = PH_KILLER_2; - PhaseTable[i++] = PH_NONCAPTURES; - PhaseTable[i++] = PH_BAD_CAPTURES; - PhaseTable[i++] = PH_STOP; - - // Check evasions - EvasionsPhaseIndex = i - 1; - PhaseTable[i++] = PH_EVASIONS; - PhaseTable[i++] = PH_STOP; - - // Quiescence search with checks - QsearchWithChecksPhaseIndex = i - 1; - PhaseTable[i++] = PH_QCAPTURES; - PhaseTable[i++] = PH_QCHECKS; - PhaseTable[i++] = PH_STOP; - - // Quiescence search with checks only and no captures - QsearchNoCapturesPhaseIndex = i - 1; - PhaseTable[i++] = PH_QCHECKS; - PhaseTable[i++] = PH_STOP; - - // Quiescence search without checks - QsearchWithoutChecksPhaseIndex = i - 1; - PhaseTable[i++] = PH_QCAPTURES; - PhaseTable[i++] = PH_STOP; - - // Do not generate any move - NoMovesPhaseIndex = i - 1; - PhaseTable[i++] = PH_STOP; + assert(false); + return MOVE_NONE; // Silence warning }