Ply one move sorting

[chrisw]

does anyone sort moves at ply one? presumably .....

what's your hit rate for finding the later bestmove (in an unsorted list a later bestmove should, on average, be found midway in the list)

anyone with better results than that? where on average is a bestmove found in your list? First 25%? first 30%?

Chris

[Bill Rogers]

Yes, I do and I think Rebel also does. If I remember correctly Rebel does a minor eval on one ply, ie. Captures and Piece square tables and then sorts them. He claims it speeds up the program a lot.
Bill

[Dann Corbit]

does anyone sort moves at ply one? presumably .....

what's your hit rate for finding the later bestmove (in an unsorted list a later bestmove should, on average, be found midway in the list)

anyone with better results than that? where on average is a bestmove found in your list? First 25%? first 30%?

Chris

From what I have seen, many programs spend extreme effort ordering at the root (e.g. using qsort() to order every single move with expensive calculations to give each move a rank) and then lesser energy ordering subsequent moves.

An example of a program that spends special effort ordering the root move is Fruit. (See function root_list_sort()).

An example of a program that spends special effort ordering the root move is Glaurung (see RootMoveList::sort()).

[Bill Rogers]

I wonder way they would use qsort when it had been proven that a bubble sort on less than 100 items is usually the fastest sort around.
Bill

[bob]

does anyone sort moves at ply one? presumably .....

what's your hit rate for finding the later bestmove (in an unsorted list a later bestmove should, on average, be found midway in the list)

anyone with better results than that? where on average is a bestmove found in your list? First 25%? first 30%?

Chris

I don't have any real data I can find, but a few years ago I changed the way I sort them.

I originally did a static eval of each move, and used SEE to determine whether the move appeared to lose material or not. I used this in Cray Blitz for years for the first sort for a brand new search.

A few years back, I replaced the SEE and eval with a simple call to Quiesce() after making each move, and using that score to sort them. I called Quiesce() with an open window to get a real score for each root move.

That's the sort for starting off. Once I do the first iteration, I then use the node count for the subtree produced by each root move to order them beyond that point. In general the best move from the previous iteration will have a node count _way_ bigger than any other move, unless there were "changes of mind" during that iteration where any one of the best moves could have the biggest count. To solve this, I always force the best move from ply-1 to the top of the list, and sort the rest based on their node counts.

We started doing this in Cray Blitz at the suggestion of Harry Nelson who was a fanatic about solving problem positions. He noticed that in a position where there is a deep winning combination on a move that looks bad at first, each iteration the size of the subtree for that move grows with respect to the subtrees of other moves, because it gets harder and harder to prove the move is bad. Until finally that move becomes best. The idea is to move those moves that are a bit harder to search closer to the front of the list to get to them sooner, rather than later (or never, if the iteration times out before they are reached.)

I do this today in Crafty, and several others have tried it and use it as well. Whether there are better approaches remains to be seen, but this does work pretty well...

[bob]

I wonder way they would use qsort when it had been proven that a bubble sort on less than 100 items is usually the fastest sort around.
Bill

Even more importantly, this is done only once per search, which means you could use an abacus to sort 'em and not hurt performance.

[chrisw]

does anyone sort moves at ply one? presumably .....

what's your hit rate for finding the later bestmove (in an unsorted list a later bestmove should, on average, be found midway in the list)

anyone with better results than that? where on average is a bestmove found in your list? First 25%? first 30%?

Chris

I don't have any real data I can find, but a few years ago I changed the way I sort them.

I originally did a static eval of each move, and used SEE to determine whether the move appeared to lose material or not. I used this in Cray Blitz for years for the first sort for a brand new search.

A few years back, I replaced the SEE and eval with a simple call to Quiesce() after making each move, and using that score to sort them. I called Quiesce() with an open window to get a real score for each root move.

That's the sort for starting off. Once I do the first iteration, I then use the node count for the subtree produced by each root move to order them beyond that point. In general the best move from the previous iteration will have a node count _way_ bigger than any other move, unless there were "changes of mind" during that iteration where any one of the best moves could have the biggest count. To solve this, I always force the best move from ply-1 to the top of the list, and sort the rest based on their node counts.

We started doing this in Cray Blitz at the suggestion of Harry Nelson who was a fanatic about solving problem positions. He noticed that in a position where there is a deep winning combination on a move that looks bad at first, each iteration the size of the subtree for that move grows with respect to the subtrees of other moves, because it gets harder and harder to prove the move is bad. Until finally that move becomes best. The idea is to move those moves that are a bit harder to search closer to the front of the list to get to them sooner, rather than later (or never, if the iteration times out before they are reached.)

I do this today in Crafty, and several others have tried it and use it as well. Whether there are better approaches remains to be seen, but this does work pretty well...

Well, I have an idea I tested which is why I ask

would you be able to come up with some stats, say on a test suite of a zillion positions ...

