sort every moves or pickNext

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.
Ras
Posts: 1348
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: sort every moves or pickNext

Post by Ras » Sun May 17, 2020 10:55 am

hgm wrote:
Sun May 17, 2020 10:12 am
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.
Rasmus Althoff
https://www.ct800.net

User avatar
hgm
Posts: 24441
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: sort every moves or pickNext

Post by hgm » Sun May 17, 2020 11:19 am

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
Posts: 4496
Joined: Tue Feb 28, 2012 10:56 pm

Re: sort every moves or pickNext

Post by syzygy » Sun May 17, 2020 3:27 pm

hgm wrote:
Sun May 17, 2020 10:12 am
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.

User avatar
hgm
Posts: 24441
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: sort every moves or pickNext

Post by hgm » Sun May 17, 2020 5:56 pm

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
Posts: 3191
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: sort every moves or pickNext

Post by Michael Sherwin » Mon May 18, 2020 3:14 am

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.
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through

Post Reply