Cache over-writing and PV's

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Zenmastur
Posts: 487
Joined: Sat May 31, 2014 6:28 am

Cache over-writing and PV's

Post by Zenmastur » Thu Oct 16, 2014 12:09 am

I am doing some analysis on historic games. I'm using stockfish 090414 64 bit. In one game white played a slight inaccuracy on move 15 that altered the course of the game. The white player went on to win in this now famous game. I am doing very deep analysis of the whole game with particular attention to the position that would have resulted had this slight mis-step not been made. I would actually like to show a forced win starting at move 15. I know!... This is a tall order to fill and may not be possible.

In any case, I ran into several positions during this analysis that seemed unusually hard for the computer to solve. This seems unusual since all the positions are a single line of play. I'm wondering why a particular position in a line of play is VERY hard for the computer to handle. By "very hard" I mean it may take 100 times as long or longer to analyze as the positions that came before it in the line of play or the position that come after it. This seems strange to me.

Eventually I came to a position which the computer couldn't solve in any reasonable time frame. i.e. many days. Now there is nothing unusual about this since they are innumerable positions that can't be solved to a mate. This position seems to evoke some unusual behavior from stockfish. In the position black is on the move. If I make any move for black the computer will find a mate in relatively short period of time. So what I did was make each of blacks legal moves and let it find the mate. This loaded the cache with the mating positions for each of blacks legal moves. Then I let it work on the main position. It still can't find the mate!

On one attempt I let it go to 70 plies (or iterations, not sure which is which). This took a very long time. It still couldn't pin down the mate. So I stopped and restarted the search. Many times this will cause the program to pick up where it left off the last search with approximately the same score and same line of play at a much shallower depth, not always, but often enough that its worth trying. I've done this multiple times on this position. It still can't find the mates.

This is the output from arena for the most recent attempt:
[D] 1n6/2k4p/6b1/8/P1BR1P2/2K5/2P4P/8 b - a3 0 43

