Integrate next_stage() logic into next_move()

Measured bench speed up goes from 0,7% to 2%,
given the unreliable measure a reverse simmplification
test was done on fishtest:

master vs patch
LLR: -2.94 (-2.94,2.94) [-3.00,1.00]
Total: 15499 W: 2685 L: 2867 D: 9947

Test result is positive, master is weaker.

No functional change.

diff --git a/src/movepick.cpp b/src/movepick.cpp
index 4971b304ba0c12f550151564ba0fe5c038c5c61c..9611315c3a5aedc8c0e55f4d2d5fa23fa4ca3cd0 100644 (file)
--- a/src/movepick.cpp
+++ b/src/movepick.cpp
@@ -26,13 +26,13 @@
 namespace {
 
   enum Stages {
 namespace {
 
   enum Stages {

-    MAIN_SEARCH, GOOD_CAPTURES, KILLERS, QUIET, BAD_CAPTURES,
+    MAIN_SEARCH, GOOD_CAPTURES_INIT, GOOD_CAPTURES, KILLERS, KILLERS_2,
+    QUIET_INIT, QUIET, BAD_CAPTURES,

     EVASION, ALL_EVASIONS,
     EVASION, ALL_EVASIONS,

-    QSEARCH_WITH_CHECKS, QCAPTURES_1, CHECKS,
-    QSEARCH_WITHOUT_CHECKS, QCAPTURES_2,
-    PROBCUT, PROBCUT_CAPTURES,
+    QSEARCH_WITH_CHECKS, QCAPTURES_CHECKS_INIT, QCAPTURES_CHECKS, CHECKS,
+    QSEARCH_WITHOUT_CHECKS, QCAPTURES_NO_CHECKS, REMAINING,

     RECAPTURE, RECAPTURES,
     RECAPTURE, RECAPTURES,

-    STOP
+    PROBCUT, PROBCUT_INIT, PROBCUT_CAPTURES

   };
 
   // Our insertion sort, which is guaranteed to be stable, as it should be
   };
 
   // Our insertion sort, which is guaranteed to be stable, as it should be


@@ -77,7 +77,7 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d, Search::Stack* s)
 
   stage = pos.checkers() ? EVASION : MAIN_SEARCH;
   ttMove = ttm && pos.pseudo_legal(ttm) ? ttm : MOVE_NONE;
 
   stage = pos.checkers() ? EVASION : MAIN_SEARCH;
   ttMove = ttm && pos.pseudo_legal(ttm) ? ttm : MOVE_NONE;

-  endMoves += (ttMove != MOVE_NONE);
+  stage += (ttMove == MOVE_NONE);

 }
 
 MovePicker::MovePicker(const Position& p, Move ttm, Depth d, Square s)
 }
 
 MovePicker::MovePicker(const Position& p, Move ttm, Depth d, Square s)


@@ -98,11 +98,11 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d, Square s)
   {
       stage = RECAPTURE;
       recaptureSquare = s;
   {
       stage = RECAPTURE;
       recaptureSquare = s;

-      ttm = MOVE_NONE;
+      return;

   }
 
   ttMove = ttm && pos.pseudo_legal(ttm) ? ttm : MOVE_NONE;
   }
 
   ttMove = ttm && pos.pseudo_legal(ttm) ? ttm : MOVE_NONE;

-  endMoves += (ttMove != MOVE_NONE);
+  stage += (ttMove == MOVE_NONE);

 }
 
 MovePicker::MovePicker(const Position& p, Move ttm, Value th)
 }
 
 MovePicker::MovePicker(const Position& p, Move ttm, Value th)


@@ -118,7 +118,7 @@ MovePicker::MovePicker(const Position& p, Move ttm, Value th)
           && pos.capture(ttm)
           && pos.see(ttm) > threshold ? ttm : MOVE_NONE;
 
           && pos.capture(ttm)
           && pos.see(ttm) > threshold ? ttm : MOVE_NONE;
 

-  endMoves += (ttMove != MOVE_NONE);
+  stage += (ttMove == MOVE_NONE);

 }
 
 
 }
 
 


@@ -179,70 +179,6 @@ void MovePicker::score<EVASIONS>() {
           m.value = history[pos.moved_piece(m)][to_sq(m)] + fromTo.get(c, m);
 }
 
           m.value = history[pos.moved_piece(m)][to_sq(m)] + fromTo.get(c, m);
 }
 

