KNNN vs K : how come Stockfish cannot find the mate in 17?

[bstjean]

To make a long story short, I have posted an entry on the subject on my blog. Am I missing something here?

Stockfish seems to be unable to find this mate in 17 and alternates between different results even though its search deep enough to have seen the mate in 17!

My blog entry:

https://endormitoire.wordpress.com/2018 ... 3-knights/

P.S. Please reply here (not on my blog) !!

tia

[Toadofsky]

Here is the endgame code in question:

https://github.com/official-stockfish/S ... ndgame.cpp

[zullil]

To make a long story short, I have posted an entry on the subject on my blog. Am I missing something here?

Stockfish seems to be unable to find this mate in 17 and alternates between different results even though its search deep enough to have seen the mate in 17!

My blog entry:

https://endormitoire.wordpress.com/2018 ... 3-knights/

P.S. Please reply here (not on my blog) !!

tia

What is Stockfish 240813? Is it four years old?

Latest Stockfish (1 thread, 256 MB hash) finds Mate-in-20 at depth 45, Mate-in 19 at depth 46, Mate-in-18 at depth 54 and Mate-in-17 at depth ... not there yet!

[Guenther]

To make a long story short, I have posted an entry on the subject on my blog. Am I missing something here?

Stockfish seems to be unable to find this mate in 17 and alternates between different results even though its search deep enough to have seen the mate in 17!

My blog entry:

https://endormitoire.wordpress.com/2018 ... 3-knights/

P.S. Please reply here (not on my blog) !!

tia

[D]4k3/8/8/8/8/8/8/4KNNN w - - 0 1

[syzygy]

Cfish (which sets contempt to 0 in infinite mode) with default 16MB hash and 1 thread:

Code: Select all

info depth 49 seldepth 66 multipv 1 score mate 21 nodes 193417525 nps 5835496 hashfull 999 tbhits 0 time 33145 pv e1e2 e8d7 e2d3 d7d6 d3e4 d6e6 f1d2 e6d6 e4d4 d6e6 h1g3 e6d6 d2c4 d6e6 c4e5 e6d6 g1f3 d6e6 d4c5 e6e7 c5c6 e7e6 e5g4 e6e7 f3g5 e7e8 c6c7 e8f8 g3f5 f8g8 c7d7 g8f8 g4e5 f8g8 d7e7 g8h8 g5e4 h8h7 e4f6 h7h8 e5g6
...
info depth 51 seldepth 38 multipv 1 score mate 18 nodes 320876945 nps 5716776 hashfull 999 tbhits 0 time 56129 pv e1e2 e8d7 g1f3 d7d6 e2d3 d6c5 h1g3 c5d5 f1e3 d5d6 d3d4 d6c6 g3e4 c6c7 d4e5 c7b6 f3d4 b6a5 e5d5 a5b4 e3c2 b4a5 d5c6 a5a6 e4c5 a6a7 c6c7 a7a8 c2e3 a8a7 e3c4 a7a8 c4b6 a8a7 d4b5

But the shortest mate is in 17 moves:

Code: Select all

info depth 1 seldepth 1 multipv 1 score mate 17 nodes 0 nps 0 tbhits 13 time 3 pv f1h2 e8d7 h2g4 d7c6 g1e2 c6b5 e2f4 b5a4 g4e5 a4a3 f4d5 a3a2 e5c4 a2b3 c4b6 b3c2 h1f2 c2c1 f2d3 c1c2 d3c5 c2c1 b6a4 c1c2 d5e3 c2b1 e1d1 b1a1 e3c4 a1b1 a4c3 b1a1 c5b3

edit: Contempt plays no role here, since the specialised endgame code takes over. SF9 gives identical node counts. (And I now see that I am rehashing what Louis Zulli already wrote.)

[syzygy]

So I’m wondering why Stockfish, at 41 plies deep, is not able to stick to a mate-in-33 principal variation all along starting from ply 33 ?

Because it prunes away many branches of the search tree and reduces others. Without pruning and reducing, it would not get very deep.

The output of cripplefish (basically SF without pruning and reductions):

Code: Select all

