TalkChess.com

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.

Couldn't you change the move ordering of capture moves following a null-move so that you try the move with the largest SEE first? That should get you the thread move you're looking for too, and should be less complicated than your scheme. There are cases that it won't catch, of course, and there is a cost to using SEE for sorting captures, but perhaps it's worth it if you do so only after a NULL move and make good use of the threat move...

Using a sub-optimal move ordering is far from free. So although you might gain in simplicity, you could lose a lot in performance.

But if you would SEE every capture, you would not have to actually search them, and you could identify the biggest threat based on that. You would not see cases like QxQ BxQ RxN, though, where the traded Q was protecting the N, or the recapturing B was soft-pinned on it. (But this might not be very common.)

I don't think the scheme I proposed here gets very complicated, though. On a beta cutoff you return the cut move if it was not a recapture (to the same square), and the child returned nothing. In all other cases you pass on what the child returned. In an all-node you remember what the child returned for a move that recaptured (to the same square) at least as much as what the preceding move captured, and return that if you indeed failed low. Or return nothing, when there is no such move.

After thinking some more about this, I realized that a lot of cases are 'self-correcting'. E.g. if the trade preceding the threat is an indirect one, like BxQ - RxQ - PxN, the first thing you would normally try after null fails low, is pre-emptively executing your hostage by RxQ. This would normally be good enough to fail high. Two ply later the trade would have been consumed, and the PxN threat would be first in line, and thus recognized even without any smart threat detection.

This would not work if the retaliation RxQ was in some way dependent on the preceding capture BxQ, and thus cannot be done pre-emptively. E.g. because the R was soft-pinning the B on the Q. In this case solving the BxQ 'threat' would not buy you anything, because you don't really hold a hostage. Punishing a soft-pin has more the character of a direct recapture. So the criterion for whether to propagate your child's threat move to your parent is really whether the adequate retaliation is by a move that became possible because of the preceding ply, or not.

This being said, for independent retaliations trying to cure the initiating capture (BxQ) in general is a better move than pre-emptively executing your hostage (RxQ), because a hostage is a useful asset, which you should rather keep. Designating the BxQ as threat move (rather than PxN), as the proposed algorithm would, upgrades, for instance, the capture of the Bishop to gain of a Bishop + rescue of a Queen, rather than just capture of a Bishop, and would thus get priority over moves that merely capture a Queen, such as the pre-emptive hostage execution RxQ.

After a direct trade, e.g. QxQ - BxQ - PxN, one would normally proceed after failure of the null move with the reciprocal QxQ, initiating the trade yourself. Then the PxN also becomes first in line after the following null move, and if you handsomely solve that threat, the reciprocal QxQ would be a cut move, so that you would never get to bother with the measly PxN threat (which at best rescues a Knight). So it becomes a moot point whether you did correctly identify the threat move.

This is partly due to the accidental property of orthodox Chess that the strongest pieces, Q and R, are in a class of their own. So that a trade threat can always be reprocicated. It would be different, for example, if a Chancellor attacked a protected Queen with its N move (CxQ, BxC, NxP). There is no possibility then to pre-empt with QxC. Designating the CxQ as threat move would be wrong, and still lose you the Knight through PxN after you 'cured' the threat by withdrawing the Q. Identifying PxN as threat, and withdrawing the N as a consequence, would still lose you 50cP because of the slightly unfavorable Q-for-C trade, but would be a lot better than going on Pawn hunting (and lose the Knight in retaliation). In orthodox Chess a similar situation can still occur with a trade through a soft-pin: (pinned)BxQ - RxQ - PxN does force a Q trade without the possibility to reciprocate with QxQ, or pre-empt with RxQ. Here it would be beneficial to immediately know PxN is the true threat.

BTW, the CxQ example tells us something: according to the earlier definition BxC would not be an adequate retaliation (as C < Q), and thus elevate CxQ to threat move. Indeed it is a threat of some sort, losing 50cP, but not nearly as much as the PxN, which loses a minor. So it is important in cases like this to compare the value of the threat. I.e. not pass the child's threat move to the capture only when the move leading to that child is strictly adequate (so the preceding 2 ply are a pure trade), but even when the 'inadequacy' is smaller than the threat.

