Use std::stable_sort() instead of std::sort()

Standard does not mandate std::sort() to be stable, so we
can have, and actually do have different node count on
different platforms.

So use the platform independent std::stable_sort() and gain
same functionality on any platform (Windows, Unix, Mac OS)
and with any compiler (MSVC, gcc or Intel C++).

This sort is teoretically slower, but profiling shows only a very
minimal drop in performance, probably due to the fact that
the set to sort is very small, mainly only captures and with
less frequency non-captures, anyhow we are talking of 30-40 moves
in the worst average case. Sorting alghortims are build to work on
thousands or even milions of elements. With such small sets
performance difference seems not noticable.

After 999 games at 1+0

Mod vs Orig +234 =523 -242 -3 ELO

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

diff --git a/src/move.h b/src/move.h
index 672eade6bcb676f4f9751070d2bcbab86f88965d..03df770dc824eee7849b37be806042fe0015c2d7 100644 (file)
--- a/src/move.h
+++ b/src/move.h
@@ -62,7 +62,7 @@ struct MoveStack {
   int score;
 };
 
-// Note that operator< is set up such that std::sort() will sort in descending order
+// Note that operator< is set up such that std::stable_sort() will sort in descending order
 inline bool operator<(const MoveStack& f, const MoveStack& s) { return s.score < f.score; }
 
 

diff --git a/src/movepick.cpp b/src/movepick.cpp
index ea435026241f21b72275af2fd0585b35480ff9a8..0dd44bbd8db54925e035728bea470075fe5004ae 100644 (file)
--- a/src/movepick.cpp
+++ b/src/movepick.cpp
@@ -123,7 +123,7 @@ void MovePicker::go_next_phase() {
   case PH_GOOD_CAPTURES:
       lastMove = generate_captures(pos, moves);
       score_captures();
-      std::sort(moves, lastMove);
+      std::stable_sort(moves, lastMove);
       return;
 
   case PH_KILLERS:
@@ -134,7 +134,7 @@ void MovePicker::go_next_phase() {
   case PH_NONCAPTURES:
       lastMove = generate_noncaptures(pos, moves);
       score_noncaptures();
-      std::sort(moves, lastMove);
+      std::stable_sort(moves, lastMove);
       return;
 
   case PH_BAD_CAPTURES:
@@ -142,20 +142,20 @@ void MovePicker::go_next_phase() {
       // to get SEE move ordering.
       curMove = badCaptures;
       lastMove = lastBadCapture;
-      std::sort(badCaptures, lastMove);
+      std::stable_sort(badCaptures, lastMove);
       return;
 
   case PH_EVASIONS:
       assert(pos.is_check());
       lastMove = generate_evasions(pos, moves, pinned);
       score_evasions();
-      std::sort(moves, lastMove);
+      std::stable_sort(moves, lastMove);
       return;
 
   case PH_QCAPTURES:
       lastMove = generate_captures(pos, moves);
       score_captures();
-      std::sort(moves, lastMove);
+      std::stable_sort(moves, lastMove);
       return;
 
   case PH_QCHECKS:

diff --git a/src/ucioption.cpp b/src/ucioption.cpp
index 1b8665546a20297d1047c564db736cec0f7800ea..6e727954e68095a6896a03ac3fc5f1fbc2a4db74 100644 (file)
--- a/src/ucioption.cpp
+++ b/src/ucioption.cpp
@@ -210,7 +210,7 @@ void print_uci_options() {
   for (Options::const_iterator it = options.begin(); it != options.end(); ++it)
       vec.push_back(it->second);
 
-  std::sort(vec.begin(), vec.end());
+  std::stable_sort(vec.begin(), vec.end());
 
   for (std::vector<Option>::const_iterator it = vec.begin(); it != vec.end(); ++it)
   {