Mate potential from pairs of pieces [chess variants]

[Evert]

This week I added a bit of code to Sjaak to determine at startup whether a pair of pieces is able to force mate against a lone king (it already had code to detect whether a lone piece was able to do it). It does this by static retrograde analysis: from a checkmate position, it works back to the previous position(s) and tests whether there is a piece configuration that allows the piece delivering check to control all other escape squares and be able to deliver mate on the next move. If that is never possible, mate cannot be forced and the combination of pieces is flagged as such.
This does not, of course, identify whether it's possible to drive the lone king to the corner. Only if mate is possible once it gets there.

For normal chess, this correctly identifies

Code: Select all

 0 Knight N (N,n)
   Cannot deliver mate alone
   Can deliver mate with help of B 
 1 Bishop B (B,b)
   Pair bonus
   Cannot deliver mate alone
   Can deliver mate with help of N B 

For Spartan, I get

Code: Select all

 0 Knight N (N,n)
   Cannot deliver mate alone
   Can deliver mate with help of B L 
 1 Bishop B (B,b)
   Pair bonus
   Cannot deliver mate alone
   Can deliver mate with help of N B L 
 9 Lieutenant L (L,l)
   Pair bonus
   Cannot deliver mate alone
   Can deliver mate with help of N B L 

which is not very relevant since BL and NL never occur on the same side. It nevertheless looks plausible to be, although I haven't tried KNLK to see how difficult it would be.
For Courier chess, I get

Code: Select all

 0 Knight N (N,n)
   Cannot deliver mate alone
   Can deliver mate with help of B W 
 1 Bishop B (B,b)
   Pair bonus
   Cannot deliver mate alone
   Can deliver mate with help of N B F E W 
 3 Ferz F (F,f)
   Pair bonus
   Cannot deliver mate alone
   Can deliver mate with help of B W 
 4 Elephant E (E,e)
   Pair bonus
   Cannot deliver mate alone
   Can deliver mate with help of B W 
 7 Wazir W (W,w)
   Cannot deliver mate alone
   Can deliver mate with help of N B F E W 

and here I am surprised. Although false positives here don't really hurt (Sjaak just won't recognise the draw, but it won't do that without this code anyway) I am curious about some of these. What I find particularly interesting is that KFWK can force a mate (as can KWWK) while KFFK cannot. Similar KWNK and KEWK.
So now I'm curious, does anyone know whether these endings can indeed be won?

[hgm]

You can use fairygen...
KWWK should not have forcible mates. KFWK has some long mates, but is general draw. KNWK is general win.

[Evert]

You can use fairygen...

Yes, indeed.
I completely forgot I have it waiting for me to look at.

KWWK should not have forcible mates. KFWK has some long mates, but is general draw. KNWK is general win.

Thanks for that!
Of course, if the "not forcible" part is due to not being able to drive the king to the corner, there's not much I can do about that. However, I think I've found a blind spot in the implementation of the algorithm: it assumes that the checking piece is safe while defending the alternative escape squares before delivering mate. I suspect that's not always true, especially when dealing with pieces like the Wazir and the Ferz. The fix is to exclude squares attacked by the defending king but not by either of the other attacking pieces as possible prior locations for the mating piece.
Not too difficult to add, but I may not get to it before the holidays...

[hgm]

In KWWK there are no mate-in-2 because W cannot get from c1 to a1 in3 moves.

[Evert]

In KWWK there are no mate-in-2 because W cannot get from c1 to a1 in3 moves.

Is that a necessary and sufficient criterion?
Anyway, the algorithm currently finds (using R for the wazir)
[d]8/8/8/8/8/K7/1R6/kR6 b - -
which then gets turned into
[d]8/8/8/8/8/K7/1R6/1kR5 b - -
by retrograde analysis. This is of course wrong because a) the position is impossible and b) 1... Kxc1 instead of 1... Ka1 2. Wb1#. The first is not so easy to detect in general but the second (and IMO more important) issue should be fairly easy.

[hgm]

c1 must be covered or he would not step to a1. After checking on b1 the piece covering it must checkmate on a1.

Mate on b1 is only possible with piece that forks a1, c1.

[Evert]

c1 must be covered or he would not step to a1. After checking on b1 the piece covering it must checkmate on a1.

Mate on b1 is only possible with piece that forks a1, c1.

Well, that is the basics behind the method: the square where the piece was found to deliver mate has to be a square that can be reached from a square from where all alternative escape squares are covered.
That's a generalisation of the same statement that should hold also if kings and pieces move very differently.
What I was wondering is whether your statement is more generally valid than I thought it would be.

[hgm]

It only holds for orthodox king. But W does not satisfy it: it cannot go from c1 to a1 in 3 moves (uncapt, noncapt, capt). With 2 W there is also no piece that can fork a1, c1, so no forced mates.

[Evert]

It only holds for orthodox king.

That's what I thought. I'll keep my current more general implementation.

But W does not satisfy it: it cannot go from c1 to a1 in 3 moves (uncapt, noncapt, capt). With 2 W there is also no piece that can fork a1, c1, so no forced mates.

Right; the only reason the code currently thinks that it's possible is because the illegal position I posted earlier is not detected as such.

[hgm]

Even if it was legal, it would be no good: c1 is not covered.
[d]8/8/8/8/8/RK6/1R6/1k6 w
is legal and mate after 1... Ka1 2. Wa2#, but it is a help mate because of c1.