info depth 14 seldepth 15 multipv 1 score cp 1025 nodes 50628474 nps 8952868 hashfull 999 tbhits 0 time 5655 pv e1d2 e8d8 d2c3 d8d7 f1g3 d7d6 g3e4 d6e5 h1g3 e5d5 c3d3 d5e6 d3d4 e6f7
info depth 15 seldepth 16 multipv 1 score cp 1025 nodes 156689513 nps 8619259 hashfull 999 tbhits 0 time 18179 pv e1d2 e8d8 d2c3 d8d7 f1g3 d7d6 g3e4 d6e5 h1g3 e5d5 c3d3 d5e6 d3d4 e6d7 g3f1
info depth 16 seldepth 17 multipv 1 score cp 1025 nodes 566885749 nps 8415637 hashfull 999 tbhits 0 time 67361 pv e1d2 e8d8 d2c3 d8d7 f1g3 d7d6 g3e4 d6e5 h1g3 e5d5 c3d3 d5c6 d3d4 c6d7 d4c3 d7c6 g3f1
info depth 17 seldepth 20 multipv 1 score cp 1030 nodes 2334788524 nps 8484339 hashfull 999 tbhits 0 time 275188 pv g1f3 e8d7 f3g5 d7d6 e1d2 d6e5 d2d3 e5d5 g5e4 d5e5 f1e3 e5e6 d3d4 e6d7 e3c4 d7e6 e4d2

Every additional ply takes more than 3x as long, so it will take a while before we are at 33 ply...

[syzygy]

But with 16 MB hash I'm not being fair to cripplefish. A larger TT really helps here, since the number of possible positions is relatively limited but far higher than fits in 16 MB.

Cripplefish with 6 threads and 4 GB hash:

Code: Select all

info depth 20 seldepth 21 multipv 1 score cp 1038 nodes 2999949682 nps 50541641 hashfull 292 tbhits 0 time 59356 pv e1d2 e8d8 g1f3 d8d7 d2c3 d7d6 c3d4 d6e6 h1g3 e6d7 g3e4 d7c8 f3e5 c8d8 f1e3 d8e7 e3f5 e7f8 f5g3 f8e8 g3f1
info depth 21 seldepth 24 multipv 1 score cp 1046 lowerbound nodes 9357538349 nps 50714241 hashfull 446 tbhits 0 time 184515 pv e1d1
info depth 21 seldepth 24 multipv 1 score cp 13257 lowerbound nodes 10075877548 nps 50674312 hashfull 447 tbhits 0 time 198836 pv e1d1
info depth 21 seldepth 25 multipv 1 score cp 13275 lowerbound nodes 10077032278 nps 50674258 hashfull 447 tbhits 0 time 198859 pv e1d1
info depth 21 seldepth 26 multipv 1 score mate 50 lowerbound nodes 10077652350 nps 50674063 hashfull 447 tbhits 0 time 198872 pv e1d1
info depth 21 seldepth 26 multipv 1 score mate 24 lowerbound nodes 10509004095 nps 50625552 hashfull 448 tbhits 0 time 207583 pv e1d1

Now it seems to get stuck. Maybe the TT is not big enough yet...

How Cripplefish can find mate at the 21st iteration (although the shortest mate needs 33 ply) is explained by HGM here.

[syzygy]

Cripplefish with 16 GB hash and just 1 thread:

Code: Select all

