Threat detection

[hgm]

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.

Well, reducing less is much more expensive then just sorting it earlier. If the move helps, it should already be apparent at QS level. A problem might be that interpositions are inherently risky, as the square you move to is known to be under attack, and you have no guarantee it will be protected. (In fact by moving there you just decreased the number of protectors by one, if it was not a Pawn move.) So the chances that the piece is simply captured to renew the threat is appreciable. And even if it succeeds, the interposed piece will now be soft-pinned, which creates a weakness.

Withdrawing the threatened piece is in general a better solution. Unless the piece itself was soft-pinned. For weak pieces, with few moves, (safe) withdrawal is often not possible, but such pieces are easily protected. Unfortunately it is quite hard to selectively geenrate moves that protect a given square. Anyway, these type of decision are a next step; first the threat has to be identified.

And that is another weakness of the Stockfish method you describe: the move that refutes the null move is very often (perhaps usually) not the threat, but just an unrelated trade of a higher piece, so that preventing it buys you absolutely nothing. This is the problem that has to be solved first, before it can be judged whether any particular counter measure to the threat is beneficial.

If there would be multiple independent refutations to the null move, there is nothing you can do anyway. Your real moves will also fail low, because the opponent will cash at least one of the threats. You cannot do something smart here, as you won't be made aware of the second threat. But if you fail low, it also doesn't matter much how you sort the moves. (It would hurt to reduce less, though.)

[Ras]

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

Upon closer re-evaluation, there's one gotcha hidden here. If the null move "refutation" is a quiet move, then it doesn't really refute, it just carries on the game (e.g. castling).

Ranking these kinds of moves too high actually costs performance because they don't refute "stupid" moves that would cost material, and if a quiet null move refutation is tried before the captures in the next depth level, it will take longer to get the desired cutoff.

So I've changed the plot to look whether the null move refutation is a non-capture, and if so, I rank it above all other non-captures in the move list, but after the captures. If it is a capture, I don't change the MVV/LVA value.

The moment when to decide whether it is a capture or not isn't during the null move search, but when generating the relevant reply move list in the next non-null depth level because the captured piece may already have moved by then.

In the 3 plies pre-search, which is easiest for me to compare because of its low complexity, this gives 10% fewer nodes than always putting the null move refutation to the top of the relevant move list. In spectacular cases, it can even be 30% fewer. Sometimes 5% more, but about 10% fewer is average.

The interesting thing is that this helps performance especially in the late opening and early middle game when a lot of suitable quiet moves are available, but nothing really forced. Usually, that is something around 20k-30k nodes, but sometimes up to 120k nodes for this 3 plies root sorting alone. That's because every root move is searched with full window.

Do you think it might make sense to limit that window to +/- 200 cps? The move sorting would be less accurate, but maybe it would be sufficient to limit the pre-sorting to group the root moves into winning moves, equal moves and losing moves?

[hgm]

Upon closer re-evaluation, there's one gotcha hidden here. If the null move "refutation" is a quiet move, then it doesn't really refute, it just carries on the game (e.g. castling).

Ranking these kinds of moves too high actually costs performance because they don't refute "stupid" moves that would cost material, and if a quiet null move refutation is tried before the captures in the next depth level, it will take longer to get the desired cutoff.

The fact that the null-move refutation was a non-capture implies that all captures failed low. So it seems that you would only have to try new captures here (capture of the moved piece, or over the square that it evacuated), or captures that went up in SEE because a protector was moved away. (Or got pinned over the evacuated square...) OK, that can get pretty complex, but the more complex the situation, the rarer it will occur. And a mistake in move ordering is never fatal. So I would still be tempted to only try capture of the moved piece, or over the evacuated square (so forget about the protection stuff), then try the quiet null-move refutation, and only then try the pre-existing captures (which failed low in the null move) in MVV/LVA order. The latter speculates on the idea that a piece might have losed its protection because of the preceding move, and did not have enough other protectors, so that the capture will now be more profitable.

Problem is that the null-move non-capture refutation might be pretty marginal, not at all the best quiet move. (You take the first that happens to work.) A real quiet move might have some positional gain, and require a better refutation. So sticking to the null-move refutation is risky. With normal killers each quiet move that needs a quiet refutation (because it was not stupid enough to blunder something away), would continue to search for a better one that does the job. Which will then be promoted to killer, and tried in all sibblings untill an even better one is needed. Which will then replace it as killer, etc. So after having searched a few quiet moves, you probably have a better killer than what you got from the null move.

So perhaps it would be better to bet on the normal killer, rather than a quiet null-move refutation, assuming that this is a generally better quiet move, which also would have worked better for the null move. Children that come up with an improved killer only do so because all captures failed low (just like in the null move), and the previous killers as well. It could of course be that the move to refute specifically targeted the killer, e.g. by attacking its to-square. Perhaps it is beneficial to keep some killer statistics, count the number of successes, and assume that the killer with the best track record would also have been the best null-move refutation.

So I've changed the plot to look whether the null move refutation is a non-capture, and if so, I rank it above all other non-captures in the move list, but after the captures. If it is a capture, I don't change the MVV/LVA value.

This sounds like the normal killer heuristic.

The moment when to decide whether it is a capture or not isn't during the null move search, but when generating the relevant reply move list in the next non-null depth level because the captured piece may already have moved by then.

Well, if it is a capture in the null-move search, and not now, it means you are moving to a square attacked by the piece that was there after the null move (which can move back to capture you). This does not soud very advisable.

Do you think it might make sense to limit that window to +/- 200 cps? The move sorting would be less accurate, but maybe it would be sufficient to limit the pre-sorting to group the root moves into winning moves, equal moves and losing moves?

Even that sounds very generous. In principle you are not interested in moves that give away material at all. Basically you want to search everything that is within ~50cP from the best move, to get a good sorting of the early part of the move list.

[Ras]

The fact that the null-move refutation was a non-capture implies that all captures failed low. So it seems that you would only have to try new captures here

Mh yeah, but that would require quite some rewrite, especially since there is no kind of tracking of moving piece vs. null move. I'm not sure whether this tracking would break even. And SEE isn't there anyway right now.

And a mistake in move ordering is never fatal.

Yes, it's just about itching out a bit more performance.

(You take the first that happens to work.)

Not in the pre-sorting, which is pretty important because it influences the move ordering also in the "real" search at depth level root-1. Since also the root null move refutation is scanned with full window, the null move refutation is actually the best move with depth 2 plies.

So perhaps it would be better to bet on the normal killer

That is also in place, though I'm not yet completely clear what has more influence. It's a bit hacky.. For the moment, it seems to me that the null move refutation was overvalued, ranking it always to the top after hash and PV move.

Well, if it is a capture in the null-move search, and not now, it means you are moving to a square attacked by the piece that was there after the null move (which can move back to capture you). This does not soud very advisable.

Good point. Just tried to only ramp up the null move refutation if it has been a quiet move both in the null move search and also in the actual occuring move list, but that doesn't seem to have noticeable influence on the node count.

Basically you want to search everything that is within ~50cP from the best move, to get a good sorting of the early part of the move list.

OK, so the basic idea to limit the window isn't that bad. The issue is that I don't know the "best" move when starting the sorting, but I can use mini-pre-pre-search of 1 ply plus QS to get an idea what the current eval should be.

I'll have to check out how that interacts with the optional CPU throttling, which only kicks in after the pre-sorting; the pre-sorting in itself already gives a semi-decent move along with a mini-PV in that mode. But I guess there won't be that many winning moves in the same position, usually it's only one anyway.

Thanks.