Ordering Capture Moves

[jfern2011]

Hello,

My chess engine tends to visit fewer nodes when I search captures before all other moves, and even fewer when I sort the captures (not surprisingly). However, if I defer searching losing captures (based on MVV/LVA and SEE) until after non-captures are searched, the engine visits many more nodes per ply. Does this make sense? Should I always search all captures before non-captures?

Thanks,
Jason

[cdani]

My chess engine tends to visit fewer nodes when I search captures before all other moves, and even fewer when I sort the captures (not surprisingly). However, if I defer searching losing captures (based on MVV/LVA and SEE) until after non-captures are searched, the engine visits many more nodes per ply. Does this make sense? Should I always search all captures before non-captures?

The tendency is that an engine is stronger if it searches bad captures or bad quiets (SEE) after good quiets. I suppose that this will happen also on your engine. So better just test it.

[Sven]

However, if I defer searching losing captures (based on MVV/LVA and SEE) until after non-captures are searched, the engine visits many more nodes per ply. Does this make sense?

I don't think it makes sense. How do you decide whether a capture is losing? You only wrote "based on MVV/LVA and SEE" which is not precisely what I expected. Often this decision is based on SEE only (or a similar calculation) while the score taken for ordering of non-losing captures is MVV/LVA.

[hgm]

Now that we are talking about ordering of captures: How much sense would it make to try to learn from what happened in a sibbling node, rather than rigidly adhering to the static MVV/LVA + SEE ordering? Just as you use killers to get the best non-captures in front.

Usually the hash move does the job. But sometimes beta has been raised since the previous visit, and the the hash move no longer works. Then you have to search through the captures again. And in the root of QS you rarely have a hash hit. Now many (perhaps most) non-captures in the parent are useless moves, which do not essentially alter the situation (like shuffling Rooks on the back rank, moving the King inside its fortress, etc.), and they should all have the same refutation. And if that is not the first move of the static ordering (e.g. because that is BxR, and the B happened to be soft-pinned on the Queen, or it can be recaptured with a Knight that forks K and Q), it is very likely that this would not work in most sibblings. So why keep trying it first, when a later NxP did work, and likely works almost everywhere?

Similarly, when a bunch of non-captures in an all-node were all refuted by the same hash move, but in the new iteration beta has been raised so that this hash move fails low in one of them... It will likely fail low in all of the children that used it. If this happens at large requested depth, turning the fail-high tree into a fail-low tree is quite expensive, and totally wasted effort, as you would now have to search an alternative. If the first child you searched did find such an alternative that is good enough to beat the raised beta, it seems much more sensible to immediately search that in other non-capture children that used the same hash move.

So it seems useful to communicate to sibblings whether a hash move failed low, and what it was, and what new cut-move was found. Perhaps a list of 'anti-killer captures', which were tried without success, and could get a penalty on their sort key for that. This would not affect any captures that are new in the current node, e.g. due to the moved piece being capturable in its new location, or a soft-pinned piece being moved to expose a fat target behind it. One could even make the information transferred between sibblings quite detailed, like accompanying every capture that did not cut by the move that refuted it, so that it can be tested whether this move would still be possible. E.g. if the BxR in a sibbling failed because of an RxQ reply over the evacuated B square, the BxR would not be tainted in the current node if the move leading to it moved the Rook off the ray. So when a capture comes up, you can check if it was in the sibbling's 'black list', and if the listed refutation would still be pseudo-legal after the move, postpone its search by lowering its sort key, and extract a new capture. (Note that this can perhaps even make SEE largely redundant, as captures with SEE < 0 (or actually better, with QS < 0) will be put on the black list by the first node that tries them, so they can be postponed compared to strict MVV/LVA, the listed refutation showing that the target was protected, (or a more important counter-threat existed), and from where and by what, so that we ca cheaply test whether this protection is still present, and whether it guarantees that SEE < 0 (e.g. RxB protected by P).

BTW, the similarity of the position after most late moves is probably the reason why it works so well to keep increasing the reduction as you search more moves, even if the moves are basically in random order. There are just a few ways needed to refute these moves, like two or three; if what refutes one doesn't refute some other, because it accidentally interfered with the refutation method for the first move, you just use the alternative method of refutation for it. As the number of searched moves in the all-node increases, it becomes increasingly likely that you have encountered enough different refutations to handle anything that is yet to follow, and therefore don't have to search those very seriously.

