Sorting moves during move ordering

[Ronald]

I tested the difference a long time ago, and at that time the difference was significant, although I don't remember how much...

Testing it now is not so easy, because I calculate the historyscore on the fly and I don't have space to store the values.

[Desperado]

If you are using some sort of historyscore for the sorting of quiet moves, the historyscore of moves change while searching the current quiet move. If you presort the quiet moves, you don't use the changes in historyscore for the still to search quiet moves which can lead to a different order of those moves.

That is true. But you can choose to assign the sorting values once per stage, so it would not matter if they change.
On the other hand it might be an improvement to use updated history counters. In the end you only have the choice in the "pick next best" model.

At least that can be a very different (good) reason beside the technical speedup to choose this technique.

[xr_a_y]

If you are using some sort of historyscore for the sorting of quiet moves, the historyscore of moves change while searching the current quiet move. If you presort the quiet moves, you don't use the changes in historyscore for the still to search quiet moves which can lead to a different order of those moves.

Clever !

[nionita]

I tested the difference a long time ago, and at that time the difference was significant, although I don't remember how much...

Testing it now is not so easy, because I calculate the historyscore on the fly and I don't have space to store the values.

In Barbarossa I got a few ELo with this, don't remember how much, but it was significant. I took the idea from Crafty, I think. Or maybe from a comment from Bob.

[silentshark]

If you are using some sort of historyscore for the sorting of quiet moves, the historyscore of moves change while searching the current quiet move. If you presort the quiet moves, you don't use the changes in historyscore for the still to search quiet moves which can lead to a different order of those moves.

Clever !

Yes, I'd not thought of this. My 'pick the next highest scoring' algorithm doesn't lend itself easily to this, but I will give this a whirl.

On a related note, have people experimented with putting more effort into sorting moves which are a long way from the leaves? For example, might it be worth trying other tricks to better sort moves at, say, depth > 8 (or whatever)?

[hgm]

Indeed, speed is only important near the leaves. And using the updated history counts for every new move only makes a difference if there is sufficient updating going on, i.e. when the tree hanging from the node is large. So it seems likely that the entire positive effect of doing this comes from the nodes close to the roots, and is partly offset by it requiring a more expensive sorting method near the leaves. So it does make sense to adapt the algorithm to the remaining depth.

On another note, I am still dissatisfied by the performance of killer + history. Killer is too local, and only helps to get the first move of a refutation for the later moves of the node (where the first move still has to find it the hard way). While history is too global: it suggests the same moves everywhere.

What I would like is a kind of 'killer tree', which suggests not just the first move of the refutation to a sibbling node, but acts as a 'template' for the entire sibbling sub-tree. Come to think of it, it might not be too difficult to do that. But I will discuss it in a topic of its own.

[Ras]

Is it better to sort all moves in advance or should the highest ordered move just be found at each iteration instead?

I'm doing a hybrid approach: I loop through the move list and note the "best" move via static move ranking (such as PV move, hash table move, threat move, MVV-LVA, killer moves, history scores).

This first move gets swapped to the top of the list and tried. In about 50% of the cases, that leads already to a cut-off so that the rest of the move list is never tried. If the first move is from the hash table, that's even 90%. However, if the first move hasn't cut, and if I have more than two moves overall, I sort the remaining move list using a Shellsort with the Ciura sequence up to 57. With the typical short move list lengths in chess, Shellsort performs better than Quicksort.