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