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