MVV/LVA move ordering and qSearch

[Fguy64]

OK, if your Qsearch is just a straight-up capture search, then MVV/LVA is touted as a means to prevent "explosions. Now MVV/LVA is a 2-key sort first a descending sort on the value of the victim, then an ascending sort on the value of the attacker.

Is there any reason why we can't just sort on the value of the difference between the attacker an the defender. In this second case, PxN would be ordered before QxQ, whereas this would not happen with MVV/LVA.

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

Now, when it comes to alpha/beta search, explosions aren't an issue, and we are free to play a bit with move ordering. Not so with Qsearch is my impression.

[bob]

OK, if your Qsearch is just a straight-up capture search, then MVV/LVA is touted as a means to prevent "explosions. Now MVV/LVA is a 2-key sort first a descending sort on the value of the victim, then an ascending sort on the value of the attacker.

Is there any reason why we can't just sort on the value of the difference between the attacker an the defender. In this second case, PxN would be ordered before QxQ, whereas this would not happen with MVV/LVA.

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

Now, when it comes to alpha/beta search, explosions aren't an issue, and we are free to play a bit with move ordering. Not so with Qsearch is my impression.

You can be even more accurate by sorting on SEE scores. But as testing has shown, removing the most valuable victim first does reduce the tree size. Which means MVV/LVA is the best ordering scheme. At the point in your q-search where you actually are about to play that MVV/LVA-ordered capture, you can use SEE and ignore the move if SEE says this loses material (I do this in Crafty anytime I do captures, which means in the regular search as well as in the q-search. In the regular search, I order by MVV/LVA but avoid searching the capture if SEE < 0. I don't throw it out in the regular search, but I do defer it until the "rest of the moves" stage of the search. In the q-search, I just throw it out if SEE < 0

[Fguy64]

OK, if your Qsearch is just a straight-up capture search, then MVV/LVA is touted as a means to prevent "explosions. Now MVV/LVA is a 2-key sort first a descending sort on the value of the victim, then an ascending sort on the value of the attacker.

Is there any reason why we can't just sort on the value of the difference between the attacker an the defender. In this second case, PxN would be ordered before QxQ, whereas this would not happen with MVV/LVA.

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

Now, when it comes to alpha/beta search, explosions aren't an issue, and we are free to play a bit with move ordering. Not so with Qsearch is my impression.

You can be even more accurate by sorting on SEE scores. But as testing has shown, removing the most valuable victim first does reduce the tree size. Which means MVV/LVA is the best ordering scheme. At the point in your q-search where you actually are about to play that MVV/LVA-ordered capture, you can use SEE and ignore the move if SEE says this loses material (I do this in Crafty anytime I do captures, which means in the regular search as well as in the q-search. In the regular search, I order by MVV/LVA but avoid searching the capture if SEE < 0. I don't throw it out in the regular search, but I do defer it until the "rest of the moves" stage of the search. In the q-search, I just throw it out if SEE < 0

ok, noted. hmmm I find myself wondering how much of this reduction in tree size is a statistical thing with regards to pruning and removing the piece with the highest material value, or does it also have to do with mobility, whereby removing a mobile piece like a Queen has the biggest impact on the number of possible replies.

[hgm]

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.

[mcostalba]

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

You just need one sort only also for order in MVV/LVA of course.

[Fguy64]

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

OK I can more or less see that results in the same ordering. Marco, is that the sort of thing you refer to?

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

I can see about the fewer nodes.
[/quote]
....

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?

regards.

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