-
-/// generate_next_stage() generates, scores, and sorts the next bunch of moves
-/// when there are no more moves to try for the current stage.
-
-void MovePicker::generate_next_stage() {
-
-  assert(stage != STOP);
-
-  cur = moves;
-
-  switch (++stage) {
-
-  case GOOD_CAPTURES: case QCAPTURES_1: case QCAPTURES_2:
-  case PROBCUT_CAPTURES: case RECAPTURES:
-      endMoves = generate<CAPTURES>(pos, moves);
-      score<CAPTURES>();
-      break;
-
-  case KILLERS:
-      killers[0] = ss->killers[0];
-      killers[1] = ss->killers[1];
-      killers[2] = countermove;
-      cur = killers;
-      endMoves = cur + 2 + (countermove != killers[0] && countermove != killers[1]);
-      break;
-
-  case QUIET:
-      endMoves = generate<QUIETS>(pos, moves);
-      score<QUIETS>();
-      if (depth < 3 * ONE_PLY)
-      {
-          ExtMove* goodQuiet = std::partition(cur, endMoves, [](const ExtMove& m)
-                                             { return m.value > VALUE_ZERO; });
-          insertion_sort(cur, goodQuiet);
-      } else
-          insertion_sort(cur, endMoves);
-      break;
-
-  case BAD_CAPTURES:
-      // Just pick them in reverse order to get correct ordering
-      cur = moves + MAX_MOVES - 1;
-      endMoves = endBadCaptures;
-      break;
-
-  case ALL_EVASIONS:
-      endMoves = generate<EVASIONS>(pos, moves);
-      if (endMoves - moves > 1)
-          score<EVASIONS>();
-      break;
-
-  case CHECKS:
-      endMoves = generate<QUIET_CHECKS>(pos, moves);
-      break;
-
-  case EVASION: case QSEARCH_WITH_CHECKS: case QSEARCH_WITHOUT_CHECKS:
-  case PROBCUT: case RECAPTURE: case STOP:
-      stage = STOP;
-      break;
-
-  default:
-      assert(false);
-  }
-}
-

 int MovePicker::see_sign() const
 {
   return  stage == GOOD_CAPTURES ?  1
 int MovePicker::see_sign() const
 {
   return  stage == GOOD_CAPTURES ?  1


@@ -258,80 +194,166 @@ Move MovePicker::next_move() {
 
   Move move;
 
 
   Move move;
 

-  while (true)
-  {
-      while (cur == endMoves && stage != STOP)
-          generate_next_stage();
+  switch (stage) {

 
 

-      switch (stage) {
+  case MAIN_SEARCH: case EVASION: case QSEARCH_WITH_CHECKS:
+  case QSEARCH_WITHOUT_CHECKS: case PROBCUT:
+      ++stage;
+      return ttMove;

 
 

-      case MAIN_SEARCH: case EVASION: case QSEARCH_WITH_CHECKS:
-      case QSEARCH_WITHOUT_CHECKS: case PROBCUT:
-          ++cur;
-          return ttMove;
+  case GOOD_CAPTURES_INIT:
+      endBadCaptures = cur = moves;
+      endMoves = generate<CAPTURES>(pos, cur);
+      score<CAPTURES>();
+      ++stage;

 
 

-      case GOOD_CAPTURES:
+  case GOOD_CAPTURES:
+      while (cur < endMoves)
+      {

           move = pick_best(cur++, endMoves);
           if (move != ttMove)
           {
               if (pos.see_sign(move) >= VALUE_ZERO)
                   return move;
 
           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;
+              // Losing capture, move it to the beginning of the array
+              *endBadCaptures++ = move;

           }
           }

-          break;
+      }
+      ++stage;

 
 

-      case KILLERS:
-          move = *cur++;
-          if (    move != MOVE_NONE
-              &&  move != ttMove
-              &&  pos.pseudo_legal(move)
-              && !pos.capture(move))
-              return move;
-          break;
+      // First killer move
+      move = ss->killers[0];
+      if (    move != MOVE_NONE
+          &&  move != ttMove
+          &&  pos.pseudo_legal(move)
+          && !pos.capture(move))
+          return move;
+
+  case KILLERS:
+      ++stage;
+      move = ss->killers[1]; // Second killer move
+      if (    move != MOVE_NONE
+          &&  move != ttMove
+          &&  pos.pseudo_legal(move)
+          && !pos.capture(move))
+          return move;
+
+  case KILLERS_2:
+      ++stage;
+      move = countermove;
+      if (    move != MOVE_NONE
+          &&  move != ttMove
+          &&  move != ss->killers[0]
+          &&  move != ss->killers[1]
+          &&  pos.pseudo_legal(move)
+          && !pos.capture(move))
+          return move;
+
+  case QUIET_INIT:
+      cur = endBadCaptures;
+      endMoves = generate<QUIETS>(pos, cur);
+      score<QUIETS>();
+      if (depth < 3 * ONE_PLY)
+      {
+          ExtMove* goodQuiet = std::partition(cur, endMoves, [](const ExtMove& m)
+                                             { return m.value > VALUE_ZERO; });
+          insertion_sort(cur, goodQuiet);
+      } else
+          insertion_sort(cur, endMoves);
+      ++stage;

 
 

-      case QUIET:
+  case QUIET:
+      while (cur < endMoves)
+      {

           move = *cur++;
           if (   move != ttMove
           move = *cur++;
           if (   move != ttMove

-              && move != killers[0]
-              && move != killers[1]
-              && move != killers[2])
+              && move != ss->killers[0]
+              && move != ss->killers[1]
+              && move != countermove)

               return move;
               return move;

-          break;
+      }
+      ++stage;
+      cur = moves; // Point to beginning of bad captures

 
 

-      case BAD_CAPTURES:
-          return *cur--;
+  case BAD_CAPTURES:
+      if (cur < endBadCaptures)
+          return *cur++;
+      break;
+
+  case ALL_EVASIONS:
+      cur = moves;
+      endMoves = generate<EVASIONS>(pos, cur);
+      if (endMoves - cur > 1)
+          score<EVASIONS>();
+      stage = REMAINING;
+      goto remaining;
+
+  case QCAPTURES_CHECKS_INIT:
+  case QCAPTURES_NO_CHECKS:
+      cur = moves;
+      endMoves = generate<CAPTURES>(pos, cur);
+      score<CAPTURES>();
+      ++stage;

 
 

-      case ALL_EVASIONS: case QCAPTURES_1: case QCAPTURES_2:
+remaining:
+  case QCAPTURES_CHECKS:
+  case REMAINING:
+      while (cur < endMoves)
+      {

           move = pick_best(cur++, endMoves);
           if (move != ttMove)
               return move;
           move = pick_best(cur++, endMoves);
           if (move != ttMove)
               return move;

+      }
+      if (stage == REMAINING)

           break;
           break;

+      cur = moves;
+      endMoves = generate<QUIET_CHECKS>(pos, cur);
+      ++stage;

 
 

-      case PROBCUT_CAPTURES:
-           move = pick_best(cur++, endMoves);
-           if (move != ttMove && pos.see(move) > threshold)
-               return move;
-           break;
+  case CHECKS:
+      while (cur < endMoves)
+      {
+          move = cur++->move;
+          if (move != ttMove)
+              return move;
+      }
+      break;

 
 

-      case RECAPTURES:
+  case RECAPTURE:
+      cur = moves;
+      endMoves = generate<CAPTURES>(pos, cur);
+      score<CAPTURES>();
+      ++stage;
+
+  case RECAPTURES:
+      while (cur < endMoves)
+      {

           move = pick_best(cur++, endMoves);
           if (to_sq(move) == recaptureSquare)
               return move;
           move = pick_best(cur++, endMoves);
           if (to_sq(move) == recaptureSquare)
               return move;

-          break;
-
-      case CHECKS:
-          move = *cur++;
-          if (move != ttMove)
-              return move;
-          break;
+      }
+      break;

 
 

-      case STOP:
-          return MOVE_NONE;
+  case PROBCUT_INIT:
+      cur = moves;
+      endMoves = generate<CAPTURES>(pos, cur);
+      score<CAPTURES>();
+      ++stage;

 
 

-      default:
-          assert(false);
+  case PROBCUT_CAPTURES:
+      while (cur < endMoves)
+      {
+          move = pick_best(cur++, endMoves);
+          if (   move != ttMove
+              && pos.see(move) > threshold)
+              return move;

       }
       }

+      break;
+
+  default:
+      assert(false);

   }
   }

+
+  return MOVE_NONE;

 }
 }

