Chess move list ordering

Recent performance profiling of iCE showed that iCE spends a significant time just sorting the moves.

In iCE moves get assigned an order value that expresses their likelihood of being best. Depending on the kind of move this value might come from the expected material win (Static Exchange Evaluation), from its attacking value (victim vs attacker) or by the history of the move in previous searches.

After a value has been assigned to the moves in the current move generation stage they have to be ordered in descending order.

An alternative to sorting would be to just always pick the next best move from the list each time a move is accessed but this is a bit more messy. I like the cleanness of processing an ordered list.

As the number of moves in each stage is usually small insertion sort is used instead of the typical used quicksort. The algorithm for insertion sort is rather simple and I have implemented it in the TMovelist class of iCE. C++ already provides a sort algorithm with std::sort but this was significantly slower than my implementation.

To speed up the ordering I thought about special sort implementations for short lists. So first I performed an analyses what move lists usually are processed. Statistics shows that 85% of the lists have 8 or less elements. 

Move list length statistics. The last column stands here for 9 and more moves

For a fixed and small number of elements exists a technique called sorting net to sort the elements by just by a fixed sequence of element compares and swaps.

To sort a list of 4 elements the following sorting network can be used

SWAP(0, 1); SWAP(2, 3); SWAP(0, 2); SWAP(1, 3); SWAP(1, 2);

SWAP(a, b) compares a with b and swaps them if they are out of order. For more elements the sequence of swaps gets longer, so for 10 elements already 32 SWAP operations are necessary.

As the statistics looked promising I implemented the sorting networks for lists up to 12 elements and used my insertion sort algorithm for the remaining longer lists. Overall I got a small overall speedup, less than I hoped for. But profiling showed that although only 15% of the lists are longer than 8 elements, sorting them takes most of the time.

I kept the change anyway as I is not really complex and actually I like the concept.