Sorting algorithms

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
User avatar
Kempelen
Posts: 620
Joined: Fri Feb 08, 2008 9:44 am
Location: Madrid - Spain
Contact:

Sorting algorithms

Post by Kempelen » Sat Apr 22, 2017 9:39 am

Hello,

Today I was thinking on what algorithm to use for sorting moves, that be the faster. Currently I am using "selection sort" as it was the first that comes to my mind when writting my engine, but now I trying to investigating what is the best. In Chess Programming Wiki I have not found much on the comparison of them for chess moves, and I have look also in open source engines and have found insertion sort or even shell sort, but have not found many explanations why the choice.

Of course I could try and profile, but I would prefer to read a bit before codeing l¡ke crazy, so to not waste much time (very limited :) ) .

Any orientation in this area will be wellcome.

Thanks
Fermin
Fermin Serrano
Author of 'Rodin' engine
http://sites.google.com/site/clonfsp/

Ras
Posts: 1161
Joined: Tue Aug 30, 2016 6:19 pm
Contact:

Re: Sorting algorithms

Post by Ras » Sat Apr 22, 2017 10:14 am

Probably the best thing is selection sort. Fetching the best move and putting it to the top, then trying it. Only fetching the second best move if need be, and so on. True, the worst case performance is O(N^2), but with a good move sorting, that is rare.

The next best thing is Shellsort. For small lists up to 100 elements, it is faster than quicksort because of less overhead. Use the Ciura sequence. If you are using GCC or CLANG, use jump tables instead of the outest loop, that saves a lot of branching.

The worst thing is the C standard library Quicksort because every compare operation is a function call that cannot even be inlined. Does not apply to C++ AFAIK.

If you are interested, I can post the C source code of a little benchmark where I compared Shellsort, Shellsort with jump tables and C library Quicksort when it comes to sorting chess moves. So you can check out the performance on your own machine.

Further information on sorting short lists can be found here:

http://embeddedgurus.com/stack-overflow ... d-systems/

User avatar
hgm
Posts: 23792
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Sorting algorithms

Post by hgm » Sat Apr 22, 2017 10:38 am

The fastest way to sort is to avoid having to do it. To that end I generate captures in MVV order, staged by victim value group. It is not very often that a value group is attacked by more than one attacker (or in fact that it is attacked at all), so then there is nothing to sort. If there are multiple attackers, I still have to sort the captures on that value group in LVA order. As the group is never very large, I just extract the best remaining move (i.e. lowest attacker) every time I need one. As captures are early moves, the chances they cause a cutoff are significant, so it pays to postpone work on moves you don't want to search immediately.

I don't sort the killers.

That leaves the non-captures. If I want to sort those by history, I distribute them over 256 history bins (logarithmically spaced), each bin containing a linked list of moves with a history score in the range of the bin. This requires storage for the links, but in Chess there won't ever be more than 256 moves per position, so you can use 8-bit links, stored in the upper byte of the move. That just leaves an arry of 256 bytes for indicateng the first element in the list of each bin. Plus a four 64-bit words of packed bit-flags to indicate which bins are populated (so that you won't have to waste any time on initialyzing empty lists, and can loop over populated lists fast through bit extraction of the flags). I don't sort within a list; the bins are sufficiently narrow that this is pointless. That reduces sorting overhead to practically zero.
Last edited by hgm on Sat Apr 22, 2017 11:15 am, edited 1 time in total.

Henk
Posts: 5833
Joined: Mon May 27, 2013 8:31 am

Re: Sorting algorithms

Post by Henk » Sat Apr 22, 2017 11:13 am

Not for Skipper.

Code: Select all

 
          ulong source = Board.CurPieces;
          ulong target = Board.Pieces(-Board.CurPlayer);
          CollectCaptures(moves, source, target)

         // sort moves
works better than

