using connected moves for move ordering

[Rein Halbersma]

In Stockfish, the threat move that lets a null move search fail low is examined for a connection with the current move 2 ply higher in the tree, for the purpose of letting a reduced search there fail low so that a deeper re-search will be triggered there.

I wonder whether the reverse would be a good idea. Namely, during move ordering, one could (after the usual TT move, killers, good captures etc.) prioritize moves connected to the current move 2 ply higher in the tree. One could do this even conditionally on a null move being played 1 ply higher in the tree. So e.g. after Ra1-d1 null, prioritize all moves with the rook on the d-line, etc.

Has this been tried before, and if so, how did it test?

[hgm]

Usually, the null-move refutation in this case is a capture. So it would already be sorted in front. And if it is not in front of the capture ordening, it is usually for good reaon. If my Knight attacks a hanging Pawn, while QxQ is possible, the best way to collect the Pawn is to first trade Queens, and then take the Pawn. This avoids lots of tactical complications. Srting the NxP before the QxQ, because it was tactically connected to the move 2 ply earlier, would force you to go through all those tactical complications.

So the real problem is how to recognize that the Knight move does not deserve to be reduced, because it is actually instrumental in making the null move fail low. But you would not see that from the QxQ preferred null-move refutation, but only two ply later (e.g. N-move <null> QxQ RxQ NxP).

The NxP move is the first that gets you (in current eval) above beta in a way where he cannot get back.; the QxQ did get you up a lot higher, but the RxQ was a non-futile reply that countered this completely. So the NxP can beidentified as the crucial move in this branch, and the QxQ as just preparation.

But the problem is that there are other branches: if the <null> fails low, the RxQ is played in a all node, and many alternatives will be tried. They might not all continue with that same NxP. In fact, amongst these moves are those that save the Pawn in stead of recapturing the Queen, and they will not be refuted by NxP, but by withdrawing your Queen. But you can limit yourself to QxQ replies that are non-futile (i.e. capture enough to get you above alpha), which presumably will only encompass recaptures of the Queen. If these all are refuted by the same move (NxP in this case) you can back up the NxP as 'key move' towards the root. The rule then becomes that you have to look for tactical connection between the key move, and the move 2 ply earlier, rather than the cut move, and the move two ply earlier.

So:
1) A cut move is a key move of the cut node when all replies where futile.
2) If a cut move in node C has non-futile replies that all lead to cut nodes with the same key move, then that move is inherited by C as key move.
3) look for tactical connection between key move of a node and the move 2 ply before that node.

[Rein Halbersma]

Usually, the null-move refutation in this case is a capture. So it would already be sorted in front. And if it is not in front of the capture ordening, it is usually for good reaon. If my Knight attacks a hanging Pawn, while QxQ is possible, the best way to collect the Pawn is to first trade Queens, and then take the Pawn. This avoids lots of tactical complications. Srting the NxP before the QxQ, because it was tactically connected to the move 2 ply earlier, would force you to go through all those tactical complications.

So the real problem is how to recognize that the Knight move does not deserve to be reduced, because it is actually instrumental in making the null move fail low. But you would not see that from the QxQ preferred null-move refutation, but only two ply later (e.g. N-move <null> QxQ RxQ NxP).

The NxP move is the first that gets you (in current eval) above beta in a way where he cannot get back.; the QxQ did get you up a lot higher, but the RxQ was a non-futile reply that countered this completely. So the NxP can beidentified as the crucial move in this branch, and the QxQ as just preparation.

But the problem is that there are other branches: if the <null> fails low, the RxQ is played in a all node, and many alternatives will be tried. They might not all continue with that same NxP. In fact, amongst these moves are those that save the Pawn in stead of recapturing the Queen, and they will not be refuted by NxP, but by withdrawing your Queen. But you can limit yourself to QxQ replies that are non-futile (i.e. capture enough to get you above alpha), which presumably will only encompass recaptures of the Queen. If these all are refuted by the same move (NxP in this case) you can back up the NxP as 'key move' towards the root. The rule then becomes that you have to look for tactical connection between the key move, and the move 2 ply earlier, rather than the cut move, and the move two ply earlier.

So:
1) A cut move is a key move of the cut node when all replies where futile.
2) If a cut move in node C has non-futile replies that all lead to cut nodes with the same key move, then that move is inherited by C as key move.
3) look for tactical connection between key move of a node and the move 2 ply before that node.

Interesting points! There can indeed be delaying tactics that obscure the connection, and good captures will already be at the front. That is how things are done already, and perhaps the scope for improvement is little. Especially since *generating* connected moves is more expensive than *detecting* a connection between two moves.

But still, it's not about finding *the* refutation, it's only about generating all connected moves to finding *a* refutation as soon as possible, in case the TT, killers and good captures didn't fail high already. So for your N move followed by NXP example, there would be a lot more moves connected to the original N move. E.g also all moves to and ray attacks through the original knight's square would be candidates. All I'm saying is that they could be generated before moves unconnected to the knight's move. E.g. by given them a small bonus during move sorting, so that also good captures connected to an earlier move get sorted upwards compared to other equally good captures.