how far down the move list is the bestmove (say anything found after 60 secs or so) - then average it over the N positions. express at percentage (with no sort giving result 50% presumably)

clearly if one can push the likely candidate bestmoves way up the front of the move list, this is equivalent to some search speed improvement (its faster to find a new best if its 3rd in the move list than if its 30th)

[Don]

I wonder way they would use qsort when it had been proven that a bubble sort on less than 100 items is usually the fastest sort around.
Bill

For small lists, insertion sort is better than bubble sort. It's even more so on modern hardware. I use insertion sort for these quick and dirty sorts.

In THEORY, they are the same O(n^2) but bubble sort tends to require more writes and is harder on the memory cache from what I understand.

Still, it probably doesn't make any difference if we are talking about just the root move list. As Bob says, we could use an abacus.

Bubble sort may be fine for doing what Bob says, where a list is almost sorted and you are just resorting because it's sensitive to the initial state of the list and has very poor worst case behavior. But for general sorting of small lists I think insertion sort is a better choice.

[bob]

does anyone sort moves at ply one? presumably .....

what's your hit rate for finding the later bestmove (in an unsorted list a later bestmove should, on average, be found midway in the list)

anyone with better results than that? where on average is a bestmove found in your list? First 25%? first 30%?

Chris

I don't have any real data I can find, but a few years ago I changed the way I sort them.

I originally did a static eval of each move, and used SEE to determine whether the move appeared to lose material or not. I used this in Cray Blitz for years for the first sort for a brand new search.

A few years back, I replaced the SEE and eval with a simple call to Quiesce() after making each move, and using that score to sort them. I called Quiesce() with an open window to get a real score for each root move.

That's the sort for starting off. Once I do the first iteration, I then use the node count for the subtree produced by each root move to order them beyond that point. In general the best move from the previous iteration will have a node count _way_ bigger than any other move, unless there were "changes of mind" during that iteration where any one of the best moves could have the biggest count. To solve this, I always force the best move from ply-1 to the top of the list, and sort the rest based on their node counts.

We started doing this in Cray Blitz at the suggestion of Harry Nelson who was a fanatic about solving problem positions. He noticed that in a position where there is a deep winning combination on a move that looks bad at first, each iteration the size of the subtree for that move grows with respect to the subtrees of other moves, because it gets harder and harder to prove the move is bad. Until finally that move becomes best. The idea is to move those moves that are a bit harder to search closer to the front of the list to get to them sooner, rather than later (or never, if the iteration times out before they are reached.)

I do this today in Crafty, and several others have tried it and use it as well. Whether there are better approaches remains to be seen, but this does work pretty well...

Well, I have an idea I tested which is why I ask

would you be able to come up with some stats, say on a test suite of a zillion positions ...

how far down the move list is the bestmove (say anything found after 60 secs or so) - then average it over the N positions. express at percentage (with no sort giving result 50% presumably)

clearly if one can push the likely candidate bestmoves way up the front of the move list, this is equivalent to some search speed improvement (its faster to find a new best if its 3rd in the move list than if its 30th)

OK, I can do that. But it needs to be precisely specified what I am measuring.

option 1:

For each iteration, I simply count how many times the best move was first, or second or ... down to how many times was the best move last.

option 2:

Only count the final iteration stats, since those reflect what happened on the iteration that actually produced the move played...

It would be easy to do either way although option 1 would be the easiest to do for me. I could then run any number of test positions you choose and report back on the results.

One _important_ note however, is that root-move ordering for normal games is not the same as root-move ordering for problem positions. Typically a test position has some surprising move (commonly a sacrifice) that will look bad until the search goes deep enough to expose the "punch line"... Something that moves those surprising moves up will help tactical test positions but hurt normal chess. One example is trying all captures first, regardless of material gain or loss. That will help with tactical positions that have a sacrifice as a starting point, but will make the tree larger for normal positions.

So, tell me how to proceed and I will fire it up...

[Dann Corbit]

I wonder way they would use qsort when it had been proven that a bubble sort on less than 100 items is usually the fastest sort around.
Bill

1. If we only apply the algorithm to ply 1, then the choice of the algorithm to sort is completely irrelevant. IOW, if qsort() took 1 millisecond and an O(N^2) sort took 1 nanaosecond, then our search is 1/1000th second slower, but that is for the whole search.

2. Bubble sort is very fast if the list is nearly sorted. Insertion sort performs better if the list has some entropy. In any case, almost every decent qsort() library actually changes the algorithm to an O(N^2) sort for small partitions so it will call a faster sort anyway.

The use of qsort() was just a 'for instance' and I do know of more than one program that does use qsort() in this phase. But changing the ordering algorithm for ply 1 is not going to change the performance of the search at all anyway.

The algorithm to order moves on subsequent plies is *much* more important in the grand scheme of things.