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
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
-
- Posts: 1808
- Joined: Wed Mar 08, 2006 9:19 pm
- Location: Oslo, Norway
Re: Move ordering: Delaying moves on the history phase.
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?
- Hash mvoe
- Winning and equal captures and promotions, ordered by MVV/LVA.
- Killers
- Remaining quiet moves, ordered by history counters
- Losing captures
- 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
-
- Posts: 12541
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Move ordering: Delaying moves on the history phase.
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).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
If you did that, then I cannot imagine how it could perform worse.
-
- Posts: 1922
- Joined: Thu Mar 09, 2006 12:51 am
- Location: Earth
Re: Move ordering: Delaying moves on the history phase.
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).Tord Romstad wrote: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'll have to do some big move ordering tests. Unfortunately, there are about a million things that come before that on my todo-list...
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Move ordering: Delaying moves on the history phase.
Yes it is quite normal to do that... And it has been done since the 1970's in fact...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 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
Re: Move ordering: Delaying moves on the history phase.
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.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 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 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.
-
- Posts: 620
- Joined: Fri Feb 08, 2008 10:44 am
- Location: Madrid - Spain
Re: Move ordering: Delaying moves on the history phase.
Again here is the novice doing questions: ..... why could not a capture be a killer?michiguel wrote:After killers, when you try moves that are not captures.....
-
- Posts: 27809
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Move ordering: Delaying moves on the history phase.
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.
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.
-
- Posts: 388
- Joined: Wed Mar 08, 2006 10:08 pm
Re: Move ordering: Delaying moves on the history phase.
I have it a little more simpler than that. All negative SEE moves are picked last, and they are sorted by their SEE scores.hgm wrote: order negative-SEE non-captures with Pawns before the bad captures, and other negative-SEE moves behind the bad captures.
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).
Re: Move ordering: Delaying moves on the history phase.
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.
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.