MVV/LVA move ordering and qSearch

[Uri Blass]

SEE is not more accurate at all. If you havethe choice between QxQ with SEE=0 and PxN with SEE=+2, SEE does not see that QxQ will get you almost certainy +2, and PxN will get you -6 most of the time. I would not call that remotely accurate...

SEE only considers recaptures to the same square. So you get toasted, because the opponent retaliates against another square!

Completely irrelevant. QxQ may Get you that knight. Or it might not. Suppose the recapture is BxQ+. Now you get to move your king and not pick up the knight.

This is not about tree searching. As a general rule, and this is accurate in _most_ positions, I would prefer a +2 capture over a +0 capture according to SEE. Yes there are exceptions. But they are _exceptions_. Not the more common occurrence.

MVV/LVA is weaker than SEE for lots of reasons, if all you care about is choosing the most accurate capture. However, removing the queen first does shrink the resulting sub-tree, which is what this is all about. It is not about overloaded pieces, pinned pieces, trapped pieces, giving/not-giving check and such.

Of Course QxQ may not win the knight but the point of H.G.Muller is that in most cases it wins the knight(he used the words almost certainly).

If you want to check his claim than you need to look at qsearch positions
when QxQ with see=0 and PxN with see=2 are possible and calculate statistics about the percentage of cases when QxQ wins the knight and also calculate statistics about the number of cases when PxN wins the knight.

PxN often is refuted by QxQ of the opponent so my guess is that PxN wins the knight less often than QxQ but I admit that I did not calculate statistics about it.

Uri

[bob]

MVV/LVA is weaker than SEE for lots of reasons, if all you care about is choosing the most accurate capture. However, removing the queen first does shrink the resulting sub-tree, which is what this is all about. It is not about overloaded pieces, pinned pieces, trapped pieces, giving/not-giving check and such.