NG-Play (and thus the CT800) has something like this. The best move from the null search is saved and then passed on to the next depth level. When doing the late move generation, the mvv/lva values of the moves are modified. A PV move gets maximum, then hash best move, then the threat move.

Interesting. So you assume late moves have a good chance to have the same refutation as the null move. Have you tried to extend that analogy to their entire sub-tree. (I guess not, because I know your hash table is really small, so perhaps not much of that sub-tree would still be there.)

My plan with the null move was not so much to mimic it in other nodes, as well to take directed action in their parent to prevet this node would work in the child. So move away the threat victim, or capture the threat attacker. These would get the value of the threat added to their normal victim value. Even non-captures that move away the threat victim could get capture status that way. (And perhaps interposing a less valuable piece should be treated similarly.)

The idea is that null move is tried in cut-nodes, to get a cheap cutoff. If the null move fails low because of a pending threat, a move that defuses that threat should be able to achieve the expected fail high, so that I would never get to any late moves.

hgm wrote:Interesting. So you assume late moves have a good chance to have the same refutation as the null move.

Actually, the best null move itself is assumed to be a refutation for most of the moves one depth level further down the road.

Have you tried to extend that analogy to their entire sub-tree.

This "threat move" plot is done both at root and within the Negascout.

At root, I have extended that to be part of the Negalight pre-sorting (3 plies depth), and I remember something like 10% fewer nodes or so. Totally worthless on the PC, but a nice and free speedup if you have only 20-30 kNPS. It also showed that the idea works.

My plan with the null move was not so much to mimic it in other nodes, as well to take directed action in their parent to prevet this node would work in the child.

More like a human chess player would do that, right? It's pretty easy as long as the solution is capturing the threatening piece, but when you weigh in moving the threatened piece away, you have more moves, and when moving other pieces in-between, it's even more, and that still doesn't include the possibility to just ignore the opponent's threat and putting up higher threats.

"Directed action" is hard, given that engines don't actually "understand" what they are doing. They can calculate "If I do this, then that happens, so I can't do this, but if I do something else, that doesn't happen", but that's completely different from "I should do this in order to prevent that".

True, it is hard. But that does not mean it is impossible. Moving away the threatened piece might be a lot of moves, but it can still only be a fraction of the total number of moves. (And this gets even more true for large-board variants with many pieces.) So by searching those before the others, you could still reduce the time you need to find the cut move by a factor 5-10. The more moves there are, the larger the chance one of them will solve the problem. And if there are few, it hardly hurts when they don't solve it.

I guess this would mainly help at the tip of the branches, when you get to 1 ply in a position that in the previous iteration was only searched in QS, and failed high there through stand pat. It can do that in the face of any threats, but the null move would not survive those threats, and then you have no hash move. If the threat is a low x high attack on one of your pieces, evading is often the only remedy, and in the normal move ordering such moves would typically come quite late.

The engine I am currently working on has staged move generation, and basically generates the non-captures in arbitrary order. I might as well start with generating the non-captures with the threatened piece. Although I still have the feeling that it would be better to already generate them at the point where you get to generating captures on victims of lower value than what you stand to lose through the threat. (A typical position for me has some 50 captures, so always finishing the search of all captures could waste a lot of time on moves that predictably will not help.)

hgm wrote: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.

Examine the killer(ply+1) move saved from the cutoff position of the null move search, or if there was no killer saved then examine the best move in the hash table. This should give the threat move.

Further ideas to try might be to examine the attack squares and captures of the threat move. Move ordering could be adjusted to defend these squares, or move the attacked pieces first. Another idea is to save that killer threat so it is not destroyed during the subsequent search. Of course, it may end in a lot of programming for nothing but that is what you are asking for if you dare to program.

IIRC Stockfish had a concept similar what you are describing here. Whenever a null move failed low, SF looked at the move that failed high for the opponent. Every move that prevent this move from being able to be played (by moving in between the from and to squares) was then reduced less than it normally would be (it may have also removed these moves from being LMP candidates). However this all was removed somewhere around SF5 or 6.

I played with a similar concept inside of Nirvana but I could never get it to perform even neutrally. I suspect that this is due to the fact that multiple moves can cause a null move to fail low. In the case where there is more than one move, we are just randomly choosing moves that we are going to reduce less.