git.sesse.net Git - stockfish/blob - src/movepick.cpp

   1 /*
   2   Stockfish, a UCI chess playing engine derived from Glaurung 2.1
   3   Copyright (C) 2004-2023 The Stockfish developers (see AUTHORS file)
   4
   5   Stockfish is free software: you can redistribute it and/or modify
   6   it under the terms of the GNU General Public License as published by
   7   the Free Software Foundation, either version 3 of the License, or
   8   (at your option) any later version.
   9
  10   Stockfish is distributed in the hope that it will be useful,
  11   but WITHOUT ANY WARRANTY; without even the implied warranty of
  12   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13   GNU General Public License for more details.
  14
  15   You should have received a copy of the GNU General Public License
  16   along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17 */
  18
  19 #include "movepick.h"
  20
  21 #include <algorithm>
  22 #include <cassert>
  23 #include <iterator>
  24 #include <utility>
  25
  26 #include "bitboard.h"
  27 #include "position.h"
  28
  29 namespace Stockfish {
  30
  31 namespace {
  32
  33 enum Stages {
  34     // generate main search moves
  35     MAIN_TT,
  36     CAPTURE_INIT,
  37     GOOD_CAPTURE,
  38     REFUTATION,
  39     QUIET_INIT,
  40     QUIET,
  41     BAD_CAPTURE,
  42
  43     // generate evasion moves
  44     EVASION_TT,
  45     EVASION_INIT,
  46     EVASION,
  47
  48     // generate probcut moves
  49     PROBCUT_TT,
  50     PROBCUT_INIT,
  51     PROBCUT,
  52
  53     // generate qsearch moves
  54     QSEARCH_TT,
  55     QCAPTURE_INIT,
  56     QCAPTURE,
  57     QCHECK_INIT,
  58     QCHECK
  59 };
  60
  61 // Sort moves in descending order up to and including
  62 // a given limit. The order of moves smaller than the limit is left unspecified.
  63 void partial_insertion_sort(ExtMove* begin, ExtMove* end, int limit) {
  64
  65     for (ExtMove *sortedEnd = begin, *p = begin + 1; p < end; ++p)
  66         if (p->value >= limit)
  67         {
  68             ExtMove tmp = *p, *q;
  69             *p          = *++sortedEnd;
  70             for (q = sortedEnd; q != begin && *(q - 1) < tmp; --q)
  71                 *q = *(q - 1);
  72             *q = tmp;
  73         }
  74 }
  75
  76 }  // namespace
  77
  78
  79 // Constructors of the MovePicker class. As arguments, we pass information
  80 // to help it return the (presumably) good moves first, to decide which
  81 // moves to return (in the quiescence search, for instance, we only want to
  82 // search captures, promotions, and some checks) and how important a good
  83 // move ordering is at the current node.
  84
  85 // MovePicker constructor for the main search
  86 MovePicker::MovePicker(const Position&              p,
  87                        Move                         ttm,
  88                        Depth                        d,
  89                        const ButterflyHistory*      mh,
  90                        const CapturePieceToHistory* cph,
  91                        const PieceToHistory**       ch,
  92                        const PawnHistory&           ph,
  93                        Move                         cm,
  94                        const Move*                  killers) :
  95     pos(p),
  96     mainHistory(mh),
  97     captureHistory(cph),
  98     continuationHistory(ch),
  99     pawnHistory(ph),
 100     ttMove(ttm),
 101     refutations{{killers[0], 0}, {killers[1], 0}, {cm, 0}},
 102     depth(d) {
 103     assert(d > 0);
 104
 105     stage = (pos.checkers() ? EVASION_TT : MAIN_TT) + !(ttm && pos.pseudo_legal(ttm));
 106 }
 107
 108 // Constructor for quiescence search
 109 MovePicker::MovePicker(const Position&              p,
 110                        Move                         ttm,
 111                        Depth                        d,
 112                        const ButterflyHistory*      mh,
 113                        const CapturePieceToHistory* cph,
 114                        const PieceToHistory**       ch,
 115                        const PawnHistory&           ph,
 116                        Square                       rs) :
 117     pos(p),
 118     mainHistory(mh),
 119     captureHistory(cph),
 120     continuationHistory(ch),
 121     pawnHistory(ph),
 122     ttMove(ttm),
 123     recaptureSquare(rs),
 124     depth(d) {
 125     assert(d <= 0);
 126
 127     stage = (pos.checkers() ? EVASION_TT : QSEARCH_TT) + !(ttm && pos.pseudo_legal(ttm));
 128 }
 129
 130 // Constructor for ProbCut: we generate captures with SEE greater
 131 // than or equal to the given threshold.
 132 MovePicker::MovePicker(
 133   const Position& p, Move ttm, Value th, const CapturePieceToHistory* cph, const PawnHistory& ph) :
 134     pos(p),
 135     captureHistory(cph),
 136     pawnHistory(ph),
 137     ttMove(ttm),
 138     threshold(th) {
 139     assert(!pos.checkers());
 140
 141     stage = PROBCUT_TT
 142           + !(ttm && pos.capture_stage(ttm) && pos.pseudo_legal(ttm) && pos.see_ge(ttm, threshold));
 143 }
 144
 145 // Assigns a numerical value to each move in a list, used
 146 // for sorting. Captures are ordered by Most Valuable Victim (MVV), preferring
 147 // captures with a good history. Quiets moves are ordered using the history tables.
 148 template<GenType Type>
 149 void MovePicker::score() {
 150
 151     static_assert(Type == CAPTURES || Type == QUIETS || Type == EVASIONS, "Wrong type");
 152
 153     [[maybe_unused]] Bitboard threatenedByPawn, threatenedByMinor, threatenedByRook,
 154       threatenedPieces;
 155     if constexpr (Type == QUIETS)
 156     {
 157         Color us = pos.side_to_move();
 158
 159         threatenedByPawn = pos.attacks_by<PAWN>(~us);
 160         threatenedByMinor =
 161           pos.attacks_by<KNIGHT>(~us) | pos.attacks_by<BISHOP>(~us) | threatenedByPawn;
 162         threatenedByRook = pos.attacks_by<ROOK>(~us) | threatenedByMinor;
 163
 164         // Pieces threatened by pieces of lesser material value
 165         threatenedPieces = (pos.pieces(us, QUEEN) & threatenedByRook)
 166                          | (pos.pieces(us, ROOK) & threatenedByMinor)
 167                          | (pos.pieces(us, KNIGHT, BISHOP) & threatenedByPawn);
 168     }
 169
 170     for (auto& m : *this)
 171         if constexpr (Type == CAPTURES)
 172             m.value =
 173               (7 * int(PieceValue[pos.piece_on(to_sq(m))])
 174                + (*captureHistory)[pos.moved_piece(m)][to_sq(m)][type_of(pos.piece_on(to_sq(m)))])
 175               / 16;
 176
 177         else if constexpr (Type == QUIETS)
 178         {
 179             Piece     pc   = pos.moved_piece(m);
 180             PieceType pt   = type_of(pos.moved_piece(m));
 181             Square    from = from_sq(m);
 182             Square    to   = to_sq(m);
 183
 184             // histories
 185             m.value = 2 * (*mainHistory)[pos.side_to_move()][from_to(m)];
 186             m.value += 2 * (*continuationHistory[0])[pc][to];
 187             m.value += (*continuationHistory[1])[pc][to];
 188             m.value += (*continuationHistory[2])[pc][to] / 4;
 189             m.value += (*continuationHistory[3])[pc][to];
 190             m.value += (*continuationHistory[5])[pc][to];
 191
 192             // bonus for checks
 193             m.value += bool(pos.check_squares(pt) & to) * 16384;
 194
 195             // bonus for escaping from capture
 196             m.value += threatenedPieces & from ? (pt == QUEEN && !(to & threatenedByRook)   ? 50000
 197                                                   : pt == ROOK && !(to & threatenedByMinor) ? 25000
 198                                                   : !(to & threatenedByPawn)                ? 15000
 199                                                                                             : 0)
 200                                                : 0;
 201
 202             // malus for putting piece en prise
 203             m.value -= !(threatenedPieces & from)
 204                        ? (pt == QUEEN ? bool(to & threatenedByRook) * 50000
 205                                           + bool(to & threatenedByMinor) * 10000
 206                                           + bool(to & threatenedByPawn) * 20000
 207                           : pt == ROOK ? bool(to & threatenedByMinor) * 25000
 208                                            + bool(to & threatenedByPawn) * 10000
 209                           : pt != PAWN ? bool(to & threatenedByPawn) * 15000
 210                                        : 0)
 211                        : 0;
 212
 213             m.value += pawnHistory[pawn_structure(pos)][pc][to];
 214         }
 215
 216         else  // Type == EVASIONS
 217         {
 218             if (pos.capture_stage(m))
 219                 m.value = PieceValue[pos.piece_on(to_sq(m))] - Value(type_of(pos.moved_piece(m)))
 220                         + (1 << 28);
 221             else
 222                 m.value = (*mainHistory)[pos.side_to_move()][from_to(m)]
 223                         + (*continuationHistory[0])[pos.moved_piece(m)][to_sq(m)]
 224                         + pawnHistory[pawn_structure(pos)][pos.moved_piece(m)][to_sq(m)];
 225         }
 226 }
 227
 228 // Returns the next move satisfying a predicate function.
 229 // It never returns the TT move.
 230 template<MovePicker::PickType T, typename Pred>
 231 Move MovePicker::select(Pred filter) {
 232
 233     while (cur < endMoves)
 234     {
 235         if constexpr (T == Best)
 236             std::swap(*cur, *std::max_element(cur, endMoves));
 237
 238         if (*cur != ttMove && filter())
 239             return *cur++;
 240
 241         cur++;
 242     }
 243     return MOVE_NONE;
 244 }
 245
 246 // Most important method of the MovePicker class. It
 247 // returns a new pseudo-legal move every time it is called until there are no more
 248 // moves left, picking the move with the highest score from a list of generated moves.
 249 Move MovePicker::next_move(bool skipQuiets) {
 250
 251 top:
 252     switch (stage)
 253     {
 254
 255     case MAIN_TT :
 256     case EVASION_TT :
 257     case QSEARCH_TT :
 258     case PROBCUT_TT :
 259         ++stage;
 260         return ttMove;
 261
 262     case CAPTURE_INIT :
 263     case PROBCUT_INIT :
 264     case QCAPTURE_INIT :
 265         cur = endBadCaptures = moves;
 266         endMoves             = generate<CAPTURES>(pos, cur);
 267
 268         score<CAPTURES>();
 269         partial_insertion_sort(cur, endMoves, std::numeric_limits<int>::min());
 270         ++stage;
 271         goto top;
 272
 273     case GOOD_CAPTURE :
 274         if (select<Next>([&]() {
 275                 // Move losing capture to endBadCaptures to be tried later
 276                 return pos.see_ge(*cur, Value(-cur->value)) ? true
 277                                                             : (*endBadCaptures++ = *cur, false);
 278             }))
 279             return *(cur - 1);
 280
 281         // Prepare the pointers to loop over the refutations array
 282         cur      = std::begin(refutations);
 283         endMoves = std::end(refutations);
 284
 285         // If the countermove is the same as a killer, skip it
 286         if (refutations[0].move == refutations[2].move
 287             || refutations[1].move == refutations[2].move)
 288             --endMoves;
 289
 290         ++stage;
 291         [[fallthrough]];
 292
 293     case REFUTATION :
 294         if (select<Next>([&]() {
 295                 return *cur != MOVE_NONE && !pos.capture_stage(*cur) && pos.pseudo_legal(*cur);
 296             }))
 297             return *(cur - 1);
 298         ++stage;
 299         [[fallthrough]];
 300
 301     case QUIET_INIT :
 302         if (!skipQuiets)
 303         {
 304             cur      = endBadCaptures;
 305             endMoves = generate<QUIETS>(pos, cur);
 306
 307             score<QUIETS>();
 308             partial_insertion_sort(cur, endMoves, -3000 * depth);
 309         }
 310
 311         ++stage;
 312         [[fallthrough]];
 313
 314     case QUIET :
 315         if (!skipQuiets && select<Next>([&]() {
 316                 return *cur != refutations[0].move && *cur != refutations[1].move
 317                     && *cur != refutations[2].move;
 318             }))
 319             return *(cur - 1);
 320
 321         // Prepare the pointers to loop over the bad captures
 322         cur      = moves;
 323         endMoves = endBadCaptures;
 324
 325         ++stage;
 326         [[fallthrough]];
 327
 328     case BAD_CAPTURE :
 329         return select<Next>([]() { return true; });
 330
 331     case EVASION_INIT :
 332         cur      = moves;
 333         endMoves = generate<EVASIONS>(pos, cur);
 334
 335         score<EVASIONS>();
 336         ++stage;
 337         [[fallthrough]];
 338
 339     case EVASION :
 340         return select<Best>([]() { return true; });
 341
 342     case PROBCUT :
 343         return select<Next>([&]() { return pos.see_ge(*cur, threshold); });
 344
 345     case QCAPTURE :
 346         if (select<Next>(
 347               [&]() { return depth > DEPTH_QS_RECAPTURES || to_sq(*cur) == recaptureSquare; }))
 348             return *(cur - 1);
 349
 350         // If we did not find any move and we do not try checks, we have finished
 351         if (depth != DEPTH_QS_CHECKS)
 352             return MOVE_NONE;
 353
 354         ++stage;
 355         [[fallthrough]];
 356
 357     case QCHECK_INIT :
 358         cur      = moves;
 359         endMoves = generate<QUIET_CHECKS>(pos, cur);
 360
 361         ++stage;
 362         [[fallthrough]];
 363
 364     case QCHECK :
 365         return select<Next>([]() { return true; });
 366     }
 367
 368     assert(false);
 369     return MOVE_NONE;  // Silence warning
 370 }
 371
 372 }  // namespace Stockfish