MVV/LVA move ordering and qSearch

[yoshiharu]

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

[hgm]

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

Indeed, you are missing the point completely. As Mauro also already implied, this is not the way alpha-beta search works.

Any sub-tree sprouting from the PV will fail low for the side that deviates, and will thus have the form of a refutation tree: the side failing low will despartely try _everything_ until he finds a move that saves the day. Which will not happen, so that everything really means everything until he is out of legal moves. No matter how stupid the moves, he will try them. That includes hanging pieces. In fact so often that it is not far beside the truth to state that hanging pieces is the favorite passtime of any Chess engine.

Now the other side, which will get the fail high, will try to refute the usually pathetic and often ridicuous attempts of his opponent with as little effort as possible. This means he tries to play either his best move, to squash the opposition once and for all, or don't play anything at all (i.e. null move), to profit from the depth reduction that allows him. So most of the time, when the opponent hangs pieces, the side failing high will not even bother to capture them, if the opponent did already do something before that was bad enough (e.g. a positionally poor move, out of the center) to cause a cutoff anyway. He just postpones gobbling up all the material he is offered untill QS, hoping that he will not even have to do it then, because stand-pat in itself will be enough to fail high. Just sit and wait while the opponent is wrecking his own position, so you can declare an easy victory at d=0.

So 99% of the positions you encounter in QS have multiple hanging pieces for both sides, because no matter how logical the root position was, by the time you reach QS you will be watching a game of a random-mover against a null-mover. The random mover hangs pieces because he doesn't know any better, and the null-mover hangs pieces because the random mover by sheer accident sometimes attacks pieces, which the null-mover is too lazy to save. And often quite justified, as he has already plenty of hostages that he can retliate against. who cares if a Pawn moves to attack my knight, when I already hold a Queen for ransom? And most of the time the random mover will not even capture what he attacks, but just play another random move.

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.

[Fguy64]

ok, thanks for the detailed write up. I will take some time to absorb this, and then if I still have a question I'll let you know.

[mcostalba]

ok, thanks for the detailed write up. I will take some time to absorb this, and then if I still have a question I'll let you know.

For me it was useful to print the bitboard of each position at the beginning of qsearch, so that after some hundreds positions you see on your screen you get the idea of what your are handling with.

BTW regrading sorting, yes, I meant that.

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