Best was to Recognize Know Endgames?

[Sven]

3. the friendly king closer to the center than the enemy king.

Is that third criterion necessary for mating, resp. for finding the mate faster?

Yes, it does help because the friendly king serves a big role in pushing the king to the edge and corner. Give two otherwise equal positions you are much farther from mate if the friendly king is on the other side of the board.

Is it absolutely necessary? No, king centralization will automatically put the friendly kind closer to the enemy king but won't make the finer distinctions that can be helpful.

With LMR and heavy pruning and other reductions you want to make the finest distinctions possible so that the moves that are good get put to the front of the list (and thus not reduced.) So the game I play when building these routines is to imagine I'm playing the ending and what moves are best - and then I ask myself if the scoring function would put these moves near the front of the list. If my king is several squares away from the king will it move toward the king or toward some random center square? They are not always the same. Sometimes a move AWAY the king is STILL equally centered or even BETTER centered such as e4 to d4 when the enemy king is on h5 so without the king heuristic there is no scoring penalty for moving in the opposite direction of the king which is obviously wrong.

I don't do this in the other basic mates, the only reason I have it for KNBK is that I specifically wrote a handler for it. I think almost any program would still mate at any reasonable level even if all you do is identify the correct corner.

I am not really sure if we are talking about the same thing. What I mean is: I believe that for KBNK mating the following two criteria are sufficient, with the first having higher priority:

1. The winning side tries to minimize the distance of the enemy king to any of the two "right" corners.
2. The winning side tries to minimize the distance between the two kings.

As I understand your first statement you favor the same 1+2 but additionally a third criterion:

3. The winning side tries to keep its own king closer to the center than the enemy king.

Now I asked whether 3. is really necessary. But your last comment is not clear to me, it still appears that you explained why 2. is needed, which is beyond any doubt.

In my opinion 3. is almost redundant when 2. is present, and might even make the application of 2. somewhat weaker.

Sven

[Don]

3. the friendly king closer to the center than the enemy king.

Is that third criterion necessary for mating, resp. for finding the mate faster?

Yes, it does help because the friendly king serves a big role in pushing the king to the edge and corner. Give two otherwise equal positions you are much farther from mate if the friendly king is on the other side of the board.

Is it absolutely necessary? No, king centralization will automatically put the friendly kind closer to the enemy king but won't make the finer distinctions that can be helpful.

With LMR and heavy pruning and other reductions you want to make the finest distinctions possible so that the moves that are good get put to the front of the list (and thus not reduced.) So the game I play when building these routines is to imagine I'm playing the ending and what moves are best - and then I ask myself if the scoring function would put these moves near the front of the list. If my king is several squares away from the king will it move toward the king or toward some random center square? They are not always the same. Sometimes a move AWAY the king is STILL equally centered or even BETTER centered such as e4 to d4 when the enemy king is on h5 so without the king heuristic there is no scoring penalty for moving in the opposite direction of the king which is obviously wrong.

I don't do this in the other basic mates, the only reason I have it for KNBK is that I specifically wrote a handler for it. I think almost any program would still mate at any reasonable level even if all you do is identify the correct corner.

I am not really sure if we are talking about the same thing. What I mean is: I believe that for KBNK mating the following two criteria are sufficient, with the first having higher priority:

1. The winning side tries to minimize the distance of the enemy king to any of the two "right" corners.
2. The winning side tries to minimize the distance between the two kings.

As I understand your first statement you favor the same 1+2 but additionally a third criterion:

3. The winning side tries to keep its own king closer to the center than the enemy king.

Now I asked whether 3. is really necessary. But your last comment is not clear to me, it still appears that you explained why 2. is needed, which is beyond any doubt.

In my opinion 3. is almost redundant when 2. is present, and might even make the application of 2. somewhat weaker.

Sven

King centralization is the lowest weight of the 3 and may not actually be necessary - but I have it just to ensure the king is not only close but on the correct side of the king. I don't know how useful it really is though.

Don

[Sven]

King centralization is the lowest weight of the 3 and may not actually be necessary - but I have it just to ensure the king is not only close but on the correct side of the king. I don't know how useful it really is though.

