Mate killer

[hgm]

I never used a mate killer before in any of my engines, but I now seem to have an application for it. I have this JavaScript universal chess-variant engine that is very slow (on large variants it hardly can search more than 1knps). Which is not a big problem, as the design goal it to provide an opponent that beginners still can beat. So a few ply search depth is good enough.

Without check extension the play is very unbalanced, especially because the King capture has to be within the horizon for a checkmate to be recognized. So at a search depth where it already outplays most humans for non-royal tactics, is still behaves like an idiot w.r.t. checkmates, and might not even recognize a mate-in-1 threat. With a check extension of a full move (for the evasion) there is a better balance, but it can require an unreasonably long time to recognize a mate-in-2 threat.

I had quite some trouble getting a speedup from using a killer heuristic for moves that lead to a forced checkmate. I guess the problem is that such moves are expensive to search, because of the extensions in their sub-tree (and you cannot checkmate without checking...). So searching them first might waste a lot of time in nodes after moves that would defend successfully against the threat. Especially since you cannot use Internal Iterative Deepening here, as searching at lower depth would usually not see the checkmate.

Another problem is verifying the alternative moves of the mating player will not lead to a quicker mate. If there is a mate in 2, you will have two mate killers, one at the current ply, and one at ply+2. If this line is searched first, and you leave both mate killers in the killer table, alternative moves at the current ply, usually lifting the mate threat, would for every reply of the opponent be followed up by an expensive search of the mate killer at ply+2, which without the proper preparing move is doomed to fail low.

This can be prevented by clearing the killer at ply+2 when any of the moves leading to it changes (conventionally done when you enter a new node at ply+1). But then, if after searching all your alternatives at the current ply, the opponent plays another non-defineding move at ply-1, and you have to refute it by the same checkmate, you have to rediscover the ply+2 killer by search.

Eventually I found a way out of this dilemma in the following way:

Instead of clearing the mat killer for ply+2 at the top of Search() for ply+1, I already clear it in the caller, just before MakeMove(). This allows this caller to test whether the move that is played is the mate killer for the current ply, so it can clear it only when that is not the case. To prevent I have to restore the ply+2 killer after it was cleared, I adopted the following search order:

After move generation a pass through all the moves is made to score them for (MVV/LVA) sorting. In this pass King capture is recognized, and leads to immediate return with a +INF score. The moves are also tested for being the current mate killer, and if this is found it will be copied to the end of the move list, and skipped for now. This to make sure no attempts to continue on the checkmate path are made if King capture is already possible. (Forced mates are usually forced by checks, or on a King confined by attacks all around it, so that most of the defender's moves stay in or step into check.)

After all other moves have been scored (and the preceding ply was found to be legal), the backlogged mate killer is then recognized as such, and searched to the nominal depth of the node. Should a mate score result, then we refrain from IDD, and search all other moves immediately at the nominal depth of the node (if there wasn't a beta cutoff already). If there is no mate score, the preceding ply was apparently a succesful defense against the move, and we start IDD with the best-scored move. This will clear the ply+2 mate killer.

If after this the opponent again tries a non-defense at ply-1, the search will have to rediscover the ply+2 mate killer. But it is better to have to do that once after all non-mating alternatives have been searched, than trying a stale mate killer on each of those alternatives with no hope for success. And in face of a mate-in-2 threat most moves will not be defenses against it, and would be refuted by the first line searched (guided by the mate killers at ply and ply+2), and leave those in tact. Only after the occasional successful defense you have to rediscover the ply+2 mate killer.

This gave a nice speedup for finding the mates.

[hgm]

I am starting to wonder now whether this same scheme would also be suitable for storing cut moves in general. Especially in large variants, where you start with many ranks filled with pieces, a large fraction of the moves will be with pieces that jump around in their own camp. Which might affect the game somewhere in the far future, but on the short term are effectively indistinguishable. Any sequence of such moves can be refuted by the same series of cut moves, which could be stored in a killer table. As long as you play the cut move from this table, the moves at the higher ply levels remain applicable. If you are forced to deviate, becasue the tabulated killer for that level no longer exists, or fails low, you would clear the killer at ply+2, so that you don't have a cut move to play there, which will cause clearing of the killer at ply+4, etc. So you will never meet a non-applicable killer that would distract the search to a useless move.

This could be better than playing the hash move obtained from the previous iteration of iterative deepening. Because that iteration might not have been deep enough to find the refutation. But as soon as you have found once sequence of cut-moves that does the trick, it would be used in all parallel branches of the refutation tree. (Which might not have been searched in the previous iteration, where this sub-tree failed low rather than high because you did not have enough depth.)

[Mike Sherwin]

I'm back! Thanks!!

This is all too complicated for me to make an intelligent comment about. So I'll comment on something related. A long time ago now I experimented with counting beta cuts and then checkmates for each root move in an otherwise material only searcher. Mar author of Cheng tried the beta cut counting for move ordering and reported +20 elo. I demonstrated counting checkmates enabled an otherwise material only searcher to intelligently progress towards giving checkmate. I have not yet counted null move failures (threats) to see how that would work.

I seem to remember that in at least one of your engines you do iterative deepening for every node. I'm guessing that is for better move ordering. That is iirc. If you are doing iterative deepening for every node then why not count things for every node. If you counted every move for white and every checkmate and every move for black and every checkmate you can use that info to modify a moves score for better move ordering. Just an idea. Thanks again!

[hgm]

Indeed, in most of my engines I do IID in every node. And often in a very suspicious way, where I immediately deepen a cut move, but if at some stage it starts to fail low, resume the IID by continuing the iteration where it first failed high. In the presence of a hash table this is usually effectively a no-op, though, as in a stable search all attempts to search the non-final iteration would be provided by the hash hit on the result of the previous root iteration, and you would only have to do the final iteration, like you weren't doing IID at all. But it speeds up searching unexplored parts of the tree, where you then find cut moves at very low depth.