Move ordering: Delaying moves on the history phase.

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
CThinker
Posts: 388
Joined: Wed Mar 08, 2006 9:08 pm
Contact:

Re: Move ordering: Delaying moves on the history phase.

Post by CThinker » Wed May 14, 2008 5:13 pm

hgm wrote: 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

Re: Move ordering: Delaying moves on the history phase.

Post by Martin » Wed May 14, 2008 6:06 pm

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

Re: Move ordering: Delaying moves on the history phase.

Post by Martin » Wed May 14, 2008 6:25 pm

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

Only 15 minutes to correct?!

User avatar
michiguel
Posts: 6401
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: Move ordering: Delaying moves on the history phase.

Post by michiguel » Wed May 14, 2008 8:39 pm

Tord Romstad wrote:
michiguel wrote: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
Posts: 12000
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Move ordering: Delaying moves on the history phase.

Post by Dann Corbit » Thu May 15, 2008 12:08 am

michiguel wrote:
Tord Romstad wrote:
michiguel wrote: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.

User avatar
michiguel
Posts: 6401
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: Move ordering: Delaying moves on the history phase.

Post by michiguel » Thu May 15, 2008 3:28 am

Dann Corbit wrote:
michiguel wrote:
Tord Romstad wrote:
michiguel wrote: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

Re: Move ordering: Delaying moves on the history phase.

Post by pijl » Thu May 15, 2008 9:27 am

michiguel wrote: 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

Re: Move ordering: Delaying moves on the history phase.

Post by PK-4 » Thu May 15, 2008 5:18 pm

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

User avatar
michiguel
Posts: 6401
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: Move ordering: Delaying moves on the history phase.

Post by michiguel » Thu May 15, 2008 5:20 pm

michiguel wrote:
Dann Corbit wrote:
michiguel wrote:
Tord Romstad wrote:
michiguel wrote: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&#41; history NLQ 2&#41; losing capt. 2&#41; losing quiets 
B= 1&#41; losing capt. 2&#41; history NLQ 3&#41; losing quiets  
C= 1&#41; history for all of them combined
D= 1&#41; combined history of NLQ + losing capt 2&#41; losing quiets

         WAC            tree size 
     &#40;solve/300&#41;     &#40;quiet positions&#41;
                         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

Re: Move ordering: Delaying moves on the history phase.

Post by Harald Johnsen » Fri May 16, 2008 7:18 am

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.

Post Reply