Code: Select all

            for (Kind i = King; i >= Pawn; i--)
            {
                ulong target = Board.GetBits(i, -Board.CurPlayer);
                for &#40;Kind j = Pawn; j <= King; j++)
                &#123;
                    ulong source = Board.GetBits&#40;j, Board.CurPlayer&#41;;
                    CollectCaptures&#40;moves, source, target&#41;                  
                &#125;
            &#125;
Tried several versions but giving no improvement.

ymatioun
Posts: 64
Joined: Fri Oct 18, 2013 9:40 pm
Location: New York

Re: Sorting algorithms

Post by ymatioun » Sat Apr 22, 2017 12:18 pm

i use insertion sort - for short, partially sorted lists it is fast, with O(N) performance in best case. I tried using selection sort instead at some point, and saw worse performance.

User avatar
hgm
Posts: 23792
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Sorting algorithms

Post by hgm » Sat Apr 22, 2017 12:40 pm

Well, I suppose that depends on how CollectCaptures() works. If you have to generate the attack sets of all attackers over and over again for each victim group, I can see that it would be faster to combine all victims.

Henk
Posts: 5833
Joined: Mon May 27, 2013 8:31 am

Re: Sorting algorithms

Post by Henk » Sat Apr 22, 2017 12:58 pm

Yes of course in the stupid way. Is there something better ? (By the way returns false when king captured)

Code: Select all

        public bool CollectCaptures2&#40;List<IMoveBase> moves, ulong curPieces, ulong opponentPieces&#41;
        &#123;
            var occupiers = Board.Occupiers;
            while &#40;curPieces != 0&#41;
            &#123;
                var location = ChessBoard&#91;curPieces & (~curPieces + 1&#41;&#93;;
                if (&#40;location.XRayMoves&#40;) & opponentPieces&#41; != 0&#41;
                &#123;
                    var pieceSort = location.Occupier.PieceSort;
                    var captures = location.Moves&#40;location.Occupier.PieceSort, occupiers&#41; & opponentPieces;
                    if (!CollectCaptures2&#40;captures, location.AllMovesDict&#40;pieceSort&#41;, moves&#41;) return false;
                &#125;
                curPieces &= curPieces - 1;
            &#125;
            return true;
        &#125;
O wait you probably mean generate and re-use attack sets for all opponent pieces.
Last edited by Henk on Sat Apr 22, 2017 1:13 pm, edited 4 times in total.

Karlo Bala
Posts: 303
Joined: Wed Mar 22, 2006 9:17 am
Location: Novi Sad, Serbia

Re: Sorting algorithms

Post by Karlo Bala » Sat Apr 22, 2017 1:00 pm

ymatioun wrote:i use insertion sort - for short, partially sorted lists it is fast, with O(N) performance in best case. I tried using selection sort instead at some point, and saw worse performance.
I think there is at least 3 ways of sorting moves

1. Sorting during generating/scoring. Use insertion sort to maintain sorted order. Perhaps the most efficient.

2. Sorting after generating/scoring. Some simple sort, insertion or bubble.

3. Sorting while picking a move (selection sort). Lazy approach, efficient for Cut nodes.
Best Regards,
Karlo Balla Jr.

Henk
Posts: 5833
Joined: Mon May 27, 2013 8:31 am

Re: Sorting algorithms

Post by Henk » Sat Apr 22, 2017 1:46 pm

Henk wrote:Yes of course in the stupid way. Is there something better ? (By the way returns false when king captured)

Code: Select all

        public bool CollectCaptures2&#40;List<IMoveBase> moves, ulong curPieces, ulong opponentPieces&#41;
        &#123;
            var occupiers = Board.Occupiers;
            while &#40;curPieces != 0&#41;
            &#123;
                var location = ChessBoard&#91;curPieces & (~curPieces + 1&#41;&#93;;
                if (&#40;location.XRayMoves&#40;) & opponentPieces&#41; != 0&#41;
                &#123;
                    var pieceSort = location.Occupier.PieceSort;
                    var captures = location.Moves&#40;location.Occupier.PieceSort, occupiers&#41; & opponentPieces;
                    if (!CollectCaptures2&#40;captures, location.AllMovesDict&#40;pieceSort&#41;, moves&#41;) return false;
                &#125;
                curPieces &= curPieces - 1;
            &#125;
            return true;
        &#125;
O wait you probably mean generate and re-use attack sets for all opponent pieces.
If you generate all attacks per attacker sort first then you still don't know the location of the attacker that attacks a victim.

Henk
Posts: 5833
Joined: Mon May 27, 2013 8:31 am

Re: Sorting algorithms

Post by Henk » Sat Apr 22, 2017 1:56 pm

Henk wrote:
Henk wrote:Yes of course in the stupid way. Is there something better ? (By the way returns false when king captured)

Code: Select all

        public bool CollectCaptures2&#40;List<IMoveBase> moves, ulong curPieces, ulong opponentPieces&#41;
        &#123;
            var occupiers = Board.Occupiers;
            while &#40;curPieces != 0&#41;
            &#123;
                var location = ChessBoard&#91;curPieces & (~curPieces + 1&#41;&#93;;
                if (&#40;location.XRayMoves&#40;) & opponentPieces&#41; != 0&#41;
                &#123;
                    var pieceSort = location.Occupier.PieceSort;
                    var captures = location.Moves&#40;location.Occupier.PieceSort, occupiers&#41; & opponentPieces;
                    if (!CollectCaptures2&#40;captures, location.AllMovesDict&#40;pieceSort&#41;, moves&#41;) return false;
                &#125;
                curPieces &= curPieces - 1;
            &#125;
            return true;
        &#125;
O wait you probably mean generate and re-use attack sets for all opponent pieces.
If you generate all attacks per attacker sort first then you still don't know the location of the attacker that attacks a victim.
I mean when all attacks per attacker sort is a bitboard(ulong)

Post Reply