delaying tactics: prune or extend?

[hgm]

[d]5rk1/5ppp/N7/1p6/8/bP5q/Pr3R2/4QRK1 b
I am worrying about positions like the one above, where one of the players can force a perpetual, but doesn't want to. The problem is that there is nothing to stop it from playing half the perpetual (i.e. a single check + evasion, on g3 and h3 alternately) in any position in the near future. So if there is some unsolvable threat against it, it can try to push it beyond the horizon by interjecting a check every other move, doubling the depth at which the threat becomes apparent.

Now check extension ameliorates this a bit, but it still doesn't make checks completely free. If the check + evasion are only eating 1 ply from the remaining depth, we still need 50% more depth to see the threat. To not hurt we would have to extend both the check and the evasion.

This, however, is extremely expensive, as well as unstable. (It opens the possibility for infinite recursion.) It seems very bad to spend so much search nodes on what basically is pointless delay. It is much more enticing to prune moves that are pointless.

It is quite hard to judge when these interjected checks are pointless, though. In the given diagram there is for instance the possibility to have the Queen check at g4-h5-g6 to pick up the unprotected Knight on a6. And that is something we would prefer to see as quickly as possible. Rather than hiding it forever by pruning the checks. And the Knight could have gone there long after the perpetual became possible, so that what was pointless checking before alters into deep tactics gaining a piece.

Extending both checking and evasion effectively merges a node with all nodes that can be reached from it through such doubly-extended check+evasion pairs into one node. Even if just one check was extended that (for the back-and-forth moving of the Queen between g3 and h3) it would double the branching factor in the nodes where the checker has the move. Superficially this would drive up the EBF by sqrt(2) = 1.41. But in many cases this will be transpositions: 1. Ra8 Nc7 2. Qg3+ Kh1 3. Rc8 Nd5 4. Qh3+ Kg1 from the diagram would lead to the same position as 1. Ra8 Nc7 2. Rc8 Nd5. So one can hope that the tree would just double in size compared to one where the Queen could not move between g3 and h3 at all: for each position with a Queen on g3 there would be a corresponding one with the Queen on h3.

In fact we could have the search bootstrap itself into doing this without allowing a real double extension, by counting on over-deep hash hits. If the situation exists in the root, it would be sufficient to only extend checks in the root (where normally we would only extend evasions). Or, more conservatively, doubly (instead of singly) extend evasions at the 1-ply level. We can the be more conservative, and only do this with evasions that are not captures. (As these would certainly not be perpetuals, at least in games without piece drops.) This would then search the position after the first check+evasion always (i.e. in any iteration) as deep as the root position itself. So we get two trees, deepening in parallel.

If a check at a deeper level would transpose from one tree into the other, it would hit upon a position that was searched on behalf of the other tree to a (remaining) depth equal to that before the check+evasion (if that other tree had already been searched at the current root depth before the currently searched move), or one ply less (if it has not yet been searched, but was searched in the previous root iteration). Both depths are sufficient to satisfy the hash probe, which requests a depth that was also lowered by one, because of the check not being extended. So although we do not actually extend the checks that are part of the perpetual cycle, they will often represent the result of a deeper search. If you transpose from the tree that was searched first into the other, you will lose a ply of depth, but you can only do that once. Transposing back would not loose anything, and would even gain back the depth if that particular branch of the first tree would already have been searched.

The cost of this double evasion extension at ply 1 seems manageable, especially since it would never been done on 'nonsense checks' refuted by a capture. And there is never any risk that it could explode the search by infinite recursion. The problem, however, is what to do if the first possibility to start the perpetual is not in the root, but occurs at a deeper level.

[mkchan]

So I see the problem being that in order to tell that the perpetual is still available at any depth down the search tree, you have to actually search for the perpetual again. Reason being situations where the other side can introduce a potential (or actual) check blocker (for example if white had a light squared bishop which can completely stop the perpetual).

To mitigate this, one probably needs to come up with a sort of quick checker if a perpetual available on a previous ply is still applicable and if so, prune that branch entirely.

[Rein Halbersma]

In Stratego, there is a similar problem with such interposing attacks that lead to nowhere. There is the rule that you can't do more than 3 consecutive moves with the same piece between 2 squares. To implement this, the position struct keeps track of a small circular buffer of the last 3 squares per player. If red has a piece diagonal of a blue piece, he can never gain this by attacking it, as the blue piece can evade 3 times after each of the 3 attacks, and the attacker has to stop because of the mentioned 2 squares rule. However, these interposing futile attacks, will triple the search depth to find deep tactics.

What you could do during move ordering is to put a repeated attack over the same 2 squares at the end of the move list (or maybe just in front of losing captures, but behind all the quiet moves). Then LMR will reduce the search depth and will search other moves more deeply first. Eventually, the interposing attack is searched, but at a reduced depth, and after the first repetition the TT will have this position with a higher depth already.

Your counter-example of the g4-h5-g6 maneuver is still handled OK with such a scheme, since the black queen keeps checking from different squares. However, after h4-g4, the next black move g4-h4 would still be pushed to the back of the move list since it repeats over the same 2 squares. You might want to tweak this scheme a bit, e.g. by ordering all repeating checks as long as the static eval is > 0 (you do want to try perpetuals if you are behind...).

[Rein Halbersma]

@hgm, you post a lengthy analysis, two people respond, and then you drop the subject? Nothing of interest to comment on?

[hgm]

It is not my intention to drop it, but I was very busy with other things the past days, and this requires some quiet thinking. I will get back to it.

[Rein Halbersma]

Thanks, looking forward to it. You have a knack for raising such intricate points.