My successful kids

Last weekend my sons played the official city championship of the city of Leipzig in the age categories U8 and U10. Both did very well, Julian my younger son finished 3rd place with 5.5/7 and Jonas even managed to score 6.5/7 and became city champion.   

Julian Petzke, 3rd place U8

Jonas Petzke, 1st place U10

Congratulations and a big thanks to their trainers.

Probably in the near future you will make dad look rather stupid when you play a game of chess with him.

A little tournament and a cross table

iCE just played a little tournament in France. The tournament includes several hundred engines grouped in different divisions according to their strength. iCE was seeded in division Karpov, which is the second highest division and managed to finish among the best three.

http://aloheac.perso.neuf.fr/Ligue_Karpov.htm

It means it will play in the Kasparov division (the highest) next time. Probably it will lose most of the games there, this division is very tough. But it will be fun watching.

PS.: I'm also posting this to try out the new cross table HTML generator of shaker. Unfortunately the table is to big (its width) to fit into this blog. So I have to make an image out of it, but otherwise it works. Yeah !

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.