Null capture pruning

[mcostalba]

Null move is a well known and powerful technique to avoid searching nodes that will fail-high anyway.

But null move has some weak points. As example consider the below position

[d]7k/8/5b2/8/8/8/1Q6/1K6 w - - 0 1

White is in advantage but a null move test will never fail-high as it should because the black bishop will capture the white queen.

This capture is an artifact of null move algorithm and is due to the side to move change.

If we could detect this kind of "false positives" after the null move we could discard many more nodes then we currently do.

In new Stockfish 1.1, just announced on the general forum, there is some code (disabled by default) that tries to safely and cheaply detect these null captures artifacts and returns a fail-high score instead.

The code works in two steps:

1- The first step, just after the null move search, detects a possible null capture artifact candidate.

2- The second step, just before to leave the null move part, verifies that the candidate is really a false positive, and returns a fail-high score in that case.


The key in the first step is the use of SEE togheter with the null value, in the second step the verification is done with a search at reduced depth.

As a good side effect, also when the verification search reveals a real threat, so that the node is not discarded, the TT move is updated with the value returned by the verification search that, in this case, takes the role of an internal iterative deepening (IID) search. So the extra effort spent for verification turns out to be useful in any case.

It is still not clear if the technique is effective, my tests give mixed results, probably the current choice of parameters in Stockfish is not the optimal one. That's the reason I post, if people is interested I would like this idea to be verified and tuned by a much wider audience then myself alone so that, if it proves good, I don't have to wait months to find the optimal setup.


Thanks
Marco

[Ron Murawski]

Null move is a well known and powerful technique to avoid searching nodes that will fail-high anyway.

But null move has some weak points. As example consider the below position

[d]7k/8/5b2/8/8/8/1Q6/1K6 w - - 0 1

White is in advantage but a null move test will never fail-high as it should because the black bishop will capture the white queen.

This capture is an artifact of null move algorithm and is due to the side to move change.

If we could detect this kind of "false positives" after the null move we could discard many more nodes then we currently do.

In new Stockfish 1.1, just announced on the general forum, there is some code (disabled by default) that tries to safely and cheaply detect these null captures artifacts and returns a fail-high score instead.

The code works in two steps:

1- The first step, just after the null move search, detects a possible null capture artifact candidate.

2- The second step, just before to leave the null move part, verifies that the candidate is really a false positive, and returns a fail-high score in that case.


The key in the first step is the use of SEE togheter with the null value, in the second step the verification is done with a search at reduced depth.

As a good side effect, also when the verification search reveals a real threat, so that the node is not discarded, the TT move is updated with the value returned by the verification search that, in this case, takes the role of an internal iterative deepening (IID) search. So the extra effort spent for verification turns out to be useful in any case.

It is still not clear if the technique is effective, my tests give mixed results, probably the current choice of parameters in Stockfish is not the optimal one. That's the reason I post, if people is interested I would like this idea to be verified and tuned by a much wider audience then myself alone so that, if it proves good, I don't have to wait months to find the optimal setup.


Thanks
Marco

You might find this paper on Null Move Verification useful:
http://www.cs.biu.ac.il/~davoudo/pubs/vrfd_null.html

I use a similar null move verification search in my engine and it helped playing strength very slightly.

Ron

[hgm]

I don't quite get this. Why do you call this an 'artifact'? It seems to me that your Queen under attack is a very real threat; except for checks, they don't come more real than that...

So you cannot afford null move in this situation, and you need to search real moves. And you will have to do that at a larrger depth (i.e. not reduced), or you might invite horizon effect. The attack on your Queen by the Bishop might have been a delaying tacktic, to push a threat you have against one of the opponent's pieces over the horizon.

I furthermore do not completely get your algorithm. Are you saying we should reduce good captures when current eval is above beta?

[Eelco de Groot]

Null move is a well known and powerful technique to avoid searching nodes that will fail-high anyway.

But null move has some weak points. As example consider the below position

[d]7k/8/5b2/8/8/8/1Q6/1K6 w - - 0 1

White is in advantage but a null move test will never fail-high as it should because the black bishop will capture the white queen.

This capture is an artifact of null move algorithm and is due to the side to move change.

If we could detect this kind of "false positives" after the null move we could discard many more nodes then we currently do.

In new Stockfish 1.1, just announced on the general forum, there is some code (disabled by default) that tries to safely and cheaply detect these null captures artifacts and returns a fail-high score instead.

The code works in two steps:

1- The first step, just after the null move search, detects a possible null capture artifact candidate.

2- The second step, just before to leave the null move part, verifies that the candidate is really a false positive, and returns a fail-high score in that case.


The key in the first step is the use of SEE togheter with the null value, in the second step the verification is done with a search at reduced depth.

As a good side effect, also when the verification search reveals a real threat, so that the node is not discarded, the TT move is updated with the value returned by the verification search that, in this case, takes the role of an internal iterative deepening (IID) search. So the extra effort spent for verification turns out to be useful in any case.

It is still not clear if the technique is effective, my tests give mixed results, probably the current choice of parameters in Stockfish is not the optimal one. That's the reason I post, if people is interested I would like this idea to be verified and tuned by a much wider audience then myself alone so that, if it proves good, I don't have to wait months to find the optimal setup.


