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.
Henk
Posts: 5816
Joined: Mon May 27, 2013 8:31 am

Re: Sorting algorithms

Post by Henk » Sat Apr 22, 2017 2:07 pm

Henk wrote:
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)
So an attack set per attacker sort is probably a map(square, bitboard) per attacker sort

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

Re: Sorting algorithms

Post by Henk » Sat Apr 22, 2017 2:31 pm

Henk wrote:
Henk wrote:
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)
So an attack set per attacker sort is probably a map(square, bitboard) per attacker sort
Then you may get something like this

Code: Select all

        public bool CollectCaptures&#40;Sort pieceSort, ulong curPieces, Dictionary<ulong, ulong> attackDict, List<IMoveBase> moves, ulong opponentPieces&#41;
        &#123;
            ulong attacks;
            while &#40;curPieces != 0&#41;
            &#123;
                var location = ChessBoard&#91;curPieces & (~curPieces + 1&#41;&#93;;
                if &#40;attackDict.TryGetValue&#40;location.BitCoord, out attacks&#41;)
                &#123;
                    var captures = attacks & opponentPieces;
                    if (!CollectCaptures&#40;captures, location.AllMovesDict&#40;pieceSort&#41;, moves&#41;) return false;
                &#125;              
                curPieces &= curPieces - 1;
            &#125;
            return true;
        &#125;
Doubt if that will be fast enough. For you save only an
var captures = location.Moves(location.Occupier.PieceSort, occupiers); and that operation is not that very expensive

User avatar
hgm
Posts: 23713
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 2:43 pm

Well, you could keep a byte per piece with bit flags indicating which (non-Pawn) piece attacks it. That would be 16 bytes, which you could clear with two 64-bit store operations before move generation. When you find a capture, instead of generating the move, you would set the attacker bit in the victim byte. Afterwards you run through the victim bytes (in order of decreasing victim value), to see which attacks are flagged, and generate the move for those. In fact you could do that by bit extraction.

[Edit] I did not consider Pawns here, because calculating captures of pieces by Pawns can be done just as easily by victim (where for each of 8 pieces you would have to consider two squares where the attack can come from) as by attacker (where for each of 8 Pawns you would have to test two squares where the attack goes to). So for each victim you would start testing for Pawn attacks on it, (because a Pawn would always be LVA), and then test the byte with attacker flags for attacks by other pieces.

That leaves Pawn x Pawn, but those could be stored in the Pawn hash table. As 16 flags indicating whether each of 8 Pawns can capture an enemy Pawn to the left or to the right. When you then get to captures on Pawn, you start extracting those bit flags for all P x P, and then use the attackers byte of the Pawn for attacks by other pieces.

brtzsnr
Posts: 433
Joined: Fri Jan 16, 2015 3:02 pm
Contact:

Re: Sorting algorithms

Post by brtzsnr » Sun Apr 23, 2017 3:07 pm

I asked something similar a few weeks ago. My sorting is a bit more advanced than what I understood your engine does:

1) I split into phases: hash, captures / queen promotion, killers, quiets.
2) I sort each phase separately, but only if needed. E.g. I don't sort quiets if I'm not done with killers.
3) I use shell sort with Cuira gaps. They seem to work best. I tried selection sort, insertion sort, quick sort, heap sort and a combination of some of them.

1) & 2) help because numbers of captures is usually small and in > 90% positions you don't need to sort quiets which are the bulk of the moves. Even with this, sorting alone takes 8% of the time which is the largest chunk of time spent.

Other ideas suggested:
1) Filter moves before sorting to reduce the number of moves to be sorted.
2) Bitonic sorting.
3) Not sorting late moves.


http://talkchess.com/forum/viewtopic.ph ... ht=sorting

AlvaroBegue
Posts: 920
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Sorting algorithms

Post by AlvaroBegue » Sun Apr 23, 2017 6:51 pm

brtzsnr wrote:[...]
3) I use shell sort with Cuira gaps. They seem to work best. I tried selection sort, insertion sort, quick sort, heap sort and a combination of some of them.
It took me a bit to Google for this because of a misspelling: It's "Ciura".

jwes
Posts: 778
Joined: Sat Jul 01, 2006 5:11 am

Re: Sorting algorithms

Post by jwes » Mon Apr 24, 2017 12:37 am