Stockfish_14090421_x64_modern:
1/1 00:00.001 76 76k +6.41 43. ... Kc6 44.Be6 Bh5
2/2 00:00.001 212 212k +6.48 43. ... Kb6 44.Bd3 Kc7
3/3 00:00.001 551 551k +6.80 43. ... Kb6 44.Rd5 Kb7
4/5 00:00.002 1k 739k +6.84 43. ... Nd7 44.a5 h6 45.Bd3 Bf7
5/6 00:00.002 2k 1,074k +6.90 43. ... h5 44.Rd5 Nc6 45.f5 Be8 46.f6
6/6 00:00.002 3k 1,376k +6.89 43. ... h5 44.Rd5 h4 45.f5 Be8 46.a5 Bc6 47.Rd4
7/7 00:00.002 3k 1,724k +6.96 43. ... h5 44.Rd5 h4 45.f5 Be8 46.a5 Nc6
8/8 00:00.002 4k 2,150k +6.92 43. ... h5 44.Rd5 h4 45.f5 Be8 46.a5 Nc6 47.Bb5 Nxa5
9/13 00:00.005 11k 2,226k +7.21 43. ... Nd7 44.a5 h6 45.a6 Nb6 46.Be6 Kb8 47.f5 Bh5 48.Rh4
10/13 00:00.006 19k 3,140k +7.40 43. ... h5 44.Rd5 Nc6 45.f5 Be8 46.f6 Nd8 47.a5 Nc6 48.Rf5 Bg6
11/13 00:00.008 22k 2,706k +7.50 43. ... h5 44.Rd5 Nc6 45.f5 Be8 46.f6 Nd8 47.a5 Bf7 48.Rf5 Kb7 49.Re5 Bxc4
12/17 00:00.016 44k 2,746k +7.96 43. ... Nd7 44.a5 h6 45.a6 h5 46.Bd3 Bf7 47.a7 Nb6 48.Be4 h4 49.a8Q Nxa8 50.Bxa8 h3
13/18 00:00.022 63k 2,863k +8.71 43. ... Kc6 44.Be6 Kc7 45.f5 Be8 46.f6 Nc6 47.Rc4 Kd8 48.f7 Bxf7 49.Bxf7 Ne5 50.Rd4+ Kc8 51.Be6+ Kc7 52.Rd7+
14/21 00:00.028 85k 3,043k +8.89 43. ... Nd7 44.a5 h6 45.a6 Nb6 46.Be6 Bh7 47.f5 Kb8 48.f6 Bg6 49.Rb4 Ka7 50.f7 Bxf7 51.Bxf7 Kxa6
15/21 00:00.033 99k 2,997k +8.96 43. ... Kc6 44.Be6 Kc7 45.f5 Be8 46.f6 Nc6 47.Rc4 Kd8 48.Rc5 Ne7 49.f7 Bxf7 50.Bxf7 Kd7 51.a5 Kd8
16/24 00:00.069 266k 3,851k +9.45 43. ... Nd7 44.a5 h6 45.a6 Nb6 46.Be6 Be8 47.f5 Bh5 48.f6 Be8 49.Rb4 Bg6 50.f7 Bxf7 51.Bxf7 Kc6 52.a7
17/24 00:00.082 325k 3,969k +9.69 43. ... Kc6 44.Be6 Kc7 45.f5 Be8 46.f6 h5 47.f7 Bxf7 48.Bxf7 Nd7 49.Bxh5 Nf6 50.Bf7 Kb6 51.Rb4+ Ka5 52.Be6
18/25 00:00.101 439k 4,351k +9.82 43. ... h5 44.Rd5 Nc6 45.f5 Be8 46.Bb5 Ne7 47.Re5 Nxf5 48.Bxe8 Nh4 49.Bxh5 Kd6 50.Rb5 Ng2 51.a5 Nf4 52.a6 Ne6 53.Rb6+ Ke5
19/27 00:00.115 517k 4,498k +9.92 43. ... Kc6 44.Be6 Kc7 45.f5 Be8 46.f6 h5 47.f7 Bxf7 48.Bxf7 Nd7 49.Bxh5 Nf6 50.Bf7 Kb6 51.Rb4+ Kc6 52.a5 Kc5 53.a6
20/29 00:00.143 682k 4,771k +10.05 43. ... h5 44.Rd5 Nc6 45.f5 Be8 46.Bb5 Ne7 47.Re5 Nxf5 48.Bxe8 Nh4 49.Bxh5 Kd6 50.Rb5 Ng2 51.a5 Kc6 52.Be8+ Kc7 53.a6 Ne3 54.Rb7+ Kd6
21/32 00:00.198 1,028k 5,190k +10.44 43. ... Kc6 44.Be6 Kc7 45.f5 Be8 46.f6 Nc6 47.Rh4 Kd6 48.f7 Bxf7 49.Bxf7 Ke5 50.Rxh7 Kf4 51.Bd5 Nb8 52.Rf7+ Ke3 53.a5 Na6 54.Bc4 Nc5 55.a6 Ne4+ 56.Kb4
22/32 00:00.239 1,237k 5,176k +10.57 43. ... Kc6 44.Be6 Kc7 45.f5 Be8 46.f6 Nc6 47.Rh4 Kd6 48.f7 Bxf7 49.Bxf7 Ke5 50.Rxh7 Kf4 51.Bd5 Nb8 52.Rf7+ Ke3 53.a5 Na6 54.Bc4 Nc5 55.a6 Ne4+ 56.Kb4
23/37 00:00.352 1,982k 5,631k +12.57 43. ... h5 44.Rd5 Nc6 45.f5 Be8 46.f6 Nb8 47.Rc5+ Kd8 48.Be6 Nc6 49.f7 Bxf7 50.Bxf7 Nb8 51.Rxh5 Ke7 52.Bc4 Kf6 53.a5 Kg6 54.Rb5 Nd7 55.a6 Nf8 56.a7 Kf6
24/37 00:00.401 2,261k 5,638k +13.31 43. ... Kc6 44.Be6 Kc7 45.f5 Be8 46.f6 Nc6 47.Rh4 Kd6 48.f7 Bxf7 49.Bxf7 Ke5 50.Rxh7 Kf4 51.Bd5 Nb8 52.Rf7+ Kg4 53.a5 Na6 54.Be6+ Kg5 55.Bc4 Nc5 56.a6 Kg4 57.a7 Na4+
25/42 00:00.523 3,110k 5,947k +16.04 43. ... Kb6 44.Rd5 Kb7 45.f5 Be8 46.Rd8 Bh5 47.f6 Kc7 48.Rd5 Be8 49.Ra5 h5 50.Rc5+ Kd8 51.Be6 Nc6 52.f7 Bxf7 53.Bxf7 Nb8 54.Rxh5 Ke7 55.Bc4 Kf6 56.a5 Kg6 57.Rb5 Nd7 58.a6 Nf8 59.a7 Kf6 60.a8Q Kg6
26/43 00:00.607 3,691k 6,081k +17.09 43. ... Kc6 44.Be6 Kc7 45.f5 Be8 46.f6 Nc6 47.Rh4 Kd6 48.f7 Bxf7 49.Bxf7 Ke5 50.Rxh7 Kf4 51.Bd5 Nb8 52.Rf7+ Ke3 53.a5 Na6 54.Bc4 Nc5 55.a6 Ne4+ 56.Kb4 Ng5 57.a7 Nxf7 58.Bxf7 Kd2
27/45 00:01.014 6,488k 6,399k +25.03 43. ... h5 44.Rd5 h4 45.f5 Bh5 46.f6 Bg6 47.Rg5 Be4 48.Re5 Bg6 49.f7 Bxf7 50.Re7+ Kb6 51.Rxf7
28/47 00:01.173 7,498k 6,392k +27.00 43. ... Kc6 44.Be6 Kc7 45.f5 Be8 46.f6 Nc6 47.Rh4 Kd6 48.f7 Bxf7 49.Bxf7 Ke5 50.Rxh7 Kf4 51.Bd5 Nb8 52.Rf7+ Kg4 53.a5 Kh3 54.Bc4 Nc6 55.a6 Kxh2 56.a7 Ne5 57.Rh7+ Kg3 58.a8Q Ng6 59.Qg8
29/47 00:01.524 9,986k 6,553k +30.82 43. ... h5 44.Rd5 h4 45.f5 Be8 46.f6 Bg6 47.Rg5 Be4 48.Re5 Bg6 49.f7 Bxf7 50.Re7+ Kb6 51.Rxf7 Nc6
30/47 00:02.200 15,082k 6,856k +36.81 43. ... Kc6 44.Be6 Kc7 45.f5 Be8 46.f6 Nc6 47.Rh4 Kd6 48.f7 Bxf7 49.Bxf7 Ke5 50.Rxh7 Kf4 51.Bd5 Nb8 52.Rf7+ Kg4 53.a5 Kh3 54.Bc4 Nc6 55.a6 Kxh2 56.a7 Ne5 57.Rh7+ Kg3 58.a8Q Ng6 59.Qg8
31/47+ 00:03.035 20,909k 6,889k +86.24 43. ... Kc6 44.Be6 Na6 45.f5 Bxf5 46.Bxf5 Kc7 47.Bxh7 Kb8 48.Rc4 Ka7 49.Be4 Kb8
31/47+ 00:03.100 21,454k 6,921k +111.62 43. ... Kc6 44.Be6 Na6 45.f5 Bxf5 46.Bxf5 Kc7 47.Bxh7 Kb8 48.Rc4 Ka7
31/47 00:03.460 24,213k 6,998k +59.75 43. ... Kc6 44.Be6 Na6 45.f5 Kc7 46.fxg6 hxg6 47.Rg4 Nc5 48.Rc4 Kd6 49.Rxc5 Kxc5 50.h4 Kd6 51.Bf7 g5 52.hxg5 Ke7 53.g6 Kf8 54.a5 Kg7 55.Kb4 Kf8 56.a6 Kg7 57.a7 Kf6 58.a8Q Ke7 59.g7 Kxf7 60.g8Q+ Kf6 61.Qh8+ Kg6
32/47 00:03.517 24,595k 6,993k +59.75 43. ... Kc6 44.Be6 Na6 45.f5 Kc7 46.fxg6 hxg6 47.Rg4 Nc5 48.Rc4 Kd6 49.Rxc5 Kxc5 50.h4 Kd6 51.Bf7 g5 52.hxg5 Ke7 53.g6 Kf8 54.a5 Kg7 55.Kb4 Kf8 56.a6 Kg7 57.a7 Kf6 58.a8Q Ke7 59.g7 Kxf7 60.g8Q+ Kf6 61.Qh8+ Kg6
33/47 00:03.668 25,642k 6,991k +59.75 43. ... Kc6 44.Be6 Na6 45.f5 Kc7 46.fxg6 hxg6 47.Rg4 Nc5 48.Rc4 Kd6 49.Rxc5 Kxc5 50.h4 Kd6 51.Bf7 g5 52.hxg5 Ke7 53.g6 Kf8 54.a5 Kg7 55.Kb4 Kf8 56.a6 Kg7 57.a7 Kf6 58.a8Q Ke7 59.g7 Kxf7 60.g8Q+ Kf6 61.Qh8+ Kg6
34/47 00:03.728 26,085k 6,997k +59.75 43. ... Kc6 44.Be6 Na6 45.f5 Kc7 46.fxg6 hxg6 47.Rg4 Nc5 48.Rc4 Kd6 49.Rxc5 Kxc5 50.h4 Kd6 51.Bf7 g5 52.hxg5 Ke7 53.g6 Kf8 54.a5 Kg7 55.Kb4 Kf8 56.a6 Kg7 57.a7 Kf6 58.a8Q Ke7 59.g7 Kxf7 60.g8Q+ Kf6 61.Qh8+ Kg6 62.Qc6+
35/47+ 00:03.823 26,772k 7,003k +59.81 43. ... Kc6 44.Be6 Na6 45.f5 Kc7 46.fxg6 hxg6 47.Rg4 Nc5 48.Rc4 Kd6
35/47+ 00:03.936 27,583k 7,008k +59.87 43. ... Kc6 44.Be6 Na6 45.f5 Kc7 46.fxg6 hxg6 47.Rg4 Nc5 48.Rc4 Kd6
35/47+ 00:04.040 28,393k 7,028k +59.96 43. ... Kc6 44.Be6 Na6 45.f5 Kc7 46.fxg6 hxg6 47.Rg4 Nc5 48.Rc4 Kd6 49.Rxc5 Kxc5 50.h4 Kd6
35/47+ 00:04.112 28,962k 7,043k +60.08 43. ... Kc6 44.Be6 Na6 45.f5 Kc7 46.fxg6 hxg6 47.Rg4 Nc5 48.Rc4 Kd6 49.Rxc5 Kxc5 50.h4 Kd6
35/47+ 00:04.155 29,329k 7,059k +60.24 43. ... Kc6 44.Be6 Na6 45.f5 Kc7 46.fxg6 hxg6 47.Rg4 Nc5 48.Rc4 Kd6
35/47+ 00:04.197 29,662k 7,067k +60.45 43. ... Kc6 44.Be6 Na6 45.f5 Kc7 46.fxg6 hxg6 47.Rg4 Nc5 48.Rc4 Kd6 49.Rxc5 Kxc5 50.h4 Kd6
35/47+ 00:04.256 30,167k 7,088k +60.75 43. ... Kc6 44.Be6 Na6 45.f5 Kc7 46.fxg6 hxg6 47.Rg4 Nc5 48.Rc4 Kd6 49.Rxc5 Kxc5 50.h4 Kd6
35/47+ 00:04.302 30,536k 7,098k +61.16 43. ... Kc6 44.Be6 Na6 45.f5 Kc7 46.fxg6 hxg6 47.Rg4 Nc5 48.Rc4 Kd6
35/47+ 00:04.360 30,970k 7,103k +61.72 43. ... Kc6 44.Be6 Na6 45.f5 Kc7 46.fxg6 hxg6 47.Rg4 Nc5 48.Rc4 Kd6 49.Rxc5 Kxc5 50.h4 Kd6
35/47+ 00:04.418 31,407k 7,109k +62.48 43. ... Kc6 44.Be6 Na6 45.f5 Kc7 46.fxg6 hxg6 47.Rg4 Nc5 48.Rc4 Kd6
35/47+ 00:04.473 31,830k 7,116k +63.54 43. ... Kc6 44.Be6 Na6 45.f5 Kc7 46.fxg6 h5 47.g7
35/47+ 00:04.545 32,346k 7,117k +64.99 43. ... Kc6 44.Be6 Na6 45.f5 Kc7 46.fxg6 h5
35/47+ 00:04.599 32,777k 7,127k +66.98 43. ... Kc6 44.Be6 Na6 45.f5 Kc7 46.fxg6 h5
35/47+ 00:04.652 33,225k 7,142k +69.72 43. ... Kc6 44.Be6 Na6 45.f5 Kc7 46.fxg6 h5
35/47+ 00:04.711 33,706k 7,155k +73.48 43. ... Kc6 44.Be6 Na6 45.f5 Kc7 46.fxg6 h5
35/47+ 00:04.784 34,266k 7,163k +78.64 43. ... Kc6 44.Be6 Na6 45.f5 Kc7 46.fxg6 h5
35/47+ 00:04.835 34,716k 7,180k +85.74 43. ... Kc6 44.Be6 Na6 45.f5 Kc7 46.fxg6 h5 47.g7 Nc5
35/47+ 00:04.918 35,434k 7,205k +95.51 43. ... Kc6 44.Be6 Na6 45.f5 Kc7 46.fxg6 h5
35/47+ 00:04.967 35,870k 7,222k +108.93 43. ... Kc6 44.Be6 Na6 45.f5 Kc7 46.fxg6 h5
35/51 00:13.651 101,418k 7,429k +M29 43. ... h6 44.Be6 Be8 45.f5 Nc6 46.f6 Ne5 47.Re4 Ng6 48.Bf5 Bf7 49.Bxg6 Bxg6 50.Rg4 Bh5 51.Rh4 Bf7 52.Rxh6 Kd6 53.Rh7 Bg6 54.Ra7 Ke6
36/51- 00:16.055 120,458k 7,503k +M37 43. ... h6 44.Be6 Be8 45.f5 Nc6 46.f6 Ne5 47.Re4 Nf3 48.Bd5 Bg6
36/51- 00:26.410 196,127k 7,426k +M45 43. ... h5 44.Rd5 Be4 45.Rxh5 Nd7 46.a5 Nf6 47.Re5 Bc6 48.Re7+
36/51- 00:29.496 219,662k 7,447k +M56 43. ... h5 44.Rd5 Be8 45.Bb5 Bf7 46.Rf5 Bg8 47.Rxh5 Nd7 48.Bxd7 Kxd7
36/51 00:30.541 227,743k 7,457k +M28 43. ... h5 44.Rd5 Be8 45.Bb5 Bf7 46.Rf5 Be6 47.Rxh5 Bg4 48.Rh7+ Kb6 49.Rh6+ Ka5 50.Rh8 Nd7 51.Bxd7 Bxd7 52.Rh7 Be6 53.f5 Bg8 54.Re7 Kxa4 55.Rg7 Bd5 56.f6 Kb5 57.Rg5 Kc6 58.Rxd5
37/51 00:31.176 232,078k 7,444k +M28 43. ... h5 44.Rd5 Be8 45.Bb5 Bf7 46.Rf5 Be6 47.Rxh5 Bg4 48.Rh7+ Kb6 49.Rh6+ Ka5 50.Rh8 Nd7 51.Bxd7 Bxd7 52.Rh7 Be6 53.f5 Bg8 54.Re7 Kxa4 55.Rg7 Bd5 56.f6 Kb5 57.Rg5 Kc6 58.Rxd5
38/51 00:35.573 262,931k 7,391k +M28 43. ... h5 44.Rd5 Be8 45.Bb5 Bf7 46.Rf5 Be6 47.Rxh5 Bg4 48.Rh7+ Kd8 49.a5 Bf5 50.Rh8+ Kc7 51.Rh6 Kb7 52.Rf6 Be4 53.a6+ Nxa6 54.Bxa6+ Kc7 55.Bd3 Bf3 56.f5 Kd8 57.Rh6 Kc7 58.f6 Bd5 59.Bc4 Bxc4 60.Kxc4 Kd6 61.Rh7 Ke6 62.f7 Ke7 63.Kd5 Kf8 64.Kc5 Ke7 65.f8R+ Kxf8 66.Ra7
39/51 00:41.484 323,672k 7,802k +M28 43. ... h5 44.Rd5 Be8 45.Bb5 Bf7 46.Rf5 Be6 47.Rxh5 Bg4 48.Rh7+ Kd8 49.a5 Bf5 50.Rh8+ Kc7 51.Rh6 Kb7 52.Rf6 Be4 53.a6+ Nxa6 54.Bxa6+ Kc7 55.Bd3 Bf3 56.f5 Kd8 57.Rh6 Kc7 58.f6 Bd5 59.Bc4 Bxc4 60.Kxc4 Kd6 61.Rh7 Ke6 62.f7 Ke7 63.Kd5 Kf8 64.Kc5 Ke7 65.f8R+ Kxf8
40/51 00:57.943 482,098k 8,320k +M28 43. ... h5 44.Rd5 Be4 45.Rxh5 Nd7 46.a5 Kb7 47.Rh6 Nf8 48.Rf6 Nd7 49.a6+ Ka8 50.Re6 Bh1 51.Re8+ Ka7 52.Re7 Bc6 53.f5 Kb6 54.Rxd7 Bxd7 55.f6 Be8
41/54 01:01.566 518,168k 8,416k +M28 43. ... h5 44.Rd5 Be4 45.Rxh5 Nd7 46.a5 Kb7 47.Rh6 Nf8 48.Rf6 Nd7 49.a6+ Ka8 50.Re6 Bf3 51.Re8+ Ka7 52.Re7 Bc6 53.f5 Kb6 54.Rxd7 Bxd7 55.f6 Be8
42/56 01:16.226 664,758k 8,721k +M28 43. ... h5 44.Rd5 Be4 45.Rxh5 Nd7 46.a5 Kb7 47.Rh6 Nf8 48.Rf6 Nd7 49.a6+ Ka8 50.Re6 Bf3 51.Re8+ Ka7 52.Re7 Bc6 53.f5 Kb6 54.Rxd7 Bxd7 55.f6 Be8
43/56 01:55.052 1,054,333k 9,164k +M28 43. ... Bf5 44.Rd5 Be4 45.Re5 Bg2 46.Re2
44/57 02:03.174 1,142,733k 9,277k +M28 43. ... Bf5 44.Rd5 Be4 45.Re5 Bg2 46.Re2
45/57 02:06.098 1,173,265k 9,304k +M28 43. ... Bf5 44.Rd5 Be4 45.Re5 Bg2 46.Re2
46/57 02:34.998 1,454,168k 9,382k +M28 43. ... Bf5 44.Rd5 Be4 45.Re5 Bg2 46.Re2
47/57 03:03.619 1,748,551k 9,523k +M28 43. ... Bf5 44.Rd5 Be4 45.Re5 Bg2 46.Re2
48/57 03:12.095 1,840,669k 9,582k +M28 43. ... Bf5 44.Rd5 Be4 45.Re5 Bg2 46.Re2
49/57 04:05.105 2,391,383k 9,757k +M28 43. ... Bf5 44.Rd5 Be4 45.Re5 Bg2 46.Re2
50/57 04:46.988 2,829,157k 9,858k +M28 43. ... Bf5 44.Rd5 Be4 45.Re5 Bg2 46.Re2
51/57 06:50.326 4,074,104k 9,929k +M28 43. ... Bf5 44.Rd5 Be4 45.Re5 Bg2 46.Re2
52/67 48:36.682 29,443,642k 10,095k +M26 43. ... Bf5 44.Rd5 Be4 45.Re5 Bg2 46.Re2 Bf3 47.Re7+ Kd6 48.Rxh7 Nd7 49.a5 Be4 50.Rh6+ Kc5 51.Rh5+ Kd6 52.Kd4 Bf3 53.Rh6+ Kc7
53/67- 2:14:31.067 80,827,619k 10,014k +M34 43. ... Nd7
53/67- 2:22:08.836 85,145,053k 9,983k +M42 43. ... Nd7
53/67- 3:06:08.946 112,397,110k 10,063k +M53 43. ... Be8
53/71- 3:33:23.650 128,975,786k 10,073k +123.50 43. ... Be8
53/71- 3:55:45.975 141,709,398k 10,018k +123.34 43. ... Be8
53/71 5:06:52.470 185,058,793k 10,051k +M26 43. ... Bf5 44.Rd5 Be4 45.Re5 Bg2 46.Re2 Bf3 47.Re7+ Kd6 48.Rxh7 Nd7 49.a5 Be4 50.Rh6+ Kc5 51.Rh5+ Kd6
54/71- 5:17:59.945 191,625,920k 10,043k +M34 43. ... Bf5 44.Rd5 Be4 45.Re5 Bg2 46.Re2 Bf3 47.Re7+ Kd6 48.Rxh7 Nd7
54/71 7:04:25.286 256,362,361k 10,067k +M24 43. ... Bf5 44.Rd5 Bg6 45.f5 Bh5 46.f6 Bg6 47.Rd4 Nc6 48.f7 Bxf7 49.Bxf7 Ne5 50.Bh5 Kb6 51.Rd5 Nc6 52.Rd6 Kc7 53.Rxc6+ Kxc6
55/71 7:33:53.106 274,534,343k 10,081k +M24 43. ... Bf5 44.Rd5 Bg6 45.f5 Bh5 46.f6 Bg6 47.Rd4 Nc6 48.f7 Bxf7 49.Bxf7 Ne5 50.Bh5 Kb6 51.Rd5 Nc6 52.Rd6 Kc7 53.Rxc6+ Kxc6 54.Kd4 Kc7 55.Bf7
56/71- 8:34:20.534 312,181,824k 10,116k +M32 43. ... Be8 44.Be6 Nc6
56/74- 14:14:09.045 517,316,307k 10,094k +M40 43. ... Be8 44.Be6 Nc6
56/74- 14:29:38.871 525,728,926k 10,076k +M51 43. ... Be8
56/74- 17:51:16.124 653,222,332k 10,163k +123.51 43. ... Nd7
56/75- 18:18:44.261 668,537,248k 10,141k +123.35 43. ... Nd7
56/75- 18:39:39.297 678,881,722k 10,106k +123.13 43. ... Nd7
56/75- 20:06:19.267 731,520,934k 10,107k +122.84 43. ... Nd7
56/75- 20:17:10.754 735,764,639k 10,075k +122.43 43. ... Nd7
56/75- 20:34:22.403 743,654,966k 10,041k +121.87 43. ... Nd7
56/75- 20:46:44.898 750,081,710k 10,027k +121.10 43. ... Nd7
56/75- 20:53:31.461 753,063,441k 10,013k +120.05 43. ... Nd7
56/75- 20:59:50.634 756,229,049k 10,004k +118.60 43. ... Nd7
56/75- 21:28:33.997 771,949,603k 9,985k +116.61 43. ... Nd7
56/75- 21:46:38.787 781,207,493k 9,965k +113.87 43. ... Nd7
56/75- 21:56:30.721 784,902,567k 9,937k +110.11 43. ... Nd7
56/75 25:07:30.658 899,477,435k 9,944k +M24 43. ... Bf5 44.Rd5 Bg6 45.f5 Bh5 46.f6 Bg6 47.Rd4
57/75- 26:42:19.260 956,216,361k 9,946k +M32 43. ... Bf5 44.Rd5 Bh3
57/75 30:12:54.512 1,086,334,318k 9,987k +M24 43. ... Nc6 44.Rd5 Ne7 45.Re5
58/75 35:11:25.737 1,269,825,516k 10,023k +M24 43. ... Nc6 44.Rd5 Ne7 45.Re5
59/75 38:14:36.866 1,386,206,840k 10,069k +M24 43. ... Nc6 44.Rd5 Ne7 45.Re5
60/75 43:51:45.495 1,598,624,748k 10,124k +M24 43. ... Nc6 44.Rd5 Ne7 45.Re5
61/75 51:01:08.022 1,866,180,440k 10,161k +M24 43. ... Nc6 44.Rd5 Ne7 45.Re5
62/75- 54:23:00.173 1,999,546,006k 10,213k +M32 43. ... Bf5
62/77- 55:51:15.723 2,043,320,356k 10,162k +M40 43. ... Bf5