Thanks
Marco

I try to think of it a little bit like this: null move is designed to detect moves that are very poor, mainly because they pose no threat that the other side has to counteract immediately. Moves that are so poor that even if you were allowed to carry out your threat immediately, by making the second move without having to wait for a reply, you can not "repair" the first move because there was no threat. In this case Black does have a theat and in the scond move he would capture a full Queen. So the Null Move would Fail Low.

Tord wrote in his code (Glaurung 2.1) at this point in the null move pruning

else {
// The null move failed low, which means that we may be faced with
// some kind of threat. If the previous move was reduced, check if
// the move that refuted the null move was somehow connected to the
// move which was reduced. If a connection is found, return a fail
// low score (which will cause the reduced move to fail high in the
// parent node, which will trigger a re-search with full depth).

The null move fails low and in this case this is correct usage of null move, no null move reduction/pruning should be done, the move is not so poor that it poses no threat but mainly because White can immediately neutralize the threat by capturing that insolent Bishop that attacks the Queen. The "repair" move (Bishop takes Queen) would be strong enough to cause the first move to go over alpha but the null move if carried out (Queen takes Bishop first) would have been stronger.

I was thinking a bit if there is something you can do by demanding that the "repair" move, the free move, is done by a different piece than the first. In general it would mean that the repair move is not so strong, you can't carry out any immediate threat from the first move. Maybe you could say that if one side could carry out a double null move, three moves in a row but with different pieces, and your position is still so low that seen from the other side it goes over beta, the first move must have been positionally very poor. I was hoping this would say a little more positionally than normal null move which is mainly about tactics. You would have to insist the three moves are no captures I think and decide somehow that in the root position you can't make any immediate threat or those all fail. Or maybe something like: the second move fails high so normally you would make a null move cut, but if the second move is with a different piece and no capture and the third move with again a different piece and no capture now fails low, in that case the first move may be positionally interesting.


I have no idea if it would work or if it would be far too expensive. Because it is nontactical you could probably use it in PVnodes, where you have to make a postional decision instead of finding tactical refutations.

Regards,
Eelco

[hgm]

Another way to think of (recursive) null-move pruning is this: for every devation from the PV, you first try to refute it with only null moves. Ths progressively show you if the opponent can do any damage with two moves in a row (including the deviation), with three moves in a row, etc. If he can't, you don't worry. But of course this almost never happens. (Except perhaps in KQK, where you can lat the bare King move an indefinite number of times without any danger.)

So amongst all the sequences of, say, 3 opponent moves, there will be some that do so much damage that he surpasses (his) alpha. This wil first show up as a refutation of your last null move. You will then replace this null move by an alternative, a real move, to see if it solves the problem. But to make sure we are not merely pushing the damage done by the opponent's final move over the horizon, we have to search this deeper than the original null-move search. This way we expand the branches containing the move sequences of the opponent that cause trouble to greater depth, by inserting moves that remedy or pre-empt the damage the opponent can do. Sequences of harmless or useless moves (which are most branches, as the opponent tries everything in his all nodes, no matter how poor) do not get expanded to a deeper tree.

Now the question posed in the leading post is basically this one: is it always needed to extend the real move compared to the null move for which we substitute it? (Or, equivalently, take away the reduction.) It could be that, in cases where the real move is unlikely to be a delaying tactic, it is a waste of time to extend it. This could apply to recognized remedies of the threat posed by the previous move. E.g. in the example, the threat is BxQ. Capturing the B or moving the Q are recognized evasions for this threat. So why extend the QxB? The threat that made our null move fail low will certainly not exist anymore, and there is thus no risk pushing it over the horizon.

I can think of a number of arguments against this, though: the threat we solved might be only one of the threats that could make the null move fail low. There might have been another one (perhaps even a worse one), which we are not aware of. And the threat evasion we played against the major threat might as a side effect create an even more important counter threat, so that this undetected secondary threat is now pushed over the horizon. Or, probably more common, a threat-evasion by capturing the attacker might tie up the opponent's reply, because, unlike the example, he might have to recapture. Also, playing a null-move is inherently less risky than playing a specific real move to evade a threat: If deeper search reveals trouble, you can replace the null move by something that pre-empts the trouble. But if your move was already spoken for to evade a threat, you have no freedom to pre-empt anything.

But perhaps it would still possible to search known threat evasions only 1 ply deeper than the null move. (Or, if you do R=3, even two ply, by reducing them 1 ply.)

[mcostalba]

I don't quite get this. Why do you call this an 'artifact'? It seems to me that your Queen under attack is a very real threat; except for checks, they don't come more real than that...

Please try the following in your engine (I did myself to make me clear what I was trying to achieve).

If the null move fails low and _all_ the conditions you see in Stockfish apply (threat move is a capture, null move value + see > beta, etc..) then print out the current position and the threat move to stdout or to a file as you prefer.

Then look at few of that positions and to the corresponding threat moves and then aks to yourself: we can do something better then failing low in this cases ? These are what I call capture artifacts.

Marco

[hgm]

OK, we might have a small terminology mismatch here. In positions like the one you show, I would answer the question: "could we do anything better than fail low?" unequivocally with "absolutely not". The null move is absolutely no good in those positions. For getting a fail high (or at least, not a fail low) in such positions, you cannot rely on null move, but must rely on some other move. (In your example, QxB). That other move can of course fail high, but the null move will fail low. And as such null-move substitutes are not provided by an oracle in the engine, I would think we would have to start searching the real moves, in order to make sure there is one that fails high, and identify it. Of course moves like capturing an undefended attacker are good candidates, which you might want to search first. But it is not a certain remedy.

So in my mind, the only question is, how deep should I search search such moves to be convinced that they fail high? I certainly would not want to base it on a SEE only. The SEE might be could, but the capture absolutely losing, because the capturer was pinned or tied in defnce of another piece.

[mcostalba]

OK, we might have a small terminology mismatch here. In positions like the one you show, I would answer the question: "could we do anything better than fail low?" unequivocally with "absolutely not". The null move is absolutely no good in those positions. For getting a fail high (or at least, not a fail low) in such positions, you cannot rely on null move, but must rely on some other move. (In your example, QxB). That other move can of course fail high, but the null move will fail low. And as such null-move substitutes are not provided by an oracle in the engine, I would think we would have to start searching the real moves, in order to make sure there is one that fails high, and identify it. Of course moves like capturing an undefended attacker are good candidates, which you might want to search first. But it is not a certain remedy.

So in my mind, the only question is, how deep should I search search such moves to be convinced that they fail high? I certainly would not want to base it on a SEE only. The SEE might be could, but the capture absolutely losing, because the capturer was pinned or tied in defnce of another piece.

Yes, I agree. Actually the SEE is used to trigger a warning to say "Hey, _perhaps_ we are in front to one of that capture threat moves"

Then it is _always_ done a normal search at reduced depth to validate the prune: "Let's try to search if the capture threat move is a real threat or the position fails-high also if null move has failed low".

The key here is that the verification search is done at a reduced depth and the second very important point is that the verification search almost always (at least in my tests) validates the SEE: the position fails high in the great majority of these cases.

Marco

[mcostalba]

You might find this paper on Null Move Verification useful:
http://www.cs.biu.ac.il/~davoudo/pubs/vrfd_null.html

I use a similar null move verification search in my engine and it helped playing strength very slightly.

Ron

Thanks, I will read it!

[hgm]

Note that the verification Ron is referring to is exactly the complementary case of what you worry about, namely not taking a null-move fail high for granted, (taking a beta cutoff), but doing a reduced search if it occurs, and use the result of that.

My problem is that I do not properly understand the condition that you mention: "SEE together with null-move value". If the latter means score returned by the null-move search, the problem seems that the score from a fail low is merely an upper bound. So you know the null move is bad, but not how bad. This would be a problem if you want to apply this to moves unrelated to the threat, i.e. when you retaliate against a piece other than the attacker, and based on the SEE this seems to gain more than you lose on the null move. But I guess for identifying candidates it will be good enough; the veriification search will show you if the retaliation works in reality, as the opponent will start to work harder on the original threat to make up for the loss in the SEE. The main problem I perceive is if you can afford reduction of the verification search. My guess would be not, as retaliation against a target unrelated to the true threat is the most common source of horizon effect, especially if it is a valuable target: the opponent is then forced to recapture first, and this might push the original threat move over the horizon.

For capturing the attacker this is much less likely to be merely a delaying tactic. As would be withdrawal of the threatened piece. But especially with the latter, I would only feel at ease if there was the additional assurance that the withdrawal did not inadvertantly launch a counter attack, that acted as a delaying tactic. (Withdrawal usually offers much more choice than capturing the attacker, so the probability that the best withdrawal has side effects is appreciable.) So it would depend if withdrawn piece is used to refute any later moves, by capturing something. So I would only believe the results of a reduced verification search on a withdrawal move, if it failed high when the withdrawn piece is replaced by a version that is not allowed to capture (or perhaps only to capture pieces after they have moved).

I actually like this latter idea, as an alternative for cheap pruning in cases where a null move does not work: "passify" a threat evasion by endowing the moved piece with a non-capture restriction, in order to invite immediate play of any threat the opponent might have, and thus make a fail high even in a reduced search highly significant (i.e. enough to prune on it). We must be a little careful, though, as counter threats acting as delaying tactic need not only be due to captures with a relocated piece, but could also be due to threats revealed by that piece, or blocking of defenders by the piece in its new location. (e.g. a Pawn push could turn what was a Q trade into a Q loss, by blocking a BxQ recapture.) So what actually is needed is to replace the moved piece by a "ghost", which cannot capture, and is transparent to enemy pieces (i.e. they move right through it). And it should leave a "residue" on its original square, which makes that square impassible to friendly pieces. Such a "ghost move" could be used similarly to the null move, in cases where there is a threat against you (i.e. search with reduction, prune if this search fails high). I am not sure if you could afford as large a reduction in thei "ghost-move pruning" as with null move: a ghost move remains more risky, because you don't have this extra tempo up your sleeve that the null move gives you.