Threat detection
Posted: Sat Sep 09, 2017 4:55 pm
It would be nice if the null-move search could not only make us aware that we are facing a threat (through the returned score), but also what this threat is. So that we can take that into account when sorting the moves in the node where the null moves fails low. After all, it makes little sense to start with the MVV/LVA move BxR when our Queen is under attack.
The most obvious idea is of course to have each node return its best move. The null-move reply would then return the move that refuted the null move. If that is, say, PxN, we know our Knight is threatened, and moves with that Knight (including captures) would rescue it, as would captures of that Pawn. Unfortunately this almost never works, because of the way we sort captures. We go for the highest victims first, and the Knight is pretty low on that list. Any trade of higher material comes before it. So the null-move refutation is likely initiating the trade of a Queen or Rook, like QxQ - BxQ - PxN. By identifying QxQ as the threat you will prevent the trade, but still lose the Knight.
So in general the actual threat (the capture that loses us the material) comes from a later ply in the refutation. To make it available in the node that tried the null move, it would have to be backed up towards the root. So nodes will return a 'threat move', which can be different from the best move in the node.
A move can be identified as a threat move when it fails high, and the opponent does not have an 'adequate retaliation' in the reply node. I.e. he cannot capture a piece of at least the same value. So if there are no captures left after the PxN in the example, or the opponent can only recapture the Pawn, the PxN is a threat move. We make a node without adequate retaliations report this fact to the parent, to establish this.
In cut-nodes it is easy: either the child did not have an adequate retaliation, in which case the cut move gets returned as threat move, or it does have an adequate retaliation, which allows it to get even (so that the cut move was just a trade, or even a sacrifice), but nevertheless fails low because of a threat not resolved by the trade. In the latter case it will return the treat move, and the cut-node will just pass that on to his parent.
In all nodes it is more complex, because these have many children, which might all return different threat moves. Not all its moves will be adequate refutations, however. Being an all node, it will also search non-sensical replies, such as RxP in reply to Qx(protected)Q. We will ignore those in any case, ad only look at the adequate retaliations. So after QxQ we would only consider capture of a Q. Suppose, for now, that there is only one way to recapture the Queen (the BxQ in the example). Then the all-node will return the threat move it got from its BxQ child (which is PxN) also as its own threat move. The cut-node where QxQ was played then will also pass this to its parent, so that in the end we know the null move failed because of the PxN threat, and can selectively take action to remove that threat. (E.g. if all else fails, even consider withdrawing the Knight with a non-capture before going Pawn hunting.)
Now there are several twists to this basic idea. For one, trading Queens (or whatever) does not always go through QxQ, but can also be indirect, e.g. RxQ - BxQ - PxN. In fact the general search strategy tends to create such indirect trades abundantly, through lines like
hangs Q (to B) - null(1) - attacks Q (with R) - null(2) - attacks N (with P) - null(3) - RxQ - BxQ - PxN
Here null move #1 was smart, why capture a Queen if your eval is already above beta, and you can keep the offered one as a 'hostage' you can always execute later. Null move #2 gets a bit arrogant, but as you still hold a Queen hostage, you can still give it a try. With null move #3 the cut-move player is over-playing his hand, however, as he now has 2 threats against him, and only holds a single hostage. So this null move gets refuted when the opponent starts to collect.
With such an indirect trade, the threat could be cured by making the trade impossible. If the Q would withdraw from the R attack, it would not make the PxN threat go away, but as you still hold the opponent Q hostage, this doesn't worry you too much. Instead of null - RxQ - BxQ - PxN you get save Q (from R) - PxN - BxQ, and end up Q vs N ahead, which presumably makes you fail very high. This seems much preferable over save N (from P) - RxQ - BxQ, which would make you come out even. We can accomodate this by being more subtle in what we retur from all-nodes. If the adequate refutation in such a node was not a direct recapture, we should only return the threat move obtained from its child, if it was a more dangerous threat than the move leading to it. So if the adequacy goal for retaliation is a Q, a threat move obtained through BxQ should be returned if the BxQ was a direct recapture after QxQ, but be considered inadequate against a RxQ. So that the RxQ cut move leading to it would be picked as threat move in the parent.
Tactical connection between the moves in the line is another complication. It could be that the threat move oly became possible because of the preceding trade. E.g. when in QxQ - BxQ - RxN the traded Q was origially protecting the N. Or when the R was originally blocked by the B (soft pin). In these cases it would still help to withdraw the N, although it will now also help to make the trade impossible by withdrawing the Q. (If this Q was protecting the N, however, it would have to be withdraw so that it keeps protecting the N. This would make it a less certain remedy when we do not pay attention to this. So it seems safer to just withdraw the N or capture the R, which will surely defuse the RxN threat.
The only case that does require special treatment is when the 'threat move' deeper in the tree became possible because the 'threatened' moved in the trade, i.e. used to recapture (RxR - NxR - QxN). So a cut-move that recaptures previously moved piece should never be designated threat move, even when there are no adequate retaliations. That means the NxR move does not get a threat move from its search, and the all-node where it was played has nothing to return. This makes the initial RxR (a cut move) the threat move, and will encourage withdrawal of the (apparently insufficiently protected) Rook.
The most obvious idea is of course to have each node return its best move. The null-move reply would then return the move that refuted the null move. If that is, say, PxN, we know our Knight is threatened, and moves with that Knight (including captures) would rescue it, as would captures of that Pawn. Unfortunately this almost never works, because of the way we sort captures. We go for the highest victims first, and the Knight is pretty low on that list. Any trade of higher material comes before it. So the null-move refutation is likely initiating the trade of a Queen or Rook, like QxQ - BxQ - PxN. By identifying QxQ as the threat you will prevent the trade, but still lose the Knight.
So in general the actual threat (the capture that loses us the material) comes from a later ply in the refutation. To make it available in the node that tried the null move, it would have to be backed up towards the root. So nodes will return a 'threat move', which can be different from the best move in the node.
A move can be identified as a threat move when it fails high, and the opponent does not have an 'adequate retaliation' in the reply node. I.e. he cannot capture a piece of at least the same value. So if there are no captures left after the PxN in the example, or the opponent can only recapture the Pawn, the PxN is a threat move. We make a node without adequate retaliations report this fact to the parent, to establish this.
In cut-nodes it is easy: either the child did not have an adequate retaliation, in which case the cut move gets returned as threat move, or it does have an adequate retaliation, which allows it to get even (so that the cut move was just a trade, or even a sacrifice), but nevertheless fails low because of a threat not resolved by the trade. In the latter case it will return the treat move, and the cut-node will just pass that on to his parent.
In all nodes it is more complex, because these have many children, which might all return different threat moves. Not all its moves will be adequate refutations, however. Being an all node, it will also search non-sensical replies, such as RxP in reply to Qx(protected)Q. We will ignore those in any case, ad only look at the adequate retaliations. So after QxQ we would only consider capture of a Q. Suppose, for now, that there is only one way to recapture the Queen (the BxQ in the example). Then the all-node will return the threat move it got from its BxQ child (which is PxN) also as its own threat move. The cut-node where QxQ was played then will also pass this to its parent, so that in the end we know the null move failed because of the PxN threat, and can selectively take action to remove that threat. (E.g. if all else fails, even consider withdrawing the Knight with a non-capture before going Pawn hunting.)
Now there are several twists to this basic idea. For one, trading Queens (or whatever) does not always go through QxQ, but can also be indirect, e.g. RxQ - BxQ - PxN. In fact the general search strategy tends to create such indirect trades abundantly, through lines like
hangs Q (to B) - null(1) - attacks Q (with R) - null(2) - attacks N (with P) - null(3) - RxQ - BxQ - PxN
Here null move #1 was smart, why capture a Queen if your eval is already above beta, and you can keep the offered one as a 'hostage' you can always execute later. Null move #2 gets a bit arrogant, but as you still hold a Queen hostage, you can still give it a try. With null move #3 the cut-move player is over-playing his hand, however, as he now has 2 threats against him, and only holds a single hostage. So this null move gets refuted when the opponent starts to collect.
With such an indirect trade, the threat could be cured by making the trade impossible. If the Q would withdraw from the R attack, it would not make the PxN threat go away, but as you still hold the opponent Q hostage, this doesn't worry you too much. Instead of null - RxQ - BxQ - PxN you get save Q (from R) - PxN - BxQ, and end up Q vs N ahead, which presumably makes you fail very high. This seems much preferable over save N (from P) - RxQ - BxQ, which would make you come out even. We can accomodate this by being more subtle in what we retur from all-nodes. If the adequate refutation in such a node was not a direct recapture, we should only return the threat move obtained from its child, if it was a more dangerous threat than the move leading to it. So if the adequacy goal for retaliation is a Q, a threat move obtained through BxQ should be returned if the BxQ was a direct recapture after QxQ, but be considered inadequate against a RxQ. So that the RxQ cut move leading to it would be picked as threat move in the parent.
Tactical connection between the moves in the line is another complication. It could be that the threat move oly became possible because of the preceding trade. E.g. when in QxQ - BxQ - RxN the traded Q was origially protecting the N. Or when the R was originally blocked by the B (soft pin). In these cases it would still help to withdraw the N, although it will now also help to make the trade impossible by withdrawing the Q. (If this Q was protecting the N, however, it would have to be withdraw so that it keeps protecting the N. This would make it a less certain remedy when we do not pay attention to this. So it seems safer to just withdraw the N or capture the R, which will surely defuse the RxN threat.
The only case that does require special treatment is when the 'threat move' deeper in the tree became possible because the 'threatened' moved in the trade, i.e. used to recapture (RxR - NxR - QxN). So a cut-move that recaptures previously moved piece should never be designated threat move, even when there are no adequate retaliations. That means the NxR move does not get a threat move from its search, and the all-node where it was played has nothing to return. This makes the initial RxR (a cut move) the threat move, and will encourage withdrawal of the (apparently insufficiently protected) Rook.