Best was to Recognize Know Endgames?

[hgm]

Even for chess it's almost impossible to pre-calculate EVERY possible material signature without imposing some limitations. You can have legal positions with 10 knights for one side for example. And there are people who will set up such positions so you have to be able to handle them.

I did not consider material signatures only reachable through promotion. They do not occur in practice, and if someone sets them up (which you detect in the root) you can redefine the mapping and recalculate the table with the material combinations that are still reachable. If promoting pieces survive during the search, this would basically give you some random material correction, but the possible range {-100, 100} is such that this is negligible to the promotion gain. The mapping would be such that you would never map into a signature that has special handling by taking an extra Queen.

Apart from the fact that a huge table takes up RAM that might be useful for other purposes (e.g. for a larger TT table or for caching tablebases), both methods should be about equally cheap for the reason that a search will see relatively few unique material signatures. I guess the question is, is it cheaper to (incrementally?) calculate the multidimensional index or is it cheaper to (incrementally) calculate the material signature hash key.

Well, what I meant by 'huge' was something like 3-5MB, so not really significant on the scale of today's hash tables. But larger than L2/L3 (although even that might no longer be true, nowadays).

The multidimensional index is nothing but a (perfect) hash key. There is no difference in how you calculate them incrementally (for an additive key). Each piece has the key increment for its type stored in its piece list. E.g. wB=1, wB'=2, bB=4, bB'=8, wN=16, bN=48, wR=144, ..., where you would otherwise store random keys. The code is identical.

For KBNK it seems important to me to distinguish between good corners and bad corners. There will always be a time control short enough that the search will not be able to figure out a win when the opponent king is in a bad corner.

Oh yes, of course you are right. In fact even with top engines this would probably be true at any reasonable time control, (say shorter than a few weeks per move), in KBNK, as you will need about 60 ply to drive from one corner to the other. I do actually do use a PST with a gradient towards the deadly corner (and very large values), when it detects KBNK in the root.

In fact detecting the existence of a deadly corner (and determining which one it is) was an interesting problem in itself.

[Uri Blass]

Even for chess it's almost impossible to pre-calculate EVERY possible material signature without imposing some limitations. You can have legal positions with 10 knights for one side for example. And there are people who will set up such positions so you have to be able to handle them.

I did not consider material signatures only reachable through promotion. They do not occur in practice, and if someone sets them up (which you detect in the root) you can redefine the mapping and recalculate the table with the material combinations that are still reachable. If promoting pieces survive during the search, this would basically give you some random material correction, but the possible range {-100, 100} is such that this is negligible to the promotion gain. The mapping would be such that you would never map into a signature that has special handling by taking an extra Queen.

Apart from the fact that a huge table takes up RAM that might be useful for other purposes (e.g. for a larger TT table or for caching tablebases), both methods should be about equally cheap for the reason that a search will see relatively few unique material signatures. I guess the question is, is it cheaper to (incrementally?) calculate the multidimensional index or is it cheaper to (incrementally) calculate the material signature hash key.

Well, what I meant by 'huge' was something like 3-5MB, so not really significant on the scale of today's hash tables. But larger than L2/L3 (although even that might no longer be true, nowadays).

The multidimensional index is nothing but a (perfect) hash key. There is no difference in how you calculate them incrementally (for an additive key). Each piece has the key increment for its type stored in its piece list. E.g. wB=1, wB'=2, bB=4, bB'=8, wN=16, bN=48, wR=144, ..., where you would otherwise store random keys. The code is identical.

For KBNK it seems important to me to distinguish between good corners and bad corners. There will always be a time control short enough that the search will not be able to figure out a win when the opponent king is in a bad corner.

Oh yes, of course you are right. In fact even with top engines this would probably be true at any reasonable time control, (say shorter than a few weeks per move), in KBNK, as you will need about 60 ply to drive from one corner to the other. I do actually do use a PST with a gradient towards the deadly corner (and very large values), when it detects KBNK in the root.

In fact detecting the existence of a deadly corner (and determining which one it is) was an interesting problem in itself.

