sort every moves or pickNext

[Ras]

Using quick sort for sorting the whole lot at one is only O(N*log(N))

Quicksort performs worse than Shellsort on list lengths below 100, which is typical for move lists. If using C, then the function calls via function pointers won't be inlined, which adds another performance hog (not applicable to C++ with templating of course).

The picking speculates that you will get a quick cutoff; to find the best move is only O(N). But not every node is a cut node; about half of them are all-nodese, where you eventually search all moves.

You can just find the "best" (by sorting measure) move and swap it to the top so that you don't sort if the first move cuts. Only sort the remainder if the first move doesn't cut. Also, the remaining move list has only a length of N-1 so that even in abscence of a cutting first move, getting the best move to the top hasn't been completely in vain.

[hgm]

I often have to deal with variants where there are far more than 100 moves.

But my preferred sorting method for non-captures is just binning the moves by relative history score. That is, when updating the history table you keep track of the maximum history value. And I keep history scores as floats. That way you can use the upper bits directly as bin index. If you have much more bins than you have moves, bins will not often contain more than one move. So by running through the bins top-down you encounter the moves in sorted order. If there are more moves in the same bin, their history values are so close that it presumably does not matter which one you try first.

To speed up looping through sparsely populated bins you flag bins into which you store a move in a few uint64 words. You can then loop through the populated bins by extracting the bits from these flag words.

This is O(N) even for an all-node, and hardly requires more time than scoring the moves.

[syzygy]

Sorting by picking the best every time is an O(N^2) process, which can get pretty slow if there are many moves (like there typically would be for non-captures). Using quick sort for sorting the whole lot at one is only O(N*log(N)), which is significantly less work if N is large. The picking speculates that you will get a quick cutoff; to find the best move is only O(N). But not every node is a cut node; about half of them are all-nodese, where you eventually search all moves.

Since "ALL nodes" cannot be avoided anyway, why not pick remaining moves in the order they were generated if the best k moves haven't led to a cutoff? That gives linear complexity.

[hgm]

True. But some engines use a reduction that is dependent on the order, and randomly ordering the late moves might make that less effective.

Besides, even picking two moves could already be slower than the binned sorting.

[Michael Sherwin]

What I do in RomiChess is generate all the bitboards first without spinning them into a move list. That checks for legality since Romi uses pseudo legal move generation. Next I play the hash move and the check for validity is as simple as checking the bit in the bitboard for the piece. Romi does not have to make a move list out of the remaining bits until after Castlings, promotions, good captures, two killer moves and a move killer. Then for quiet moves and bad captures is AddMoves() called to make a list that is ordered by a shallow search or if depth is < 3 ordered by the pst.