Pick best moves one per cycle instead of sorting

When the move list is very small, like captures normally
are, it is faster to pick the best move with a linear
scan, one per cycle.

This has the added advantage that the picked capture move is
very possibly a cut-off move, so that other searches are
avoided. For non-captures it is still faster to sort in
advance.

Because scan-and-pick alghortim is not stable, node count
has changed.

After 885 games at 1+0
Mod vs Orig +196 =510 -179 50.96%  451.0/885

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

diff --git a/src/move.h b/src/move.h
index 2ba0884087422d7bdd908d1130d3b19ed3a02486..844ec1f6be609d198be1b656630e55eaf327a387 100644 (file)
--- a/src/move.h
+++ b/src/move.h
@@ -86,6 +86,27 @@ inline void sort_moves(T* firstMove, T* lastMove)
         }
 }
 
+// Picks up the best move in range [curMove, lastMove), one per cycle.
+// It is faster then sorting all the moves in advance when moves are few,
+// as normally are the possible captures. Note that is not a stable alghoritm.
+template<typename T>
+inline T pick_best(T* curMove, T* lastMove)
+{
+    T bestMove, tmp;
+
+    bestMove = *curMove;
+    while (++curMove != lastMove)
+    {
+        if (*curMove < bestMove)
+        {
+            tmp = *curMove;
+            *curMove = bestMove;
+            bestMove = tmp;
+        }
+    }
+    return bestMove;
+}
+
 ////
 //// Inline functions
 ////

diff --git a/src/movepick.cpp b/src/movepick.cpp
index 34cb642b4a514b60c12a0cf6d4d62beb235dc084..0da6b61bbbbe99f176eea9a5c67f75db9cd8b306 100644 (file)
--- a/src/movepick.cpp
+++ b/src/movepick.cpp
@@ -122,7 +122,6 @@ void MovePicker::go_next_phase() {
   case PH_GOOD_CAPTURES:
       lastMove = generate_captures(pos, moves);
       score_captures();
-      sort_moves(moves, lastMove);
       return;
 
   case PH_KILLERS:
@@ -141,20 +140,17 @@ void MovePicker::go_next_phase() {
       // to get SEE move ordering.
       curMove = badCaptures;
       lastMove = lastBadCapture;
-      sort_moves(badCaptures, lastMove);
       return;
 
   case PH_EVASIONS:
       assert(pos.is_check());
       lastMove = generate_evasions(pos, moves, pinned);
       score_evasions();
-      sort_moves(moves, lastMove);
       return;
 
   case PH_QCAPTURES:
       lastMove = generate_captures(pos, moves);
       score_captures();
-      sort_moves(moves, lastMove);
       return;
 
   case PH_QCHECKS:
@@ -267,17 +263,17 @@ Move MovePicker::get_next_move() {
   {
       while (curMove != lastMove)
       {
-          move = (curMove++)->move;
-
           switch (phase) {
 
           case PH_TT_MOVES:
+              move = (curMove++)->move;
               if (   move != MOVE_NONE
                   && move_is_legal(pos, move, pinned))
                   return move;
               break;
 
           case PH_GOOD_CAPTURES:
+              move = pick_best(curMove++, lastMove).move;
               if (   move != ttMoves[0].move
                   && move != ttMoves[1].move
                   && pos.pl_move_is_legal(move, pinned))
@@ -297,6 +293,7 @@ Move MovePicker::get_next_move() {
               break;
 
           case PH_KILLERS:
+              move = (curMove++)->move;
               if (   move != MOVE_NONE
                   && move != ttMoves[0].move
                   && move != ttMoves[1].move
@@ -306,6 +303,7 @@ Move MovePicker::get_next_move() {
               break;
 
           case PH_NONCAPTURES:
+              move = (curMove++)->move;
               if (   move != ttMoves[0].move
                   && move != ttMoves[1].move
                   && move != killers[0].move
@@ -316,11 +314,18 @@ Move MovePicker::get_next_move() {
 
           case PH_EVASIONS:
           case PH_BAD_CAPTURES:
+              move = pick_best(curMove++, lastMove).move;
               return move;
 
           case PH_QCAPTURES:
+              move = pick_best(curMove++, lastMove).move;
+              if (   move != ttMoves[0].move
+                  && pos.pl_move_is_legal(move, pinned))
+                  return move;
+              break;
+
           case PH_QCHECKS:
-              // Maybe postpone the legality check until after futility pruning?
+              move = (curMove++)->move;
               if (   move != ttMoves[0].move
                   && pos.pl_move_is_legal(move, pinned))
                   return move;