I think that you understimate the search of top engines.
You do not need 60 plies to drive the king from one corner to another.

Smart use of the hash tables together with single reply extension
can clearly help here.

Here is some analysis by Qazar (not a top engine that seems not to have knowledge about the right corner of KBN vs K)

You can see based on the pv at depth 32 that the king is still in the wrong corner so Qazar does not seem to have the knowledge but it does not prevent Qazar to find later mate by search.

[D]7k/8/6KN/7B/8/8/8/8 w - - 5 1

Quazar_0.4_x64:
1 00:00 3 10 +9.57 Kg6-f5
2 00:00 25 88 +9.61 Nh6-f7+ Kh8-g8 Kg6-f5
3 00:00 68 241 +9.63 Nh6-f7+ Kh8-g8 Kg6-f5 Kg8-g7
4 00:00 143 508 +9.56 Nh6-f7+ Kh8-g8 Kg6-f5 Kg8-g7 Kf5-e4
5 00:00 397 1,412 +9.81 Kg6-f6 Kh8-h7 Nh6-f5 Kh7-g8 Bh5-f7+ Kg8-f8
6 00:00 795 2,829 +9.99 Nh6-f5 Kh8-g8 Kg6-f6 Kg8-f8 Nf5-d6 Kf8-g8 Bh5-f7+ Kg8-f8
7 00:00 1,852 6,590 +10.20 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-f7+ Kg8-h8 Ng5-e4 Kh8-h7
8 00:00 3,713 13,213 +10.63 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-f8 Ng5-e6+ Kf8-g8 Kf6-e5 Kg8-h8 Bg6-d3
9 00:00 15,195 51,334 +10.37 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-e4 Kh8-g8 Be4-g6
10 00:00 21,174 71,533 +10.40 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-f7+ Kg8-h8 Bf7-e8 Kh8-g8 Be8-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Ke5-d4 Kh8-g8 Kd4-d5 Kg8-h8 Bg6-e4
11 00:00 30,760 103,918 +10.41 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-f7+ Kg8-h8 Ng5-e6 Kh8-h7 Ne6-d4 Kh7-h6 Nd4-f5+ Kh6-h7 Bf7-e6 Kh7-h8 Kf6-e5 Kh8-h7
12 00:00 68,302 208,874 +10.41 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-f7+ Kg8-h8 Ng5-e6 Kh8-h7 Ne6-d4 Kh7-h6 Nd4-f5+ Kh6-h7 Bf7-e6 Kh7-h8 Kf6-e5 Kh8-h7 Be6-f7 Kh7-h8 Bf7-d5 Kh8-h7
13 00:00 98,355 273,969 +10.41 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-f7+ Kg8-h8 Ng5-e6 Kh8-h7 Ne6-d4 Kh7-h6 Nd4-f5+ Kh6-h7 Bf7-e6 Kh7-h8 Kf6-e5 Kh8-h7 Be6-f7 Kh7-h8 Bf7-d5 Kh8-h7
14 00:00 144,752 387,037 +10.52 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Ke5-d5 Kh8-g8 Kd5-d4 Kg8-h8 Bg6-e4 Kh8-g8
15 00:00 458,788 865,637 +10.43 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Ke5-d5 Kh8-g8 Kd5-d4 Kg8-h8 Kd4-e5 Kh8-g8 Ke5-e4 Kg8-h8 Bg6-f7 Kh8-h7
16 00:00 695,472 1,061,789 +10.37 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Ke5-d5 Kh8-g8 Kd5-d4 Kg8-h8 Kd4-e5 Kh8-g8 Ke5-e4 Kg8-h8 Ke4-f4 Kh8-g8 Kf4-e3 Kg8-h8 Bg6-e4 Kh8-g8
17 00:00 834,621 1,164,046 +10.37 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Ke5-d4 Kh8-g8 Kd4-d5 Kg8-h8 Kd5-e5 Kh8-g8 Ke5-e4 Kg8-h8 Ke4-f4 Kh8-g8 Kf4-e3 Kg8-h8 Bg6-e4 Kh8-g8
18 00:00 1,399,523 1,447,283 +10.37 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Ke5-d4 Kh8-g8 Kd4-d5 Kg8-h8 Kd5-e5 Kh8-g8 Ke5-e4 Kg8-h8 Ke4-f4 Kh8-g8 Kf4-e3 Kg8-h8 Bg6-e4 Kh8-g8
19 00:01 2,321,423 1,710,702 +10.37 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Ke5-d4 Kh8-g8 Kd4-d5 Kg8-h8 Kd5-e5 Kh8-g8 Ke5-e4 Kg8-h8 Ke4-f4 Kh8-g8 Kf4-e3 Kg8-h8 Ke3-d3 Kh8-g8 Kd3-d4 Kg8-h8 Kd4-e5
20 00:01 3,133,199 1,877,291 +10.37 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Ke5-d4 Kh8-g8 Kd4-d5 Kg8-h8 Kd5-e5 Kh8-g8 Ke5-e4 Kg8-h8 Ke4-f4 Kh8-g8 Kf4-e3 Kg8-h8 Ke3-d3 Kh8-g8 Kd3-d4 Kg8-h8 Kd4-e5
21 00:02 4,140,345 2,010,852 +10.39 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Ng7-f5 Kh7-h8 Kf6-e5 Kh8-h7 Ke5-d5 Kh7-h8 Kd5-d4 Kh8-h7 Kd4-d5
22+ 00:02 4,152,240 2,001,079 +10.54 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Ng7-f5 Kh7-h8 Bf7-a2 Kh8-h7 Ba2-e6 Kh7-h8 Nf5-d4 Kh8-h7 Be6-f7 Kh7-h6 Nd4-b5 Kh6-h7 Nb5-d4
22- 00:03 7,056,887 2,185,471 +10.31 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Ng7-f5 Kh7-h8 Bf7-a2 Kh8-h7 Ba2-e6 Kh7-h8 Nf5-d4 Kh8-h7 Be6-f7 Kh7-h6 Nd4-b5 Kh6-h7 Nb5-a3 Kh7-h8 Na3-c2 Kh8-h7 Nc2-e3 Kh7-h8 Ne3-d5 Kh8-h7 Nd5-f4 Kh7-h6 Bf7-d5 Kh6-h7 Bd5-f7
22 00:03 8,800,685 2,265,881 +10.41 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Ng7-f5 Kh7-h8 Bf7-a2 Kh8-h7 Ba2-e6 Kh7-h8 Nf5-d4 Kh8-h7 Be6-f7 Kh7-h6 Nd4-f5+ Kh6-h7 Nf5-d4
23- 00:05 12,851,694 2,401,736 +10.33 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Ng7-f5 Kh7-h8 Nf5-d4 Kh8-h7 Nd4-f5
23 00:07 17,120,598 2,438,831 +10.31 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Ng7-f5 Kh7-h8 Nf5-d4 Kh8-h7 Bf7-d5 Kh7-h6 Nd4-f5+ Kh6-h7 Bd5-f7
24+ 00:07 17,131,110 2,434,779 +10.39 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Ng7-f5 Kh7-h8 Nf5-d4 Kh8-h7 Bf7-d5 Kh7-h6 Nd4-f5+ Kh6-h7 Bd5-a2 Kh7-h8 Ba2-f7 Kh8-h7 Kf6-e5 Kh7-h8 Bf7-e6 Kh8-h7 Be6-f7
24 00:08 19,853,250 2,461,655 +10.41 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Bf7-g6+ Kh7-g8 Ng7-e6 Kg8-h8 Bg6-c2 Kh8-g8 Bc2-e4 Kg8-h8 Be4-c2
25+ 00:08 19,869,333 2,463,649 +10.54 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Bf7-g6+ Kh7-h8 Ng7-f5 Kh8-g8 Kf6-e7 Kg8-h8 Bg6-f7 Kh8-h7 Ke7-f6 Kh7-h8 Kf6-e5 Kh8-h7 Ke5-d4 Kh7-h8 Kd4-e4 Kh8-h7 Nf5-d6 Kh7-h6
25 00:09 23,831,484 2,525,056 +10.54 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Kf6-e5 Kh6-h7
26 00:13 37,773,986 2,708,589 +10.58 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Kf6-e5 Kh6-h7
27- 00:20 56,579,070 2,770,767 +10.50 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Bf7-a2 Kh7-h8 Ba2-d5 Kh8-h7 Ng7-f5 Kh7-h8 Bd5-f7 Kh8-h7 Kf6-e5 Kh7-h8 Ke5-d4 Kh8-h7 Kd4-e4 Kh7-h8
27- 00:26 72,610,516 2,780,520 +10.42 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Bf7-a2 Kh7-h8 Ba2-d5 Kh8-h7 Ng7-f5 Kh7-h8 Bd5-f7 Kh8-h7 Kf6-e5 Kh7-h8 Ke5-d4 Kh8-h7 Kd4-e4 Kh7-h8
27 00:32 90,677,792 2,799,907 +10.30 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Bf7-d5 Kh7-h6 Bd5-e6 Kh6-h7 Be6-f7 Kh7-h6 Ng7-f5+ Kh6-h7 Kf6-e5 Kh7-h8 Ke5-d4 Kh8-h7 Kd4-e4 Kh7-h8 Ke4-e5 Kh8-h7 Ke5-f6 Kh7-h8 Nf5-g7 Kh8-h7
28+ 00:32 90,719,628 2,799,902 +10.39 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Bf7-d5 Kh7-h6 Bd5-e6 Kh6-h7 Be6-f7 Kh7-h6 Ng7-f5+ Kh6-h7 Kf6-e5 Kh7-h8 Ke5-d4 Kh8-h7 Kd4-e4 Kh7-h8 Ke4-e5 Kh8-h7 Ke5-f6 Kh7-h8 Bf7-d5 Kh8-h7 Bd5-e6 Kh7-h8 Kf6-e5 Kh8-h7 Be6-f7
28 00:35 98,135,719 2,792,150 +10.39 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Bf7-d5 Kh7-h6 Bd5-e6 Kh6-h7 Ng7-f5 Kh7-h8 Be6-d5 Kh8-h7 Bd5-f7 Kh7-h8 Bf7-a2 Kh8-h7 Ba2-e6
29+ 00:35 98,188,514 2,791,190 +10.58 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Bf7-d5 Kh7-h6 Bd5-e6 Kh6-h7 Ng7-f5 Kh7-h8 Be6-d5 Kh8-h7 Bd5-f7 Kh7-h8 Kf6-e5 Kh8-h7 Ke5-e4 Kh7-h8 Ke4-d4 Kh8-h7 Kd4-e5 Kh7-h8 Bf7-e6 Kh8-h7 Be6-f7
29+ 00:35 98,189,903 2,791,230 +10.58 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Bf7-d5 Kh7-h6 Bd5-e6 Kh6-h7 Be6-f7 Kh7-h8 Bf7-g6 Kh8-g8 Ng7-e6 Kg8-h8 Kf6-f5 Kh8-g8 Kf5-g5 Kg8-h8 Bg6-e4 Kh8-g8 Kg5-f6 Kg8-h8 Ne6-g5 Kh8-g8 Ng5-e6
29 00:38 109,229,579 2,802,986 +10.41 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Bf7-g6+ Kh7-h8 Ng7-e6
30 00:48 138,769,727 2,841,080 +10.41 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Ng7-e6
31+ 00:49 139,694,423 2,837,356 +10.58 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Bf7-d5 Kh7-h6 Ng7-f5+ Kh6-h7 Bd5-e6 Kh7-h8 Be6-f7 Kh8-h7 Kf6-e5 Kh7-h8 Ke5-d4 Kh8-h7 Kd4-d5 Kh7-h8 Kd5-e4 Kh8-h7 Ke4-d3 Kh7-h8
31+ 00:49 139,697,555 2,837,420 +10.58 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Bf7-d5 Kh7-h6 Ng7-f5+ Kh6-h7 Bd5-e6 Kh7-h8 Be6-f7 Kh8-h7 Kf6-e5 Kh7-h8 Ke5-d4 Kh8-h7 Kd4-d5 Kh7-h8 Kd5-e4 Kh8-h7 Ke4-d4 Kh7-h8 Bf7-e6 Kh8-h7 Be6-f7
31 00:53 153,941,899 2,857,814 +10.43 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Bf7-d5 Kh7-h6 Ng7-f5+ Kh6-h7 Bd5-e6 Kh7-h8 Be6-f7 Kh8-h7 Nf5-g7 Kh7-h6 Bf7-a2 Kh6-h7 Ba2-d5
32 01:15 215,148,052 2,867,264 +10.43 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Bf7-d5 Kh7-h6 Ng7-f5+ Kh6-h7 Bd5-e6 Kh7-h8 Nf5-e3 Kh8-h7
33+ 01:15 215,311,574 2,865,853 +10.58 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Bf7-d5 Kh7-h6 Ng7-f5+ Kh6-h7 Bd5-e6 Kh7-h8 Nf5-e3 Kh8-h7 Be6-f7 Kh7-h6 Ne3-f5+ Kh6-h7 Kf6-e7 Kh7-h8 Ke7-e6 Kh8-h7 Ke6-d5 Kh7-h8 Kd5-e4 Kh8-h7 Ke4-d4 Kh7-h8 Kd4-d5 Kh8-h7 Kd5-d6 Kh7-h8 Kd6-c5 Kh8-h7 Kc5-d4
33+ 01:15 215,319,295 2,865,956 +10.69 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Kf6-e5 Kg8-h8 Bg6-f7 Kh8-h7 Ke5-f6 Kh7-h6 Ne6-g7 Kh6-h7 Bf7-d5 Kh7-h6 Ng7-f5+ Kh6-h7 Bd5-e6 Kh7-h8 Nf5-e3 Kh8-h7 Be6-f7 Kh7-h6 Ne3-f5+ Kh6-h7 Kf6-e5 Kh7-h8 Ke5-e4 Kh8-h7 Ke4-d4 Kh7-h8 Kd4-d5 Kh8-h7 Kd5-d6 Kh7-h8 Kd6-c5 Kh8-h7 Kc5-d4
33+ 01:15 216,512,248 2,866,345 +150.93 Nh6-f7+ Kh8-g8 Nf7-g5 Kg8-f8 Kg6-f6 Kf8-g8 Bh5-g6 Kg8-h8 Ng5-e6 Kh8-g8 Ne6-d4 Kg8-h8 Bg6-e4 Kh8-g8 Nd4-e6 Kg8-h8 Ne6-d8 Kh8-g8 Nd8-f7 Kg8-f8 Be4-d5 Kf8-g8 Kf6-g6 Kg8-f8 Nf7-e5 Kf8-e7 Ne5-c4 Ke7-e8 Kg6-f6 Ke8-f8 Nc4-b6 Kf8-e8 Bd5-f7+ Ke8-d8 Kf6-e6 Kd8-c7 Nb6-a4 Kc7-d8 Bf7-h5 Kd8-c7 Bh5-e2 Kc7-d8 Be2-b5 Kd8-c7 Ke6-e7 Kc7-c8 Ke7-d6 Kc8-b8 Na4-b2 Kb8-c8 Kd6-e7 Kc8-c7 Nb2-c4 Kc7-c8 Bb5-e8 Kc8-c7 Be8-d7 Kc7-b8 Ke7-d6 Kb8-b7 Bd7-h3 Kb7-a6 Kd6-c6 Ka6-a7 Bh3-c8 Ka7-b8 Nc4-d6 Kb8-a7 Kc6-c7 Ka7-a8 Bc8-b7+ Ka8-a7 Nd6-c8+
34 02:24 389,748,493 2,694,238 +M23 Kg6-f6 Kh8-h7 Nh6-f7 Kh7-g8 Bh5-g6 Kg8-f8 Bg6-h7 Kf8-e8 Nf7-e5 Ke8-d8 Kf6-e6 Kd8-c7 Ne5-d7 Kc7-b7 Bh7-d3 Kb7-c6 Bd3-c4 Kc6-c7 Bc4-b5 Kc7-d8 Ke6-d6 Kd8-e8 Bb5-c4 Ke8-d8 Bc4-f7 Kd8-c8 Nd7-c5 Kc8-d8 Bf7-g6 Kd8-c8 Bg6-e4 Kc8-d8 Be4-c6 Kd8-c8 Bc6-d7+ Kc8-b8 Kd6-c6 Kb8-a7 Kc6-c7 Ka7-a8 Kc7-b6 Ka8-b8 Nc5-a6+ Kb8-a8 Bd7-c6+
35 02:38 425,887,469 2,681,235 +M23 Kg6-f6 Kh8-h7 Nh6-f7 Kh7-g8 Bh5-g6 Kg8-f8 Bg6-h7 Kf8-e8 Nf7-e5 Ke8-d8 Kf6-e6 Kd8-c7 Ne5-d7 Kc7-b7 Bh7-d3 Kb7-c6 Bd3-c4 Kc6-c7 Bc4-b5 Kc7-d8 Ke6-d6 Kd8-e8 Bb5-c4 Ke8-d8 Bc4-f7 Kd8-c8 Nd7-c5 Kc8-d8 Bf7-g6 Kd8-c8 Bg6-e4 Kc8-d8 Be4-c6 Kd8-c8 Bc6-d7+ Kc8-b8 Kd6-c6 Kb8-a7 Kc6-c7 Ka7-a8 Kc7-b6 Ka8-b8 Nc5-a6+ Kb8-a8 Bd7-c6+
36 03:06 494,574,782 2,653,881 +M23 Kg6-f6 Kh8-h7 Nh6-f7 Kh7-g8 Bh5-g6 Kg8-f8 Bg6-h7 Kf8-e8 Nf7-e5 Ke8-d8 Kf6-e6 Kd8-c7 Ne5-d7 Kc7-b7 Bh7-d3 Kb7-c6 Bd3-c4 Kc6-c7 Bc4-b5 Kc7-d8 Ke6-d6 Kd8-e8 Bb5-c4 Ke8-d8 Bc4-f7 Kd8-c8 Nd7-c5 Kc8-d8 Bf7-g6 Kd8-c8 Bg6-e4 Kc8-d8 Be4-c6 Kd8-c8 Bc6-d7+ Kc8-b8 Kd6-c6 Kb8-a7 Kc6-c7 Ka7-a8 Kc7-b6 Ka8-b8 Nc5-a6+ Kb8-a8 Bd7-c6+
37 03:34 567,164,780 2,644,877 +M23 Kg6-f6 Kh8-h7 Nh6-f7 Kh7-g8 Bh5-g6 Kg8-f8 Bg6-h7 Kf8-e8 Nf7-e5 Ke8-d8 Kf6-e6 Kd8-c7 Ne5-d7 Kc7-b7 Bh7-d3 Kb7-c6 Bd3-c4 Kc6-c7 Bc4-b5 Kc7-d8 Ke6-d6 Kd8-e8 Bb5-c4 Ke8-d8 Bc4-f7 Kd8-c8 Nd7-c5 Kc8-d8 Bf7-g6 Kd8-c8 Bg6-e4 Kc8-d8 Be4-c6 Kd8-c8 Bc6-d7+ Kc8-b8 Kd6-c6 Kb8-a7 Kc6-c7 Ka7-a8 Kc7-b6 Ka8-b8 Nc5-a6+ Kb8-a8 Bd7-c6+
38 04:09 659,770,885 2,645,941 +M22 Kg6-f6 Kh8-h7 Nh6-f7 Kh7-g8 Bh5-g6 Kg8-f8 Bg6-h7 Kf8-e8 Nf7-e5 Ke8-d8 Kf6-e6 Kd8-c7 Ne5-d7 Kc7-b7 Bh7-d3 Kb7-c6 Bd3-e2 Kc6-c7 Be2-f3 Kc7-c8 Ke6-d6 Kc8-d8 Bf3-e4 Kd8-e8 Be4-g6+ Ke8-d8 Nd7-c5 Kd8-c8 Bg6-e4 Kc8-d8 Be4-c6 Kd8-c8 Bc6-d7+ Kc8-b8 Kd6-c6 Kb8-a7 Kc6-c7 Ka7-a8 Kc7-b6 Ka8-b8 Nc5-a6+ Kb8-a8 Bd7-c6+
39 04:48 768,448,517 2,659,930 +M22 Kg6-f6 Kh8-h7 Nh6-f7 Kh7-g8 Bh5-g6 Kg8-f8 Bg6-h7 Kf8-e8 Nf7-e5 Ke8-d8 Kf6-e6 Kd8-c7 Ne5-d7 Kc7-b7 Bh7-d3 Kb7-c6 Bd3-e2 Kc6-c7 Be2-f3 Kc7-c8 Ke6-d6 Kc8-d8 Bf3-e4 Kd8-e8 Be4-g6+ Ke8-d8 Nd7-c5 Kd8-c8 Bg6-e4 Kc8-d8 Be4-c6 Kd8-c8 Bc6-d7+ Kc8-b8 Kd6-c6 Kb8-a7 Kc6-c7 Ka7-a8 Kc7-b6 Ka8-b8 Nc5-a6+ Kb8-a8 Bd7-c6+
40 05:23 865,861,324 2,678,744 +M22 Kg6-f6 Kh8-h7 Nh6-f7 Kh7-g8 Bh5-g6 Kg8-f8 Bg6-h7 Kf8-e8 Nf7-e5 Ke8-d8 Kf6-e6 Kd8-c7 Ne5-d7 Kc7-b7 Bh7-d3 Kb7-c6 Bd3-e2 Kc6-c7 Be2-f3 Kc7-c8 Ke6-d6 Kc8-d8 Bf3-e4 Kd8-e8 Be4-g6+ Ke8-d8 Nd7-c5 Kd8-c8 Bg6-e4 Kc8-d8 Be4-c6 Kd8-c8 Bc6-d7+ Kc8-b8 Kd6-c6 Kb8-a7 Kc6-c7 Ka7-a8 Kc7-b6 Ka8-b8 Nc5-a6+ Kb8-a8 Bd7-c6+

