Move ordering: Delaying moves on the history phase.

[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.

[Martin]

Typo: Also, in many positions THERE are a lot of such captures.

Only 15 minutes to correct?!

[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?

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

Ok, I tried. I tested it with Dann's "silent but deadly" suite at depth 6 (~130 positions) counting total nodes. This was preliminar, but I still think that more positions at shallower depth is better than deeper searches and less positions.

The best for me is at the beginning (after hash move)
1) non losing captures determined by SEE but ordered by MMV/LVA
2) killers
3) see later for the rest

This is clearly better than
1) non losing captures determined by SEE and ordered by SEE
2) killers
or
1) all captures ordered by SEE
2) killers
or (which was second)
1) all captures ordered by MVV/LVA
2) killers

For the rest, I may settle for ordering all moves (losing captures + quiet moves, losing and non losing) with history heuristics (which helps me ~10%). Delaying losing quiet moves does not help significantly and searching at depth 7 was only 64.4 Mnodes vs. 65.5 Mnodes.

I tested other things, after killers, like 3) losing captures (ordered by MVV/LVA), 4) quiet moves (ordered by history)
or 3) losing captures, 4) quiet moves 5) losing quiet
or 3) quiet moves 4) losing captures 5) losing quiet
and also the suggestion from HGMuller regarding pawn advances.

My impression is that after killers, no matter what I do, I do not see big differences. Even if I try losing captures first, is not bad. It is almost the same. I should run the whole thing with a deeper depth, but I doubt I will see a big difference.

In conclusion, for my program, after the killers, delaying quiet moves with SEE adds a negligible gain (nps drop more than than the almost invisible). Also, delaying losing captures is not good. The likelihood for a move to be cutoff after killers seems to have a random nature.

Most of the positions in the suite are middlegames. Endgames may be different.

The random nature of this phase may explain why delaying captures is bad in certain cases such as in your program. You gamble with quiet vs. losing quiets. Sometimes you are right and sometimes you are wrong. It may be better to gamble in your program with moves that if they are wrong, they are cut off quickly.

Miguel

[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

Ok, I tried. I tested it with Dann's "silent but deadly" suite at depth 6 (~130 positions) counting total nodes. This was preliminar, but I still think that more positions at shallower depth is better than deeper searches and less positions.

The best for me is at the beginning (after hash move)
1) non losing captures determined by SEE but ordered by MMV/LVA
2) killers
3) see later for the rest

This is clearly better than
1) non losing captures determined by SEE and ordered by SEE
2) killers
or
1) all captures ordered by SEE
2) killers
or (which was second)
1) all captures ordered by MVV/LVA
2) killers

For the rest, I may settle for ordering all moves (losing captures + quiet moves, losing and non losing) with history heuristics (which helps me ~10%). Delaying losing quiet moves does not help significantly and searching at depth 7 was only 64.4 Mnodes vs. 65.5 Mnodes.

I tested other things, after killers, like 3) losing captures (ordered by MVV/LVA), 4) quiet moves (ordered by history)
or 3) losing captures, 4) quiet moves 5) losing quiet
or 3) quiet moves 4) losing captures 5) losing quiet
and also the suggestion from HGMuller regarding pawn advances.

My impression is that after killers, no matter what I do, I do not see big differences. Even if I try losing captures first, is not bad. It is almost the same. I should run the whole thing with a deeper depth, but I doubt I will see a big difference.

In conclusion, for my program, after the killers, delaying quiet moves with SEE adds a negligible gain (nps drop more than than the almost invisible). Also, delaying losing captures is not good. The likelihood for a move to be cutoff after killers seems to have a random nature.

Most of the positions in the suite are middlegames. Endgames may be different.

The random nature of this phase may explain why delaying captures is bad in certain cases such as in your program. You gamble with quiet vs. losing quiets. Sometimes you are right and sometimes you are wrong. It may be better to gamble in your program with moves that if they are wrong, they are cut off quickly.

Miguel

I would be interested to see what happens if you try your exact same ordering methods against a simple tactical test like WAC.

[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?

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

Ok, I tried. I tested it with Dann's "silent but deadly" suite at depth 6 (~130 positions) counting total nodes. This was preliminar, but I still think that more positions at shallower depth is better than deeper searches and less positions.

The best for me is at the beginning (after hash move)
1) non losing captures determined by SEE but ordered by MMV/LVA
2) killers
3) see later for the rest

This is clearly better than
1) non losing captures determined by SEE and ordered by SEE
2) killers
or
1) all captures ordered by SEE
2) killers
or (which was second)
1) all captures ordered by MVV/LVA
2) killers

For the rest, I may settle for ordering all moves (losing captures + quiet moves, losing and non losing) with history heuristics (which helps me ~10%). Delaying losing quiet moves does not help significantly and searching at depth 7 was only 64.4 Mnodes vs. 65.5 Mnodes.

I tested other things, after killers, like 3) losing captures (ordered by MVV/LVA), 4) quiet moves (ordered by history)
or 3) losing captures, 4) quiet moves 5) losing quiet
or 3) quiet moves 4) losing captures 5) losing quiet
and also the suggestion from HGMuller regarding pawn advances.

My impression is that after killers, no matter what I do, I do not see big differences. Even if I try losing captures first, is not bad. It is almost the same. I should run the whole thing with a deeper depth, but I doubt I will see a big difference.

In conclusion, for my program, after the killers, delaying quiet moves with SEE adds a negligible gain (nps drop more than than the almost invisible). Also, delaying losing captures is not good. The likelihood for a move to be cutoff after killers seems to have a random nature.

Most of the positions in the suite are middlegames. Endgames may be different.