This is running on 3-cores and 8 GB of cache. You'll notice that it finds the mate then loses it and then finds another mate etc. On one attempt that I let run to 70 plies it repeated this process a couple more times than is shown here.

I've come to the conclusion that there isn't sufficient cache for stockfish to do the work on one branch of the tree with out over-writing enough of the cache to destroy the PV's (not really a PV but the set of position in the cache from the other branches). So, when it gets back near the root position it doesn't have a good PV for the other branches to guide it to the mate. So it has to recreate them all over again. This takes a lot of time and in the process destroys the data from the last branch it searched. This would explain the behavior seen above and in the attempt that I let run to 70 plies.

I'm wondering what everyone else thinks. Is this a valid conclusion?

Assuming it is a valid conclusion, I wondering what can be done to remedy the problem other than buying a new machine with tons of memory.

I'm actually spec'ing a new machine specifically to play correspondence chess. The idea is to get enough cores and memory to support 25 games at a time control of 10 moves in 30-50 days. It appears that memory is going to be a problem. If 8-GB of cache isn't enough memory to solve a relatively simple position like this, then I'm going to need at least 512-GB of memory. DDR4 memory is still quite expensive so we're talking about $8K-$10K just for memory.

This seems excessive. I got to thinking about how to lessen the memory requirements. The only idea I could come up with is to split the cache ( or have a smaller secondary cache) who's sole purpose in life is to store the critical lines of play (similar to the PV). I.E. only a position that is deemed best at some point during a search can be written to the secondary cache. I'm thinking this will allow MUCH deeper/longer searches before this becomes an issue.


