KBNK

[hgm]

Devoid of knowledge as it is, Fairy-Max never could mate with Bishop + Knight. It just allowed the King to escape to the wrong corner, and not knowing that it was the wrong corner, but knowing that Kings in corners are bad, it would trap it there forever, repositioning its B and N to avoid repetitions, until the 50-move axe fell.

Of course this can be easily prevented by adding the knowledge of what is the wrong corner for this specific end-game. Fairy-Max is intended to be a general, configurable variant engine, though, and in other end-games with color-bound unorthodox pieces, it would be really hard to know what is the 'wrong corner'.

I found an alternative, extremely simple approach, which seems to work. In Fairy-Max all light pieces + King have the same PST, which values a corner about 24cP below the center. I recently added code to detect a bare King in the root, and multiply its PST contribution by 5 in that case. (Each piece type already had its own 'PST weight', which was set to 0 or 1, and I just up that to 5.) That does greatly help driving a bare King into a corner with many light and super-light pieces. But it does not solve the wrong-corner problem.

So what I do now is that a move of a bare King at game level increases the PST value at its to-square by 5cP (so with weight 5 that is 25cP). Once it has been at a square, it likes to return there. If it has been there several times, it loves to return there. And of course the all-powerful opponent then tries to prevent that.

Code: Select all

if(pstWeight[piece] == 5) PST[toSqr] += 5;

So once having taken shelter in the safe corner, it very quickly starts to mark that corner where it is trapped as a very good place place to be, if there is no mate within the horizon. Aimlessly avoiding repetitions by repositioning B and N does not solve this, as the 'stay-put bonus' is only dependent on the bare-King location. The only way to deny it to him is forcing him out of the corner where he could afford to stay for some 10 moves without getting mated, and of course the dangerous corner and the approach to it still look as bad a place for it as ever, so the strong side will then switch to that alternative. In stead of painting himself into a corner, the bare King paints itself out of the corner! Once trapped in the unsafe corner, the mate comes within the horizon, and PST plays no role.

With this simple modification, it managed to effect a KBNK mate in 40 moves in self-play at 40/10' (where it searches about 18 ply, without null move, but with LMR. (And as there are no captures, only the hash move is not reduced, so this is basically 12 ply in most branches, as every all node counts for two ply.)

[d]8/8/8/8/4k3/8/8/KNB5 w - - 0 1
[pgn][Event "Computer Chess Game"]
[Site "hgm-xboard"]
[Date "2014.10.11"]
[Round "-"]
[White "Fairy-Max 4.8T"]
[Black "Fairy-Max 4.8T"]
[Result "1-0"]
[TimeControl "40/600"]
[FEN "8/8/8/8/4k3/8/8/KNB5 w - - 0 1"]
[SetUp "1"]
1. Kb2 {+6.39/19} Kd4 {-6.23/18 10} 2. Kc2 {+6.60/19 14} Ke4 {-6.45/19 12}
3. Nc3+ {+6.77/19 15} Kf5 {-6.55/18 11} 4. Kd3 {+6.77/18 9} Ke5
{-6.55/18 10} 5. Ne2 {+6.75/18 10} Kf5 {-6.61/18 13} 6. Bf4 {+6.82/18 13}
Kg6 {-6.72/18 8} 7. Ke4 {+6.79/18 17} Kf6 {-6.64/18 10} 8. Be5+
{+6.76/18 20} Ke6 {-6.63/18 14} 9. Nf4+ {+6.74/17 9} Kd7 {-6.59/17 9} 10.
Kd5 {+6.71/17 14} Ke7 {-6.60/18 16} 11. Kc6 {+6.77/18 15} Kd8 {-6.69/19 19}
12. Bf6+ {+6.92/18 10} Kc8 {-6.72/18 8} 13. Nd5 {+6.91/19 16} Kb8
{-6.71/19 8} 14. Nb6 {+6.88/19 16} Ka7 {-6.70/20 9} 15. Nd7 {+6.85/19 12}
Ka6 {-6.69/20 12} 16. Bd8 {+6.82/19 16} Ka7 {-6.68/21 13} 17. Bb6+
{+6.83/19 8} Ka8 {-6.68/21 9} 18. Nf6 {+6.82/19 7} Kb8 {-6.67/21 17} 19.
Bc5 {+6.79/19 19} Kc8 {-6.66/19 13} 20. Bd6 {+6.88/19 14} Kd8 {-6.65/20 12}
21. Nd5 {+6.87/19 10} Kc8 {-6.68/20 13} 22. Be5 {+6.90/19 11} Kd8
{-6.69/20 26} 23. Bf4 {+6.91/19 13} Kc8 {-6.89/20 9} 24. Ne7+
{+79.73/20 12} Kd8 {-6.98/21 11} 25. Kd6 {+79.80/20 9} Ke8 {-79.78/21 20}
26. Bh6 {+79.82/20 15} Kf7 {-79.88/21 8} 27. Bg5 {+79.87/20 10} Ke8
{-79.89/21 10} 28. Kc7 {+79.87/20 13} Kf8 {-79.88/22 18} 29. Kd8
{+79.88/21 8} Kf7 {-79.89/23 17} 30. Kd7 {+79.87/21 10} Kf8 {-79.90/23 18}
31. Ke6 {+79.90/21 10} Kg7 {-79.91/21 10} 32. Be3 {+79.91/20 8} Kf8
{-79.92/21 15} 33. Nf5 {+79.92/20 11} Ke8 {-79.93/21 12} 34. Bg5
{+79.93/20 8} Kf8 {-79.94/25 8} 35. Be7+ {+79.94/24 9} Kg8 {-79.95/28 1.5}
36. Kf6 {+79.95/28 2.0} Kh7 {-79.96/28 0.2} 37. Kf7 {+79.96/28 0.1} Kh8
{-79.97/28 0.1} 38. Kg6 {+79.97/28} Kg8 {-79.98/28} 39. Nh6+ {+79.98/28}
Kh8 {-79.99/28} 40. Bf6# {+79.99/28}
{White mates} 1-0[/pgn]