[Uri Blass]

I can add that smart search can also build tablebases in some simple positions at long time control so with today hardware there is no reason to have a special knowledge about this endgame and probably it is possible to do stockfish slightly stronger at least at long time control by removing the special knowledge that it has for KBN vs K.

The only knowledge that is important for long time control is knowing if a position is a draw or a win and not knowing how to win won endgames.

[hgm]

Something is a bit suspect here: just before it finds the mating line at 34 ply, with score +M23, it gets a '33+' line with a score of +150.93. I don't see how it could ever get such a score from normal (material + PST + mobility) evaluation, and it is not a mate score either. So it seems to have some pattern, and considering the root material, only KBNK patterns can match.

[Uri Blass]

I do not know how it got the 150 pawns score but it is possible that it got a fail high and decided to solve it only in the next iteration.

Considering the pv at depth 32 I am going to be surprised if it is some knowledge that is relevant only to kbn vs k.

[hgm]

Even in a fail high the score should come from an evaluation, right? It is not picking random numbers for scores when it detects the evaluation is outside the search window.

If the 150 does not come from knowledge, then what could it come from? It certainly won't be coming from a position with 150 pawns on the board...

The most likely explanation seems that it has some pattern halfway. From sub-optimal defense in being driven towards the pattern, and an attempt to flee away from it to the wrong side, it can discover forced mating sequences from the position that matches the pattern, which can then be grafted through the TT. It is clear that grafting must be going on: +M23 is mate in 45 ply, so the mate is not within the horizon at 34 ply. It cannot be all check extensions; there aren't that many checks in the PV, and checking is mostly a waste of time in KBNK anyway.

