how to track down a BUG?

[Kempelen]

thank you everyone for the help you give me!
I was inspired by stockfish code where they return beta-1 if the move that make a checkmate and the previous move are "connected".

Can sameone tell what is a connected move and and why that check is needed before returning beta-1?

[elcabesa]

thank you everyone for the help you give me!
I was inspired by stockfish code where they return beta-1 if the move that make a checkmate and the previous move are "connected".

Can sameone tell what is a connected move and and why that check is needed before returning beta-1?

it's the move that make be possible the threat move.

for example the same piece is moved, the square of arrive is vacant from the previous move, the piece was in the slide path of the attacker and so on

this is from stockfish code

Code: Select all

// connected_moves() tests whether two moves are 'connected' in the sense
  // that the first move somehow made the second move possible (for instance
  // if the moving piece is the same in both moves). The first move is assumed
  // to be the move that was made to reach the current position, while the
  // second move is assumed to be a move from the current position.

[lucasart]

Anyway, HGM is right. This whole thing is "clumsy". It may look smart because it's rather complicated, but complicated is not always synonym of better. I have found a significant improvement over this method already. And my test results are being confirmed by Marco and Gary -- looking good so far.

So you probably shouldn't take this Glaurung/SF trick of returning a fail low as an example of how to handle the null threat best. However the prevents_threat() and yields_threat() (used to be called connected_moves()) are quite nice ideas:
- moves that prevent the threat move should not be brutally reduced/pruned. At least not at low depth (when depth increases, the way to prevent a move can be with more complex tactics than just preventing it "geometrically" on the board).
- precondition of connected moves and previous move reduced are in order to adress LMR tactical mistakes. It's at the parent node that we may be missing some winning tactics by reducing the search (and ending up with a threat that the opponent has difficulty to refute). These preconditions were probably introduced (by Tord in Glaurung) because doing it at every node is far too costly, so focusing on connected moves is a nice idea, if we want to mitigate the tactical mistakes of search reductions near the leaves.

[Michel]

Anyway, HGM is right. This whole thing is "clumsy". It may look smart because it's rather complicated, but complicated is not always synonym of better. I have found a significant improvement over this method already. And my test results are being confirmed by Marco and Gary -- looking good so far.

Just to clarify.

IMHO this is not a cleaner implementation of what Stockfish does. And neither is it an implementation of HGM's idea (which, if I understand correctly, is to remove the reduction of an LMR'ed move under certain conditions). It is something else.

I think the basis of the quoted idea is that even if the null move fails low there is a fair chance that the threat may be refuted later in the reduced search. So the continued search might well fail high (which is a fail low in the parent, so no research). Testing apparently shows that this gamble pays off.

I wonder if this is really dependent on extending the threat avoiding moves.

[michiguel]

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)

(bold is mine)
It doesn't if you have sidetomove_bonus in your eval.

Miguel

- 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).

[michiguel]

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).

There is one fundamental difference (not necessarily better or worse):
Tord's way: the reduction is removed in the parent node by re-search. Your way: it's is done in the child's node. So, if the search turns successful, when it returns to the original parent's node it will also trigger a research, effectively doing an extension since the child was not reduce (the parent does not know that).

Miguel

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

[Michel]

effectively doing an extension since the child was not reduce (the parent does not know that).

It seems to me that the child could easily communicate this to the parent in some way....

[hgm]

And neither is it an implementation of HGM's idea (which, if I understand correctly, is to remove the reduction of an LMR'ed move under certain conditions). It is something else.

'Removing the reduction' is just another way of saying 're-searching at full depth'. So I think it is fully equivalent to standard LMR. (No idea what Stockfish exactly does, of course.)

Immediate re-search of the same move is always wasteful, involving a needless return and call, with possible loss of things calculated during initialization. This is even more severe with PVS researches, where you lose the generated moves, and have to recreate the move list when you re-enter the node for re-search. So in PVS my engines also do not return a fail low of the null-window search (which in the parent would be the fail-high that triggers re-search), but instead open the window themselves (lowering alpha) and then iterate through the existing move list again.

[michiguel]

effectively doing an extension since the child was not reduce (the parent does not know that).

It seems to me that the child could easily communicate this to the parent in some way....

It could return a "reduction_erased" flag.

When I tested a similar idea once (did not work) I did the null move test in the parent node.

If think returning alpha in this cases very dangerous and should be avoided IMHO. It makes a piece of code extremely dependent of whatever is happening somewhere else. If you make a simple modification, the whole think could break very badly. For instance, you decide to test NOT to research on LMR moves, and the whole thing falls apart

Miguel

[lucasart]

Anyway, HGM is right. This whole thing is "clumsy". It may look smart because it's rather complicated, but complicated is not always synonym of better. I have found a significant improvement over this method already. And my test results are being confirmed by Marco and Gary -- looking good so far.

Just to clarify.

IMHO this is not a cleaner implementation of what Stockfish does. And neither is it an implementation of HGM's idea (which, if I understand correctly, is to remove the reduction of an LMR'ed move under certain conditions). It is something else.

I know. But it's more efficient, because extending the whole node (directly, or indirectly, by making the parent node call back at full depth) is a waste of time.

It's better to selectively extend the moves that prevent the threat (this is at low depth only). Testing confirms (Marco, Gary, and I tested separately, and all got positive results):
https://github.com/mcostalba/Stockfish/ ... a5b6ba0190