[hgm]

Fruit only lasts 3 moves longer, with the bare King:

[pgn][Event "Computer Chess Game"]
[Site "hgm-xboard"]
[Date "2014.10.11"]
[Round "-"]
[White "Fairy-Max 4.8T"]
[Black "Fruit 2.1"]
[Result "1-0"]
[TimeControl "40/600"]
[FEN "8/8/8/8/4k3/8/8/KNB5 w - - 0 1"]
[SetUp "1"]
1. Kb2 {+6.50/18} Kd4 {-7.37/19 21} 2. Nc3 {+6.59/18 9} Ke5 {-7.37/19 17}
3. Kc2 {+6.58/18 15} Ke6 {-7.40/21 14} 4. Kd3 {+6.58/17 9} Ke5
{-7.46/21 32} 5. Ne2 {+6.79/17 12} Kd5 {-7.42/16 14} 6. Bf4 {+6.75/17 13}
Kc5 {-7.46/19 17} 7. Ke4 {+6.75/17 13} Kc6 {-7.48/18 15} 8. Nd4+
{+6.63/16 9} Kd7 {-7.48/18 13} 9. Kd5 {+6.68/16 10} Ke7 {-7.58/19 1:28} 10.
Bg5+ {+6.67/16 13} Kf7 {-7.54/17 1.0} 11. Bh4 {+6.74/17 12} Kg6
{-7.64/17 14} 12. Ne2 {+6.88/18 21} Kf5 {-7.73/18 10} 13. Be7 {+6.91/18 8}
Kg4 {-7.69/15 1.1} 14. Ke4 {+6.94/18 8} Kh3 {-8.01/16 7} 15. Kf3
{+7.15/19 11} Kh2 {-8.01/17} 16. Bc5 {+7.15/20 8} Kh3 {-8.01/18 12} 17.
Nf4+ {+7.15/21 15} Kh2 {-8.01/19} 18. Bf2 {+7.14/21 9} Kh1 {-8.01/19} 19.
Bg3 {+7.13/22 10} Kg1 {-7.87/4} 20. Ke2 {+7.11/23 18} Kh1 {-7.55/4} 21. Bh4
{+7.12/24 13} Kh2 {-8.01/22 18} 22. Kf1 {+7.13/24 15} Kh1 {-7.39/4 0.1} 23.
Be7 {+7.08/25 22} Kh2 {-7.65/4 0.1} 24. Kf2 {+7.07/24 17} Kh1 {-8.01/22}
25. Nh3 {+7.06/23 15} Kh2 {-7.47/4} 26. Ng5 {+7.03/23 13} Kh1 {-8.01/21}
27. Ne4 {+6.80/22 25} Kh2 {-8.01/22} 28. Bd6+ {+7.05/21 33} Kh3
{-8.01/23 21} 29. Kf3 {+7.11/21 16} Kh4 {-8.01/22} 30. Be5 {+7.10/21 22}
Kh5 {-8.01/21 8} 31. Kf4 {+7.09/20 11} Kg6 {-8.01/16 24} 32. Bf6
{+79.84/18 14} Kf7 {-7.81/15 33} 33. Kf5 {+79.85/18 16} Ke8 {-7.94/14 11}
34. Ke6 {+79.90/18 15} Kf8 {-99.84/18} 35. Nd6 {+79.91/18 9} Kg8 {-7.73/4}
36. Kf5 {+79.92/18 9} Kh7 {-99.86/56 33} 37. Kg5 {+79.93/19 10} Kg8
{-99.88/52} 38. Kg6 {+79.94/20 7} Kf8 {-99.90/49} 39. Bg5 {+79.95/28 6} Kg8
{-99.92/47} 40. Be7 {+79.96/28 0.2} Kh8 {-99.94/34} 41. Nf5 {+79.97/28 0.1}
Kg8 {-99.96/4 0.1} 42. Nh6+ {+79.98/28 0.1} Kh8 {-99.98/30} 43. Bf6#
{+79.99/28}
{White mates} 1-0
[/pgn]

