MVV/LVA move ordering and qSearch

[JVMerlino]

QS is all about deciding most efficiently who was most stupid in positions that are completely stupid and have nothing to do with Chess as we know it.

Brilliant!

And chess engines spend most of their time doing this, which also seems stupid, does it not?

But we've all seen programmers with new engines ask why their engines are playing silly moves in some cases, and it's because their engines don't have any qsearch.

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.

jm

[bob]

Most people sort on something like 16xVictim-Attacker, so that it is a single-key sort anyway.

The point is that when you can do both QxQ and PxN, in most cases QxQ will be the best move, and most easily proven to be the best move (i.e. with the lowest number of QS nodes). Because after your QxQ, if you are not done already because his Q was undefended, he must recapture (the only non-futile move), and you play PxN anyway. But if you play PxN, now he will _always_ reply with QxQ. Sometimes this then is even winning for him (i.e. the PxN fails low), when it was your Q that was undefended. And otherwise you now have to recapture the Q.

So by playing PxN first you exclude the possibility to profit in the case his Q was undefended, and you take the risk to fail low on it when your Q was undefended. Only in the case that both were defended you break even.

I don't think it is a matter of the Q being undefended. SEE finds that perfectly, yet SEE ordering is not as good. The only possible explanation is that QxQ simply reduces the size of the resulting sub-tree significantly more than PxN, even though PxN generally wins more material

[bob]

So by playing PxN first you exclude the possibility to profit in the case his Q was undefended, and you take the risk to fail low on it when your Q was undefended. Only in the case that both were defended you break even.

This I don't follow. QxQ will still be avaluated, therefore if it is a better move it will get played, no? Isn't "what if the Q is undefended somewhat of a ... specious?... argument, in the sense that anyone who is strong enough to appreciate a well written chess engine is probably not going to hang their queen anyway. In other words, I can't see a whole lot of value in coding to benefit from the possibility of the opponent hanging his/her queen. Unless I am missing the point?

We are talking about QSearch, here, hence it doesn't matter how skilled your opponent is: at the height of QS, you of course have to try all possible good captures at each position, unless a stand pat or fail high occurs: what I believe HGM is saying is that if (amongst the zillions of crazy positions a qsearch algorithm analyses) the position currently evaluated has a Q hanging for the side not on move, then QxQ is a killer, whilst if the Q is not hanging, you would evaluate PxN after QxQ: but if in the latter case (Q not hanging) you try PxN first, then the issue is whether _your_ Q is hanging, etc. Thence the gain in node count. If I got this right

Cheers, mr

This isn't quite right. I used to use SEE to order these captures, and SEE is far more accurate than MVV/LVA. So this is more about reducing the size of the sub-tree, than about accuracy. Most likely here's the reason:

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.

Otherwise, I don't see any rational explanation for why MVV/LVA order is better. Yet we know that it is.

[hgm]

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!

[hgm]

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.

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

[wgarvin]

Anyways, the point is that my idea would involve only a single key sort, which presents certain logistical advantages.

I don't see any advantage there. You're talking about the performance difference between sorting by (A - B) and sorting by ((A << 6) + B). You're talking about one extra instruction per move, which is probably insignificant compared to the cost of actually sorting (even partial selection sort ala crafty).

[Fguy64]

Anyways, the point is that my idea would involve only a single key sort, which presents certain logistical advantages.

I don't see any advantage there. You're talking about the performance difference between sorting by (A - B) and sorting by ((A << 6) + B). You're talking about one extra instruction per move, which is probably insignificant compared to the cost of actually sorting (even partial selection sort ala crafty).

OK, I see your point. I'm just musing on various ideas here. Also I am working in java.

I'll just elaborate on what I meant by "logistical advantage", based on my currently not so optimal board & move representation.

my board is just a 64 element array of integers. (32-bit).

A candidate move in search is currently represented by minimum three integers, from square, to square, and promotion piece. All of these integers are 127 or less. then there are additional temporary integers to represent sort keys. If I could represent my sort key in a single byte, I could fold the entire move into 32-bits, with all the advantages that that might entail. One idea I had was some kind of an ascending "pre-sort" on my piece list before generating the candidate moves for each piece.

I can also visualize certain advantages to my approach when in comes to retrieving the principal variation when I implement iterative deepening. I don't yet have hash tables, that is down the road a bit.

Anyways, it would not surprise me to learn I'm barking up the wrong tree. I like to try things, and rely on proper research when I run out of ideas.

[mcostalba]

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

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.

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.

[hgm]

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.