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-2008 Tord Romstad (Glaurung author)
   4   Copyright (C) 2008-2010 Marco Costalba, Joona Kiiski, Tord Romstad
   5
   6   Stockfish is free software: you can redistribute it and/or modify
   7   it under the terms of the GNU General Public License as published by
   8   the Free Software Foundation, either version 3 of the License, or
   9   (at your option) any later version.
  10
  11
  12   Stockfish is distributed in the hope that it will be useful,
  13   but WITHOUT ANY WARRANTY; without even the implied warranty of
  14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15   GNU General Public License for more details.
  16
  17   You should have received a copy of the GNU General Public License
  18   along with this program.  If not, see <http://www.gnu.org/licenses/>.
  19 */
  20
  21 #include <algorithm>
  22 #include <cassert>
  23
  24 #include "movegen.h"
  25 #include "movepick.h"
  26 #include "search.h"
  27 #include "types.h"
  28
  29 namespace {
  30
  31   enum MovegenPhase {
  32     PH_TT_MOVE,       // Transposition table move
  33     PH_GOOD_CAPTURES, // Queen promotions and captures with SEE values >= captureThreshold (captureThreshold <= 0)
  34     PH_GOOD_PROBCUT,  // Queen promotions and captures with SEE values > captureThreshold (captureThreshold >= 0)
  35     PH_KILLERS,       // Killer moves from the current ply
  36     PH_NONCAPTURES_1, // Non-captures and underpromotions with positive score
  37     PH_NONCAPTURES_2, // Non-captures and underpromotions with non-positive score
  38     PH_BAD_CAPTURES,  // Queen promotions and captures with SEE values < captureThreshold (captureThreshold <= 0)
  39     PH_EVASIONS,      // Check evasions
  40     PH_QCAPTURES,     // Captures in quiescence search
  41     PH_QRECAPTURES,   // Recaptures in quiescence search
  42     PH_QCHECKS,       // Non-capture checks in quiescence search
  43     PH_STOP
  44   };
  45
  46   CACHE_LINE_ALIGNMENT
  47   const uint8_t MainSearchTable[] = { PH_TT_MOVE, PH_GOOD_CAPTURES, PH_KILLERS, PH_NONCAPTURES_1, PH_NONCAPTURES_2, PH_BAD_CAPTURES, PH_STOP };
  48   const uint8_t EvasionTable[] = { PH_TT_MOVE, PH_EVASIONS, PH_STOP };
  49   const uint8_t QsearchWithChecksTable[] = { PH_TT_MOVE, PH_QCAPTURES, PH_QCHECKS, PH_STOP };
  50   const uint8_t QsearchWithoutChecksTable[] = { PH_TT_MOVE, PH_QCAPTURES, PH_STOP };
  51   const uint8_t QsearchRecapturesTable[] = { PH_TT_MOVE, PH_QRECAPTURES, PH_STOP };
  52   const uint8_t ProbCutTable[] = { PH_TT_MOVE, PH_GOOD_PROBCUT, PH_STOP };
  53
  54   // Unary predicate used by std::partition to split positive scores from remaining
  55   // ones so to sort separately the two sets, and with the second sort delayed.
  56   inline bool has_positive_score(const MoveStack& move) { return move.score > 0; }
  57
  58   // Picks and pushes to the front the best move in range [firstMove, lastMove),
  59   // it is faster than sorting all the moves in advance when moves are few, as
  60   // normally are the possible captures.
  61   inline MoveStack* pick_best(MoveStack* firstMove, MoveStack* lastMove)
  62   {
  63       std::swap(*firstMove, *std::max_element(firstMove, lastMove));
  64       return firstMove;
  65   }
  66 }
  67
  68 /// Constructors for the MovePicker class. As arguments we pass information
  69 /// to help it to return the presumably good moves first, to decide which
  70 /// moves to return (in the quiescence search, for instance, we only want to
  71 /// search captures, promotions and some checks) and about how important good
  72 /// move ordering is at the current node.
  73
  74 MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const History& h,
  75                        Search::Stack* ss, Value beta) : pos(p), H(h), depth(d) {
  76   captureThreshold = 0;
  77   badCaptures = moves + MAX_MOVES;
  78
  79   assert(d > DEPTH_ZERO);
  80
  81   if (p.in_check())
  82   {
  83       killers[0].move = killers[1].move = MOVE_NONE;
  84       phasePtr = EvasionTable;
  85   }
  86   else
  87   {
  88       killers[0].move = ss->killers[0];
  89       killers[1].move = ss->killers[1];
  90
  91       // Consider sligtly negative captures as good if at low depth and far from beta
  92       if (ss && ss->eval < beta - PawnValueMidgame && d < 3 * ONE_PLY)
  93           captureThreshold = -PawnValueMidgame;
  94
  95       // Consider negative captures as good if still enough to reach beta
  96       else if (ss && ss->eval > beta)
  97           captureThreshold = beta - ss->eval;
  98
  99       phasePtr = MainSearchTable;
 100   }
 101
 102   ttMove = (ttm && pos.is_pseudo_legal(ttm) ? ttm : MOVE_NONE);
 103   phasePtr += int(ttMove == MOVE_NONE) - 1;
 104   go_next_phase();
 105 }
 106
 107 MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const History& h, Square recaptureSq)
 108                       : pos(p), H(h) {
 109
 110   assert(d <= DEPTH_ZERO);
 111
 112   if (p.in_check())
 113       phasePtr = EvasionTable;
 114   else if (d >= DEPTH_QS_CHECKS)
 115       phasePtr = QsearchWithChecksTable;
 116   else if (d >= DEPTH_QS_RECAPTURES)
 117   {
 118       phasePtr = QsearchWithoutChecksTable;
 119
 120       // Skip TT move if is not a capture or a promotion, this avoids
 121       // qsearch tree explosion due to a possible perpetual check or
 122       // similar rare cases when TT table is full.
 123       if (ttm != MOVE_NONE && !pos.is_capture_or_promotion(ttm))
 124           ttm = MOVE_NONE;
 125   }
 126   else
 127   {
 128       phasePtr = QsearchRecapturesTable;
 129       recaptureSquare = recaptureSq;
 130       ttm = MOVE_NONE;
 131   }
 132
 133   ttMove = (ttm && pos.is_pseudo_legal(ttm) ? ttm : MOVE_NONE);
 134   phasePtr += int(ttMove == MOVE_NONE) - 1;
 135   go_next_phase();
 136 }
 137
 138 MovePicker::MovePicker(const Position& p, Move ttm, const History& h, PieceType parentCapture)
 139                        : pos(p), H(h) {
 140
 141   assert (!pos.in_check());
 142
 143   // In ProbCut we consider only captures better than parent's move
 144   captureThreshold = PieceValueMidgame[Piece(parentCapture)];
 145   phasePtr = ProbCutTable;
 146
 147   if (   ttm != MOVE_NONE
 148       && (!pos.is_capture(ttm) ||  pos.see(ttm) <= captureThreshold))
 149       ttm = MOVE_NONE;
 150
 151   ttMove = (ttm && pos.is_pseudo_legal(ttm) ? ttm : MOVE_NONE);
 152   phasePtr += int(ttMove == MOVE_NONE) - 1;
 153   go_next_phase();
 154 }
 155
 156
 157 /// MovePicker::go_next_phase() generates, scores and sorts the next bunch
 158 /// of moves when there are no more moves to try for the current phase.
 159
 160 void MovePicker::go_next_phase() {
 161
 162   curMove = moves;
 163   phase = *(++phasePtr);
 164   switch (phase) {
 165
 166   case PH_TT_MOVE:
 167       lastMove = curMove + 1;
 168       return;
 169
 170   case PH_GOOD_CAPTURES:
 171   case PH_GOOD_PROBCUT:
 172       lastMove = generate<MV_CAPTURE>(pos, moves);
 173       score_captures();
 174       return;
 175
 176   case PH_KILLERS:
 177       curMove = killers;
 178       lastMove = curMove + 2;
 179       return;
 180
 181   case PH_NONCAPTURES_1:
 182       lastNonCapture = lastMove = generate<MV_NON_CAPTURE>(pos, moves);
 183       score_noncaptures();
 184       lastMove = std::partition(curMove, lastMove, has_positive_score);
 185       sort<MoveStack>(curMove, lastMove);
 186       return;
 187
 188   case PH_NONCAPTURES_2:
 189       curMove = lastMove;
 190       lastMove = lastNonCapture;
 191       if (depth >= 3 * ONE_PLY)
 192           sort<MoveStack>(curMove, lastMove);
 193       return;
 194
 195   case PH_BAD_CAPTURES:
 196       // Bad captures SEE value is already calculated so just pick
 197       // them in order to get SEE move ordering.
 198       curMove = badCaptures;
 199       lastMove = moves + MAX_MOVES;
 200       return;
 201
 202   case PH_EVASIONS:
 203       assert(pos.in_check());
 204       lastMove = generate<MV_EVASION>(pos, moves);
 205       score_evasions();
 206       return;
 207
 208   case PH_QCAPTURES:
 209       lastMove = generate<MV_CAPTURE>(pos, moves);
 210       score_captures();
 211       return;
 212
 213   case PH_QRECAPTURES:
 214       lastMove = generate<MV_CAPTURE>(pos, moves);
 215       return;
 216
 217   case PH_QCHECKS:
 218       lastMove = generate<MV_NON_CAPTURE_CHECK>(pos, moves);
 219       return;
 220
 221   case PH_STOP:
 222       lastMove = curMove + 1; // Avoid another go_next_phase() call
 223       return;
 224
 225   default:
 226       assert(false);
 227       return;
 228   }
 229 }
 230
 231
 232 /// MovePicker::score_captures(), MovePicker::score_noncaptures() and
 233 /// MovePicker::score_evasions() assign a numerical move ordering score
 234 /// to each move in a move list.  The moves with highest scores will be
 235 /// picked first by get_next_move().
 236
 237 void MovePicker::score_captures() {
 238   // Winning and equal captures in the main search are ordered by MVV/LVA.
 239   // Suprisingly, this appears to perform slightly better than SEE based
 240   // move ordering. The reason is probably that in a position with a winning
 241   // capture, capturing a more valuable (but sufficiently defended) piece
 242   // first usually doesn't hurt. The opponent will have to recapture, and
 243   // the hanging piece will still be hanging (except in the unusual cases
 244   // where it is possible to recapture with the hanging piece). Exchanging
 245   // big pieces before capturing a hanging piece probably helps to reduce
 246   // the subtree size.
 247   // In main search we want to push captures with negative SEE values to
 248   // badCaptures[] array, but instead of doing it now we delay till when
 249   // the move has been picked up in pick_move_from_list(), this way we save
 250   // some SEE calls in case we get a cutoff (idea from Pablo Vazquez).
 251   Move m;
 252
 253   // Use MVV/LVA ordering
 254   for (MoveStack* cur = moves; cur != lastMove; cur++)
 255   {
 256       m = cur->move;
 257       cur->score =  PieceValueMidgame[pos.piece_on(move_to(m))]
 258                   - type_of(pos.piece_on(move_from(m)));
 259
 260       if (is_promotion(m))
 261           cur->score += PieceValueMidgame[Piece(promotion_piece_type(m))];
 262   }
 263 }
 264
 265 void MovePicker::score_noncaptures() {
 266
 267   Move m;
 268   Square from;
 269
 270   for (MoveStack* cur = moves; cur != lastMove; cur++)
 271   {
 272       m = cur->move;
 273       from = move_from(m);
 274       cur->score = H.value(pos.piece_on(from), move_to(m));
 275   }
 276 }
 277
 278 void MovePicker::score_evasions() {
 279   // Try good captures ordered by MVV/LVA, then non-captures if
 280   // destination square is not under attack, ordered by history
 281   // value, and at the end bad-captures and non-captures with a
 282   // negative SEE. This last group is ordered by the SEE score.
 283   Move m;
 284   int seeScore;
 285
 286   // Skip if we don't have at least two moves to order
 287   if (lastMove < moves + 2)
 288       return;
 289
 290   for (MoveStack* cur = moves; cur != lastMove; cur++)
 291   {
 292       m = cur->move;
 293       if ((seeScore = pos.see_sign(m)) < 0)
 294           cur->score = seeScore - History::MaxValue; // Be sure we are at the bottom
 295       else if (pos.is_capture(m))
 296           cur->score =  PieceValueMidgame[pos.piece_on(move_to(m))]
 297                       - type_of(pos.piece_on(move_from(m))) + History::MaxValue;
 298       else
 299           cur->score = H.value(pos.piece_on(move_from(m)), move_to(m));
 300   }
 301 }
 302
 303 /// MovePicker::get_next_move() is the most important method of the MovePicker
 304 /// class. It returns a new pseudo legal move every time it is called, until there
 305 /// are no more moves left. It picks the move with the biggest score from a list
 306 /// of generated moves taking care not to return the tt move if has already been
 307 /// searched previously. Note that this function is not thread safe so should be
 308 /// lock protected by caller when accessed through a shared MovePicker object.
 309
 310 Move MovePicker::get_next_move() {
 311
 312   Move move;
 313
 314   while (true)
 315   {
 316       while (curMove == lastMove)
 317           go_next_phase();
 318
 319       switch (phase) {
 320
 321       case PH_TT_MOVE:
 322           curMove++;
 323           return ttMove;
 324           break;
 325
 326       case PH_GOOD_CAPTURES:
 327           move = pick_best(curMove++, lastMove)->move;
 328           if (move != ttMove)
 329           {
 330               assert(captureThreshold <= 0); // Otherwise we must use see instead of see_sign
 331
 332               // Check for a non negative SEE now
 333               int seeValue = pos.see_sign(move);
 334               if (seeValue >= captureThreshold)
 335                   return move;
 336
 337               // Losing capture, move it to the tail of the array
 338               (--badCaptures)->move = move;
 339               badCaptures->score = seeValue;
 340           }
 341           break;
 342
 343      case PH_GOOD_PROBCUT:
 344           move = pick_best(curMove++, lastMove)->move;
 345           if (   move != ttMove
 346               && pos.see(move) > captureThreshold)
 347               return move;
 348           break;
 349
 350       case PH_KILLERS:
 351           move = (curMove++)->move;
 352           if (   move != MOVE_NONE
 353               && pos.is_pseudo_legal(move)
 354               && move != ttMove
 355               && !pos.is_capture(move))
 356               return move;
 357           break;
 358
 359       case PH_NONCAPTURES_1:
 360       case PH_NONCAPTURES_2:
 361           move = (curMove++)->move;
 362           if (   move != ttMove
 363               && move != killers[0].move
 364               && move != killers[1].move)
 365               return move;
 366           break;
 367
 368       case PH_BAD_CAPTURES:
 369           move = pick_best(curMove++, lastMove)->move;
 370           return move;
 371
 372       case PH_EVASIONS:
 373       case PH_QCAPTURES:
 374           move = pick_best(curMove++, lastMove)->move;
 375           if (move != ttMove)
 376               return move;
 377           break;
 378
 379       case PH_QRECAPTURES:
 380           move = (curMove++)->move;
 381           if (move_to(move) == recaptureSquare)
 382               return move;
 383           break;
 384
 385       case PH_QCHECKS:
 386           move = (curMove++)->move;
 387           if (move != ttMove)
 388               return move;
 389           break;
 390
 391       case PH_STOP:
 392           return MOVE_NONE;
 393
 394       default:
 395           assert(false);
 396           break;
 397       }
 398   }
 399 }