Short summation:

Most programs seem to have this issue to a greater or lesser extent. This can occur when analyzing any position. Its not restricted to "special" position or deep analysis. Over writing the cache can occur with any program and depends roughly on the number of positions per second written to the cache and the total number of entries the cache can store. e.g. cell-phones are unlikely to have much memory for cache so over writing the cache is likely to occur in very short periods of time. Solving this issue will have an impact on most platforms be it a phone a desk-top machine or a multi-rack blade cluster. Doing more with less always has tangible benefits.

So my questions are:

1.) What is the best way to solve this problem assuming that no extra memory can be added to the system?

2.) In your opinion, is adding a second cache for the critical lines likely to solve or at least mitigate this problem and to what extent do you think it will be effective?

All opinions and thoughts on the subject are welcome.

Regards,

Forrest
Only 2 defining forces have ever offered to die for you.....Jesus Christ and the American Soldier. One died for your soul, the other for your freedom.

xmas79
Posts: 286
Joined: Mon Jun 03, 2013 5:05 pm
Location: Italy

Re: Cache over-writing and PV's

Post by xmas79 » Thu Oct 16, 2014 1:04 am

This is called Search Instability. Welcome to the Transposition Tables party....
No reliable way to solve it, except... adding memory :)))

Zenmastur
Posts: 487
Joined: Sat May 31, 2014 6:28 am

