Integrate next_stage() logic into next_move()
authorsyzygy <syzygy@server.fake>
Sat, 10 Sep 2016 19:37:36 +0000 (21:37 +0200)
committerMarco Costalba <mcostalba@gmail.com>
Tue, 13 Sep 2016 05:14:09 +0000 (07:14 +0200)
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.

src/movepick.cpp
src/movepick.h

index 4971b30..9611315 100644 (file)
 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,
-    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,
-    STOP
+    PROBCUT, PROBCUT_INIT, PROBCUT_CAPTURES
   };
 
   // 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;
-  endMoves += (ttMove != MOVE_NONE);
+  stage += (ttMove == MOVE_NONE);
 }
 
 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;
-      ttm = MOVE_NONE;
+      return;
   }
 
   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)
@@ -118,7 +118,7 @@ MovePicker::MovePicker(const Position& p, Move ttm, Value th)
           && 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);
 }
 
-
-/// 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
@@ -258,80 +194,166 @@ Move MovePicker::next_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;
 
-              // 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 != killers[0]
-              && move != killers[1]
-              && move != killers[2])
+              && move != ss->killers[0]
+              && move != ss->killers[1]
+              && move != countermove)
               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;
+      }
+      if (stage == REMAINING)
           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;
-          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;
 }
index e69255e..1e1b8e6 100644 (file)
@@ -108,8 +108,7 @@ public:
 
 private:
   template<GenType> void score();
-  void generate_next_stage();
-  ExtMove* begin() { return moves; }
+  ExtMove* begin() { return cur; }
   ExtMove* end() { return endMoves; }
 
   const Position& pos;
@@ -117,12 +116,11 @@ private:
   Move countermove;
   Depth depth;
   Move ttMove;
-  ExtMove killers[3];
   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