Mate killer
Posted: Wed Mar 13, 2024 1:34 pm
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.
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.