brtzsnr wrote:I asked something similar a few weeks ago. My sorting is a bit more advanced than what I understood your engine does:

1) I split into phases: hash, captures / queen promotion, killers, quiets.
2) I sort each phase separately, but only if needed. E.g. I don't sort quiets if I'm not done with killers.
3) I use shell sort with Cuira gaps. They seem to work best. I tried selection sort, insertion sort, quick sort, heap sort and a combination of some of them.

1) & 2) help because numbers of captures is usually small and in > 90% positions you don't need to sort quiets which are the bulk of the moves. Even with this, sorting alone takes 8% of the time which is the largest chunk of time spent.

Other ideas suggested:
1) Filter moves before sorting to reduce the number of moves to be sorted.
2) Bitonic sorting.
3) Not sorting late moves.


http://talkchess.com/forum/viewtopic.ph ... ht=sorting
Has anyone tried diffent sorts for expected cut nodes and all nodes?

bnemias
Posts: 373
Joined: Thu Aug 14, 2008 1:21 am
Location: Albuquerque, NM

Re: Sorting algorithms

Post by bnemias » Wed Apr 26, 2017 2:33 am

ymatioun wrote:i use insertion sort - for short, partially sorted lists it is fast
I believe it. N^2 routines aren't bad, in general, for small N. When I did serious work on quicksort in the 80's, I had a cutoff value when I would switch to an N^2 routine (insertion). At the time, the cutoff was somewhere in the range of 9..25. But various factors influence the optimum value. The data does too, of course, but so does the hardware speed. I found, investigating years later that cutoffs up to 400 were quite reasonable before noticing much degradation.

So yeah, Insertion ought to be fine (even preferable) for small N.

Dann Corbit
Posts: 10101
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Sorting algorithms

Post by Dann Corbit » Wed Apr 26, 2017 4:57 am

Use quickselect to partition the top set (whatever count you like, I choose 3) and then only sort those with a high energy sort.

A worthwhile experiment, that may not work for every engine.

Quickselect is linear. You can use a fixed, optimal algorithm for the tiny set of top positions.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

tpetzke
Posts: 686
Joined: Thu Mar 03, 2011 3:57 pm
Location: Germany
Contact:

Re: Sorting algorithms

Post by tpetzke » Thu Apr 27, 2017 3:09 pm

Usually the lists to sort are small if you use staged move generation. So I have implemented sorting nets for lists with up to 12 elements. For bigger ones I then use insertion sort.

Code: Select all

template<int count> void TMoveList&#58;&#58;net_sort&#40;)
&#123;
	assert&#40;count >= 2 && count <= 12&#41;;

	switch &#40;count&#41;
	&#123;
		case 2&#58; compare_swap&#40;0, 1&#41;; return;
		case 3&#58; compare_swap&#40;1, 2&#41;; compare_swap&#40;0, 2&#41;; compare_swap&#40;0, 1&#41;; return;
		case 4&#58; compare_swap&#40;0, 1&#41;; compare_swap&#40;2, 3&#41;; compare_swap&#40;0, 2&#41;; compare_swap&#40;1, 3&#41;; compare_swap&#40;1, 2&#41;;	    return;
Thomas...

=======
http://macechess.blogspot.com - iCE Chess Engine

Dann Corbit
Posts: 10101
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Sorting algorithms

Post by Dann Corbit » Thu Apr 27, 2017 3:40 pm

tpetzke wrote:Usually the lists to sort are small if you use staged move generation. So I have implemented sorting nets for lists with up to 12 elements. For bigger ones I then use insertion sort.

Code: Select all

template<int count> void TMoveList&#58;&#58;net_sort&#40;)
&#123;
	assert&#40;count >= 2 && count <= 12&#41;;

	switch &#40;count&#41;
	&#123;
		case 2&#58; compare_swap&#40;0, 1&#41;; return;
		case 3&#58; compare_swap&#40;1, 2&#41;; compare_swap&#40;0, 2&#41;; compare_swap&#40;0, 1&#41;; return;
		case 4&#58; compare_swap&#40;0, 1&#41;; compare_swap&#40;2, 3&#41;; compare_swap&#40;0, 2&#41;; compare_swap&#40;1, 3&#41;; compare_swap&#40;1, 2&#41;;	    return;
Must be a pretty big patch of code for the 12 branch.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

Post Reply