[Don]

Something is a bit suspect here: just before it finds the mating line at 34 ply, with score +M23, it gets a '33+' line with a score of +150.93. I don't see how it could ever get such a score from normal (material + PST + mobility) evaluation, and it is not a mate score either. So it seems to have some pattern, and considering the root material, only KBNK patterns can match.

There is some bug in Komodo that also makes it do that sort of thing. It will see a mate but report it as something like a mate taking 100 moves or more. I think it is a hash table interaction with the maximum mate depth Komodo can report - so with the hash table Komodo perhaps strings together a mate in some ridiculous number of ply and then moves on to the next iteration.

I see that here in this ending - so I have a good test case and I will try to fix this glitch. Because of aspiration at the root I will get fail high scores that look like modest wins similar to the 150 pawn score you see here.

[Uri Blass]

Even in a fail high the score should come from an evaluation, right? It is not picking random numbers for scores when it detects the evaluation is outside the search window.

If the 150 does not come from knowledge, then what could it come from? It certainly won't be coming from a position with 150 pawns on the board...

The most likely explanation seems that it has some pattern halfway. From sub-optimal defense in being driven towards the pattern, and an attempt to flee away from it to the wrong side, it can discover forced mating sequences from the position that matches the pattern, which can then be grafted through the TT. It is clear that grafting must be going on: +M23 is mate in 45 ply, so the mate is not within the horizon at 34 ply. It cannot be all check extensions; there aren't that many checks in the PV, and checking is mostly a waste of time in KBNK anyway.

