Some thoughts on QS

[hgm]

I am still looking for a pruning method in QS that is more effective in preventing search explosion through plunder raids of powerful pieces. One way to achieve this could be more aggressive pruning of captures that seem bad. Normally this is done only for captures that seem bad by SEE, i.e. through recapture on the same square. But this does not help against plunder raids, where two powerful pieces clean out the board, never exposing themselves to recapture in the process.

The idea is that a capture is bad if after making it, the opponent captures something even bigger, so that in two ply you achieved nothing other than lowering the current eval. But this is a bit too simple, because even with SEE the two ply do have a side effect, namely that you lured another, potentially more valuable piece to the capture square. (I don't want to consider side effects like discovered threats; these are too rare to make that pay off.)

If you capture Qx(protected R) it seems a bad idea, because after recapture you are down Q vs R. It could still end well if the recapturer is Q, and you had a second attacker (say K) on the square, which now does KxQ. SEE would catch that. But now consider the case where there is a pre-existing attack on your Q, and you can play NxR. The NxR looks good SEE-wise, because he can only recapture the less valuable N. But of course the situation is just as bad as wit Qx(protected R), because he will not recapture N, but Q. The pre-existing attack on your Q counts as pre-emptive protection of everything, as it were.

But again, there is the exception that the attack on your Q is with Q, and your Q was protected, so that the initial Rook capture is merely followed by a Queen trade. So perhaps we should only consider threats that are Low x High captures, or captures of unprotected pieces. (Or, in a more refined treatment, have SEE > 0.) In the face of a Qx(unprotected Q) threat it certainly seems unwise to capture a Rook. Even if it is PxR. This can help stopping unpromising plunder raids at an earlier stage; e.g. if I can do Qx(unprotected B) in the face of an existing threat Qx(unprotected R), it doesn't really further my cause to play QxB, despite its SEE of +3. The situation is in a sense similar as for an (unsupported R)x(protected B) capture, which has SEE = -2. So with the threatening loss of -5, it seems wise to prune anything that does not at least capture +5, even if it has SEE > 0.

This is not the whole story, though. There is an essential difference between retaliation on the same square and that on a different square: the initial capturer survives, and any new attacks it might have from the new location remain in existence after the retaliation. With exchange on the same square no new moves are created (ignoring discovered threats). If after PxR our P would check his K, we would not be put off by a threat against our unprotected Q. So in deciding whether a SEE>0 capture should be pruned because of a pre-existing counter threat, it should be taken into account not only what we capture, but also whether what we attack with that capture neutralizes the counter threat. E.g. if we have a hanging R, subject to PxR, but we can play Nx(unprotected B), where the N then attacks a Q, that latter attack serves as a pre-emptive defense of our R. Even if the Q is protected we stand to gain Q-N = +6 from that attack, outweighing the -5 loss of the Rook, with a B already in the pocket. So the capture is promising, and should not be pruned.

In summary:
* 'obvious threats' against us are attacks against unprotected pieces.
* The 'value' of such threats is defined as the value of the hanging piece.
* Captures of pieces worth less than the value of the worst threat against us are candidates for pruning, even if they have SEE>0.
* If such candidates create a new attack on an unprotected piece for us that is at least equal in value to our threatened piece, we must not prune.
* In addition, captures with our most-threatened piece must be searched even if they have SEE<0 when we have an attack against an unprotected more (or equally) valuable piece.

The latter because they create a situation in the daughter node where he now faces a threat of a hanging valuable piece against him, and will thus prune the recapture of our suicide attack, so that the SEE is not relevant. In fact we should even try it when the values are equal: although he now will not prune the recapture, we will cash our threat when he makes it, and it will be a mere trade (after we grabbed something with the initial capture). So the trade is material for tempo, which is not obviously bad, and thus does not deserve to be pruned.

[ZirconiumX]

Stupid thought by an idiot: prune if SEE < alpha. Even if we are not better positionally, we will probably be able to make up with material.

End of stupid thought.

Matthew:out

[bob]

Stupid thought by an idiot: prune if SEE < alpha. Even if we are not better positionally, we will probably be able to make up with material.

End of stupid thought.

Matthew:out

There are much better ways that if SEE < alpha. For example, winning a pawn is not a good capture if you are a rook down. What HG is talking is the case where opposing queens get into the opponent's side of the board and eat pieces left and right, all futile... Rather than eating, one side would actually choose to stop the other from raiding its pieces, but q-search doesn't understand that. I've seen huge qsearch spaces caused by this...

[Don]

Stupid thought by an idiot: prune if SEE < alpha. Even if we are not better positionally, we will probably be able to make up with material.

End of stupid thought.

Matthew:out

There are much better ways that if SEE < alpha. For example, winning a pawn is not a good capture if you are a rook down. What HG is talking is the case where opposing queens get into the opponent's side of the board and eat pieces left and right, all futile... Rather than eating, one side would actually choose to stop the other from raiding its pieces, but q-search doesn't understand that. I've seen huge qsearch spaces caused by this...

Perhaps a stupid idea, but what if we simply limited the number of non-recapturing consecutive captures by queens or perhaps anything? It's almost always the case that after any extended number of non-recapturing captures one of the sides blundered and should have played differently.

There is almost no strength loss if you put fairly severe limits on the quies search anyway, I think if you stop after 7 ply of quies there is very little strength loss - but I have not checked this recently and I'm unsure of the numbers.

[rvida]

There is almost no strength loss if you put fairly severe limits on the quies search anyway, I think if you stop after 7 ply of quies there is very little strength loss - but I have not checked this recently and I'm unsure of the numbers.

I agree 100%. For some staged test positions it looks "intelligent" when 1ply search does not explode to several million nodes, but in practical game play the difference is unmeasurable.

Critter 1.6a limits QS to 6 plies in non-pv and 8 plies in pv. After this limit only captures on the lastmove target square are considered. This is very arbitrary and one may argue that simply returning standpat score is better (faster). In my tests the Elo gain/loss is unmeasurable.

[Don]

There is almost no strength loss if you put fairly severe limits on the quies search anyway, I think if you stop after 7 ply of quies there is very little strength loss - but I have not checked this recently and I'm unsure of the numbers.

I agree 100%. For some staged test positions it looks "intelligent" when 1ply search does not explode to several million nodes, but in practical game play the difference is unmeasurable.

Critter 1.6a limits QS to 6 plies in non-pv and 8 plies in pv. After this limit only captures on the lastmove target square are considered. This is very arbitrary and one may argue that simply returning standpat score is better (faster). In my tests the Elo gain/loss is unmeasurable.

We have a more liberal limit which is probably much more than needed and like you we eventually revert to simply doing recaptures.

It's probably better to be safe than sorry, in other words to have a limit like you do so that it doesn't go crazy in some odd-ball position.

[diep]

I am still looking for a pruning method in QS that is more effective in preventing search explosion through plunder raids of powerful pieces. One way to achieve this could be more aggressive pruning of captures that seem bad. Normally this is done only for captures that seem bad by SEE, i.e. through recapture on the same square. But this does not help against plunder raids, where two powerful pieces clean out the board, never exposing themselves to recapture in the process.

The idea is that a capture is bad if after making it, the opponent captures something even bigger, so that in two ply you achieved nothing other than lowering the current eval. But this is a bit too simple, because even with SEE the two ply do have a side effect, namely that you lured another, potentially more valuable piece to the capture square. (I don't want to consider side effects like discovered threats; these are too rare to make that pay off.)

If you capture Qx(protected R) it seems a bad idea, because after recapture you are down Q vs R. It could still end well if the recapturer is Q, and you had a second attacker (say K) on the square, which now does KxQ. SEE would catch that. But now consider the case where there is a pre-existing attack on your Q, and you can play NxR. The NxR looks good SEE-wise, because he can only recapture the less valuable N. But of course the situation is just as bad as wit Qx(protected R), because he will not recapture N, but Q. The pre-existing attack on your Q counts as pre-emptive protection of everything, as it were.

But again, there is the exception that the attack on your Q is with Q, and your Q was protected, so that the initial Rook capture is merely followed by a Queen trade. So perhaps we should only consider threats that are Low x High captures, or captures of unprotected pieces. (Or, in a more refined treatment, have SEE > 0.) In the face of a Qx(unprotected Q) threat it certainly seems unwise to capture a Rook. Even if it is PxR. This can help stopping unpromising plunder raids at an earlier stage; e.g. if I can do Qx(unprotected B) in the face of an existing threat Qx(unprotected R), it doesn't really further my cause to play QxB, despite its SEE of +3. The situation is in a sense similar as for an (unsupported R)x(protected B) capture, which has SEE = -2. So with the threatening loss of -5, it seems wise to prune anything that does not at least capture +5, even if it has SEE > 0.

This is not the whole story, though. There is an essential difference between retaliation on the same square and that on a different square: the initial capturer survives, and any new attacks it might have from the new location remain in existence after the retaliation. With exchange on the same square no new moves are created (ignoring discovered threats). If after PxR our P would check his K, we would not be put off by a threat against our unprotected Q. So in deciding whether a SEE>0 capture should be pruned because of a pre-existing counter threat, it should be taken into account not only what we capture, but also whether what we attack with that capture neutralizes the counter threat. E.g. if we have a hanging R, subject to PxR, but we can play Nx(unprotected B), where the N then attacks a Q, that latter attack serves as a pre-emptive defense of our R. Even if the Q is protected we stand to gain Q-N = +6 from that attack, outweighing the -5 loss of the Rook, with a B already in the pocket. So the capture is promising, and should not be pruned.

In summary:
* 'obvious threats' against us are attacks against unprotected pieces.
* The 'value' of such threats is defined as the value of the hanging piece.
* Captures of pieces worth less than the value of the worst threat against us are candidates for pruning, even if they have SEE>0.
* If such candidates create a new attack on an unprotected piece for us that is at least equal in value to our threatened piece, we must not prune.
* In addition, captures with our most-threatened piece must be searched even if they have SEE<0 when we have an attack against an unprotected more (or equally) valuable piece.

The latter because they create a situation in the daughter node where he now faces a threat of a hanging valuable piece against him, and will thus prune the recapture of our suicide attack, so that the SEE is not relevant. In fact we should even try it when the values are equal: although he now will not prune the recapture, we will cash our threat when he makes it, and it will be a mere trade (after we grabbed something with the initial capture). So the trade is material for tempo, which is not obviously bad, and thus does not deserve to be pruned.

I realize you don't like plunder raids - writing some knowledge there and debugging that well should solve it. For Diep the discussion is a different one - there is no doubt between that doing great captures and giving great checks is a good idea in Qsearch.

However where most 'good captures', say taking a pawn on b7, can increase the score, as the queen is dangerous there and can be forced to go back, it'll increase score say 0.5 pawn or so.

Yet playing the move Na6-c5 increases score a lot more, say 2.2 pawns effectively. From shitty mobility to great center control, besides the usual bonuses.

In fact previous move the opponent might've played just a relative 'bad move' just to get the LMR reduction in order to avoid you from playing Na6-c5.

The big pain is recognizing which moves are gonna give this huge score increase.

Shouldn't we do more last few plies there than just some captures?

It's more of a philosophical question as testing things out there could involve writing massive knowledge code for move ordering - in short the huge difference in Diep in this case between a knowledgeable evaluation.

Worlds most knowledgeable evaluation, versus the relative simplistic move ordering and relative simple move choice in qsearch where only checks and captures get considered in the current Diep incarnation, as far as i can check (debug). Note i am sure i consider more in move ordering than any other program, yet still it's relative simple compared to evaluation, as otherwise the program would slow down too much; the question is not on the ordering so much, it's about whether we still want to try moves and when?

Shouldn't there be more sophisticated termination prior to jumping into qsearch? (regardless of the question, which only comes AFTER that, is in determining WHICH actual moves might give this huge score increase).

[hgm]

Stupid thought by an idiot: prune if SEE < alpha. Even if we are not better positionally, we will probably be able to make up with material.

This does not work, becaue it is pretty common that you have two or more SEE>0 captures in a horizon node. E.g. if you have Nx(protected R) and Px(protected B) elsewhere, each of those has SEE = +2. But you play NxR, and now he has to recapture to keep you at +2 rather than +5, so that he canot use the move to save his B, and you play PxB, which after his recapture pushes you back to +4. So if alpha = +3, you would end above it, but you would never see that if you pruned the captures because they had SEE = +2 < alpha.

So moves are never futile because of their SEE score. They can be futile because the victim value is too low, because then the opponent an stand pat to refute you. But when the SEE score is based on an exchange where you keep the move, the scores acumulate, and you can go on collecting more.

It might be possible to achieve something in the case the SEE score is based on a sequence of odd length, though. Capturing a hanging piece is the simplest of those, but already covered by the rule that the victim value should bring you above alpha, as victim value and SEE coincide there. But with RxB, NxR, QxN you would have SEE = +1, and with alpha = 2 this could be worth pruning despite the fact that the RxB is not futile. Because the first to ply only drop you further below alpha, and to cash the rewards you have to give up the turn, and there can be no follow-up, as this will give him the opportunity to stand pat.

Note that the classical piece values of Chess are accidentally such that odd length corresponds to odd see (because 1,3,5 and 9 are all odd). So the rule there could be: prune if SEE < alpha && ODD(SEE)

[hgm]

Perhaps a stupid idea, but what if we simply limited the number of non-recapturing consecutive captures by queens or perhaps anything?

This is not stupid at all, and I did something like that in my 1980s engine Usurpator II. Where it was needed to compensate for the poor move ordering. I limited consecutive captures with Q there. and it worked, without causing too much visible inaccuracy.

Tricks like that tend to interfere with hashing, though, because they make the treatment of a node path dependent. The same holds for recaptures to the same square only (but perhaps it would not pay to hash those nodes anyway).

But it might be possible to achieve something similar by putting a limit on the total number of Queen (or other super-piece) moves, by having it affect the depth parameter, and hashing QS by depth. You would have to do that anyway if you want to consider checks only for the first few plies. So you would get something like this:

QS(depth=N) calls QS(depth=N-1) when N=0, -1, at which levels you search captures and checks. But from depth = -2 on, you would do
QS(N) calls QS(N-1) for captures with 'super-pieces'
QS(N) calls QS(N) for other captures
and when depth = -4 you no longer consider captures with the super-pieces.

[hgm]

I realize you don't like plunder raids - writing some knowledge there and debugging that well should solve it. For Diep the discussion is a different one - there is no doubt between that doing great captures and giving great checks is a good idea in Qsearch.

Indeed, plunder raids are the main problem I am battling. When a piece like a Lion manages to jump to a safe square within the opponent's camp, it can then start to pick off all neighboring pieces 'en passant', as it were, ending on the same safe square as it was. There could be upto 8 such neighbors, and the Lion could capture them in 8! = 40,320 different orders. If the opponent is then doing the same with his Lion...

However where most 'good captures', say taking a pawn on b7, can increase the score, as the queen is dangerous there and can be forced to go back, it'll increase score say 0.5 pawn or so.

Yet playing the move Na6-c5 increases score a lot more, say 2.2 pawns effectively. From shitty mobility to great center control, besides the usual bonuses.

In fact previous move the opponent might've played just a relative 'bad move' just to get the LMR reduction in order to avoid you from playing Na6-c5.

Absolutely right; such huge score swings causes a terrible 'positional' horizon effect, just as bad as captures do without QS. I already saw that in Joker, where the castling bonus was more than 1 Pawn and awarded at the time of the actual castling. It starts to sac Pawns to push the opponent's castling over the horizon.

Moves like that deserve to be searched in QS, because a position where you can do them cannot be described as 'quiet'. I once considered to search Pawn pushes in QS, because they can also give huge score swings (e.g. when creating a passer). And like captures, they are irreversible. So in the end you would run out of them. And futility pruning would take care of most of them in practice anyway.

Of course an alternative, and perhaps more efficient way of solving it would be to distribute the bonus over several moves. E.g. with castling you can already give a bonus for each square between King and Rook that gets evacuated, and with the Pawns you can give a bonus for candidate passers, and majorities. But for the Na6-c5 example there seems no way to 'soften' it.

You could extend this to such moves as Na6-c5, based on some static (PST-like) score threshold. Searching only moves along the gradient of a static board table effectively makes them irreversible too. Only when you have a moving target (like the King for checks) you have the danger of infinite recursion.