Best was to Recognize Know Endgames?

[Michel]

1 --> makes sure mates are not overwritten in the hashtable

Note that this is quite dangerous if you do it indiscriminately since it may polute the hash table with useless entries.

[michiguel]

1 --> makes sure mates are not overwritten in the hashtable

Note that this is quite dangerous if you do it indiscriminately since it may polute the hash table with useless entries.

Yes, I need to do a full evaluation and test it to make sure it does not affect strength. I think it should be ok because the number of mates are small in normal positions, and they will be overwritten in the next iteration. Number of mates will increase in this type of positions, but those are the type of position in which they should be kept. In fact, they are not even a fraction of the total hashtable if enough memory is used, because the number of positions are very limited. The hash table is not even filled. In this case, if only 16 Mb is used, 78% of the hashtable is filled after 200 s search. if 512 Mb is used, the stats are

Code: Select all

HASH TABLE STATS
  Stores attempted    35914393  <----
  Stores overfilled      30456
  Stores same         34785191  <----
  Stores diff          1098746
  Quads filled              31
  Quads occupied        532460
  Quads maximum        8388608
  Singles occupied     1098658
  Singles maximum     33554432
  Hash memory filled      3.27 %   <====

Which means, most "stores" attempted belong to the "same" key, that is, they are "refreshes" of the same position, not really collisions. Only 3.21% is filled after a search that leads to a +Mate 21

Code: Select all

 170660124  43:     74.2  +Mat_21  1.Kf6 Kh7 2.Nf7 Kg8 3.Bg6 Kf8 4.Bh7 Ke8
                                   5.Ne5 Kd8 6.Ke6 Kc7 7.Nd7 Kb7 8.Bd3 Kc6
                                   9.Bc4 Kc7 10.Bb5 Kd8 11.Nc5 Kc7 12.Na4
                                   Kd8 13.Kd6 Kc8 14.Nc5 Kd8 15.Nb7+ Kc8
                                   16.Kc6 Kb8 17.Nd6 Ka7 18.Kc7 Ka8 19.Bf1
                                   Ka7 20.Nc8+ Ka8 21.Bg2# [TT]

from one of the positions of this thread.

Miguel

[hgm]

Indeed. I had huge problems with that when I tried a more advanced replacement scheme (i.e. some kind of depth-preferred, rather than the always-replace it normally uses) in micro-Max. When the latter detects King capture it increases the iteration depth to 99, to make sure any IID loop is terminated on the beta cutoff the King capture gives. But this depth ended up in the hash table, and could never be replaced in the depth-preferred part by something else than other King capture positions.

So within seconds the entire depth-preferred part of the table was filled with King-capture positions, rendering it useles, and effectively making it play with the old always-replace scheme in a table of half the size. It was really important to top off the depth of positions that strictly speaking would be valid to infinite depth when you store it in the hash table, to make sure they would be swiftly replaced. When you get a hit on an entry with a mate score, you can always correct the draft if it was not high enough for the request, when logic dictates it is valid to any depth (like the d=5 result on a mate-in-3 score, say).

[Joost Buijs]

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

You are right. Nightmare also finds the mate within a few minutes.
The only difference is that it finds a mate in 21 and not in 22. This is probably a small bug in Qazar.
Nightmare has no special knowledge about KBNK, the only endgame heuristic it has is centralizing the king and decentralizing the enemy king.
During normal gameplay (in KBNK) it almost always finds a mate after a few moves. However I think there are positions it won't win within 50 moves, but these are very sparse.

[sje]

[d]7k/8/6KN/7B/8/8/8/8 w - - 0 1[/d]

Code: Select all

[] sf 7k/8/6KN/7B/8/8/8/8 w - - 0 1

[] dtbm
Bd1 Even
Be2 Even
Bf3 Even
Bg4 Even
Kf5 MateIn24
Kf6 MateIn21
Kf7 MateIn24
Kg5 MateIn24
Nf5 MateIn24
Nf7+ MateIn22
Ng4 MateIn24
Ng8 Even

[] dg
1 Kf6 Kh7 2 Nf7 Kg8 3 Bg6 Kf8 4 Bh7 Ke8 5 Ne5 Kd8 6 Be4 Kc7 7 Nc4 Kd7 8 Kf7 Kd8
9 Bc2 Kc7 10 Ba4 Kd8 11 Bb5 Kc7 12 Ke6 Kc8 13 Kd6 Kd8 14 Na5 Kc8 15 Bd7+ Kb8 16
Kc6 Ka7 17 Bc8 Kb8 18 Kd7 Ka7 19 Kc7 Ka8 20 Bb7+ Ka7 21 Nc6# 1-0

[sje]

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

Code: Select all

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

[] dtbm
Ba4 MateIn33
Bb5 MateIn33
Bc6 MateIn33
Bd7+ Even
Bf7 MateIn33
Bg6 MateIn33
Bh5 MateIn33
Ka7 MateIn33
Nf1 MateIn34
Nf3 MateIn33
Ng4 MateIn33

[] dg
1 Ba4 Kc7 2 Ka7 Kd6 3 Kb6 Kd5 4 Bc2 Kc4 5 Kc6 Kc3 6 Bf5 Kd4 7 Kd6 Kc4 8 Nf3 Kb4
9 Kd5 Kc3 10 Kc5 Kb2 11 Kb4 Ka1 12 Kc3 Ka2 13 Bc2 Ka1 14 Nd2 Ka2 15 Nb3 Ka3 16
Bb1 Ka4 17 Nd4 Ka5 18 Be4 Ka4 19 Bd5 Ka3 20 Nb5+ Ka4 21 Kc4 Ka5 22 Kc5 Ka4 23
Ba2 Ka5 24 Bb3 Ka6 25 Nd6 Ka5 26 Nb7+ Ka6 27 Kc6 Ka7 28 Bc4 Ka8 29 Kb6 Kb8 30
Be6 Ka8 31 Nc5 Kb8 32 Na6+ Ka8 33 Bd5# 1-0