getting M23 in 34 plies can be result of many options

It can be thanks to single reply extensions that are not check extensions(at least I did that extension in movei in the past when later I decided to do it only when the side to move has relatively good position because if the side to move is already losing I am not interested in extending so latest movei does not have that extension).

It can be thanks to pruning based on hash tables so the program already has an exact score of mate in 10 at some node and returns
the mate score instead of searching(the mate in 10 score comes from a different line that the program searched earliar and save the result of the search in the hash tables).

[lucasart]

Something is a bit suspect here: just before it finds the mating line at 34 ply, with score +M23, it gets a '33+' line with a score of +150.93. I don't see how it could ever get such a score from normal (material + PST + mobility) evaluation, and it is not a mate score either. So it seems to have some pattern, and considering the root material, only KBNK patterns can match.

There is some bug in Komodo that also makes it do that sort of thing. It will see a mate but report it as something like a mate taking 100 moves or more. I think it is a hash table interaction with the maximum mate depth Komodo can report - so with the hash table Komodo perhaps strings together a mate in some ridiculous number of ply and then moves on to the next iteration.

I'm glad I'm not the only one to have this problem. I never bothered to investigate it as it never had anymore than a cosmetic effect (still plays the right move). Something to put far away in the todo list...

[syzygy]

I think that you understimate the search of top engines.
You do not need 60 plies to drive the king from one corner to another.

Smart use of the hash tables together with single reply extension
can clearly help here.

Here is some analysis by Qazar (not a top engine that seems not to have knowledge about the right corner of KBN vs K)

You can see based on the pv at depth 32 that the king is still in the wrong corner so Qazar does not seem to have the knowledge but it does not prevent Qazar to find later mate by search.

[D]7k/8/6KN/7B/8/8/8/8 w - - 5 1

Without special knowledge (and tablebases off) my engine takes 2 minutes to find a mate in 29 which then quickly goes down to mate in 21.

With special knowledge a mate in 25 is found in less than 8 seconds and mate in 21 in 14 seconds.

I can add that smart search can also build tablebases in some simple positions at long time control so with today hardware there is no reason to have a special knowledge about this endgame and probably it is possible to do stockfish slightly stronger at least at long time control by removing the special knowledge that it has for KBN vs K.

Removing KBN vs K knowledge from Stockfish would not save anything (just look at how special positions are treated in do_evaluate()).