'Analogy grafting' and the horizon effect

[bob]

You should read the paper Botvinnik and/or Donskoy wrote back in the 70's, "the method of analogies." It sounded pretty good, but it was way too expensive back then. I think this might have been Botvinniks paper now that I think about it, the one where Berliner excoriated him in the JICCA and called him an outright fraud... Berliner proved that his examples were fabricated, even though the underlying idea seemed reasonable.

Georgy Adelson-Velsky, Vladimir Arlazarov, Mikhail Donskoy (1975). Some Methods of Controlling the Tree Search in Chess Programs.
has chapter 4 Method of Analogies, reprinted 1988 in Levy's Computer Chess Compendium

see also
http://www.stmintz.com/ccc/index.php?id=19469

Thanks. I knew it was either in a paper by them or the "chess, computers and long range planning" book Botvinnik wrote.

[hgm]

An interesting exmple for how the technique works / fails is the following position:

[d]k7/1p3Rpp/pPpp2Pr/6r1/8/8/8/K7 b

At 1 ply any black move looks good, at 2 ply black would see that most moves get him mated through Rf8#, and that moves like 1... Re5 aiming to interpose won't help, as Rf8xe8# is searched in QS. So for the non-checks it has to resort to 1... Rf5 to keep the mate at bay. Which at least at 2 ply pushes the mate over the horizon at the cost of a Rook (2. Rxf5), after which black can stand pat.

Now the idea is that check-evasion pairs like 1... Rg1+ 2. Ka2 would create an analogy, so that moves like 2... Kb8, 2... a5 etc, which would consume the second ply (as white's evasion was extended), and thus normally push the 3. Rf8# over the horizon in a 2-ply search, would be recognized as fatal by analogy with the position without the check: the latter would be in the TT as a mate-in-1 through a 1-ply search with a non-capture hash move. That is good.

Unfortunately, moves like 2... Re1 break the analogy. As a human you would recognize this move as a (somewhat weaker) analogy of 1... Re5, but moving the Rook from g5 to e5 does not alter the hash key in the same way as moving it from g1 to e1. So when we probe the TT for the analogy, we get a miss. In QS white then won't see 3. Rf8+, so that the check still seems to have solved the mate threat, which is exactly what the method aimed to prevent. In fact even silly moves with the checking Rook, like Rg1-g4, or Rg1-c1 would all break the analogy.

So I guess the method would have to be refined a bit to be useful in cases where the checking piece survives the evasion. (For true spite checks, where the checker is captured, we would not have this problem.) When the analogy mapping was first defined by (Ka1-a2, Rg5-g1), when Rg1-g4 is played it should be redefined as (Ka1-a2, Rg5-g4). It is still just a displacement of two pieces, after all. So we should remember not only the hash-key 'delta', but also which pieces were displaced to obtain it, so that we can correct it later when such pieces move again. Then the position after 2... Rg1-g4 would be analogous to the original position, but with white to move. Presumably null move would also have been searched from the start position, and have been found to get black mated.

The move 2... Rg1-f1 would be a bit tricky, though. It would also redefine the analogy to make the position after it analogous to the starting position with white to move, which was a mate-in-1. But now it isn't a mate-in-1, because Rf1 x-ray protects the mating square, like after 1... Rf5. So it seems we should not be too generous in redefining the analogy after another move with the checker to a square where it could not have moved in a single move. We should make that subject to the condition that the new location of that piece is not tactically connected to the hash move of the new analogous position. This hash move was Rf8#. So moving Rg1-f1, which makes it cover f8, should definitely be seen as an essential breaking of the analogy, and prevent redifinition of the mapping. That means no analogy would be found in the TT after 2... Rf1, so that we enter normal QS, and white plays 3. Rxf1, which would be the correct result (at this depth).

So initially the checks would be effectively discarded as pointless, and at 4 ply it would be seen that 1... Rf5 2. Rxf5 non-check 3. Rf8# would not limit the damage to loss of a Rook, but would just delay the mate. Repetitive checking
(1... Rg1+ 2. Ka2 Rh2+ 3. Ka3 Rg3+ 4. Ka4 Rh4+ 5. Ka5, which is as far as we get in a 4-ply search) still have not led anywhere, and the analogy with positions without the checks will still recognize it as a mated-in-2.

Although this is what the method aims to do, in this particular case it is of course wrong, because eventually the repetitive checks do lead to mate (5... Rg5#). We do need 5 ply to see that, however. (And even 6-ply if we don't deal with the futile interposition of the Rook on the f-file, which does not help after the last check because the interposed Rook will still be captured in QS with mate as the side effect, but would eat a ply if we do it earlier, say on f1.) This is critically dependent on the presence of the Pawn on d6, however: without that the white King would eventually find shelter from the checks on c7. There is no way this could have been predicted without the actual search.

Some heuristics could help here. Like that on an emptyish board, checking by a single Rook is pointless (the King will march towards it), checking by a single Queen is drawish, checking by two different Rooks is matish. Then, in the case where the decision is between mating and being mated, (which should be a pretty rare case, btw), it might be a good idea to extend. Perhaps one should always extend checks (in addition to the evasion) with a new piece after the King stepped out of a check, so that these 'hand-over-hand' Rook mates would be followed to completion even at 1 ply.

[Aleks Peshkov]

1) Search should fastly discover the mate in one after black null move and there is no sensible defense to Rf8 is present. IMHO moves that try to defend from a concrete threat after null move should be investigated first by any sensible chess engine and this position should not be allowd to stand pat.

2) Search should be guided by evaluation. King safety of both black and white kings should extend the search here (and posibly earlier during search to this position as it is very unnatural).

