Evaluation questions

[amanjpro]

Best advice is to quit. But fools never listen to good advice.

Am I reading this wrong, or did you just call the OP a fool?

[Henk]

Yes you must be a fool to work on a chess engine. Cost enormous.
But thats no news. Maybe forty years ago a good idea.

[ZirconiumX]

Thomas and Amanj,

Thank you for these ordering schemes! I am going to try them out asap.

Thomas,

for MVV-LVA...

I think the size of the moves usually ranges from 1-100... So it would probably make sense to leverage caching when sorting...

Would you recommend insertion-sort? Or would a combination of insertion-sort and dual-pivot-quicksort be better? I know that these sorts rely on swapping pretty heavily... and dual-pivot-quicksort seems to do very well between 32-256 elements. Also, stability shouldn't matter much, right? (Would it make a difference how two "equal" moves are ordered?)

Actually, C++ has exactly the algorithm you need for this: std::nth_element is O(n) for each element. While this is technically O(n^2) worst case, the algorithmic math changes here because in a cut node you do not need all N elements.

Alternatively you could explore std::make_heap and std::pop_heap, which is O(n log n) worst case. As always, benchmark.

[Ras]

I think the size of the moves usually ranges from 1-100

The maximum found is 218 moves IIRC, in a constructed, but legal position.

... So it would probably make sense to leverage caching when sorting...

The number one thing: don't use dynamic memory allocation during search. You can put these arrays on the stack with no malloc.

Would you recommend insertion-sort? Or would a combination of insertion-sort and dual-pivot-quicksort be better?

I swap the "best" (as per move sorting) move to the top, and only if that doesn't lead to a cut-off, I sort the rest of the array using Shellsort.

Also, stability shouldn't matter much, right?

My Shellsort isn't stable - no problems with that.

[Mergi]

Actually, C++ has exactly the algorithm you need for this: std::nth_element is O(n) for each element. While this is technically O(n^2) worst case, the algorithmic math changes here because in a cut node you do not need all N elements.

Alternatively you could explore std::make_heap and std::pop_heap, which is O(n log n) worst case. As always, benchmark.

I was wondering what would be the benefit of this approach over just plain std::max_element? I've done some testing before in my engine and std::max_element proved to be by far the best solution (comparing std::sort, std::nth_element, std::max_element). It seems to me, that since the absolute majority of moves gets discarded anyway, there's no point in spending time sorting (even partially).

I could maybe imagine having the first move picked by std::nth_element, and then having the rest of the moves already "kinda" sorted if you need to pick more moves later, to be of some small benefit? But even then, the problem is that if you call std::nth_element to pick the best move (index 0), there's absolutely no guarantee of how the rest of the array will look like.

[lithander]

for MVV-LVA...

I think the size of the moves usually ranges from 1-100... So it would probably make sense to leverage caching when sorting...

Would you recommend insertion-sort? Or would a combination of insertion-sort and dual-pivot-quicksort be better? I know that these sorts rely on swapping pretty heavily... and dual-pivot-quicksort seems to do very well between 32-256 elements. Also, stability shouldn't matter much, right? (Would it make a difference how two "equal" moves are ordered?)

With MVV-LVA you only have to sort the captures so that's far less then a 100 moves. Also as soon as you get a cutoff all effort spent on sorting the remaining moves was done in vain.

That means that sorting-approaches that don't really scale well with large N can actually be the best choice here because N is typically small. For example if you assign a move score to each generated move (based on MVV-LVA and history/killer heuristic or whatever else you want to use for move ordering) and then iterate over the move list and just pick the move with the best score and remove it or mark it as played... in a scenario where you really have to play 100 moves in sorted order that would be terribly inefficient O(n^2) but in the vast majority of cases you get an early cutoff and so it might turn out to be the "best" way to select moves, regardless of it's bad scaling.

I would search a set of test position to a fixed depth and measure the time it takes to complete all tests. If the search order is the same and you are just trying different sorting algorithms then the number of visited nodes should be the same in all tests. But the runtime to completion would differ. Then you can pick the approach that performed best.

[Bo Persson]

That means that sorting-approaches that don't really scale well with large N can actually be the best choice here because N is typically small. For example if you assign a move score to each generated move (based on MVV-LVA and history/killer heuristic or whatever else you want to use for move ordering) and then iterate over the move list and just pick the move with the best score and remove it or mark it as played... in a scenario where you really have to play 100 moves in sorted order that would be terribly inefficient O(n^2) but in the vast majority of cases you get an early cutoff and so it might turn out to be the "best" way to select moves, regardless of it's bad scaling.

There is also a point where you might suspect that the ordering is of no use, so after perhaps 5-10 unsuccessful selected moves, you could just give up and try the remaining ones unsorted. Perhaps they all have the same lousy score anyway?

Avoids the O(n^2) for the terrible 100 moves case.