Hmmmm it seems a bit too simple. I know very well that MVV / LVA of non-negative SEE captures work the best in qsearch: Tord found this in Glaurung much before the people start to consider a proven fact (you were well among the latest as I have seen to happen often. I think it is because under the enourmous weight of your experience it takes some time for you to steer away from the known routes

Not exactly. First, when someone suggested this could be better, I decided to run the test, and discovered it was better. I had previously compared SEE vs MVV/LVA, and SEE was a clear winner. But used in combination, as is currently being discussed, things are better still.

Anyhow the explanation you gave is that because you have to reach a terminal position it is better to reduce the sub-tree early:

Somewhere in the path, you lose material. But alpha/beta is a depth-first search strategy, so you have to reach a terminal position, before you can get a score, so that you can see that the entire path is bad due to a poor move earlier. QxQ reduces the size of the resulting sub-tree more than PxN, and we want to search a complete sub-tree and get a score as quickly as possible.

This reasoning misses the important point that in qsearch you, at every node, try a "stand pat" evaluation and if it is above beta you return immediately WITHOUT to reach any terminal position.

Irrelevant. We are doing this _everywhere_. So in the normal search, reducing the size of the following sub-tree is important. In the q-search, I suspect this effect is less pronounced. I did not try SEE - MVV/LVA in normal search, and just SEE in the q-search. I could try that easily enough, and it may well be even better.

So under this point of view seems much easier to reach the stand pat score after the first capture of a PXN (where you go under of a knight value) then after a QXQ where you go under of a queen and you can practically forget the stand pat.

....there must be something more on why MVV/LVA on non-negative SEE captures works better then all the other known alternatives.

[bob]

Completely irrelevant. QxQ may Get you that knight. Or it might not. Suppose the recapture is BxQ+. Now you get to move your king and not pick up the knight.

Extremely unlikely. The probability that your own Q is hanging, or the opponent Q is attacking something else that is hanging is far larger. In the presence of QxQ, PXN is almost alays a very, very bad move.

You play a different game than I play. Given the choice of picking up a knight, or trading queens and then picking up the knight, my inclination is to pick up the knight. In fact, if something is undefended, my initial inclination is to take it, assuming intuition doesn't say "warning... trap possible."

In the tree, QxQ PxQ is far less likely to cause a cutoff than PxN which is an outright win of material, within the scope of either MVV/LVA or SEE.

[bob]

SEE is not more accurate at all. If you havethe choice between QxQ with SEE=0 and PxN with SEE=+2, SEE does not see that QxQ will get you almost certainy +2, and PxN will get you -6 most of the time. I would not call that remotely accurate...

SEE only considers recaptures to the same square. So you get toasted, because the opponent retaliates against another square!

Completely irrelevant. QxQ may Get you that knight. Or it might not. Suppose the recapture is BxQ+. Now you get to move your king and not pick up the knight.

This is not about tree searching. As a general rule, and this is accurate in _most_ positions, I would prefer a +2 capture over a +0 capture according to SEE. Yes there are exceptions. But they are _exceptions_. Not the more common occurrence.

MVV/LVA is weaker than SEE for lots of reasons, if all you care about is choosing the most accurate capture. However, removing the queen first does shrink the resulting sub-tree, which is what this is all about. It is not about overloaded pieces, pinned pieces, trapped pieces, giving/not-giving check and such.

Of Course QxQ may not win the knight but the point of H.G.Muller is that in most cases it wins the knight(he used the words almost certainly).

If you want to check his claim than you need to look at qsearch positions
when QxQ with see=0 and PxN with see=2 are possible and calculate statistics about the percentage of cases when QxQ wins the knight and also calculate statistics about the number of cases when PxN wins the knight.

PxN often is refuted by QxQ of the opponent so my guess is that PxN wins the knight less often than QxQ but I admit that I did not calculate statistics about it.

Uri

I suppose the only way to end the debate is to run the test. I think I will do this for the specific example above, where I can play PxN where SEE is +2 or +3, and QxQ where SEE is < 2 (no point in testing when SEE is > 3 as SEE would always search QxQ where Q is hanging before PxN where Knight is hanging.

I'll run this, probably on the cluster, and sum the results.

[bob]

OK. Took a bit of work, here is what I did.

In Quiesce() only (not in normal search) I generate all captures as always. Then as I MVV/LVA score the moves for sorting, I check for a QxQ move with swap < 200, and set a flag if found. I check for PxN and set a flag if found. If both are found, I increment a counter telling me how many times I encountered a position where both QxQ and PxN are possible.

I then do a normal q-search. If it fails high, I again check to see if we had both QxQ and PxN moves (QxQ will always be ordered first because of MVV/LVA). If both were possible, I do the following:

(1) if we fail high on PxN, then QxQ did not fail high. I increment the number of PxN fail highs.

(2) if we fail high on QxQ, I increment the number of QxQ fail highs, but I then do an additional search to see if PxN will also fail high. If so, I increment the number of PxN fail highs.

At the end of a game (these are games played at 30 moves per minute on my core-2 duo laptop, I print the number of times both were possible, and the number of times each failed high.

QxQ/PxN=16463 QxQ=7088 PxN=12305
QxQ/PxN=82848 QxQ=25217 PxN=43130

I can play more games, but it seems pretty clear. PxN fails high twice as often as QxQ in the qsearch when both are legal.

Now can we put this discussion to bed about QxQ being better than PxN when QxQ does not win significant material while PxN does? I'll be happy to run more games if needed. Note that there are other combinations that will make QxQ look even worse. NxR vs QxQ for example, or PxB vs QxQ. I only checked the one specific case referenced.

So, as I suspected, this is not about QxQ failing high more often than PxN, it really is about reducing the size of the subtree below that position...

Unless someone can come up with another possibility...

[bob]

OK. Took a bit of work, here is what I did.

In Quiesce() only (not in normal search) I generate all captures as always. Then as I MVV/LVA score the moves for sorting, I check for a QxQ move with swap < 200, and set a flag if found. I check for PxN and set a flag if found. If both are found, I increment a counter telling me how many times I encountered a position where both QxQ and PxN are possible.

I then do a normal q-search. If it fails high, I again check to see if we had both QxQ and PxN moves (QxQ will always be ordered first because of MVV/LVA). If both were possible, I do the following:

(1) if we fail high on PxN, then QxQ did not fail high. I increment the number of PxN fail highs.

(2) if we fail high on QxQ, I increment the number of QxQ fail highs, but I then do an additional search to see if PxN will also fail high. If so, I increment the number of PxN fail highs.

At the end of a game (these are games played at 30 moves per minute on my core-2 duo laptop, I print the number of times both were possible, and the number of times each failed high.

QxQ/PxN=16463 QxQ=7088 PxN=12305
QxQ/PxN=82848 QxQ=25217 PxN=43130

I can play more games, but it seems pretty clear. PxN fails high twice as often as QxQ in the qsearch when both are legal.

Now can we put this discussion to bed about QxQ being better than PxN when QxQ does not win significant material while PxN does? I'll be happy to run more games if needed. Note that there are other combinations that will make QxQ look even worse. NxR vs QxQ for example, or PxB vs QxQ. I only checked the one specific case referenced.

So, as I suspected, this is not about QxQ failing high more often than PxN, it really is about reducing the size of the subtree below that position...

Unless someone can come up with another possibility...

Should have explained the above data.

The first line comes from game one. The first number is the number of times it reached a qsearch position where QxQ and PxN were both possible, and where QxQ would not win significant material (this is more a question about MVV/LVA vs SEE, and SEE would spot QxQ instantly if it wins material. MVV/LVA will try QxQ first even if it is an even exchange, before it would try PxN which obviously wins material). The second number is the number of times QxQ failed high, the third is the number of times PxN failed high. In some positions neither fail high. In some both would fail high. And in some, only one fails high. I didn't try to break that down, but could.

Clearly, from a "which is better objectively in terms of producing a cutoff?" perspective, PxN is the clear winner. Yet QxQ makes for a smaller overall tree since the queens come off quicker.

[JVMerlino]

Which seems like a paradox -- a very good way to make your engine noticeably stronger is to spend more than half of its time looking at stupid moves.

I would say that QS is about the only place where the moves are not stupid. Because the winning side (i.e. the side that will secure the fail high) at least makes an effort to play the best moves. In full-width search he hardly ever does, he is just null-moving as much as possible. And the losing side refrains from futile captures in QS, and thus will also try only moves that at least bring him ahead, even though that might not last.

It is most initial positions of QS that are stupid, but as you play out the captures they quickly clear up by removing all of the hanging material.

I agree, and I probably should have clarified my statement. As you said, most initial positions that get sent to a QS are stupid, but an engine spends a great deal of time resolving these stupid positions -- stupid in, stupid out.

And if I ever get around to implementing SEE, then hopefully my engine will be less stupid.

jm

[bob]

hmmm...

went to a lot of trouble to run these tests. No one has a comment after seeing real data as opposed to conjectured possibilities??? Clearly PxN is better than QxQ with regard to producing a cutoff, as I had suspected. The QxQ advantage is somewhere else, _not_ in its superiority to PxN based on expected material gain.

All that is left is the original idea from the discussion when I converted to this ordering after others had reported it was better, namely that it reduces the size of the sub-tree below the capture since the Q gets removed.

[Uri Blass]

hmmm...

went to a lot of trouble to run these tests. No one has a comment after seeing real data as opposed to conjectured possibilities??? Clearly PxN is better than QxQ with regard to producing a cutoff, as I had suspected. The QxQ advantage is somewhere else, _not_ in its superiority to PxN based on expected material gain.

All that is left is the original idea from the discussion when I converted to this ordering after others had reported it was better, namely that it reduces the size of the sub-tree below the capture since the Q gets removed.

I can only say that the results that you give are counter intuitive and
it may be interesting to get some epd file of random 100 positions when both PXN and QxQ are possible in the qsearch to see what happens and why do you get that there are more fail high for PxN.

I expected that you should get often cases when QxQ is better
because PxN is simply refuted by QxQ of the opponent like the following diagram.

[d]8/4k3/3q4/7n/6P1/3Q4/8/6K1 w - - 0 1

[bob]

hmmm...

went to a lot of trouble to run these tests. No one has a comment after seeing real data as opposed to conjectured possibilities??? Clearly PxN is better than QxQ with regard to producing a cutoff, as I had suspected. The QxQ advantage is somewhere else, _not_ in its superiority to PxN based on expected material gain.

All that is left is the original idea from the discussion when I converted to this ordering after others had reported it was better, namely that it reduces the size of the sub-tree below the capture since the Q gets removed.

I can only say that the results that you give are counter intuitive and
it may be interesting to get some epd file of random 100 positions when both PXN and QxQ are possible in the qsearch to see what happens and why do you get that there are more fail high for PxN.

Why is it "counter-intuitive" that PxN, which wins a piece for a pawn if not a piece outright, is better than QxQ which is an even trade (although obviously it might win more.) It seems completely logical to me that a move that wins material has a greater probability of failing high than a move that appears to be an even trade. What am I missing that you are thinking about?

I expected that you should get often cases when QxQ is better
because PxN is simply refuted by QxQ of the opponent like the following diagram.

[d]8/4k3/3q4/7n/6P1/3Q4/8/6K1 w - - 0 1

That makes no sense to me. It is my move, and I can play PxN. What was my opponent's last move? Only possible choice is a queen move that attacks my queen. Otherwise I could have taken his queen already. What do you suppose the probability of a hanging queen is as opposed to a defended queen?

I did some further measurements, but only a quick one-game test to see what the probability is that a QxQ wins the queen outright, as opposed to just being a trade. The only time that QxQ becomes a frequent winner is in endgames after a pawn promotion. Otherwise the queen rips get played in the normal search before the q-search is reached. It takes very unusual conditions in the q-search to expose an attack on an undefended queen, so that the opponent would not want to play PxN but would prefer to play QxQ to save his queen instead.

Remember that the q-search doesn't try non-captures for most people, which would seem to make this scenario pretty rare. The first game I gave data for above was 150+ moves long. At about 2 seconds per move average. Yet there were only about 16,000 cases where both moves could be played in the same position. And by a 2:1 majority PxN would fail high more times than QxQ.