3) It is possible to create special mate search towards lone king, but I am not sure that it gives much Elo points.

[Aleks Peshkov]

You should read the paper Botvinnik and/or Donskoy wrote back in the 70's, "the method of analogies." :) It sounded pretty good, but it was way too expensive back then. I think this might have been Botvinniks paper now that I think about it, the one where Berliner excoriated him in the JICCA and called him an outright fraud... Berliner proved that his examples were fabricated, even though the underlying idea seemed reasonable.

Georgy Adelson-Velsky, Vladimir Arlazarov, Mikhail Donskoy (1975). Some Methods of Controlling the Tree Search in Chess Programs.
has chapter 4 Method of Analogies, reprinted 1988 in Levy's Computer Chess Compendium

see also
http://www.stmintz.com/ccc/index.php?id=19469

I have read about it in a book about Kaissa engine by its authors.

As far as I understood it was a poor man's substitute to the lack of transposition tables in Kaissa. Kaissa had nominal 5 ply full-width search + QS at tournament time controls.

[hgm]

1) Search should fastly discover the mate in one after black null move and there is no sensible defense to Rf8 is present. IMHO moves that try to defend from a concrete threat after null move should be investigated first by any sensible chess engine and this position should not be allowd to stand pat.

I agree about prioritizing selected defensive moves. The problem with null move is that it might not always identify the real threat, however. Alpha-beta search is very 'lazy', and even in the presence of a mate-in-1 threat it might be happy with just grabbing a (protected) Pawn, recognizing it cannot be recaptured because that would be punished by the existing mate threat. And the gain of that Pawn might then cause a cutoff, and completely mis-identify the threat. It would then try to move the Pawn out of harm's way, rather than defend against the mate-in-1. Null move with a null window is just a poor threat identifier. Static threat identifiers have worked better for me (identifying all LxH captures and attacks on unprotected pieces), at least for material, but identifying mate threats that way is not easy.

The main problem, however, is how to handle the case where the losing side is delaying the inevitable by checks all the way upto QS. Stand pat can only be done in QS, but there you usually don't do a null move.

2) Search should be guided by evaluation. King safety of both black and white kings should extend the search here (and posibly earlier during search to this position as it is very unnatural).

Good point.

[Aleks Peshkov]

1) Search should fastly discover the mate in one after black null move and there is no sensible defense to Rf8 is present. IMHO moves that try to defend from a concrete threat after null move should be investigated first by any sensible chess engine and this position should not be allowd to stand pat.

I agree about prioritizing selected defensive moves. The problem with null move is that it might not always identify the real threat, however.

The quality of the threat move depends on move order. I disagree with common captures first, killers later approach. Some engines try mate-threat killer move before captures. If we assign probable gain to killer moves, then we can try dangerous killers before stupid recapture sequences.

The main problem, however, is how to handle the case where the losing side is delaying the inevitable by checks all the way upto QS. Stand pat can only be done in QS, but there you usually don't do a null move.

Losing side at tips of the search should be allowed to try only moves that destroy the threat move or make the known threat move gain less painfull. That way the losing side sometimes miss its own counter-threat due pruning, but will never fail high due horizon effect.