X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fmovepick.cpp;h=9ada404b299bacc6c5c127c66eab4ce32a303987;hp=797f5e9497ab14e6d142a0bad75b560914f6018a;hb=59f64fda4fffe595d53183caae94b1d9a2062f32;hpb=e1ed67aacbe7fb4b462b9141d3137bed0a3ea70b

diff --git a/src/movepick.cpp b/src/movepick.cpp
index 797f5e94..3fe09bb7 100644
--- a/src/movepick.cpp
+++ b/src/movepick.cpp
@@ -1,7 +1,7 @@
 /*
   Stockfish, a UCI chess playing engine derived from Glaurung 2.1
   Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
-  Copyright (C) 2008-2009 Marco Costalba
+  Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad
 
   Stockfish is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
@@ -18,405 +18,331 @@
   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
 
-
-////
-//// Includes
-////
-
-#include <algorithm>
 #include <cassert>
 
-#include "history.h"
-#include "evaluate.h"
-#include "movegen.h"
 #include "movepick.h"
-#include "search.h"
-#include "value.h"
-
-
-////
-//// Local definitions
-////
+#include "thread.h"
 
 namespace {
 
-  /// Variables
-
-  MovePicker::MovegenPhase PhaseTable[32];
-  int MainSearchPhaseIndex;
-  int EvasionsPhaseIndex;
-  int QsearchWithChecksPhaseIndex;
-  int QsearchWithoutChecksPhaseIndex;
+  enum Stages {
+    MAIN_SEARCH, CAPTURES_S1, KILLERS_S1, QUIETS_1_S1, QUIETS_2_S1, BAD_CAPTURES_S1,
+    EVASION,     EVASIONS_S2,
+    QSEARCH_0,   CAPTURES_S3, QUIET_CHECKS_S3,
+    QSEARCH_1,   CAPTURES_S4,
+    PROBCUT,     CAPTURES_S5,
+    RECAPTURE,   CAPTURES_S6,
+    STOP
+  };
+
+  // Our insertion sort, which is guaranteed to be stable, as it should be
+  void insertion_sort(ExtMove* begin, ExtMove* end)
+  {
+    ExtMove tmp, *p, *q;
 
-}
+    for (p = begin + 1; p < end; ++p)
+    {
+        tmp = *p;
+        for (q = p; q != begin && *(q-1) < tmp; --q)
+            *q = *(q-1);
+        *q = tmp;
+    }
+  }
 
+  // pick_best() finds the best move in the range (begin, end) and moves it to
+  // the front. It's faster than sorting all the moves in advance when there
+  // are few moves e.g. the possible captures.
+  Move pick_best(ExtMove* begin, ExtMove* end)
+  {
+      std::swap(*begin, *std::max_element(begin, end));
+      return *begin;
+  }
 
-////
-//// Functions
-////
+} // namespace
 
 
-/// Constructor for the MovePicker class.  Apart from the position for which
-/// it is asked to pick legal moves, MovePicker also wants some information
-/// to help it to return the presumably good moves first, to decide which
+/// Constructors of the MovePicker class. As arguments we pass information
+/// to help it to return the (presumably) good moves first, to decide which
 /// moves to return (in the quiescence search, for instance, we only want to
-/// search captures, promotions and some checks) and about how important good
-/// move ordering is at the current node.
+/// search captures, promotions and some checks) and how important good move
+/// ordering is at the current node.
 
-MovePicker::MovePicker(const Position& p, bool pv, Move ttm, Depth d, SearchStack* ss) : pos(p) {
+MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats& h, const CounterMovesHistoryStats& cmh,
+                       Move cm, Search::Stack* s) : pos(p), history(h), counterMovesHistory(cmh), depth(d) {
 
-  pvNode = pv;
-  ttMove = ttm;
-  if (ss)
-  {
-      mateKiller = (ss->mateKiller == ttm)? MOVE_NONE : ss->mateKiller;
-      killer1 = ss->killers[0];
-      killer2 = ss->killers[1];
-  } else
-      mateKiller = killer1 = killer2 = MOVE_NONE;
-
-  depth = d;
-  movesPicked = 0;
-  numOfMoves = 0;
-  numOfBadCaptures = 0;
-  checkKillers = checkLegal = false;
-
-  if (p.is_check())
-      phaseIndex = EvasionsPhaseIndex;
-  else if (depth > Depth(0))
-      phaseIndex = MainSearchPhaseIndex;
-  else if (depth == Depth(0))
-      phaseIndex = QsearchWithChecksPhaseIndex;
-  else
-      phaseIndex = QsearchWithoutChecksPhaseIndex;
+  assert(d > DEPTH_ZERO);
 
-  Color us = pos.side_to_move();
+  endBadCaptures = moves + MAX_MOVES - 1;
+  countermove = cm;
+  ss = s;
 
-  dc = p.discovered_check_candidates(us);
-  pinned = p.pinned_pieces(us);
+  if (pos.checkers())
+      stage = EVASION;
+
+  else
+      stage = MAIN_SEARCH;
 
-  finished = false;
+  ttMove = (ttm && pos.pseudo_legal(ttm) ? ttm : MOVE_NONE);
+  endMoves += (ttMove != MOVE_NONE);
 }
 
+MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats& h, const CounterMovesHistoryStats& cmh,
+                       Square s) : pos(p), history(h), counterMovesHistory(cmh) {
 
-/// MovePicker::get_next_move() is the most important method of the MovePicker
-/// class.  It returns a new legal move every time it is called, until there
-/// are no more moves left of the types we are interested in.
+  assert(d <= DEPTH_ZERO);
 
-Move MovePicker::get_next_move() {
+  if (pos.checkers())
+      stage = EVASION;
 
-  Move move;
+  else if (d > DEPTH_QS_NO_CHECKS)
+      stage = QSEARCH_0;
 
-  while (true)
-  {
-    // If we already have a list of generated moves, pick the best move from
-    // the list, and return it.
-    move = pick_move_from_list();
-    if (move != MOVE_NONE)
-    {
-        assert(move_is_ok(move));
-        return move;
-    }
+  else if (d > DEPTH_QS_RECAPTURES)
+      stage = QSEARCH_1;
 
-    // Next phase
-    phaseIndex++;
-    switch (PhaseTable[phaseIndex]) {
-
-    case PH_TT_MOVE:
-        if (ttMove != MOVE_NONE)
-        {
-            assert(move_is_ok(ttMove));
-            if (move_is_legal(pos, ttMove, pinned))
-                return ttMove;
-        }
-        break;
-
-    case PH_MATE_KILLER:
-        if (mateKiller != MOVE_NONE)
-        {
-            assert(move_is_ok(mateKiller));
-            if (move_is_legal(pos, mateKiller, pinned))
-                return mateKiller;
-        }
-        break;
-
-    case PH_GOOD_CAPTURES:
-        numOfMoves = generate_captures(pos, moves);
-        score_captures();
-        std::sort(moves, moves + numOfMoves);
-        movesPicked = 0;
-        checkLegal = true;
-        break;
-
-    case PH_KILLERS:
-        movesPicked = numOfMoves = 0;
-        checkLegal = false;
-        if (killer1 != MOVE_NONE && move_is_legal(pos, killer1, pinned) && !pos.move_is_capture(killer1))
-            moves[numOfMoves++].move = killer1;
-        if (killer2 != MOVE_NONE && move_is_legal(pos, killer2, pinned) && !pos.move_is_capture(killer2) )
-            moves[numOfMoves++].move = killer2;
-        break;
-
-    case PH_NONCAPTURES:
-        checkKillers = (numOfMoves != 0); // previous phase is PH_KILLERS
-        numOfMoves = generate_noncaptures(pos, moves);
-        score_noncaptures();
-        std::sort(moves, moves + numOfMoves);
-        movesPicked = 0;
-        checkLegal = true;
-        break;
-
-    case PH_BAD_CAPTURES:
-        // Bad captures SEE value is already calculated by score_captures()
-        // so just sort them to get SEE move ordering.
-        std::sort(badCaptures, badCaptures + numOfBadCaptures);
-        movesPicked = 0;
-        break;
-
-    case PH_EVASIONS:
-        assert(pos.is_check());
-        numOfMoves = generate_evasions(pos, moves, pinned);
-        score_evasions();
-        std::sort(moves, moves + numOfMoves);
-        movesPicked = 0;
-        break;
-
-    case PH_QCAPTURES:
-        numOfMoves = generate_captures(pos, moves);
-        score_qcaptures();
-        std::sort(moves, moves + numOfMoves);
-        movesPicked = 0;
-        break;
-
-    case PH_QCHECKS:
-        // Perhaps we should order moves move here?  FIXME
-        numOfMoves = generate_non_capture_checks(pos, moves, dc);
-        movesPicked = 0;
-        break;
-
-    case PH_STOP:
-        return MOVE_NONE;
-
-    default:
-        assert(false);
-        return MOVE_NONE;
-    }
+  else
+  {
+      stage = RECAPTURE;
+      recaptureSquare = s;
+      ttm = MOVE_NONE;
   }
+
+  ttMove = (ttm && pos.pseudo_legal(ttm) ? ttm : MOVE_NONE);
+  endMoves += (ttMove != MOVE_NONE);
 }
 
+MovePicker::MovePicker(const Position& p, Move ttm, const HistoryStats& h, const CounterMovesHistoryStats& cmh, PieceType pt)
+                       : pos(p), history(h), counterMovesHistory(cmh) {
 
-/// A variant of get_next_move() which takes a lock as a parameter, used to
-/// prevent multiple threads from picking the same move at a split point.
+  assert(!pos.checkers());
 
-Move MovePicker::get_next_move(Lock &lock) {
+  stage = PROBCUT;
 
-   lock_grab(&lock);
-   if (finished)
-   {
-       lock_release(&lock);
-       return MOVE_NONE;
-   }
-   Move m = get_next_move();
-   if (m == MOVE_NONE)
-       finished = true;
+  // In ProbCut we generate only captures that are better than the parent's
+  // captured piece.
+  captureThreshold = PieceValue[MG][pt];
+  ttMove = (ttm && pos.pseudo_legal(ttm) ? ttm : MOVE_NONE);
 
-   lock_release(&lock);
-   return m;
-}
+  if (ttMove && (!pos.capture(ttMove) || pos.see(ttMove) <= captureThreshold))
+      ttMove = MOVE_NONE;
 
+  endMoves += (ttMove != MOVE_NONE);
+}
 
-/// MovePicker::score_captures(), MovePicker::score_noncaptures(),
-/// MovePicker::score_evasions() and MovePicker::score_qcaptures() assign a
-/// numerical move ordering score to each move in a move list.  The moves
-/// with highest scores will be picked first by pick_move_from_list().
 
-void MovePicker::score_captures() {
-  // Winning and equal captures in the main search are ordered by MVV/LVA.
+/// score() assign a numerical value to each move in a move list. The moves with
+/// highest values will be picked first.
+template<>
+void MovePicker::score<CAPTURES>() {
+  // Winning and equal captures in the main search are ordered by MVV.
   // Suprisingly, this appears to perform slightly better than SEE based
-  // move ordering.  The reason is probably that in a position with a winning
-  // capture, capturing a more valuable (but sufficiently defended) piece
-  // first usually doesn't hurt.  The opponent will have to recapture, and
+  // move ordering. The reason is probably that in a position with a winning
+  // capture, capturing a valuable (but sufficiently defended) piece
+  // first usually doesn't hurt. The opponent will have to recapture, and
   // the hanging piece will still be hanging (except in the unusual cases
   // where it is possible to recapture with the hanging piece). Exchanging
   // big pieces before capturing a hanging piece probably helps to reduce
   // the subtree size.
-  // While scoring captures it moves all captures with negative SEE values
-  // to the badCaptures[] array.
-  Move m;
-  int seeValue;
-
-  for (int i = 0; i < numOfMoves; i++)
-  {
-      m = moves[i].move;
-      seeValue = pos.see(m);
-      if (seeValue >= 0)
-      {
-          if (move_promotion(m))
-              moves[i].score = QueenValueMidgame;
-          else
-              moves[i].score = int(pos.midgame_value_of_piece_on(move_to(m)))
-                              -int(pos.type_of_piece_on(move_from(m)));
-      }
-      else
-      {
-          // Losing capture, move it to the badCaptures[] array
-          assert(numOfBadCaptures < 63);
-          moves[i].score = seeValue;
-          badCaptures[numOfBadCaptures++] = moves[i];
-          moves[i--] = moves[--numOfMoves];
-      }
+  // In main search we want to push captures with negative SEE values to the
+  // badCaptures[] array, but instead of doing it now we delay until the move
+  // has been picked up in pick_move_from_list(). This way we save some SEE
+  // calls in case we get a cutoff.
+  for (auto& m : *this){
+      m.value = PieceValue[MG][pos.piece_on(to_sq(m))] - 200*relative_rank(pos.side_to_move(), to_sq(m));
   }
 }
 
-void MovePicker::score_noncaptures() {
-  // First score by history, when no history is available then use
-  // piece/square tables values. This seems to be better then a
-  // random choice when we don't have an history for any move.
-  Move m;
-  int hs;
+template<>
+void MovePicker::score<QUIETS>() {
 
-  for (int i = 0; i < numOfMoves; i++)
-  {
-      m = moves[i].move;
-      hs = H.move_ordering_score(pos.piece_on(move_from(m)), move_to(m));
-
-      // Ensure history is always preferred to pst
-      if (hs > 0)
-          hs += 1000;
+  Square prevSq = to_sq((ss-1)->currentMove);
+  const HistoryStats& cmh = counterMovesHistory[pos.piece_on(prevSq)][prevSq];
 
-      // pst based scoring
-      moves[i].score = hs + pos.mg_pst_delta(m);
-  }
+  for (auto& m : *this)
+      m.value =  history[pos.moved_piece(m)][to_sq(m)]
+               + cmh[pos.moved_piece(m)][to_sq(m)] * 3;
 }
 
-void MovePicker::score_evasions() {
-
-  for (int i = 0; i < numOfMoves; i++)
-  {
-      Move m = moves[i].move;
-      if (m == ttMove)
-          moves[i].score = 2*HistoryMax;
-      else if (!pos.square_is_empty(move_to(m)))
-      {
-          int seeScore = pos.see(m);
-          moves[i].score = (seeScore >= 0)? seeScore + HistoryMax : seeScore;
-      } else
-          moves[i].score = H.move_ordering_score(pos.piece_on(move_from(m)), move_to(m));
-  }
-}
+template<>
+void MovePicker::score<EVASIONS>() {
+  // Try good captures ordered by MVV/LVA, then non-captures if destination square
+  // is not under attack, ordered by history value, then bad-captures and quiet
+  // moves with a negative SEE. This last group is ordered by the SEE value.
+  Value see;
 
-void MovePicker::score_qcaptures() {
+  for (auto& m : *this)
+      if ((see = pos.see_sign(m)) < VALUE_ZERO)
+          m.value = see - HistoryStats::Max; // At the bottom
 
-  // Use MVV/LVA ordering
-  for (int i = 0; i < numOfMoves; i++)
-  {
-      Move m = moves[i].move;
-      if (move_promotion(m))
-          moves[i].score = QueenValueMidgame;
+      else if (pos.capture(m))
+          m.value =  PieceValue[MG][pos.piece_on(to_sq(m))]
+                   - Value(type_of(pos.moved_piece(m))) + HistoryStats::Max;
       else
-          moves[i].score = int(pos.midgame_value_of_piece_on(move_to(m)))
-                          -int(pos.type_of_piece_on(move_from(m)));
-  }
+          m.value = history[pos.moved_piece(m)][to_sq(m)];
 }
 
 
-/// MovePicker::pick_move_from_list() picks the move with the biggest score
-/// from a list of generated moves (moves[] or badCaptures[], depending on
-/// the current move generation phase).  It takes care not to return the
-/// transposition table move if that has already been serched previously.
+/// generate_next_stage() generates, scores and sorts the next bunch of moves,
+/// when there are no more moves to try for the current stage.
 
-Move MovePicker::pick_move_from_list() {
+void MovePicker::generate_next_stage() {
 
-  assert(movesPicked >= 0);
-  assert(!pos.is_check() || PhaseTable[phaseIndex] == PH_EVASIONS || PhaseTable[phaseIndex] == PH_STOP);
-  assert( pos.is_check() || PhaseTable[phaseIndex] != PH_EVASIONS);
+  cur = moves;
 
-  switch (PhaseTable[phaseIndex]) {
+  switch (++stage) {
 
-  case PH_GOOD_CAPTURES:
-  case PH_KILLERS:
-  case PH_NONCAPTURES:
-      while (movesPicked < numOfMoves)
-      {
-          Move move = moves[movesPicked++].move;
-          if (   move != ttMove
-              && move != mateKiller
-              && (!checkKillers || (move != killer1 && move != killer2))
-              && (!checkLegal || pos.pl_move_is_legal(move, pinned)))
-              return move;
-      }
+  case CAPTURES_S1: case CAPTURES_S3: case CAPTURES_S4: case CAPTURES_S5: case CAPTURES_S6:
+      endMoves = generate<CAPTURES>(pos, moves);
+      score<CAPTURES>();
       break;
 
-  case PH_EVASIONS:
-      if (movesPicked < numOfMoves)
-          return moves[movesPicked++].move;
+  case KILLERS_S1:
+      cur = killers;
+      endMoves = cur + 2;
+
+      killers[0] = ss->killers[0];
+      killers[1] = ss->killers[1];
+      killers[2].move = MOVE_NONE;
 
+      // Be sure countermoves are different from killers
+      if (   countermove != killers[0]
+          && countermove != killers[1])
+          *endMoves++ = countermove;
       break;
 
-  case PH_BAD_CAPTURES:
-      while (movesPicked < numOfBadCaptures)
-      {
-          Move move = badCaptures[movesPicked++].move;
-          if (   move != ttMove
-              && move != mateKiller
-              && pos.pl_move_is_legal(move, pinned))
-              return move;
-      }
+  case QUIETS_1_S1:
+      endQuiets = endMoves = generate<QUIETS>(pos, moves);
+      score<QUIETS>();
+      endMoves = std::partition(cur, endMoves, [](const ExtMove& m) { return m.value > VALUE_ZERO; });
+      insertion_sort(cur, endMoves);
       break;
 
-  case PH_QCAPTURES:
-  case PH_QCHECKS:
-      while (movesPicked < numOfMoves)
-      {
-          Move move = moves[movesPicked++].move;
-          // Maybe postpone the legality check until after futility pruning?
-          if (   move != ttMove
-              && pos.pl_move_is_legal(move, pinned))
-              return move;
-      }
+  case QUIETS_2_S1:
+      cur = endMoves;
+      endMoves = endQuiets;
+      if (depth >= 3 * ONE_PLY)
+          insertion_sort(cur, endMoves);
       break;
 
-  default:
+  case BAD_CAPTURES_S1:
+      // Just pick them in reverse order to get MVV/LVA ordering
+      cur = moves + MAX_MOVES - 1;
+      endMoves = endBadCaptures;
       break;
+
+  case EVASIONS_S2:
+      endMoves = generate<EVASIONS>(pos, moves);
+      if (endMoves - moves > 1)
+          score<EVASIONS>();
+      break;
+
+  case QUIET_CHECKS_S3:
+      endMoves = generate<QUIET_CHECKS>(pos, moves);
+      break;
+
+  case EVASION: case QSEARCH_0: case QSEARCH_1: case PROBCUT: case RECAPTURE:
+      stage = STOP;
+      /* Fall through */
+
+  case STOP:
+      endMoves = cur + 1; // Avoid another generate_next_stage() call
+      break;
+
+  default:
+      assert(false);
   }
