std::sort with memory?

actually, the sorting is an optimization. The search needs to recurse down every possible move up to a certain depth. However, the algorithm I am using, Alpha-beta (http://en.wikipedia.org/wiki/Alpha-beta_pruning), performs a lot better when the initial move ordering is good (good moves are searched before bad ones). Of course, I cannot just find a best move without doing the recursion, otherwise I wouldn't need the recursion in the first place. Sorting just makes it MORE LIKELY that good moves are placed in the front.

Originally Posted by cyberfish

Thanks for your offer, really appreciated it. However, it is quite complicated as I am sorting a list of chess moves generated by my chess engine during its search in the order of likelihood to be a good move. The comparison operator does things like static exchange evaluation (count pieces from both sides attacking on the destination square to estimate material gain/lose), history heuristic (how many times has a move been proven useful in other parts of the search tree), and other minor criterias. Therefore, I think it would be too context-dependent for anyone to help just by looking at that function alone.

Thanks

That's alright. Even without getting code posted here I've prompted the release of more information we can use to help you. It sounds like you don't really need to fully sort the array afterall since presumably it will still succeed without being sorted, it will just take longer, am I correct?
If so, you could instead periodically perform quick-sort-like passes similiar to how you the find k-smallest algorithm, that uses partitioning and only recurse on the lower half each time (assuming a near-even split). That would bring the lowest (best) value items to the front, and those almost as low (good) ones to close-ish to the front.
However if you are actually repeatedly sorting this array then you may find that insertion sort beats introsort as it becomes O(n) in the nearly sorted case.
Are duplicates possible, and is sorting being used to help identify them? If so then it's a different story again...

Couldn't you separate position evaluation from comparisons? The position evaluation (which would be done only once for each position) could yield a single number and you could compare based on that?

Originally Posted by cyberfish

Thanks for your offer, really appreciated it. However, it is quite complicated as I am sorting a list of chess moves generated by my chess engine during its search in the order of likelihood to be a good move. The comparison operator does things like static exchange evaluation (count pieces from both sides attacking on the destination square to estimate material gain/lose), history heuristic (how many times has a move been proven useful in other parts of the search tree), and other minor criterias. Therefore, I think it would be too context-dependent for anyone to help just by looking at that function alone.

Thanks

Make sure that if you do attempt to sort, that your sort criterion satisfies all of the conditions of a strict weak ordering. If it's a total preorder instead of a strict weak ordering, you can make use of the correspondence between the two to convert the one to the other (see my earlier link for details).

Couldn't you separate position evaluation from comparisons? The position evaluation (which would be done only once for each position) could yield a single number and you could compare based on that?

That wouldn't be as accurate as the static evaluation function doesn't resolve captures. See my post above for what I am currently doing for move ordering. Many of those techniques cannot be used with static evaluation (history heuristic for example).

Make sure that if you do attempt to sort, that your sort criterion satisfies all of the conditions of a strict weak ordering. If it's a total preorder instead of a strict weak ordering, you can make use of the correspondence between the two to convert the one to the other (see my earlier link for details).

Thanks for reminding me. Yes, it satisfies conditions of a strict weak ordering.

It sounds like you don't really need to fully sort the array afterall since presumably it will still succeed without being sorted, it will just take longer, am I correct?

that is correct.

If so, you could instead periodically perform quick-sort-like passes similiar to how you the find k-smallest algorithm, that uses partitioning and only recurse on the lower half each time (assuming a near-even split). That would bring the lowest (best) value items to the front, and those almost as low (good) ones to close-ish to the front.

That sounds like a very interesting scheme. However, as the list of moves is usually small (~30), I am not sure if it's worth the complexity.

Are duplicates possible, and is sorting being used to help identify them? If so then it's a different story again...

duplicates are possible (in the sense that two moves are estimated to be equally as good), however, they are not identified by the sorting. The sorting does not have to be stable either.