Early killer

[hgm]

There is a thing I don't like on the standard killer heuristic. The problem occurs in a situation where a profitable non-capture comes just within the horizon. E.g. a fork attack. When you need such a move to fail high, you would have been failing low in QS and d=1 in that position, as at d=1 the opponent ignores the threat and happily stands pat. At d=2 the opponent will have to reply to the move, and this will reveal that whatever he does, we initiate an exchange in QS that gains us enough to fail high.

Since in previous iterations we have been failing low, the opponent, in the (now) d=3 parent will have been failing high, and counts on it being a cut move. His former cut move (which often would be a null move) now will fail low. That means he will have to try alternatives he never tried before. Either at d=3, or, in the null-move case, even at d=3+R.

Now most if he has a capture available to finish us off, he will try that first, and we are dead after all. But if we can survive the few tactical moves he throws at us, he will get to his non-captures. Most of the non-captures do nothing substantial, and it is for refuting those that the killer heuristic was designed. The same fork that refuted his former cut move will now very likely also refute these other moves.

The problem now is that captures are searched before killers. We also did that against the former cut move, only to find that none of those was any good. Or we would not have needed the non-capture fork in the first place. Against the truckload of passive moves they will likely face the same fate. When we are now searching at d=2+R the pain can be ameliorated a bit by at least starting IID at d=1, so the captures are discarded relatively cheaply, after which we get to the fork (which became killer for this ply), and only deepen that to d=2+R.

If the former cut-move was not null, we now search at d=1, however, and searching N extra captures before the killer will drive up the cost (N+1)-fold. The question is whether this can be avoided.

Always trying the killer before the captures is not a good idea (which is of course well known), because it makes us waste time on a relatively quiet move when the opponent initiates tactics to which we have to respond. So the question is whether it would be possible to do some educated guessing as to whether the previous opponent move requires immediate tactical response, or whether this would be only a distraction for our long-term plans.

E.g. one could think of always using the standard move ordering when we have a good capture (e.g. SEE-wise) on the moved piece, but in absence of this, try the killer first. To ameliorate the impact cases where it backfires, we could communicate such a failure to sibbling nodes (e.g. by adding success/fail counters to the killer array, reset when we enter the parent).

Any thoughts?

[brtzsnr]

Some engine order killers before bad captures which I believe is in line with your idea: try killers as early as possible. Hash is quiet occasionally which also helps with strong quiets before captures.

I could not find a good implementation for "killers before bad captures" so I still put killers after all captures.

[hgm]

I thought that engines that recognize bad captures even put those behind the non-captures. So that would certainly be behind the killers. If you search killers before bad captures, it makes sense to allow bad captures to become killers.

I actually also wanted to put the killer before the good captures, in situations where all good captures likely lose material. After all, the killer would never have become a killer if any of the good captures searched before it would have been any good. So almost always all good captures would fail low, while the killer would fail high, replicating the behavior in the node where the killer was found.

You don't have to gamble on that the first time, though. If a typical position has 6 captures, and 30 non-captures, the d=3 search (turning into an all-node) will find its captures refuted by retaliation captures, and then get to the non-captures. When these need killer refutation, keeping statistics on the killer performance will tell you pretty quickly whether you are dealing with a sufficiently general killer. E.g. if the first 5 of the non-captures had all good-capture replies fail low, but the same killer do the job, it would seem logical to try that same killer first against the remaining 25 non-captures. (Or at least as long as its perfect track record lasts.)

[Evert]

I actually also wanted to put the killer before the good captures, in situations where all good captures likely lose material. After all, the killer would never have become a killer if any of the good captures searched before it would have been any good. So almost always all good captures would fail low, while the killer would fail high, replicating the behavior in the node where the killer was found.

You don't have to gamble on that the first time, though. If a typical position has 6 captures, and 30 non-captures, the d=3 search (turning into an all-node) will find its captures refuted by retaliation captures, and then get to the non-captures. When these need killer refutation, keeping statistics on the killer performance will tell you pretty quickly whether you are dealing with a sufficiently general killer. E.g. if the first 5 of the non-captures had all good-capture replies fail low, but the same killer do the job, it would seem logical to try that same killer first against the remaining 25 non-captures. (Or at least as long as its perfect track record lasts.)

Of course you don't know for sure that the good captures were possible in the position where the killer originated...
It might be worthwhile to try a type of "capture refutation": index the killer-move by the capture that you're supposed to want to make. This is more of a counter-move/history type of indexing, where you somehow mark the capture as "bad" and postpone it until after the killer.

[hgm]

You mayt not be sure, but it might be enough that it is likely. And you can weed out some obvious cases, like capture of the moved piece. That same capture was certainly not possible against other moves, and in particular against the earlier move that provided the killer. If you want to be smarter you could also exempt captures that go over the evacuated square. (Pin enforcement.)

Perhaps my thinking is a bit colored by working on huge games. A move there can only affect a small minority of all the tactics on the board. So the probability that what worked in a sibbling node works now becomes quite large.

This suggests the following order:

1) good capture of the moved piece
2) good captures over the evacuated square
3) killers with a (very) good track record in sibblings
4) other good captures
5) other killers

An alternative would be just to test for the existence of (1) and (2), and if they do exist, use normal (e.g. MVV/LVA) ordering, with even successful killers after all good or equal captures, and only start with the killer if (1) and (2) do not exist.