I don't know as well. Here is an example.

[d]3k4/8/5K2/8/3B2N1/8/8/8 w - - 0 1
wins in 25 moves (1.Ke6).

[d]3k4/8/1K6/8/3B2N1/8/8/8 w - - 0 1
wins in 21 moves (e.g. 1.Kc6).

In the first position the white king is closer to the center than in the second one but the second is clearly better.

Sven

[velmarin]

Even before 1990 (1986) Gnu Chess had this set,
KBNK,

Code: Select all

static inline int
ScoreKBNK (int winner, int king1, int king2)


/*
  Score King+Bishop+Knight versus King endings.
  This doesn't work all that well but it's better than nothing.
*/

{
  register int s, sq, KBNKsq = 0;

  for &#40;sq = 0; sq < 64; sq++)
    if &#40;board&#91;sq&#93; == bishop&#41;
      if &#40;row &#40;sq&#41; % 2 == column &#40;sq&#41; % 2&#41;
        KBNKsq = 0;
      else
        KBNKsq = 7;

  s = emtl&#91;winner&#93; - 300;
  if &#40;KBNKsq == 0&#41;
    s += KBNK&#91;king2&#93;;
  else
    s += KBNK&#91;locn &#40;row &#40;king2&#41;, 7 - column &#40;king2&#41;)&#93;;
  s -= taxicab &#40;king1, king2&#41;;
  s -= distance &#40;PieceList&#91;winner&#93;&#91;1&#93;, king2&#41;;
  s -= distance &#40;PieceList&#91;winner&#93;&#91;2&#93;, king2&#41;;
  return &#40;s&#41;;
&#125;
static int KBNK&#91;64&#93; =
&#123;99, 90, 80, 70, 60, 50, 40, 40,
 90, 80, 60, 50, 40, 30, 20, 40,
 80, 60, 40, 30, 20, 10, 30, 50,
 70, 50, 30, 10, 0, 20, 40, 60,
 60, 40, 20, 0, 10, 30, 50, 70,
 50, 30, 10, 20, 30, 40, 60, 80,
 40, 20, 30, 40, 50, 60, 80, 90,
 40, 40, 50, 60, 70, 80, 90, 99&#125;;

This very well.

[sje]

A clarification:

As I see it, there are two distinct material distribution ideas presented here.

1. The material distribution key is produced by Zobrist hash construction.

2. The material distribution key is produced by adding or subtracting a single bit with the bit position defined by the piece being added or deleted.

Idea #1 allows the use of traditional transposition table techniques, but the key itself doesn't have any encoded data.

Idea #2 doesn't allow the key to be used as a transposition table index, but it does contain clearly identifiable and useful data.

The first idea goes way back to the early 1970s with the Chess 4.x program and was used to save time avoiding repeat calls to a non-trivial material evaluation function. Today this use can be extended to allow a dispatch to a routine written specifically for a given endgame class.

The second idea is was used at least as far back as 1994; it was in my old program Spector and was used to select a tablebase file for probing. No transposition table is needed; a simple and fast binary search of an table order by a material distribution word provide for a quick identification. (See my code which was posted earlier.)

My current program Symbolic uses both ideas. It does not yet have a sophisticated material evaluation, but when it does, then the already implemented Zobrist material key will be used for probing. The program does already have the distribution key/binary search classifier; this is used for tablebase selection. It will probably not be used for dispatch for specific evaluation routines as I am too lazy to write any of them. And with the tablebase files residing on a fast SSD, there's little need to write such routines.

And now a performance improvement proposal:

A transposition table keyed by a material Zobrist key is much like a pawn structure table; both contain a lot of data which can be used not only from search to search, but also from game to game. Would it be worthwhile to save these tables after each program run and then reload them the next time around?

[Don]

In the first position the white king is closer to the center than in the second one but the second is clearly better.
Sven

There are exceptions to every rule, but you have convinced me that king centralization is probably a very minor and perhaps completely unimportant heuristic in this ending. I don't remember the details of how I built the routine but I experimented a lot with a variety of positions with different weights for them and that is what I came up with. A general rule of thumb is to keep things as simple as possible (and no simpler) so perhaps this rule was violated by me?

Anyway, probably not very important as long as you have the corner heuristic covered - that is the key to playing this reasonably well without requiring correspondence chess time controls.

If one really wanted to go crazy with this, one would take 50 or 100 positions and test them at low fixed depth to find out what is required to solve this in as few ply as possible. If for example it turns out to be 5 ply you would also want to verify that it can be solved on 6, 7 and perhaps 8. Sometimes you can tune a program to solve at one depth but not others. In the old day of preprocessed piece square tables that was a real danger but probably not so much today.

[Don]

[d]KBN5/8/8/8/8/2k5/8/8 w - - 0 1

It takes Komodo about 2 1/2 minutes to actually find a mate from this position.

[Don]

Here is a KBNvsK position that requires 33 moves, which is the longest this should take with perfect play:

[d]K1k1B3/8/8/8/8/8/7N/8 w - - 0 1

I'm going to run this overnight - it should take a lot longer than the last one took.

Don

[Don]

Actually, this took less than 5 minutes to solve too.

Here is a KBNvsK position that requires 33 moves, which is the longest this should take with perfect play:

[d]K1k1B3/8/8/8/8/8/7N/8 w - - 0 1

I'm going to run this overnight - it should take a lot longer than the last one took.

Don

[michiguel]

Actually, this took less than 5 minutes to solve too.

Here is a KBNvsK position that requires 33 moves, which is the longest this should take with perfect play:

[d]K1k1B3/8/8/8/8/8/7N/8 w - - 0 1

I'm going to run this overnight - it should take a lot longer than the last one took.

Don

I let Gaviota run on this position (AMD Phenom(tm) II X4 965 Processor × 4 3.4 Ghz), hash = 4 Gb, of course, no TBs.

After 2 min 40 seconds (160.0 s in this log) a mate is announced

Code: Select all

333150264  35     144.5    +5.85  1.Bh5 Kd7 2.Ng4 Ke6 3.Ne3 Ke5 4.Nc2 Ke4
                                   5.Kb7 Ke5 6.Kc6 Ke4 7.Kc5 Ke5 8.Nd4 Kf6
                                   9.Kd6 Kg7 10.Nf5+ Kf6 11.Ne7 Kg7 12.Ke5
                                   Kh8 13.Kf6 Kh7 14.Bf7 Kh8 15.Ng6+ Kh7
                                   16.Kg5 Kg7 17.Bb3 Kh7 18.Kf6 Kh6 19.Nf8
                                   [>]
 354260831  35     153.9      :-)  1.Bb5
 354264379  35     153.9      :-)  1.Bb5
 364415388  35     160.0  +Mat_69  1.Bb5 Kc7 2.Ka7 Kd6 3.Kb6 Kd5 4.Bc6+
                                   Kd4 5.Nf3+ Kc4 6.Be4 Kb3 7.Ne5 Kc3
                                   8.Kc5 Kb3 9.Kd4 Kb2 10.Kc4 Ka2 11.Kc3
                                   Ka1 12.Ng4 Ka2 13.Bd3 Ka1 14.Ba6 Ka2
                                   15.Kc2 Ka3 16.Kc3 [>]