Re: Cache over-writing and PV's

Post by Zenmastur » Thu Oct 16, 2014 1:16 am

xmas79 wrote:This is called Search Instability. Welcome to the Transposition Tables party....
No reliable way to solve it, except... adding memory :)))

I have an affliction...

It prevents me from believing nay sayers...

So you'll have to pardon me while I go ahead and look for a solution to this problem.

That is, unless you have evidence to support this claim.

Regards,

Forrest
Only 2 defining forces have ever offered to die for you.....Jesus Christ and the American Soldier. One died for your soul, the other for your freedom.

xmas79
Posts: 286
Joined: Mon Jun 03, 2013 5:05 pm
Location: Italy

Re: Cache over-writing and PV's

Post by xmas79 » Thu Oct 16, 2014 6:24 am

No problem here. Follow this. http://www.talkchess.com/forum/viewtopic.php?t=48274

EDIT:
btw, do you really think people behind one of the strongest chess program in the history of the world are unaware of this?

Zenmastur
Posts: 487
Joined: Sat May 31, 2014 6:28 am

Re: Cache over-writing and PV's

Post by Zenmastur » Thu Oct 16, 2014 8:49 am

xmas79 wrote:No problem here. Follow this. http://www.talkchess.com/forum/viewtopic.php?t=48274
No problem here either.