During moves 17-27 the black King is turning the h1 corner from a bad to a good place for himself, after which white starts making active attempts to get him out of there. Which in the KBNK case happens to bring him to a corner where mate is possible.

[mvk]

Very nice! Thanks for sharing!

[Evert]

Simple, but effective. I like it. Very clever!

Does it ever happen that the king gets driven to the other "wrong" corner? Or is that unlikely because the stronger side will not allow the king to pass through the centre?

Sjaak uses a very basic form of retrograde analysis to figure out which pairs of pieces are "mating pairs", so it knows to evaluate KNNK (for instance) as a draw. I may look into how easy it is to use this to figure out what corner you need to be in. Right now it (incorrectly) assumes that it needs to be the corner of the colourbound.

[hgm]

I have not seen it happen that the bare King reaches the opposite corner. The strong side tries to keep it at the edge, as soon as the safe corner gets poisoned. I was trying with WA + AG now, which is a case where it can only be forced in the corner of opposite color as the color-bound AG. There it works too, but it didn't manage within 50 moves. (And Fairy-Max claims...) But perhaps this end-game does take longer than KBNK, so that it is unreasonable to expect it within 50 moves; the AG seems appreciably weaker than B.

Of course the retrograde analysis is highly superior. (If only because you can detect cases like KNNK, and then avoid them. Fairy-Max is ignorant about this, and for its slightly more sophisticated derivative Pair-o-Max you would have to tell it which pieces form 'defisient pairs', and it would still not be able to do it for pairs of unequal pieces. ) But this is a bit beyond the scope of Fairy-Max.

You should be able to deduce the color of the corner from it if you start back-propagating from mates with the bare King in one quadrant only; for the wrong-color quadrant it would die out quickly.

For Makruk there really don't seem to be safe corners: in KNFFK with like Ferz and KFFFK mate seems possible in both corners. Fairy-Max used to not find the mate in one of the corners for KNFFK, though. But this apparently was because of null move, which in Makruk was still on with KNFFK. Now that it forces it off when it detects bare King, it had no trouble anymore.

[Evert]

Of course the retrograde analysis is highly superior. (If only because you can detect cases like KNNK, and then avoid them. Fairy-Max is ignorant about this, and for its slightly more sophisticated derivative Pair-o-Max you would have to tell it which pieces form 'defisient pairs', and it would still not be able to do it for pairs of unequal pieces. ) But this is a bit beyond the scope of Fairy-Max.

True, but what Sjaak does at the moment is a very limited form: it just looks at the last two plies before mate and tests whether the mate was forced, or if the king has to choose to step into the corner. If the latter, it's assumed to not be mate.

For Makruk there really don't seem to be safe corners: in KNFFK with like Ferz and KFFFK mate seems possible in both corners. Fairy-Max used to not find the mate in one of the corners for KNFFK, though. But this apparently was because of null move, which in Makruk was still on with KNFFK. Now that it forces it off when it detects bare King, it had no trouble anymore.

Sjaak currently considers all combinations with more than three pieces to one side as "won", that is to say, it doesn't do any score adjustments for them. Seems reasonable, but probably isn't always right (I should at least detect three colourbounds on the same colour versus a non-colourbound king).

[Rebel]