Note that my thiking might be colored a bit by the fact that I am currently dealing with a variant where having 50 captures per node, and some 250 moves in total, is quite typical. So having an efficient way to find a cut-move capture is potentially very rewarding.

[cetormenter]

Now that we are talking about ordering of captures: How much sense would it make to try to learn from what happened in a sibbling node, rather than rigidly adhering to the static MVV/LVA + SEE ordering? Just as you use killers to get the best non-captures in front.

Usually the hash move does the job. But sometimes beta has been raised since the previous visit, and the the hash move no longer works. Then you have to search through the captures again. And in the root of QS you rarely have a hash hit. Now many (perhaps most) non-captures in the parent are useless moves, which do not essentially alter the situation (like shuffling Rooks on the back rank, moving the King inside its fortress, etc.), and they should all have the same refutation. And if that is not the first move of the static ordering (e.g. because that is BxR, and the B happened to be soft-pinned on the Queen, or it can be recaptured with a Knight that forks K and Q), it is very likely that this would not work in most sibblings. So why keep trying it first, when a later NxP did work, and likely works almost everywhere?

Similarly, when a bunch of non-captures in an all-node were all refuted by the same hash move, but in the new iteration beta has been raised so that this hash move fails low in one of them... It will likely fail low in all of the children that used it. If this happens at large requested depth, turning the fail-high tree into a fail-low tree is quite expensive, and totally wasted effort, as you would now have to search an alternative. If the first child you searched did find such an alternative that is good enough to beat the raised beta, it seems much more sensible to immediately search that in other non-capture children that used the same hash move.

So it seems useful to communicate to sibblings whether a hash move failed low, and what it was, and what new cut-move was found. Perhaps a list of 'anti-killer captures', which were tried without success, and could get a penalty on their sort key for that. This would not affect any captures that are new in the current node, e.g. due to the moved piece being capturable in its new location, or a soft-pinned piece being moved to expose a fat target behind it. One could even make the information transferred between sibblings quite detailed, like accompanying every capture that did not cut by the move that refuted it, so that it can be tested whether this move would still be possible. E.g. if the BxR in a sibbling failed because of an RxQ reply over the evacuated B square, the BxR would not be tainted in the current node if the move leading to it moved the Rook off the ray. So when a capture comes up, you can check if it was in the sibbling's 'black list', and if the listed refutation would still be pseudo-legal after the move, postpone its search by lowering its sort key, and extract a new capture. (Note that this can perhaps even make SEE largely redundant, as captures with SEE < 0 (or actually better, with QS < 0) will be put on the black list by the first node that tries them, so they can be postponed compared to strict MVV/LVA, the listed refutation showing that the target was protected, (or a more important counter-threat existed), and from where and by what, so that we ca cheaply test whether this protection is still present, and whether it guarantees that SEE < 0 (e.g. RxB protected by P).

BTW, the similarity of the position after most late moves is probably the reason why it works so well to keep increasing the reduction as you search more moves, even if the moves are basically in random order. There are just a few ways needed to refute these moves, like two or three; if what refutes one doesn't refute some other, because it accidentally interfered with the refutation method for the first move, you just use the alternative method of refutation for it. As the number of searched moves in the all-node increases, it becomes increasingly likely that you have encountered enough different refutations to handle anything that is yet to follow, and therefore don't have to search those very seriously.

Note that my thiking might be colored a bit by the fact that I am currently dealing with a variant where having 50 captures per node, and some 250 moves in total, is quite typical. So having an efficient way to find a cut-move capture is potentially very rewarding.

I will try something out like this in Nirvana and test it out tonight. Unfortunately, I think that the situations in which that this technique would help are a little bit too rare so it may turn out to be just a wash.

I will report back after this test is done so in approximately 8 hours or so.

[jfern2011]

I'd certainly be interested to see what you come up with (even if it ends up taking more than 8 hours). Exchanging information between nodes like the way H.G. described isn't something I've thought of before so I'll definitely add that to my list of things to try out.

[cetormenter]

I'd certainly be interested to see what you come up with (even if it ends up taking more than 8 hours). Exchanging information between nodes like the way H.G. described isn't something I've thought of before so I'll definitely add that to my list of things to try out.

Just as I had predicted the idea was a wash. However I will keep trying variations on this idea. I feel I was too restrictive this time around.