Sort moves just after scoring

Instead of a delayed selection sort so that the highest
score move is picked up from the list when needed, sort all
the moves up front just after score them.

Selection sort is O(n*n) while std::sort is O(n*log n), it
is true that delayed selection allows us to just pick the move
until a cut off occurs or up to a given limit (12), but with
an average of 30 non capture-moves delayed pick become slower
just after 5-6 moves and we now pick up to 12.

Profiling seem to prove this idea and movepick.cpp is now 10%
faster.

Also tests seem to confirm this:

After 700 games at 1+0: Mod vs Orig +178 -160 =362 +9 ELO

Signed-off-by: Marco Costalba <mcostalba@gmail.com>

diff --git a/src/move.h b/src/move.h
index e9f7242696c9abf0fa477758b192c47f4ace9dcb..527699c82f8cf73b6ef9078c06abcf94f0b23ecf 100644 (file)
--- a/src/move.h
+++ b/src/move.h
@@ -62,6 +62,9 @@ struct MoveStack {
   int score;
 };
 
+// Note that operator< is set up such that std::sort() will sort in descending order
+inline bool operator<(const MoveStack& f, const MoveStack& s) { return s.score < f.score; }
+
 
 ////
 //// Inline functions

diff --git a/src/movepick.cpp b/src/movepick.cpp
index 6c3f4264dec1af0745aa575d2802f56ad39e362f..d0c1b587bd5d7b3ef3973b7e92c1ad9983393b76 100644 (file)
--- a/src/movepick.cpp
+++ b/src/movepick.cpp
@@ -23,6 +23,7 @@
 //// Includes
 ////
 
+#include <algorithm>
 #include <cassert>
 
 #include "history.h"
@@ -136,6 +137,7 @@ Move MovePicker::get_next_move() {
     case PH_GOOD_CAPTURES:
         numOfMoves = generate_captures(pos, moves);
         score_captures();
+        std::sort(moves, moves + numOfMoves);
         movesPicked = 0;
         break;
 
@@ -146,6 +148,7 @@ Move MovePicker::get_next_move() {
     case PH_NONCAPTURES:
         numOfMoves = generate_noncaptures(pos, moves);
         score_noncaptures();
+        std::sort(moves, moves + numOfMoves);
         movesPicked = 0;
         break;
 
@@ -153,12 +156,14 @@ Move MovePicker::get_next_move() {
         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;
 
@@ -299,26 +304,6 @@ void MovePicker::score_qcaptures() {
 }
 
 
-/// find_best_index() loops across the moves and returns index of
-/// the highest scored one.
-
-int MovePicker::find_best_index() const {
-
-  assert(movesPicked < numOfMoves);
-
-  int bestIndex = movesPicked;
-  int bestScore = moves[movesPicked].score;
-
-  for (int i = movesPicked + 1; i < numOfMoves; i++)
-      if (moves[i].score > bestScore)
-      {
-          bestIndex = i;
-          bestScore = moves[i].score;
-      }
-  return bestIndex;
-}
-
-
 /// 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
@@ -326,7 +311,6 @@ int MovePicker::find_best_index() const {
 
 Move MovePicker::pick_move_from_list() {
 
-  int bestIndex;
   Move move;
 
   switch (PhaseTable[phaseIndex]) {
@@ -337,9 +321,7 @@ Move MovePicker::pick_move_from_list() {
 
       while (movesPicked < numOfMoves)
       {
-          bestIndex = find_best_index();
-          move = moves[bestIndex].move;
-          moves[bestIndex] = moves[movesPicked++];
+          move = moves[movesPicked++].move;
           if (   move != ttMove
               && move != mateKiller
               && pos.pl_move_is_legal(move, pinned))
@@ -353,13 +335,7 @@ Move MovePicker::pick_move_from_list() {
 
       while (movesPicked < numOfMoves)
       {
-          // If this is a PV node or we have only picked a few moves, scan
-          // the entire move list for the best move.  If many moves have already
-          // been searched and it is not a PV node, we are probably failing low
-          // anyway, so we just pick the first move from the list.
-          bestIndex = (pvNode || movesPicked < 12) ? find_best_index() : movesPicked;
-          move = moves[bestIndex].move;
-          moves[bestIndex] = moves[movesPicked++];
+          move = moves[movesPicked++].move;
           if (   move != ttMove
               && move != mateKiller
               && pos.pl_move_is_legal(move, pinned))
@@ -373,9 +349,7 @@ Move MovePicker::pick_move_from_list() {
 
       while (movesPicked < numOfMoves)
       {
-          bestIndex = find_best_index();
-          move = moves[bestIndex].move;
-          moves[bestIndex] = moves[movesPicked++];
+          move = moves[movesPicked++].move;
           return move;
     }
     break;
@@ -398,11 +372,10 @@ Move MovePicker::pick_move_from_list() {
   case PH_QCAPTURES:
       assert(!pos.is_check());
       assert(movesPicked >= 0);
+
       while (movesPicked < numOfMoves)
       {
-          bestIndex = (movesPicked < 4 ? find_best_index() : movesPicked);
-          move = moves[bestIndex].move;
-          moves[bestIndex] = moves[movesPicked++];
+          move = moves[movesPicked++].move;
           // Maybe postpone the legality check until after futility pruning?
           if (   move != ttMove
               && pos.pl_move_is_legal(move, pinned))

diff --git a/src/movepick.h b/src/movepick.h
index 1c8d0d30fa08a629b4986cbba8708e5a3debe9c1..17df8678928921172646d8c8d9ed9ca0009b1643 100644 (file)
--- a/src/movepick.h
+++ b/src/movepick.h
@@ -80,7 +80,6 @@ private:
   void score_evasions();
   void score_qcaptures();
   Move pick_move_from_list();
-  int find_best_index() const;
 
   const Position& pos;
   Move ttMove, mateKiller, killer1, killer2;