At depth 45, ~16 minutes, a mate under 50 is announced.

Code: Select all

2158546628  45     981.1  +Mat_39  1.Ka7 Kd8 2.Bc6 Ke7 3.Ng4 Ke6 4.Be4 Ke7
                                   5.Kb6 Kd6 6.Kb5 Ke7 7.Kc6 Ke6 8.Bg6 Ke7
                                   9.Kd5 Kf8 10.Ke6 Kg7 11.Bb1 Kg8 12.Kf6
                                   Kh8 13.Ba2 Kh7 14.Ne5 Kh8 15.Ng6+ Kh7
                                   16.Bb1 Kg8 17.Ba2+ [>]

At depth 60, ~98 min, finally mate in 33 is announced.

Code: Select all

12212789059  60    5902.6  +Mat_33  1.Bg6 Kd7 2.Kb7 Ke6 3.Kc6 Ke5 4.Bb1 Kd4
                                   5.Nf3+ Ke3 6.Ng5 Kd4 7.Ne6+ Ke5 8.Kd7
                                   Kf6 9.Kd6 Kf7 10.Ke5 Ke7 11.Ng5 Kf8
                                   12.Kf6 Ke8 13.Bf5 Kf8 14.Be6 Ke8 15.Nf7
                                   Kf8 16.Ne5 Ke8 17.Bf7+ Kd8 18.Ke6 Kc7
                                   19.Be8 Kb6 20.Kd6 Ka5 21.Kc5 Ka6 22.Nc6
                                   Kb7 23.Nd8+ Kc7 24.Nf7 Kb7 25.Kb5 Kc7
                                   26.Ka6 Kc8 27.Kb6 Kb8 28.Bd7 Ka8 29.Bb5
                                   Kb8 30.Ba6 Ka8 31.Ne5 [>]