-  return MOVE_NONE;
 }
 
 
-/// MovePicker::init_phase_table() initializes the PhaseTable[],
-/// MainSearchPhaseIndex, EvasionPhaseIndex, QsearchWithChecksPhaseIndex
-/// and QsearchWithoutChecksPhaseIndex. It is only called once during
-/// program startup, and never again while the program is running.
-
-void MovePicker::init_phase_table() {
-
-  int i = 0;
-
-  // Main search
-  MainSearchPhaseIndex = i - 1;
-  PhaseTable[i++] = PH_TT_MOVE;
-  PhaseTable[i++] = PH_MATE_KILLER;
-  PhaseTable[i++] = PH_GOOD_CAPTURES;
-  PhaseTable[i++] = PH_KILLERS;
-  PhaseTable[i++] = PH_NONCAPTURES;
-  PhaseTable[i++] = PH_BAD_CAPTURES;
-  PhaseTable[i++] = PH_STOP;
-
-  // Check evasions
-  EvasionsPhaseIndex = i - 1;
-  PhaseTable[i++] = PH_EVASIONS;
-  PhaseTable[i++] = PH_STOP;
-
-  // Quiescence search with checks
-  QsearchWithChecksPhaseIndex = i - 1;
-  PhaseTable[i++] = PH_TT_MOVE;
-  PhaseTable[i++] = PH_QCAPTURES;
-  PhaseTable[i++] = PH_QCHECKS;
-  PhaseTable[i++] = PH_STOP;
-
-  // Quiescence search without checks
-  QsearchWithoutChecksPhaseIndex = i - 1;
-  PhaseTable[i++] = PH_TT_MOVE;
-  PhaseTable[i++] = PH_QCAPTURES;
-  PhaseTable[i++] = PH_STOP;
+/// next_move() is the most important method of the MovePicker class. It returns
+/// a new pseudo legal move every time it is called, until there are no more moves
+/// left. It picks the move with the biggest value from a list of generated moves
+/// taking care not to return the ttMove if it has already been searched.
+template<>
+Move MovePicker::next_move<false>() {
+
+  Move move;
+
+  while (true)
+  {
+      while (cur == endMoves)
+          generate_next_stage();
+
+      switch (stage) {
+
+      case MAIN_SEARCH: case EVASION: case QSEARCH_0: case QSEARCH_1: case PROBCUT:
+          ++cur;
+          return ttMove;
+
+      case CAPTURES_S1:
+          move = pick_best(cur++, endMoves);
+          if (move != ttMove)
+          {
+              if (pos.see_sign(move) >= VALUE_ZERO)
+                  return move;
+
+              // Losing capture, move it to the tail of the array
+              *endBadCaptures-- = move;
+          }
+          break;
+
+      case KILLERS_S1:
+          move = *cur++;
+          if (    move != MOVE_NONE
+              &&  move != ttMove
+              &&  pos.pseudo_legal(move)
+              && !pos.capture(move))
+              return move;
+          break;
+
+      case QUIETS_1_S1: case QUIETS_2_S1:
+          move = *cur++;
+          if (   move != ttMove
+              && move != killers[0]
+              && move != killers[1]
+              && move != killers[2])
+              return move;
+          break;
+
+      case BAD_CAPTURES_S1:
+          return *cur--;
+
+      case EVASIONS_S2: case CAPTURES_S3: case CAPTURES_S4:
+          move = pick_best(cur++, endMoves);
+          if (move != ttMove)
+              return move;
+          break;
+
+      case CAPTURES_S5:
+           move = pick_best(cur++, endMoves);
+           if (move != ttMove && pos.see(move) > captureThreshold)
+               return move;
+           break;
+
+      case CAPTURES_S6:
+          move = pick_best(cur++, endMoves);
+          if (to_sq(move) == recaptureSquare)
+              return move;
+          break;
+
+      case QUIET_CHECKS_S3:
+          move = *cur++;
+          if (move != ttMove)
+              return move;
+          break;
+
+      case STOP:
+          return MOVE_NONE;
+
+      default:
+          assert(false);
+      }
+  }
 }
+
+
+/// Version of next_move() to use at split point nodes where the move is grabbed
+/// from the split point's shared MovePicker object. This function is not thread
+/// safe so must be lock protected by the caller.
+template<>
+Move MovePicker::next_move<true>() { return ss->splitPoint->movePicker->next_move<false>(); }