Thanks for the link!

xmas79 wrote:
EDIT:
btw, do you really think people behind one of the strongest chess program in the history of the world are unaware of this?
I don't really know who you are referring to, so I have no chances of knowing what they do or don't know. Nor do I know which program you are referring to as "one of the strongest chess program in history".

I have heard of search instability before, but never looked into it to determine exactly what was being referred to.

Even if I were aware that someone has knowledge about this subject, it wouldn't stop me from asking the questions that you saw in my first post. It might make me direct it in their general direction (a.k.a. a forum I knew that they visited on a regular basis).

In general, I don't consider responses like the first one you gave informative or useful. It's been my experience that on web forums there are plenty of idiots that will volunteer perfectly useless and misleading information. (passive aggressive type behavior) So, I generally put forth a terse challenge. If they respond with a similar passive aggressive post I tend to write them off as idiots and then ignore their posts until they prove other wise or brand themselves as a passive aggressive type.

If they respond in a more "normal" fashion, like you just did, then I'll take their posts at face value, and do the required research. Since now I know that this is referred to as "search instability" I shouldn't have any problems finding information about it. When I've had the opportunity to review the available information on the subject and have had time to review the thread you linked I will probably have additional questions, like who has tried what to mitigate the problem and how successful were they.

Until then... I'm still interested in any other comments and or thoughts on the subject. I would specifically like Bob's ( Dr. Hyatt ) opinion or thoughts on the subject should he read this and cares to comment.