12218733597  60:   5905.7  +Mat_33  1.Bg6 Kd7 2.Kb7 Ke6 3.Kc6 Ke5 4.Bb1 Kd4
                                   5.Nf3+ Ke3 6.Ng5 Kd4 7.Ne6+ Ke5 8.Kd7
                                   Kf6 9.Kd6 Kf7 10.Ke5 Ke7 11.Ng5 Kf8
                                   12.Kf6 Ke8 13.Bf5 Kf8 14.Be6 Ke8 15.Nf7
                                   Kf8 16.Ne5 Ke8 17.Bf7+ Kd8 18.Ke6 Kc7
                                   19.Be8 Kb6 20.Kd6 Ka5 21.Kc5 Ka6 22.Nc6
                                   Kb7 23.Nd8+ Kc7 24.Nf7 Kb7 25.Kb5 Kc7
                                   26.Ka6 Kc8 27.Kb6 Kb8 28.Bd7 Ka8 29.Bb5
                                   Kb8 30.Ba6 Ka8 31.Ne5 [>]
12232467096  61    5917.9  +Mat_33  1.Bg6 Kd7 2.Kb7 Ke6 3.Kc6 Ke5 4.Bb1 Kd4
                                   5.Kd6 Kc4 6.Nf3 Kb4 7.Kd5 Kc3 8.Nd4 Kb2
                                   9.Bh7 Kc3 10.Kc5 Kb2 11.Kc4 Ka1 12.Kc3
                                   Ka2 13.Nb3 Ka3 14.Bb1 Ka4 15.Nd4 Ka5
                                   16.Kc4 Kb6 17.Nb5 Kb7 18.Bf5 Kc6 19.Be6
                                   Kb6 20.Bd7 Ka5 21.Nc7 Kb6 22.Ne8 Ka5
                                   23.Kc5 Ka6 24.Nd6 Ka5 25.Bc6 Ka6
                                   26.Bb5+ Ka7 27.Kc6 Kb8 28.Ba6 Ka7
                                   29.Bf1 Kb8 30.Kb6 Ka8 &#91;<&#93;
12235965572  61&#58;   5919.8  +Mat_33  1.Bg6 Kd7 2.Kb7 Ke6 3.Kc6 Ke5 4.Bb1 Kd4
                                   5.Kd6 Kc4 6.Nf3 Kb4 7.Kd5 Kc3 8.Nd4 Kb2
                                   9.Bh7 Kc3 10.Kc5 Kb2 11.Kc4 Ka1 12.Kc3
                                   Ka2 13.Nb3 Ka3 14.Bb1 Ka4 15.Nd4 Ka5
                                   16.Kc4 Kb6 17.Nb5 Kb7 18.Bf5 Kc6 19.Be6
                                   Kb6 20.Bd7 Ka5 21.Nc7 Kb6 22.Ne8 Ka5
                                   23.Kc5 Ka6 24.Nd6 Ka5 25.Bc6 Ka6
                                   26.Bb5+ Ka7 27.Kc6 Kb8 28.Ba6 Ka7
                                   29.Bf1 Kb8 30.Kb6 Ka8 &#91;<&#93;

Miguel