Move ordering: Delaying moves on the history phase.

[michiguel]

It is a common practice to delayed losing captures during move ordering to the end. After killers, when you try moves that are not captures and are ordered with some sort of history heuristic, was it tried to delay moves that are predicted to lose material based on SEE? I am going to implement this but I am sure this must have been tried. Even if if does not help much, it may have a positive effect when LMR is implemented.

Miguel

[Tord Romstad]

It is a common practice to delayed losing captures during move ordering to the end. After killers, when you try moves that are not captures and are ordered with some sort of history heuristic, was it tried to delay moves that are predicted to lose material based on SEE?

Yes, I have tried this. Currently, my move ordering is roughly as follows:

1. Hash mvoe
2. Winning and equal captures and promotions, ordered by MVV/LVA.
3. Killers
4. Remaining quiet moves, ordered by history counters
5. Losing captures

I have several times tried replacing it with the following scheme, which is similar to what you suggest:

1. Hash move
2. Winning and equal captures and promotions, ordered by MVV/LVA.
3. Killers
4. Quiet moves with SEE value 0, ordered by history counters
5. All moves with negative SEE value

Intuitively, it seems obvious to me that this is an improvement. Surely, losing non-captures are no more likely to be good than losing captures. Nevertheless, in all my tests, this scheme performed measurably worse than my normal move ordering, both with and without LMR. I wish I understood why.

I am going to implement this but I am sure this must have been tried.

I hope you go ahead and try it -- it isn't that much work. It would be interesting to see if your results agree with mine.

Tord

[Dann Corbit]

It is a common practice to delayed losing captures during move ordering to the end. After killers, when you try moves that are not captures and are ordered with some sort of history heuristic, was it tried to delay moves that are predicted to lose material based on SEE?

Yes, I have tried this. Currently, my move ordering is roughly as follows:

1. Hash mvoe
2. Winning and equal captures and promotions, ordered by MVV/LVA.
3. Killers
4. Remaining quiet moves, ordered by history counters
5. Losing captures

I have several times tried replacing it with the following scheme, which is similar to what you suggest:

1. Hash move
2. Winning and equal captures and promotions, ordered by MVV/LVA.
3. Killers
4. Quiet moves with SEE value 0, ordered by history counters
5. All moves with negative SEE value

Intuitively, it seems obvious to me that this is an improvement. Surely, losing non-captures are no more likely to be good than losing captures. Nevertheless, in all my tests, this scheme performed measurably worse than my normal move ordering, both with and without LMR. I wish I understood why.

I am going to implement this but I am sure this must have been tried.

I hope you go ahead and try it -- it isn't that much work. It would be interesting to see if your results agree with mine.

Tord

I am curious if on the negative SEE, you used the size of the negative score to finish ordering (with the most negative ones on the bottom).

If you did that, then I cannot imagine how it could perform worse.

[Zach Wegner]

Intuitively, it seems obvious to me that this is an improvement. Surely, losing non-captures are no more likely to be good than losing captures. Nevertheless, in all my tests, this scheme performed measurably worse than my normal move ordering, both with and without LMR. I wish I understood why.

After Dann's reply, I had to reread your post. What I thought I read, and what I thought I remembered reading from you before in the past, is the opposite: that all captures should be tried before non-captures. That would make much more sense to me intuitively. A capture, even if it is losing, can disrupt the position a lot more and would be more likely to be some sort of tactical shot giving a cutoff. Additionally, each capture has a smaller subtree (on average) due to there being less pieces).

I'll have to do some big move ordering tests. Unfortunately, there are about a million things that come before that on my todo-list...

[bob]

It is a common practice to delayed losing captures during move ordering to the end. After killers, when you try moves that are not captures and are ordered with some sort of history heuristic, was it tried to delay moves that are predicted to lose material based on SEE? I am going to implement this but I am sure this must have been tried. Even if if does not help much, it may have a positive effect when LMR is implemented.

Miguel

Yes it is quite normal to do that... And it has been done since the 1970's in fact...

[Harald Johnsen]

It is a common practice to delayed losing captures during move ordering to the end. After killers, when you try moves that are not captures and are ordered with some sort of history heuristic, was it tried to delay moves that are predicted to lose material based on SEE? I am going to implement this but I am sure this must have been tried. Even if if does not help much, it may have a positive effect when LMR is implemented.

Miguel

You did not tell us about the kind of nodes where you are going to change the move ordering. I think it is the PV nodes because move ordering (of quiescent moves) is pretty useless on all or cut nodes.

You don't need to use an inacurate SEE for that, just use a real QSearch, or check your hash table to get a real score.

HJ.

[Kempelen]

After killers, when you try moves that are not captures.....

Again here is the novice doing questions: ..... why could not a capture be a killer?

[hgm]

The capture should not be a killer, because captures are tried before killers anyway. The killer heuristic is a device for getting a quick cutoff when captures fail. I think you could make an exception to that if a losing capture is a killer, in a sorting where losing captures go last. Haven't tried it, though.

As to the surprising goodness of losing non-captures, I think I conjectured this before:

Would this not simply be caused by the fact that all Pawn sacrifices fall in this class?

'Bad captures' are not really captures that lose material; they are captures with negative SEE. If they do what SEE promises, they are indeed no good. So the entire use of trying them at all is that SEE might be wrong, because there were side effects it did not consider. (E.g. a defender was (soft-)pinned or overloaded.)

The probability that defenders are pinned or overloaded does not depend on what you move into the square. But if you move a Pawn into the square to lure the defender away from its other task, this 'sacrifice' is much easier to earn back through the side effect than when you move a Queen there. So the chances for a negative-SEE non-capture move with a Pawn to turn out good is much larger than a negative-SEE capture with a Piece (which typically loses 2 Pawns).

Proposed remedy:

order negative-SEE non-captures with Pawns before the bad captures, and other negative-SEE moves behind the bad captures.

[CThinker]

order negative-SEE non-captures with Pawns before the bad captures, and other negative-SEE moves behind the bad captures.

I have it a little more simpler than that. All negative SEE moves are picked last, and they are sorted by their SEE scores.

The ordering looks like this:
1. hash move
2. positive SEE captures (sorted by SEE scores)
3. killers
4. positive SEE non-captures (sorted by history counts)
5. negative SEE moves (captures and non-captures, sorted by SEE scores).

[Martin]

I use a very simple scheme without SEE in Anatoli that seems to perform well.
In the main search I only postpone captures of protected pawns by a piece that is not a pawn.
In the Qsearch I don't even try these captures at the moment (but I plan to be a bit more careful with this later, that's on that looooooooong todo list ).

This is based on the observation that such captures are expensive while others are cheap, because the tree after them is relatively small. After Q x protected N, for instance, the Q will also soon disappear.
Also, in many positions that are a lot of such captures.

As to using SEE to prune captures of pieces<>pawn in the Qsearch, apparently many engines do that (based on what I read here) but I think it's asking for trouble.
I don't have a SEE but maybe somebody can do an experiment: prune only captures of pawns (with SEE). Is the engine much slower? I expect that the cost will be small in most positions. And the upside is that you have a much more accurate Qsearch.

It is possible - didn't try that yet - that ordering captures with SEE helps a bit. I don't expect much of it though.