diff --git a/src/movepick.h b/src/movepick.h
index e69255e604b117f38e1900b397fff43ec159e398..1e1b8e6d1f721a3f5701d4e6e0301cf43b692bc8 100644 (file)
--- a/src/movepick.h
+++ b/src/movepick.h
@@ -108,8 +108,7 @@ public:
 
 private:
   template<GenType> void score();
 
 private:
   template<GenType> void score();

-  void generate_next_stage();
-  ExtMove* begin() { return moves; }
+  ExtMove* begin() { return cur; }

   ExtMove* end() { return endMoves; }
 
   const Position& pos;
   ExtMove* end() { return endMoves; }
 
   const Position& pos;


@@ -117,12 +116,11 @@ private:
   Move countermove;
   Depth depth;
   Move ttMove;
   Move countermove;
   Depth depth;
   Move ttMove;

-  ExtMove killers[3];

   Square recaptureSquare;
   Value threshold;
   int stage;
   Square recaptureSquare;
   Value threshold;
   int stage;

-  ExtMove* endBadCaptures = moves + MAX_MOVES - 1;
-  ExtMove moves[MAX_MOVES], *cur = moves, *endMoves = moves;
+  ExtMove* cur, *endMoves, *endBadCaptures;
+  ExtMove moves[MAX_MOVES];

 };
 
 #endif // #ifndef MOVEPICK_H_INCLUDED
 };
 
 #endif // #ifndef MOVEPICK_H_INCLUDED