It is stable and it is also a bit faster then std::sort()
on the tipical small move lists that we need to handle.
Verified to have same functionality of std::stable_sort()
After 999 games at 1+0
Mod vs Orig +240 =534 -225 50.75% 507.0/999 +5 ELO
Signed-off-by: Marco Costalba <mcostalba@gmail.com>
-// Note that operator< is set up such that std::sort() will sort in descending order
+// Note that operator< is set up such that sorting will be in descending order
inline bool operator<(const MoveStack& f, const MoveStack& s) { return s.score < f.score; }
inline bool operator<(const MoveStack& f, const MoveStack& s) { return s.score < f.score; }
+// Our stable insertion sort in range [firstMove, lastMove), platform independent
+template<typename T>
+inline void sort_moves(T* firstMove, T* lastMove)
+{
+ T value;
+ T *cur, *p, *d;
+
+ if (firstMove != lastMove)
+ for (cur = firstMove; ++cur != lastMove; )
+ {
+ p = d = cur;
+ value = *p--;
+ if (value < *p)
+ {
+ do *d = *p;
+ while (--d != firstMove && value < *--p);
+ *d = value;
+ }
+ }
+}
////
//// Inline functions
////
//// Inline functions
#include <cassert>
#include "history.h"
#include <cassert>
#include "history.h"
case PH_GOOD_CAPTURES:
lastMove = generate_captures(pos, moves);
score_captures();
case PH_GOOD_CAPTURES:
lastMove = generate_captures(pos, moves);
score_captures();
- std::sort(moves, lastMove);
+ sort_moves(moves, lastMove);
case PH_NONCAPTURES:
lastMove = generate_noncaptures(pos, moves);
score_noncaptures();
case PH_NONCAPTURES:
lastMove = generate_noncaptures(pos, moves);
score_noncaptures();
- std::sort(moves, lastMove);
+ sort_moves(moves, lastMove);
return;
case PH_BAD_CAPTURES:
return;
case PH_BAD_CAPTURES:
// to get SEE move ordering.
curMove = badCaptures;
lastMove = lastBadCapture;
// to get SEE move ordering.
curMove = badCaptures;
lastMove = lastBadCapture;
- std::sort(badCaptures, lastMove);
+ sort_moves(badCaptures, lastMove);
return;
case PH_EVASIONS:
assert(pos.is_check());
lastMove = generate_evasions(pos, moves, pinned);
score_evasions();
return;
case PH_EVASIONS:
assert(pos.is_check());
lastMove = generate_evasions(pos, moves, pinned);
score_evasions();
- std::sort(moves, lastMove);
+ sort_moves(moves, lastMove);
return;
case PH_QCAPTURES:
lastMove = generate_captures(pos, moves);
score_captures();
return;
case PH_QCAPTURES:
lastMove = generate_captures(pos, moves);
score_captures();
- std::sort(moves, lastMove);
+ sort_moves(moves, lastMove);