Sort moves just after scoring
authorMarco Costalba <mcostalba@gmail.com>
Fri, 1 May 2009 08:17:34 +0000 (10:17 +0200)
committerMarco Costalba <mcostalba@gmail.com>
Sat, 2 May 2009 09:07:46 +0000 (10:07 +0100)
commit4e151f7e0d70b9a61ac5adba269a80555133cb73
tree687cfe39c1f4137ea5897eab8260149963c7d630
parentd13e4c16c28048a612375b683c58cc0737d08f67
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>
src/move.h
src/movepick.cpp
src/movepick.h