sort every moves or pickNext

[mhouppin]

Well, as you refine your pruning techniques and your branching factor decreases to come around 2, I think it would definitely be worth using a pickNext function (as 90% of the generated moves will get discarded anyway, so no need to sort them).

An even better approach could be to generate moves as they are needed y the search (so first only the TT move, then the captures sorted by SEE + killers, then maybe the checks, then the quiet moves), saving even more time on move generation, scoring and sorting.

[abulmo2]

In Amoeba I started with a legal move generator and sorted the full move list. Now I use a staged move generator but still sort partial list of moves (good capture, quiet moves, bad captures). Just picking the best move of an unsorted list of moves did not work well in Amoeba. I think my insertion sort algorithm implementation works well on short list of moves pre-sorted during the move generation. I also got some speed enhancement by avoiding sorting functions from the standard (D) library, and using my own simple code.

[bob]

There's a good word to follow in computer chess engine design: Procrastination: (n) the action of delaying or postponing something. In this case, postpone the sort because you will be doing it at two types of nodes that are bad. (1) nodes that are going to fail low, where order is not so important; (2) this is the important one, fail-high nodes. If you go to all the effort of sorting the entire move list (most likely O(N^2/2, or N log(N) if you go out on a limb) and fail high on the first move, you wasted a ton of effort. Best answer is some sort of NextMove (Crafty) or a flavor of PickMove(), where you use a simple selection sort. This is one pass over the moves to pick what you think is the best, then the next time you make one pass over the remaining N-1 moves, etc. If you get a cutoff, you eliminate the effort you would have expended to sort the moves.

You can take this much further. For example, search the transposition move before generating anything. Then generate captures only and order those with MVV/LVA or whatever. Then come the non-capture moves starting with killers. Search those before generating the remaining non-capture moves. Again avoiding any sorting or whatever.

Overall the idea is, never do now what you can do later (and you might not even have to do it at all.)

[Patrice Duhamel]

In Cheese I also use staged move generation but picking moves instead of sorting them is slower.
Last time I tested it was almost the same speed for picking captures but slower for picking quiet moves.

Does picking moves works only with very good move ordering ?

[bob]

If you think about "picking" over sorting, the first gain comes from not generating things. IE try hash move BEFORE generating a single move. Then generate captures, sort according to whatever criteria you want. Then try the killer moves (quiet since captures are not allowed in them) without generating anything further. Now you can generate the rest of the moves. If you fail high on hash move, you did no generation or sorting of any kind... Ditto for killers where all you have generated so far are captures...

[Patrice Duhamel]

If you think about "picking" over sorting, the first gain comes from not generating things. IE try hash move BEFORE generating a single move. Then generate captures, sort according to whatever criteria you want. Then try the killer moves (quiet since captures are not allowed in them) without generating anything further. Now you can generate the rest of the moves. If you fail high on hash move, you did no generation or sorting of any kind... Ditto for killers where all you have generated so far are captures...

Yes, this is what I am doing, trying hash first, generating captures only, then killers, generating quiets, and trying bad captures at the end.

I don't understand why picking moves for captures or quiets instead of sorting them after generating + scoring is slower in some engines.

[hgm]

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.

Of course you can try to be clever, and use quick sort in stages: first split the entire set into a lhigh and a low half, then split the upper half in to, then the upper quarter, etc. This is only O(N), and would give you the best move. Every time you run into a sub-section that was not yet completely sorted, you fist complete the quick sort of that sub-section. If you get to the end of the move list you would have done a full quick sort, otherwise only part of it.

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