The random nature of this phase may explain why delaying captures is bad in certain cases such as in your program. You gamble with quiet vs. losing quiets. Sometimes you are right and sometimes you are wrong. It may be better to gamble in your program with moves that if they are wrong, they are cut off quickly.

Miguel

I would be interested to see what happens if you try your exact same ordering methods against a simple tactical test like WAC.

That's a good question and I will test it.

Miguel

[pijl]

My impression is that after killers, no matter what I do, I do not see big differences. Even if I try losing captures first, is not bad. It is almost the same. I should run the whole thing with a deeper depth, but I doubt I will see a big difference.
<snip>
The random nature of this phase may explain why delaying captures is bad in certain cases such as in your program. You gamble with quiet vs. losing quiets. Sometimes you are right and sometimes you are wrong. It may be better to gamble in your program with moves that if they are wrong, they are cut off quickly.

I think we should not forget why we are ordering moves. It is to find a move that gives us a beta cut as early as possible. And if possible as cheap as possible. So you should order moves by the chance that they give a cutoff and by the amount of work that is needed to search them. I rather search 3 moves with little effort (i.e. supposedly losing captures, as they may not be losing after all due to pins, overloaded defenders etc) that do have some chance of finding a nice sacrifice than one move that is taking more effort and that has no obvious tactical meaning. In the end, if no beta cuts are found, all moves are searched anyway. (Yes, I'm only talking about nullwindow searches as those are the majority in PVS anyway).
So I'm trying losing captures before quiet moves. Actually my ordering (after killers) is:
- losing captures
- castling
- minor promotions (usually a waste of effort, so perhaps I'll order them further down. The most common reason where a promotion does not work is because the queen gets captured or because there is a different threat on the other side so a minor promotion will not work either)
- non-capture moves, ordered by a combination of history and psq tables
Richard.

[PK-4]

Actually my ordering (after killers) is:
- losing captures
- castling
- minor promotions (usually a waste of effort, so perhaps I'll order them further down. The most common reason where a promotion does not work is because the queen gets captured or because there is a different threat on the other side so a minor promotion will not work either)
- non-capture moves, ordered by a combination of history and psq tables
Richard.

It would be interesting to know the result of a match between two versions of your engine, the above and a version where the move ordering is:

- castling
- minor promotions (usually a waste of effort, so perhaps I'll order them further down. The most common reason where a promotion does not work is because the queen gets captured or because there is a different threat on the other side so a minor promotion will not work either)
- non-capture moves, ordered by a combination of history and psq tables
- losing captures

[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?

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

Ok, I tried. I tested it with Dann's "silent but deadly" suite at depth 6 (~130 positions) counting total nodes. This was preliminar, but I still think that more positions at shallower depth is better than deeper searches and less positions.

The best for me is at the beginning (after hash move)
1) non losing captures determined by SEE but ordered by MMV/LVA
2) killers
3) see later for the rest

This is clearly better than
1) non losing captures determined by SEE and ordered by SEE
2) killers
or
1) all captures ordered by SEE
2) killers
or (which was second)
1) all captures ordered by MVV/LVA
2) killers

For the rest, I may settle for ordering all moves (losing captures + quiet moves, losing and non losing) with history heuristics (which helps me ~10%). Delaying losing quiet moves does not help significantly and searching at depth 7 was only 64.4 Mnodes vs. 65.5 Mnodes.

I tested other things, after killers, like 3) losing captures (ordered by MVV/LVA), 4) quiet moves (ordered by history)
or 3) losing captures, 4) quiet moves 5) losing quiet
or 3) quiet moves 4) losing captures 5) losing quiet
and also the suggestion from HGMuller regarding pawn advances.

My impression is that after killers, no matter what I do, I do not see big differences. Even if I try losing captures first, is not bad. It is almost the same. I should run the whole thing with a deeper depth, but I doubt I will see a big difference.

In conclusion, for my program, after the killers, delaying quiet moves with SEE adds a negligible gain (nps drop more than than the almost invisible). Also, delaying losing captures is not good. The likelihood for a move to be cutoff after killers seems to have a random nature.

Most of the positions in the suite are middlegames. Endgames may be different.

The random nature of this phase may explain why delaying captures is bad in certain cases such as in your program. You gamble with quiet vs. losing quiets. Sometimes you are right and sometimes you are wrong. It may be better to gamble in your program with moves that if they are wrong, they are cut off quickly.

Miguel

I would be interested to see what happens if you try your exact same ordering methods against a simple tactical test like WAC.

That's a good question and I will test it.

Miguel

Again, I do not think that this is the most thorough experiment, but I got similar results except with one (D). WAC = 1 second on an AMD 1.4 Ghz
I tried several combinations after killers but the most interesting comparison is:

Code: Select all

NLQ = non losing quiets
A= 1) history NLQ 2) losing capt. 2) losing quiets 
B= 1) losing capt. 2) history NLQ 3) losing quiets  
C= 1) history for all of them combined
D= 1) combined history of NLQ + losing capt 2) losing quiets

         WAC            tree size 
     (solve/300)     (quiet positions)
                         Mnodes			
A        269              20.8      
B        265              20.1
C        265              20.0
D        267              19.7

It is not clear whether delaying losing quiets is good idea or not but possibly delaying losing captures is not a good idea. Putting them up front may not be the best either, but treating them as any other quiet move may be (i.e. sorted by history).

I believe there are better ways to test this, but this is a quick one.

Miguel

[Harald Johnsen]

Can you do your tests on bt2630 for example ?
I don't think that all the mate in n positions of wac are interesting for move ordering.

HJ.