info depth 21 seldepth 24 multipv 1 score cp 1042 nodes 2821510076 nps 8500444 hashfull 86 tbhits 0 time 331925 pv g1f3 e8d7 f1e3 d7c6 h1g3 c6d6 g3f5 d6e6 f3d4 e6e5 e1e2 e5f6 e2f3 f6e5 e3g4 e5d5 g4f6 d5c5 f6d7 c5c4 f3e4 c4c3 e4e3 c3b2
info depth 22 seldepth 28 multipv 1 score cp 13275 lowerbound nodes 4279605865 nps 8724577 hashfull 101 tbhits 0 time 490523 pv e1d2
info depth 22 seldepth 28 multipv 1 score mate 61 lowerbound nodes 4279736164 nps 8724522 hashfull 101 tbhits 0 time 490541 pv e1d2
info depth 22 seldepth 28 multipv 1 score mate 47 lowerbound nodes 4283320678 nps 8724022 hashfull 101 tbhits 0 time 490980 pv e1d2
info depth 22 seldepth 29 multipv 1 score mate 28 lowerbound nodes 4322281822 nps 8719745 hashfull 101 tbhits 0 time 495689 pv e1d2
info depth 22 seldepth 30 multipv 1 score mate 18 nodes 7204845086 nps 8699759 hashfull 121 tbhits 0 time 828166 pv e1d2 e8d8 d2d3 d8c7 f1d2 c7d6 d2e4 d6d7 h1g3 d7e7 g1f3 e7d8 d3c4 d8c7 c4b5 c7d7 f3g5 d7c7 g3f5 c7d7 b5b6 d7e8 b6c6 e8d8 g5e6 d8c8

Still no mate in 17

[zullil]

To make a long story short, I have posted an entry on the subject on my blog. Am I missing something here?

Stockfish seems to be unable to find this mate in 17 and alternates between different results even though its search deep enough to have seen the mate in 17!

My blog entry:

https://endormitoire.wordpress.com/2018 ... 3-knights/

P.S. Please reply here (not on my blog) !!

tia

What is Stockfish 240813? Is it four years old?

Latest Stockfish (1 thread, 256 MB hash) finds Mate-in-20 at depth 45, Mate-in 19 at depth 46, Mate-in-18 at depth 54 and Mate-in-17 at depth ... not there yet!

And Mate-in-17 at depth 77 after almost an hour.

Code: Select all

info depth 77 seldepth 36 multipv 1 score mate 17 nodes 15506190692 nps 4684397 hashfull 999 tbhits 0 time 3310178 pv e1e2 e8d7 f1e3 d7d6 e2d3 d6c5 h1g3 c5d6 d3d4 d6c6 g1f3 c6b5 d4d5 b5b6 f3d4 b6c7 g3f5 c7b7 e3c4 b7a8 d5c6 a8a7 c6d7 a7b8 f5d6 b8a7 d7c8 a7a6 d6e8 a6a7 d4b5 a7a6 e8c7

Using 20 threads saves some time.

Code: Select all

info depth 67 seldepth 50 multipv 1 score mate 17 nodes 5813324357 nps 76498155 hashfull 84 tbhits 0 time 75993 pv e1f2 e8e7 f2e3 e7d6 e3d4 d6c6 h1g3 c6d7 f1e3 d7e8 d4c5 e8d7 g3f5 d7e8 c5d6 e8f8 g1f3 f8e8 f3e5 e8d8 f5d4 d8c8 e5d7 c8d8 e3c4 d8e8 d4e6 e8f7 c4e5 f7g8 d7f6 g8h8 e5g6

Using Cfish and 20 threads save a bit more time:

Code: Select all

info depth 66 seldepth 36 multipv 1 score mate 17 nodes 5028731282 nps 84039093 hashfull 82 tbhits 0 time 59838 pv e1d2 e8e7 f1e3 e7f6 d2d3 f6e5 g1f3 e5d6 d3d4 d6e6 d4c5 e6e7 e3d5 e7e6 h1g3 e6d7 f3d4 d7e8 d4e6 e8d7 e6c7 d7c8 c5c6 c8d8 g3e4 d8c8 e4d6 c8b8 d5b6 b8a7 d6b5 a7b8 c7a6

But the winner is Asmfish, who might have been very lucky.

Code: Select all

info depth 56 seldepth 36 multipv 1 time 11619 nps 77041413 score mate 17 nodes 895144179 hashfull 52 tbhits 0 pv e1e2 e8d7 e2d3 d7e6 d3d4 e6d6 f1e3 d6e6 h1g3 e6d6 g1f3 d6c6 g3f5 c6d7 d4d5 d7c7 f3d4 c7b6 e3c4 b6b7 f5d6 b7a7 d5c6 a7b8 d4e6 b8a8 c6b6 a8b8 c4e5 b8a8 e6c7 a8b8 e5c6

[CMCanavessi]

What about stockfish matefinder?