Sorting algorithms

[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&#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]

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

[hgm]

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]

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]

[...]
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]

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]

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]

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.

[tpetzke]

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;

[Dann Corbit]

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.