Move ordering: Delaying moves on the history phase.

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

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

Move ordering: Delaying moves on the history phase.

Post by michiguel » Tue May 13, 2008 9:51 pm

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
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

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

Post by Tord Romstad » Tue May 13, 2008 10:14 pm

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

Dann Corbit
Posts: 8600
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 » Tue May 13, 2008 11:53 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
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.

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

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

Post by Zach Wegner » Wed May 14, 2008 12:12 am

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.
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
Posts: 20340
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

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

Post by bob » Wed May 14, 2008 1:06 am

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
Yes it is quite normal to do that... And it has been done since the 1970's in fact...

Harald Johnsen

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

Post by Harald Johnsen » Wed May 14, 2008 7:35 am

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

User avatar
Kempelen
Posts: 619
Joined: Fri Feb 08, 2008 9:44 am
Location: Madrid - Spain
Contact:

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

Post by Kempelen » Wed May 14, 2008 8:12 am

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

User avatar
hgm
Posts: 22210
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Contact:

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

Post by hgm » Wed May 14, 2008 9:24 am

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

Post Reply