Typo: Also, in many positions THERE are a lot of such captures.
Only 15 minutes to correct?!
Move ordering: Delaying moves on the history phase.
Moderators: hgm, Rebel, chrisw
-
- Posts: 6401
- Joined: Thu Mar 09, 2006 8:30 pm
- Location: Chicago, Illinois, USA
Re: Move ordering: Delaying moves on the history phase.
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.Tord Romstad wrote:Yes, I have tried this. Currently, my move ordering is roughly as follows: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?I have several times tried replacing it with the following scheme, which is similar to what you suggest:
- Hash mvoe
- Winning and equal captures and promotions, ordered by MVV/LVA.
- Killers
- Remaining quiet moves, ordered by history counters
- Losing captures
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.
- Hash move
- Winning and equal captures and promotions, ordered by MVV/LVA.
- Killers
- Quiet moves with SEE value 0, ordered by history counters
- All moves with negative SEE value
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.I am going to implement this but I am sure this must have been tried.
Tord
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
-
- Posts: 12541
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Move ordering: Delaying moves on the history phase.
I would be interested to see what happens if you try your exact same ordering methods against a simple tactical test like WAC.michiguel wrote: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.Tord Romstad wrote:Yes, I have tried this. Currently, my move ordering is roughly as follows: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?I have several times tried replacing it with the following scheme, which is similar to what you suggest:
- Hash mvoe
- Winning and equal captures and promotions, ordered by MVV/LVA.
- Killers
- Remaining quiet moves, ordered by history counters
- Losing captures
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.
- Hash move
- Winning and equal captures and promotions, ordered by MVV/LVA.
- Killers
- Quiet moves with SEE value 0, ordered by history counters
- All moves with negative SEE value
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.I am going to implement this but I am sure this must have been tried.
Tord
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
-
- Posts: 6401
- Joined: Thu Mar 09, 2006 8:30 pm
- Location: Chicago, Illinois, USA
Re: Move ordering: Delaying moves on the history phase.
That's a good question and I will test it.Dann Corbit wrote:I would be interested to see what happens if you try your exact same ordering methods against a simple tactical test like WAC.michiguel wrote: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.Tord Romstad wrote:Yes, I have tried this. Currently, my move ordering is roughly as follows: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?I have several times tried replacing it with the following scheme, which is similar to what you suggest:
- Hash mvoe
- Winning and equal captures and promotions, ordered by MVV/LVA.
- Killers
- Remaining quiet moves, ordered by history counters
- Losing captures
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.
- Hash move
- Winning and equal captures and promotions, ordered by MVV/LVA.
- Killers
- Quiet moves with SEE value 0, ordered by history counters
- All moves with negative SEE value
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.I am going to implement this but I am sure this must have been tried.
Tord
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
Miguel
Re: Move ordering: Delaying moves on the history phase.
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).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.
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.
Re: Move ordering: Delaying moves on the history phase.
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: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.
- 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
-
- Posts: 6401
- Joined: Thu Mar 09, 2006 8:30 pm
- Location: Chicago, Illinois, USA
Re: Move ordering: Delaying moves on the history phase.
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 Ghzmichiguel wrote:That's a good question and I will test it.Dann Corbit wrote:I would be interested to see what happens if you try your exact same ordering methods against a simple tactical test like WAC.michiguel wrote: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.Tord Romstad wrote:Yes, I have tried this. Currently, my move ordering is roughly as follows: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?I have several times tried replacing it with the following scheme, which is similar to what you suggest:
- Hash mvoe
- Winning and equal captures and promotions, ordered by MVV/LVA.
- Killers
- Remaining quiet moves, ordered by history counters
- Losing captures
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.
- Hash move
- Winning and equal captures and promotions, ordered by MVV/LVA.
- Killers
- Quiet moves with SEE value 0, ordered by history counters
- All moves with negative SEE value
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.I am going to implement this but I am sure this must have been tried.
Tord
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
Miguel
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
I believe there are better ways to test this, but this is a quick one.
Miguel
Re: Move ordering: Delaying moves on the history phase.
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.
I don't think that all the mate in n positions of wac are interesting for move ordering.
HJ.
-
- Posts: 6401
- Joined: Thu Mar 09, 2006 8:30 pm
- Location: Chicago, Illinois, USA
Re: Move ordering: Delaying moves on the history phase.
That is why I did it with the ~130 positions of the "silent but deadly" suite provided by Dann Corbit. It is the column on the right. I will later repeat the whole thing at higher depth with more combinations and I can include the test you suggest.Harald Johnsen wrote: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.
I am interested to know if there is a difference between middlegames and endgames. First, I have to include promotions etc. I will report what I find.
Miguel
-
- Posts: 3196
- Joined: Fri May 26, 2006 3:00 am
- Location: WY, USA
- Full name: Michael Sherwin
Re: Move ordering: Delaying moves on the history phase.
Hi Miguel,michiguel wrote: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.Tord Romstad wrote:Yes, I have tried this. Currently, my move ordering is roughly as follows: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?I have several times tried replacing it with the following scheme, which is similar to what you suggest:
- Hash mvoe
- Winning and equal captures and promotions, ordered by MVV/LVA.
- Killers
- Remaining quiet moves, ordered by history counters
- Losing captures
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.
- Hash move
- Winning and equal captures and promotions, ordered by MVV/LVA.
- Killers
- Quiet moves with SEE value 0, ordered by history counters
- All moves with negative SEE value
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.I am going to implement this but I am sure this must have been tried.
Tord
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
In RomiChess when the remaining depth is > 3 all moves after the killers are searched to a shallow depth with node->score = -Search(-beta - 100, -alpha + 100, ... to get a score for each and every move. Or what works almost as well is to just call qsearch with an opened window for each remaining move.
Sofar this has only worked for me and may just be a waste of time. However...
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through