Regards,

Forrest
Only 2 defining forces have ever offered to die for you.....Jesus Christ and the American Soldier. One died for your soul, the other for your freedom.

Stan Arts
Posts: 179
Joined: Fri Feb 14, 2014 9:53 pm
Location: the Netherlands

Re: Cache over-writing and PV's

Post by Stan Arts » Thu Oct 16, 2014 9:15 am

This second cache is already very common. The classical approach is a depth and exact score (possibly PV nodes) preferred part of the table, that eventually saves a lot of interesting nodes that took a lot of work high up the tree.
And an always replace part that simply stores every node searched. That gives you a lot of local hits or stuff deep down the tree.

Might not be just a lack of memory as a program like Stockfish does a lot of funky stuff depending on move ordening and so researching with hash information is sometimes going to have you search different searchspace. Just a guess.

xmas79
Posts: 286
Joined: Mon Jun 03, 2013 5:05 pm
Location: Italy

Re: Cache over-writing and PV's

Post by xmas79 » Thu Oct 16, 2014 9:19 am

Zenmastur wrote:
xmas79 wrote:No problem here. Follow this. http://www.talkchess.com/forum/viewtopic.php?t=48274
No problem here either.

Thanks for the link!

xmas79 wrote:
EDIT:
btw, do you really think people behind one of the strongest chess program in the history of the world are unaware of this?
I don't really know who you are referring to, so I have no chances of knowing what they do or don't know. Nor do I know which program you are referring to as "one of the strongest chess program in history".
Aren't you using "stockfish"? Why did you choose stockfish? It is a random choice or have you pondered on it and then picked up one of the strongest chess program in the world?
I have heard of search instability before, but never looked into it to determine exactly what was being referred to.

