Note that this is quite dangerous if you do it indiscriminately since it may polute the hash table with useless entries.1 --> makes sure mates are not overwritten in the hashtable
Best was to Recognize Know Endgames?
Moderators: hgm, Rebel, chrisw
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Best was to Recognize Know Endgames?
-
- Posts: 6401
- Joined: Thu Mar 09, 2006 8:30 pm
- Location: Chicago, Illinois, USA
Re: Best was to Recognize Know Endgames?
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 areMichel wrote:Note that this is quite dangerous if you do it indiscriminately since it may polute the hash table with useless entries.1 --> makes sure mates are not overwritten in the hashtable
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 % <====
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]
Miguel
-
- Posts: 27796
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Best was to Recognize Know Endgames?
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).
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).
-
- Posts: 1563
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
Re: Best was to Recognize Know Endgames?
You are right. Nightmare also finds the mate within a few minutes.Uri Blass wrote:
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
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.
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
7k/8/6KN/7B/8/8/8/8 w - - 0 1
[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
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
K1k1B3/8/8/8/8/8/7N/8 w - - 0 1
[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