X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fmovepick.cpp;h=0da6b61bbbbe99f176eea9a5c67f75db9cd8b306;hb=6b16ebc82566a69b9336cca6aa7a19ab1824b85d;hp=43f30f7709565e22502e6e94438a0aa91ac663d1;hpb=75d001adddfaa7a2eb57af99cf6c57a12913d2d1;p=stockfish diff --git a/src/movepick.cpp b/src/movepick.cpp index 43f30f77..34d29562 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-2016 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,535 +18,333 @@ 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 -//// +#include "thread.h" namespace { - /// Variables - - MovePicker::MovegenPhase PhaseTable[32]; - int MainSearchPhaseIndex; - int EvasionsPhaseIndex; - int QsearchWithChecksPhaseIndex; - int QsearchNoCapturesPhaseIndex; - int QsearchWithoutChecksPhaseIndex; - int NoMovesPhaseIndex; - -} + enum Stages { + MAIN_SEARCH, CAPTURES_INIT, GOOD_CAPTURES, KILLERS, COUNTERMOVE, QUIET_INIT, QUIET, BAD_CAPTURES, + EVASION, EVASIONS_INIT, ALL_EVASIONS, + PROBCUT, PROBCUT_INIT, PROBCUT_CAPTURES, + QSEARCH_WITH_CHECKS, QCAPTURES_1_INIT, QCAPTURES_1, QCHECKS, + QSEARCH_NO_CHECKS, QCAPTURES_2_INIT, QCAPTURES_2, + QSEARCH_RECAPTURES, QRECAPTURES + }; + + // Our insertion sort, which is guaranteed to be stable, as it should be + void insertion_sort(ExtMove* begin, ExtMove* end) + { + ExtMove tmp, *p, *q; + for (p = begin + 1; p < end; ++p) + { + tmp = *p; + for (q = p; q != begin && *(q-1) < tmp; --q) + *q = *(q-1); + *q = tmp; + } + } + // 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; + } -//// -//// Functions -//// +} // namespace -/// 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 +/// 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 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, EvalInfo* ei) : pos(p) { - pvNode = pv; - ttMove = ttm; - mateKiller = (ss.mateKiller == ttm)? MOVE_NONE : ss.mateKiller; - killer1 = ss.killers[0]; - killer2 = ss.killers[0]; - 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); - bool noCaptures = ei - && (ei->attackedBy[us][0] & pos.pieces_of_color(them)) == 0 - && !ei->mi->specialized_eval_exists() - && (pos.ep_square() == SQ_NONE) - && !pos.has_pawn_on_7th(us); - - if (p.is_check()) - phaseIndex = EvasionsPhaseIndex; - else if (depth > Depth(0)) - phaseIndex = MainSearchPhaseIndex; - else if (depth == Depth(0)) - phaseIndex = (noCaptures ? QsearchNoCapturesPhaseIndex : QsearchWithChecksPhaseIndex); - else - phaseIndex = (noCaptures ? NoMovesPhaseIndex : QsearchWithoutChecksPhaseIndex); - - dc = p.discovered_check_candidates(us); - pinned = p.pinned_pieces(p.side_to_move()); - - finished = false; -} +/// 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, Search::Stack* s) + : pos(p), ss(s), depth(d) { -/// 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. + assert(d > DEPTH_ZERO); -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; - } + Square prevSq = to_sq((ss-1)->currentMove); + countermove = pos.this_thread()->counterMoves[pos.piece_on(prevSq)][prevSq]; - // Next phase - phaseIndex++; - switch (PhaseTable[phaseIndex]) { - - case PH_TT_MOVE: - if (ttMove != MOVE_NONE) - { - assert(move_is_ok(ttMove)); - if (move_is_legal(pos, ttMove, pinned)) - return ttMove; - } - 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: - badCapturesPicked = 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); - 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; - } - } + stage = pos.checkers() ? EVASION : MAIN_SEARCH; + ttMove = ttm && pos.pseudo_legal(ttm) ? ttm : MOVE_NONE; + stage += (ttMove == MOVE_NONE); } +MovePicker::MovePicker(const Position& p, Move ttm, Depth d, Square s) + : pos(p) { -/// 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. + assert(d <= DEPTH_ZERO); -Move MovePicker::get_next_move(Lock &lock) { + if (pos.checkers()) + stage = EVASION; - lock_grab(&lock); - if (finished) - { - lock_release(&lock); - return MOVE_NONE; - } - Move m = get_next_move(); - if (m == MOVE_NONE) - finished = true; - - lock_release(&lock); - return m; -} + else if (d > DEPTH_QS_NO_CHECKS) + stage = QSEARCH_WITH_CHECKS; + else if (d > DEPTH_QS_RECAPTURES) + stage = QSEARCH_NO_CHECKS; -/// 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++) + else { - 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 = QSEARCH_RECAPTURES; + recaptureSquare = s; + return; } -} -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; - - for (int i = 0; i < numOfMoves; i++) - { - m = moves[i].move; + ttMove = ttm && pos.pseudo_legal(ttm) ? ttm : MOVE_NONE; + stage += (ttMove == MOVE_NONE); +} - 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); +MovePicker::MovePicker(const Position& p, Move ttm, Value th) + : pos(p), threshold(th) { - // Ensure moves in history are always sorted as first - if (hs > 0) - hs += 1000; + assert(!pos.checkers()); - moves[i].score = hs + pos.mg_pst_delta(m); - } -} + stage = PROBCUT; -void MovePicker::score_evasions() { + // In ProbCut we generate captures with SEE higher than or equal to the given threshold + ttMove = ttm + && pos.pseudo_legal(ttm) + && pos.capture(ttm) + && pos.see_ge(ttm, threshold)? ttm : MOVE_NONE; - 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); - } - // FIXME try psqt also here + stage += (ttMove == MOVE_NONE); } -void MovePicker::score_qcaptures() { - // 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))); - } +/// score() assigns a numerical value to each move in a move list. The moves with +/// highest values will be picked first. +template<> +void MovePicker::score() { + // Winning and equal captures in the main search are ordered by MVV, preferring + // captures near our home rank. Surprisingly, this appears to perform slightly + // better than SEE-based move ordering: exchanging big pieces before capturing + // a hanging piece probably helps to reduce the subtree size. + // In the main search we want to push captures with negative SEE values to the + // badCaptures[] array, but instead of doing it now we delay until the move + // has been picked up, saving some SEE calls in case we get a cutoff. + for (auto& m : *this) + m.value = PieceValue[MG][pos.piece_on(to_sq(m))] + - Value(200 * relative_rank(pos.side_to_move(), to_sq(m))); } +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. + const HistoryStats& history = pos.this_thread()->history; + const FromToStats& fromTo = pos.this_thread()->fromTo; -int MovePicker::find_best_index() { + const CounterMoveStats* cmh = (ss-1)->counterMoves; + const CounterMoveStats* fmh = (ss-2)->counterMoves; + const CounterMoveStats* fmh2 = (ss-4)->counterMoves; - int bestScore = -10000000, bestIndex = -1; + Color c = pos.side_to_move(); - for (int i = movesPicked; i < numOfMoves; i++) - if (moves[i].score > bestScore) - { - bestIndex = i; - bestScore = moves[i].score; - } - return bestIndex; + for (auto& m : *this) + m.value = history[pos.moved_piece(m)][to_sq(m)] + + (cmh ? (*cmh)[pos.moved_piece(m)][to_sq(m)] : VALUE_ZERO) + + (fmh ? (*fmh)[pos.moved_piece(m)][to_sq(m)] : VALUE_ZERO) + + (fmh2 ? (*fmh2)[pos.moved_piece(m)][to_sq(m)] : VALUE_ZERO) + + fromTo.get(c, m); } -int MovePicker::find_best_index(Bitboard* squares, int values[]) { - - int hs; - Move m; - Square to; - int bestScore = -10000000, bestIndex = -1; - - for (int i = movesPicked; i < numOfMoves; i++) - { - m = moves[i].move; - to = move_to(m); - - if (!bit_is_set(*squares, to)) - { - // Init at first use - set_bit(squares, to); - values[to] = 0; - } - - hs = moves[i].score - values[to]; - if (hs > bestScore) - { - bestIndex = i; - bestScore = hs; - } - } - - 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; +template<> +void MovePicker::score() { + // Try captures ordered by MVV/LVA, then non-captures ordered by history value + const HistoryStats& history = pos.this_thread()->history; + const FromToStats& fromTo = pos.this_thread()->fromTo; + Color c = pos.side_to_move(); + + for (auto& m : *this) + if (pos.capture(m)) + m.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)] + fromTo.get(c, m); } -/// 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. +/// 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. It picks the move with the biggest value from a list of generated moves +/// taking care not to return the ttMove if it has already been searched. -Move MovePicker::pick_move_from_list() { +Move MovePicker::next_move() { - int bestIndex; Move move; - switch (PhaseTable[phaseIndex]) { - case PH_GOOD_CAPTURES: - assert(!pos.is_check()); - assert(movesPicked >= 0); + switch (stage) { - while (movesPicked < numOfMoves) - { - bestIndex = find_best_index(); + case MAIN_SEARCH: case EVASION: case QSEARCH_WITH_CHECKS: + case QSEARCH_NO_CHECKS: case PROBCUT: + ++stage; + return ttMove; - if (bestIndex != -1) // Found a good capture + case CAPTURES_INIT: + endBadCaptures = cur = moves; + endMoves = generate(pos, cur); + score(); + ++stage; + + case GOOD_CAPTURES: + while (cur < endMoves) + { + move = pick_best(cur++, endMoves); + if (move != ttMove) { - move = moves[bestIndex].move; - moves[bestIndex] = moves[movesPicked++]; - if ( move != ttMove - && move != mateKiller - && pos.pl_move_is_legal(move, pinned)) + if (pos.see_ge(move, VALUE_ZERO)) return move; + + // Losing capture, move it to the beginning of the array + *endBadCaptures++ = move; } } - break; - - case PH_NONCAPTURES: - assert(!pos.is_check()); - assert(movesPicked >= 0); - while (movesPicked < numOfMoves) + ++stage; + move = ss->killers[0]; // First killer move + if ( move != MOVE_NONE + && move != ttMove + && pos.pseudo_legal(move) + && !pos.capture(move)) + return move; + + case KILLERS: + ++stage; + move = ss->killers[1]; // Second killer move + if ( move != MOVE_NONE + && move != ttMove + && pos.pseudo_legal(move) + && !pos.capture(move)) + return move; + + case COUNTERMOVE: + ++stage; + move = countermove; + if ( move != MOVE_NONE + && move != ttMove + && move != ss->killers[0] + && move != ss->killers[1] + && pos.pseudo_legal(move) + && !pos.capture(move)) + return move; + + case QUIET_INIT: + cur = endBadCaptures; + endMoves = generate(pos, cur); + score(); + if (depth < 3 * ONE_PLY) { - // 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; + ExtMove* goodQuiet = std::partition(cur, endMoves, [](const ExtMove& m) + { return m.value > VALUE_ZERO; }); + insertion_sort(cur, goodQuiet); + } else + insertion_sort(cur, endMoves); + ++stage; - if (bestIndex != -1) - { - move = moves[bestIndex].move; - moves[bestIndex] = moves[movesPicked++]; - if ( move != ttMove - && move != mateKiller - && pos.pl_move_is_legal(move, pinned)) - return move; - } + case QUIET: + while (cur < endMoves) + { + move = *cur++; + if ( move != ttMove + && move != ss->killers[0] + && move != ss->killers[1] + && move != countermove) + return move; } + ++stage; + cur = moves; // Point to beginning of bad captures + + case BAD_CAPTURES: + if (cur < endBadCaptures) + return *cur++; break; - case PH_EVASIONS: - assert(pos.is_check()); - assert(movesPicked >= 0); + case EVASIONS_INIT: + cur = moves; + endMoves = generate(pos, cur); + score(); + ++stage; - while (movesPicked < numOfMoves) + case ALL_EVASIONS: + while (cur < endMoves) { - bestIndex = find_best_index(); - - if (bestIndex != -1) - { - move = moves[bestIndex].move; - moves[bestIndex] = moves[movesPicked++]; + move = pick_best(cur++, endMoves); + if (move != ttMove) return move; - } - } - break; - - case PH_BAD_CAPTURES: - assert(!pos.is_check()); - assert(badCapturesPicked >= 0); - // It's probably a good idea to use SEE move ordering here, instead - // of just picking the first move. FIXME - while (badCapturesPicked < numOfBadCaptures) + } + break; + + case PROBCUT_INIT: + cur = moves; + endMoves = generate(pos, cur); + score(); + ++stage; + + case PROBCUT_CAPTURES: + while (cur < endMoves) { - move = badCaptures[badCapturesPicked++].move; + move = pick_best(cur++, endMoves); if ( move != ttMove - && move != mateKiller - && pos.pl_move_is_legal(move, pinned)) + && pos.see_ge(move, threshold)) return move; } break; - case PH_QCAPTURES: - assert(!pos.is_check()); - assert(movesPicked >= 0); - while (movesPicked < numOfMoves) - { - bestIndex = (movesPicked < 4 ? find_best_index() : movesPicked); + case QCAPTURES_1_INIT: case QCAPTURES_2_INIT: + cur = moves; + endMoves = generate(pos, cur); + score(); + ++stage; - if (bestIndex != -1) - { - 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; - } + case QCAPTURES_1: case QCAPTURES_2: + while (cur < endMoves) + { + move = pick_best(cur++, endMoves); + if (move != ttMove) + return move; + } + if (stage == QCAPTURES_2) + break; + cur = moves; + endMoves = generate(pos, cur); + ++stage; + + case QCHECKS: + while (cur < endMoves) + { + move = cur++->move; + if (move != ttMove) + 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) + case QSEARCH_RECAPTURES: + cur = moves; + endMoves = generate(pos, cur); + score(); + ++stage; + + case QRECAPTURES: + while (cur < endMoves) { - 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)) + move = pick_best(cur++, endMoves); + if (to_sq(move) == recaptureSquare) return move; } break; default: - break; + assert(false); } - return MOVE_NONE; -} - -/// 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 { - - return PhaseTable[phaseIndex]; -} - - -/// 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; + return MOVE_NONE; }