Sorting algorithms

[Kempelen]

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

[Ras]

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/

[hgm]

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.

[Henk]

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 (Kind j = Pawn; j <= King; j++)
                {
                    ulong source = Board.GetBits(j, Board.CurPlayer);
                    CollectCaptures(moves, source, target)                  
                }
            }

Tried several versions but giving no improvement.

[ymatioun]

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.

[hgm]

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]

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(List<IMoveBase> moves, ulong curPieces, ulong opponentPieces)
        {
            var occupiers = Board.Occupiers;
            while (curPieces != 0)
            {
                var location = ChessBoard[curPieces & (~curPieces + 1)];
                if ((location.XRayMoves() & opponentPieces) != 0)
                {
                    var pieceSort = location.Occupier.PieceSort;
                    var captures = location.Moves(location.Occupier.PieceSort, occupiers) & opponentPieces;
                    if (!CollectCaptures2(captures, location.AllMovesDict(pieceSort), moves)) return false;
                }
                curPieces &= curPieces - 1;
            }
            return true;
        }

O wait you probably mean generate and re-use attack sets for all opponent pieces.

[Karlo Bala]

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.

[Henk]

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(List<IMoveBase> moves, ulong curPieces, ulong opponentPieces)
        {
            var occupiers = Board.Occupiers;
            while (curPieces != 0)
            {
                var location = ChessBoard[curPieces & (~curPieces + 1)];
                if ((location.XRayMoves() & opponentPieces) != 0)
                {
                    var pieceSort = location.Occupier.PieceSort;
                    var captures = location.Moves(location.Occupier.PieceSort, occupiers) & opponentPieces;
                    if (!CollectCaptures2(captures, location.AllMovesDict(pieceSort), moves)) return false;
                }
                curPieces &= curPieces - 1;
            }
            return true;
        }

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]

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(List<IMoveBase> moves, ulong curPieces, ulong opponentPieces)
        {
            var occupiers = Board.Occupiers;
            while (curPieces != 0)
            {
                var location = ChessBoard[curPieces & (~curPieces + 1)];
                if ((location.XRayMoves() & opponentPieces) != 0)
                {
                    var pieceSort = location.Occupier.PieceSort;
                    var captures = location.Moves(location.Occupier.PieceSort, occupiers) & opponentPieces;
                    if (!CollectCaptures2(captures, location.AllMovesDict(pieceSort), moves)) return false;
                }
                curPieces &= curPieces - 1;
            }
            return true;
        }

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)