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

   1 /*
   2   Glaurung, a UCI chess playing engine.
   3   Copyright (C) 2004-2008 Tord Romstad
   4
   5   Glaurung 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   Glaurung 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
  20 ////
  21 //// Includes
  22 ////
  23
  24 #include <cassert>
  25
  26 #include "history.h"
  27 #include "movegen.h"
  28 #include "movepick.h"
  29 #include "search.h"
  30 #include "value.h"
  31
  32
  33 ////
  34 //// Local definitions
  35 ////
  36
  37 namespace {
  38
  39   /// Variables
  40
  41   MovePicker::MovegenPhase PhaseTable[32];
  42   int MainSearchPhaseIndex;
  43   int EvasionsPhaseIndex;
  44   int QsearchWithChecksPhaseIndex;
  45   int QsearchWithoutChecksPhaseIndex;
  46
  47 }
  48
  49
  50 ////
  51 //// Functions
  52 ////
  53
  54
  55 /// Constructor for the MovePicker class.  Apart from the position for which
  56 /// it is asked to pick legal moves, MovePicker also wants some information
  57 /// to help it to return the presumably good moves first, to decide which
  58 /// moves to return (in the quiescence search, for instance, we only want to
  59 /// search captures, promotions and some checks) and about how important good
  60 /// move ordering is at the current node.
  61
  62 MovePicker::MovePicker(Position &p, bool pvnode, Move ttm, Move mk,
  63                        Move k1, Move k2, Depth dpth) {
  64   pos = &p;
  65   pvNode = pvnode;
  66   ttMove = ttm;
  67   mateKiller = (mk == ttm)? MOVE_NONE : mk;
  68   killer1 = k1;
  69   killer2 = k2;
  70   depth = dpth;
  71   movesPicked = 0;
  72   numOfMoves = 0;
  73   numOfBadCaptures = 0;
  74   dc = p.discovered_check_candidates(p.side_to_move());
  75
  76   if(p.is_check())
  77     phaseIndex = EvasionsPhaseIndex;
  78   else if(depth > Depth(0))
  79     phaseIndex = MainSearchPhaseIndex;
  80   else if(depth == Depth(0))
  81     phaseIndex = QsearchWithChecksPhaseIndex;
  82   else
  83     phaseIndex = QsearchWithoutChecksPhaseIndex;
  84
  85   pinned = p.pinned_pieces(p.side_to_move());
  86
  87   finished = false;
  88 }
  89
  90
  91 /// MovePicker::get_next_move() is the most important method of the MovePicker
  92 /// class.  It returns a new legal move every time it is called, until there
  93 /// are no more moves left of the types we are interested in.
  94
  95 Move MovePicker::get_next_move(MovegenPhase* moveType) {
  96   Move move;
  97
  98   while(true) {
  99     // If we already have a list of generated moves, pick the best move from
 100     // the list, and return it:
 101     move = this->pick_move_from_list();
 102     if(move != MOVE_NONE) {
 103       assert(move_is_ok(move));
 104       return move;
 105     }
 106
 107     // Next phase:
 108     phaseIndex++;
 109     if (moveType)
 110         *moveType = PhaseTable[phaseIndex];
 111
 112     switch(PhaseTable[phaseIndex]) {
 113
 114     case PH_TT_MOVE:
 115       if(ttMove != MOVE_NONE) {
 116         assert(move_is_ok(ttMove));
 117         Move m = generate_move_if_legal(*pos, ttMove, pinned);
 118         if(m != MOVE_NONE) {
 119           assert(m == ttMove);
 120           return m;
 121         }
 122       }
 123       break;
 124
 125     case PH_MATE_KILLER:
 126       if(mateKiller != MOVE_NONE) {
 127         assert(move_is_ok(mateKiller));
 128         Move m = generate_move_if_legal(*pos, mateKiller, pinned);
 129         if(m != MOVE_NONE) {
 130           assert(m == mateKiller);
 131           return m;
 132         }
 133       }
 134       break;
 135
 136     case PH_GOOD_CAPTURES:
 137       // pinned = pos->pinned_pieces(pos->side_to_move());
 138       numOfMoves = generate_captures(*pos, moves);
 139       this->score_captures();
 140       movesPicked = 0;
 141       break;
 142
 143     case PH_BAD_CAPTURES:
 144       badCapturesPicked = 0;
 145       break;
 146
 147     case PH_NONCAPTURES:
 148       numOfMoves = generate_noncaptures(*pos, moves);
 149       this->score_noncaptures();
 150       movesPicked = 0;
 151       break;
 152
 153     case PH_EVASIONS:
 154       assert(pos->is_check());
 155       // pinned = pos->pinned_pieces(pos->side_to_move());
 156       numOfMoves = generate_evasions(*pos, moves);
 157       this->score_evasions();
 158       movesPicked = 0;
 159       break;
 160
 161     case PH_QCAPTURES:
 162       // pinned = pos->pinned_pieces(pos->side_to_move());
 163       numOfMoves = generate_captures(*pos, moves);
 164       this->score_qcaptures();
 165       movesPicked = 0;
 166       break;
 167
 168     case PH_QCHECKS:
 169       numOfMoves = generate_checks(*pos, moves, dc);
 170       movesPicked = 0;
 171       break;
 172
 173     case PH_STOP:
 174       return MOVE_NONE;
 175
 176     default:
 177       assert(false);
 178       return MOVE_NONE;
 179     }
 180   }
 181
 182   assert(false);
 183
 184   return MOVE_NONE;
 185 }
 186
 187
 188 /// A variant of get_next_move() which takes a lock as a parameter, used to
 189 /// prevent multiple threads from picking the same move at a split point.
 190
 191 Move MovePicker::get_next_move(Lock &lock) {
 192    Move m;
 193
 194    lock_grab(&lock);
 195    if(finished) {
 196      lock_release(&lock);
 197      return MOVE_NONE;
 198    }
 199    m = this->get_next_move();
 200    if(m == MOVE_NONE)
 201      finished = true;
 202    lock_release(&lock);
 203
 204    return m;
 205 }
 206
 207
 208 /// MovePicker::number_of_moves() simply returns the numOfMoves member
 209 /// variable.  It is intended to be used in positions where the side to move
 210 /// is in check, for detecting checkmates or situations where there is only
 211 /// a single reply to check.
 212
 213 int MovePicker::number_of_moves() const {
 214   return numOfMoves;
 215 }
 216
 217
 218 /// MovePicker::score_captures(), MovePicker::score_noncaptures(),
 219 /// MovePicker::score_evasions() and MovePicker::score_qcaptures() assign a
 220 /// numerical move ordering score to each move in a move list.  The moves
 221 /// with highest scores will be picked first by
 222 /// MovePicker::pick_move_from_list().
 223
 224 void MovePicker::score_captures() {
 225   // Winning and equal captures in the main search are ordered by MVV/LVA.
 226   // Suprisingly, this appears to perform slightly better than SEE based
 227   // move ordering.  The reason is probably that in a position with a winning
 228   // capture, capturing a more valuable (but sufficiently defended) piece
 229   // first usually doesn't hurt.  The opponent will have to recapture, and
 230   // the hanging piece will still be hanging (except in the unusual cases
 231   // where it is possible to recapture with the hanging piece).  Exchanging
 232   // big pieces before capturing a hanging piece probably helps to reduce
 233   // the subtree size.
 234   for(int i = 0; i < numOfMoves; i++) {
 235     int seeValue = pos->see(moves[i].move);
 236     if(seeValue >= 0) {
 237       if(move_promotion(moves[i].move))
 238         moves[i].score = QueenValueMidgame;
 239       else
 240         moves[i].score =
 241           int(pos->midgame_value_of_piece_on(move_to(moves[i].move))) -
 242           int(pos->type_of_piece_on(move_from(moves[i].move)));
 243     }
 244     else
 245       moves[i].score = seeValue;
 246
 247   }
 248 }
 249
 250 void MovePicker::score_noncaptures() {
 251   for(int i = 0; i < numOfMoves; i++) {
 252     Move m = moves[i].move;
 253     if(m == killer1)
 254       moves[i].score = HistoryMax + 2;
 255     else if(m == killer2)
 256       moves[i].score = HistoryMax + 1;
 257     else
 258       moves[i].score = H.move_ordering_score(pos->piece_on(move_from(m)), m);
 259   }
 260 }
 261
 262 void MovePicker::score_evasions() {
 263   for(int i = 0; i < numOfMoves; i++) {
 264     Move m = moves[i].move;
 265     if(m == ttMove)
 266       moves[i].score = 2*HistoryMax;
 267     else if(!pos->square_is_empty(move_to(m))) {
 268       int seeScore = pos->see(m);
 269       moves[i].score = (seeScore >= 0)? seeScore + HistoryMax : seeScore;
 270     }
 271     else
 272       moves[i].score = H.move_ordering_score(pos->piece_on(move_from(m)), m);
 273   }
 274 }
 275
 276 void MovePicker::score_qcaptures() {
 277   // Use MVV/LVA ordering.
 278   for(int i = 0; i < numOfMoves; i++) {
 279     Move m = moves[i].move;
 280     if(move_promotion(m))
 281       moves[i].score = QueenValueMidgame;
 282     else
 283       moves[i].score =
 284         int(pos->midgame_value_of_piece_on(move_to(m))) -
 285         int(pos->midgame_value_of_piece_on(move_to(m))) / 64;
 286   }
 287 }
 288
 289
 290 /// MovePicker::pick_move_from_list() picks the move with the biggest score
 291 /// from a list of generated moves (moves[] or badCaptures[], depending on
 292 /// the current move generation phase).  It takes care not to return the
 293 /// transposition table move if that has already been serched previously.
 294 /// While picking captures in the PH_GOOD_CAPTURES phase (i.e. while picking
 295 /// non-losing captures in the main search), it moves all captures with
 296 /// negative SEE values to the badCaptures[] array.
 297
 298 Move MovePicker::pick_move_from_list() {
 299   int bestScore = -10000000;
 300   int bestIndex;
 301   Move move;
 302
 303   switch(PhaseTable[phaseIndex]) {
 304
 305   case PH_GOOD_CAPTURES:
 306     assert(!pos->is_check());
 307     assert(movesPicked >= 0);
 308     while(movesPicked < numOfMoves) {
 309       bestScore = -10000000;
 310       bestIndex = -1;
 311       for(int i = movesPicked; i < numOfMoves; i++) {
 312         if(moves[i].score < 0) {
 313           // Losing capture, move it to the badCaptures[] array
 314           assert(numOfBadCaptures < 63);
 315           badCaptures[numOfBadCaptures++] = moves[i];
 316           moves[i--] = moves[--numOfMoves];
 317         }
 318         else if(moves[i].score > bestScore) {
 319           bestIndex = i;
 320           bestScore = moves[i].score;
 321         }
 322       }
 323       if(bestIndex != -1) { // Found a good capture
 324         move = moves[bestIndex].move;\r
 325         moves[bestIndex] = moves[movesPicked++];
 326         if(move != ttMove && move != mateKiller &&
 327            pos->move_is_legal(move, pinned))
 328           return move;
 329       }
 330     }
 331     break;
 332
 333   case PH_NONCAPTURES:
 334     assert(!pos->is_check());
 335     assert(movesPicked >= 0);
 336     while(movesPicked < numOfMoves) {
 337       bestScore = -10000000;
 338
 339       // If this is a PV node or we have only picked a few moves, scan
 340       // the entire move list for the best move.  If many moves have already
 341       // been searched and it is not a PV node, we are probably failing low
 342       // anyway, so we just pick the first move from the list.
 343       if(pvNode || movesPicked < 12) {
 344         bestIndex = -1;
 345         for(int i = movesPicked; i < numOfMoves; i++)
 346           if(moves[i].score > bestScore) {
 347             bestIndex = i;
 348             bestScore = moves[i].score;
 349           }
 350       }
 351       else
 352         bestIndex = movesPicked;
 353
 354       if(bestIndex != -1) {
 355         move = moves[bestIndex].move;\r
 356         moves[bestIndex] = moves[movesPicked++];
 357         if(move != ttMove && move != mateKiller &&
 358            pos->move_is_legal(move, pinned))
 359           return move;
 360       }
 361     }
 362     break;
 363
 364   case PH_EVASIONS:
 365     assert(pos->is_check());
 366     assert(movesPicked >= 0);
 367     while(movesPicked < numOfMoves) {
 368       bestScore = -10000000;
 369       bestIndex = -1;
 370       for(int i = movesPicked; i < numOfMoves; i++)
 371         if(moves[i].score > bestScore) {
 372           bestIndex = i;
 373           bestScore = moves[i].score;
 374         }
 375
 376       if(bestIndex != -1) {
 377         move = moves[bestIndex].move;\r
 378         moves[bestIndex] = moves[movesPicked++];
 379         return move;
 380       }
 381     }
 382     break;
 383
 384   case PH_BAD_CAPTURES:
 385     assert(!pos->is_check());
 386     assert(badCapturesPicked >= 0);
 387     // It's probably a good idea to use SEE move ordering here, instead
 388     // of just picking the first move.  FIXME
 389     while(badCapturesPicked < numOfBadCaptures) {
 390       move = badCaptures[badCapturesPicked++].move;
 391       if(move != ttMove && move != mateKiller &&
 392          pos->move_is_legal(move, pinned))
 393         return move;
 394     }
 395     break;
 396
 397   case PH_QCAPTURES:
 398     assert(!pos->is_check());
 399     assert(movesPicked >= 0);
 400     while(movesPicked < numOfMoves) {
 401       bestScore = -10000000;
 402       if(movesPicked < 4) {
 403         bestIndex = -1;
 404         for(int i = movesPicked; i < numOfMoves; i++)
 405           if(moves[i].score > bestScore) {
 406             bestIndex = i;
 407             bestScore = moves[i].score;
 408           }
 409       }
 410       else
 411         bestIndex = movesPicked;
 412
 413       if(bestIndex != -1) {
 414         move = moves[bestIndex].move;\r
 415         moves[bestIndex] = moves[movesPicked++];
 416         // Remember to change the line below if we decide to hash the qsearch!
 417         // Maybe also postpone the legality check until after futility pruning?
 418         if(/* move != ttMove && */ pos->move_is_legal(move, pinned))
 419           return move;
 420       }
 421     }
 422     break;
 423
 424   case PH_QCHECKS:
 425     assert(!pos->is_check());
 426     assert(movesPicked >= 0);
 427     // Perhaps we should do something better than just picking the first
 428     // move here?  FIXME
 429     while(movesPicked < numOfMoves) {
 430       move = moves[movesPicked++].move;
 431       // Remember to change the line below if we decide to hash the qsearch!
 432       if(/* move != ttMove && */ pos->move_is_legal(move, pinned))
 433         return move;
 434     }
 435     break;
 436
 437   default:
 438     break;
 439   }
 440
 441   return MOVE_NONE;
 442 }
 443
 444
 445 /// MovePicker::init_phase_table() initializes the PhaseTable[],
 446 /// MainSearchPhaseIndex, EvasionPhaseIndex, QsearchWithChecksPhaseIndex
 447 /// and QsearchWithoutChecksPhaseIndex variables.  It is only called once
 448 /// during program startup, and never again while the program is running.
 449
 450 void MovePicker::init_phase_table() {
 451   int i = 0;
 452
 453   // Main search
 454   MainSearchPhaseIndex = i - 1;
 455   PhaseTable[i++] = PH_TT_MOVE;
 456   PhaseTable[i++] = PH_MATE_KILLER;
 457   PhaseTable[i++] = PH_GOOD_CAPTURES;
 458   // PH_KILLER_1 and PH_KILLER_2 are not yet used.
 459   // PhaseTable[i++] = PH_KILLER_1;
 460   // PhaseTable[i++] = PH_KILLER_2;
 461   PhaseTable[i++] = PH_NONCAPTURES;
 462   PhaseTable[i++] = PH_BAD_CAPTURES;
 463   PhaseTable[i++] = PH_STOP;
 464
 465   // Check evasions
 466   EvasionsPhaseIndex = i - 1;
 467   PhaseTable[i++] = PH_EVASIONS;
 468   PhaseTable[i++] = PH_STOP;
 469
 470   // Quiescence search with checks
 471   QsearchWithChecksPhaseIndex = i - 1;
 472   PhaseTable[i++] = PH_QCAPTURES;
 473   PhaseTable[i++] = PH_QCHECKS;
 474   PhaseTable[i++] = PH_STOP;
 475
 476   // Quiescence search without checks
 477   QsearchWithoutChecksPhaseIndex = i - 1;
 478   PhaseTable[i++] = PH_QCAPTURES;
 479   PhaseTable[i++] = PH_STOP;
 480 }