This is from my programmer page, 2 PST's and king tropism.

Code: Select all

                      How to mate with Bishop and Knight

 The black king needs to be driven in the corner of the colour of the bishop else a checkmate is not possible. For that purpose we use 2 piece square tables to evaluate the position of the black king. The second (and last!) thing we do is to add a king tropism bonus to the score in order the white king will follow the black king wherever it goes. And that's all there is. REBEL (via self-play) already mates the black king at depth 5 within 26 moves. 

  int x,y;
  x=abs(file[white_king] - file[black_king];    // get file distance between the white king and black king
  x=abs(rank[white_king] - rank[black_king];    // get rank distance between the white king and black king
  if (x < y) x=y;                               // furthest distance is real distance 
  x = x << 3;                                   // distance * 8
  score = 0x780 - x;                            // score = 0x780 - distance
  if (bishop on black square) score=score-TABLE1[black_king];  // drive black king into right corner
   else                       score=score-TABLE2[black_king];  // drive black king into right corner

  TABLE1                                           TABLE2
  +----+----+----+----+-----+----+---+----+        +----+----+----+----+-----+----+---+----+
8 | 150| 150| 140| 120| 100| 70 | 40 | 00 |      8 | 00 | 40 | 70 | 100| 120| 140| 150| 150|
  +----+----+----+----+----+----+----+----+        +----+----+----+----+----+----+----+----+
7 | 150| 160| 190| 210| 130| 100| 70 | 40 |      7 | 40 | 70 | 100| 130| 210| 190| 160| 150|
  +----+----+----+----+----+----+----+----+        +----+----+----+----+----+----+----+----+
6 | 140| 190| 210| 230| 160| 130| 100| 70 |      6 | 70 | 100| 130| 160| 230| 210| 190| 140|
  +----+----+----+----+----+----+----+----+        +----+----+----+----+----+----+----+----+
5 | 120| 210| 230| 250| 200| 170| 130| 100|      5 |100 | 130| 170| 200| 250| 230| 210| 120|
  +----+----+----+----+----+----+----+----+        +----+----+----+----+----+----+----+----+
4 | 100| 130| 170| 200| 250| 230| 210| 120|      4 |120 | 210| 230| 250| 200| 170| 130| 100|
  +----+----+----+----+----+----+----+----+        +----+----+----+----+----+----+----+----+
3 | 70 | 100| 130| 160| 230| 210| 190| 140|      3 |140 | 190| 210| 230| 160| 130| 100| 70 |
  +----+----+----+----+----+----+----+----+        +----+----+----+----+----+----+----+----+
2 | 40 | 70 | 100| 130| 210| 190| 160| 150|      2 |150 | 160| 190| 210| 130| 100| 70 | 40 |
  +----+----+----+----+----+----+----+----+        +----+----+----+----+----+----+----+----+
1 | 00 | 40 | 70 | 100| 120| 140| 150| 150|      1 |150 | 150| 140| 120| 100| 70 | 40 | 00 |
  +----+----+----+----+----+----+----+----+        +----+----+----+----+----+----+----+----+
    a    b    c    d    e    f    g    h              a    b    c    d    e    f    g    h  

[Evert]

I have not seen it happen that the bare King reaches the opposite corner. The strong side tries to keep it at the edge, as soon as the safe corner gets poisoned. I was trying with WA + AG now, which is a case where it can only be forced in the corner of opposite color as the color-bound AG. There it works too, but it didn't manage within 50 moves. (And Fairy-Max claims...) But perhaps this end-game does take longer than KBNK, so that it is unreasonable to expect it within 50 moves; the AG seems appreciably weaker than B.

It appears that the retrograde analysis is sufficient to detect that mate can only be forced in the opposite corner of the colour-bound AG (I found a bug in the process that caused it to miss the correct mate, which mis-classified WA/AG as a non-mating pair). I'll have to think about how to take that into account though. In particular, I don't know what the best way to implement this is if both pieces in a pair are colour-bound. For instance, AG/B (which can also deliver mate; I guess in the bishop corner, but didn't check).

[hgm]

Indeed, all color-bound pieces on the same color should be easy to recognize. In Makruk there also is the problem of 'promotion color' of Pawns, though. With 2 like Ferz + Pawns you better be very careful which Pawns to trade and which to keep.

[Henk]

I played a blitz game a few weeks ago Fairy Max4.8S against Skipper where Skipper was totally lost but the game surprisingly ended in a draw because of the KBNK end game.