how to track down a BUG?

[Sven]

I was inspired by stockfish code where they return beta-1 if the move that make a checkmate and the previous move are "connected".

The solution in Stockfish also requires that the previous move (the one prior to the null move) was reduced. Letting the previous move fail high triggers a re-search to full depth.

Sven

[lucasart]

the bug turned out to be in the search code, threat detection in nullmove.

When the nullmove test reports a checkmate I returned beta-1, this was the problem.
I was inspired by stockfish code where they return beta-1 if the move that make a checkmate and the previous move are "connected".
Now I don't return beta -1 but I only set a checkmateThreat and extend the search.

How does this idea fare in testing ? I'm curious, because I've tried everything there is about null threat: the chess programming wiki, as well as the Romstad null threat extension as implemented in SF. But I've never managed to measure any elo gain from it.

What you describe above is quite different from Stockfish, and in fact, much simpler. If we do a null move and get mated, then we stand on the edge of a knife and should be rather careful, so it could make sense to extend the search at this node.

Be careful of transplanting SF idea to your program like that. Your search may be very different from SF, and your program may "reject the transplant". What Stockfish does is rather complicated, and is a brilliant idea of Tord Romstad introduced in Glaurung:
- null moves are only performed at non PV nodes when the eval fails high (which ensures that double null moves are impossible even though SF enforces that condition twice with ss->skipNull flag, just to be sure)
- when the null move fails low, and the null refutation (threat move) is connected to the move played before the null move, AND the parent node was reduced, the search returns beta-1. For the sake of code clarity I think it should be alpha (of course alpha = beta-1, but it makes it clear the purpose is to fail low).
- at the parent node, the alpha=beta-1 becomes a fail high at non PV nodes, or a "doesn't fail low as expected on zero window search" at PV nodes. This triggers a re-search at non reduced depth, and will only work if your implementation of PVS is the same as Stockfish (when zero window fails low at PV node, you extend the depth *before* extending the window). And that is the main reason why it never worked in my engine, as my implementation of PVS is rather like Fruit than SF (it tries to adress search instability this way, and it seems to work well).

[hgm]

Much simpler to just add one to the depth and continue, (or redo the null-move search at that larger depth, although I expect that to be a real waste of time), rather than returning alpha. Then you are not dependent on any assumptions on when re-searches are triggered, and it saves you a pointless return - test - call.

[lucasart]

Much simpler to just add one to the depth and continue, (or redo the null-move search at that larger depth, although I expect that to be a real waste of time), rather than returning alpha. Then you are not dependent on any assumptions on when re-searches are triggered, and it saves you a pointless return - test - call.

True. That's what I do now. With a little detail to heed though: increasing the depth will be a problem if you have search extensions (you risk doing double extensions...). Instead I set a flag and force extension of all moves at this node.

[hgm]

Well, increasing the depth is not an extension, but just taking away the reduction, right? If you want an extension in one of the moves that lead from the node, (e.g. because it delivers check), it should increase the depth by another ply (for that move).

This is what Stockfish does (albeit in a clumsy and kludgy way). If you do it differently, it is not equivalent to normal LMR.

[lucasart]

Well, increasing the depth is not an extension, but just taking away the reduction, right?

Ah yes, I forgot that was all about nodes coming from a reduced search.

PS: Is that you in father Xmas ?

[hgm]

Indeed, that is me. (A few years ago; I think I have been using this picture as Christmass avatar for the past 4 years or so.)

[lucasart]

Well, increasing the depth is not an extension, but just taking away the reduction, right?

Ah yes, I forgot that was all about nodes coming from a reduced search.

PS: Is that you in father Xmas ?

In fact it's not the same. I did the experiment in SF and got different node counts. The point is that
- when the conditions are met (null move fails low, previous move was reduced, null refutation is connected to the last move, and other preconditions)
- returning a fail low triggers a re-search at full depth in the parent node. But this re-search will also try first razoring, static null move pruning, recursive null move pruning (amongst other things) before it returns to the same point.
- this explains why increasing the depth to cancel the reduction takes significantly more nodes

I'm currently testing a patch in Stockfish to get rid of this "hack". Quite simply, when all the preconditions are met, set a flag threatExtension = true. And extend all moves that prevent the threat move (ie. the null move refutation).

[hgm]

- returning a fail low triggers a re-search at full depth in the parent node. But this re-search will also try first razoring, static null move pruning, recursive null move pruning (amongst other things) before it returns to the same point.

OK, so Stockfish does stuff before null move. Obviously you would then have to jump back to redo that stuff too, at the latger depth.

But surely, if a move is not eligible for razoring, static null-move pruning etc. at the reduced depth, (as the fact that you did complete a null-move search there), it will also not be such at the full depth? Usually razoring and pruning margins increase with depth. My engines do stuff too before null move, like detecting check and King capture. But that is not depth dependent. The more you do, the more you gain by not doing it twice!

I already mentioned that to get exactly the same tree you would have to redo the null-move search at the increased depth. I just expressed my doubts that this would be a good thing to do.

[jdart]

I have a trace mode that will dump out the whole search tree, with evals at each leaf node, and a record of all pruning, extensions, etc. This might help see where and when the high score is getting generated. (In this case since that happens after a million nodes or so, it would be a big log file, but not unmanageable, I think).

--Jon