Even if I were aware that someone has knowledge about this subject, it wouldn't stop me from asking the questions that you saw in my first post. It might make me direct it in their general direction (a.k.a. a forum I knew that they visited on a regular basis).
Well, this is the right forum
In general, I don't consider responses like the first one you gave informative or useful. It's been my experience that on web forums there are plenty of idiots that will volunteer perfectly useless and misleading information. (passive aggressive type behavior) So, I generally put forth a terse challenge. If they respond with a similar passive aggressive post I tend to write them off as idiots and then ignore their posts until they prove other wise or brand themselves as a passive aggressive type.

If they respond in a more "normal" fashion, like you just did, then I'll take their posts at face value, and do the required research. Since now I know that this is referred to as "search instability" I shouldn't have any problems finding information about it. When I've had the opportunity to review the available information on the subject and have had time to review the thread you linked I will probably have additional questions, like who has tried what to mitigate the problem and how successful were they.
These people usually have a (very) high post counts, which I don't have. So, even if I don't have a very respectable reputation to reply to a such complex subject, maybe I gave the topic a try, so I can answer. When I faced the problem I didn't found a lot on the subject. That's why I posted to you the link... I had to do it all by myself, because no one replied in a satisfactory mode (in my opinion), something I was convinced but was difficult to prove. That's why I started to search "extensively" the subject.[/quote]
Until then... I'm still interested in any other comments and or thoughts on the subject. I would specifically like Bob's ( Dr. Hyatt ) opinion or thoughts on the subject should he read this and cares to comment.

Regards,

Forrest
Feel free to wait for other replies. There are a lot of smart people here. I've learn a lot since my first post.

Regards,
Natale.

User avatar
hgm
Posts: 23718
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Cache over-writing and PV's

Post by hgm » Thu Oct 16, 2014 9:20 am

Most programs use some sort of depth-preferred hashing, which would be very reluctant to overwrite results of very deep searches. So it would indeed is very fishy when, after having searched all daughter positions to N ply and found mate in at most M there, searching the original position would not instantly in all iterations upto N+1 report mate in M+1. The depth-N entries of the daughter nodes cannot possibly have been overwritten, as no search deeper than N has been performed, and it is pretty inconceivable that some 50 moves in a table of billions would collide with each other. (And even that should not be a problem in most hash designs, unless more than 3 of them mapped into the same bucket...)

So this likely has to do with undesirable flushing of the hashed tree of previous moves. E.g. after searching the positon after g1f3, taking it back, and trying g1e2, the engine might figure that the position after g1f3 now cannot occur anymore, as you already moved the Knight elsewhere, and thus consider all entries belonging to that search now worthless, no matter how deep a search they were from, and overwrite them. In a game this would of course be true, but in interactive analysis it can be very counter-productive, dooming your approach.

Note that the design goal of Stockfish is not to be a good or useful engine. Its goal is to optimize beating a small set of opponents in bullet games under conditions where hash replacement virtually does not occur. Any patches that would improve its hashing, or solve the problems that you are experiencing, would be instantly rejected, as they would not cause a higher win rate in the bulet games.

User avatar
Daniel Mehrmann
Posts: 855
Joined: Wed Mar 08, 2006 8:24 pm
Location: Germany
Full name: Daniel Mehrmann

Re: Cache over-writing and PV's

Post by Daniel Mehrmann » Thu Oct 16, 2014 12:57 pm

hgm wrote: Note that the design goal of Stockfish is not to be a good or useful engine. Its goal is to optimize beating a small set of opponents in bullet games under conditions where hash replacement virtually does not occur. Any patches that would improve its hashing, or solve the problems that you are experiencing, would be instantly rejected, as they would not cause a higher win rate in the bulet games.
And that's the way they are working :roll:

In my personal opinion that shouldn't be the way how "community" and/or "open source" projects should work.
I noticed this already some months ago, that they start to reject clean "bugfixes", because they lost 1 ELO point with there own fishcook stuff.

A chess engine should be for the users out there and not a potency extension for some project members.

At least i have to tell you that on this way SF isn't a good example how to write an chess engine.

Regards
Daniel

jdart
Posts: 3824
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Cache over-writing and PV's

Post by jdart » Thu Oct 16, 2014 4:27 pm

Stockfish doesn't exclusively use bullet games for testing. Still, you are right it is probably not tuned for very deep long time control searches.

--Jon

Post Reply