High branching factor when mate score is found

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

sandermvdb
Posts: 160
Joined: Sat Jan 28, 2017 1:29 pm
Location: The Netherlands

High branching factor when mate score is found

Post by sandermvdb »

I don't understand why my engine is so slow in finding deep mates. Eventually it finds them but the branching factor for the last ply is WAAAAAY higher than all the plies before. See the output below for a mate-in-12 position (NORMAL).

If I disable the following features, the mate-score is found much faster, see output below (DISABLED FEATURES).
- history heuristic
- aspiration window
- check extensions
- null move
- evaluate mobility


COMPARISON MATE-IN-12

Code: Select all

                        Normal features   disabled features
Time (seconds)              773           5
Ply                         19            25
Nodes (million)             4853          25
Extensions (million)        1030          0
Repetitions (million)       56            0.2
Branching-factor last ply   200           < 1

Why is the branching factor suddenly so high?
Should I disable certain features under certain conditions? If only 3 pieces left for instance. This sounds a bit artificial...
If the aspiration window is enabled, is it normal to have mate-in-40 scores (-32685)? In other words, what is the actual score, the boundary or the bestscore (which is outside the boundary)?

[d]8/2k5/KP6/8/8/8/8/8 b - - 0 9


NORMAL

Code: Select all

info depth 1 seldepth 3 time 212 score cp -305 nps 0 nodes 23 hashfull 0 pv c7b8 b6b7
info depth 2 seldepth 5 time 213 score cp -325 upperbound nps 0 nodes 71 hashfull 0 pv c7c8
info depth 2 seldepth 5 time 214 score cp -325 nps 0 nodes 95 hashfull 0 pv c7c8 b6b7 c8b8 a6b6
info depth 3 seldepth 5 time 214 score cp -390 upperbound nps 0 nodes 116 hashfull 0 pv c7c8
info depth 3 seldepth 5 time 214 score cp -390 upperbound nps 0 nodes 117 hashfull 0 pv c7c8
info depth 3 seldepth 5 time 215 score cp -390 nps 0 nodes 157 hashfull 0 pv c7c8 a6a7 c8d7 b6b7
info depth 4 seldepth 7 time 216 score cp -435 upperbound nps 1000 nodes 244 hashfull 0 pv c7c8
info depth 4 seldepth 7 time 216 score cp -455 upperbound nps 1000 nodes 273 hashfull 0 pv c7c8
info depth 4 seldepth 7 time 217 score cp -485 upperbound nps 1000 nodes 302 hashfull 0 pv c7c8
info depth 4 seldepth 7 time 217 score cp -530 upperbound nps 1000 nodes 331 hashfull 0 pv c7c8
info depth 4 seldepth 7 time 217 score cp -597 upperbound nps 1000 nodes 360 hashfull 0 pv c7c8
info depth 4 seldepth 7 time 218 score cp -697 upperbound nps 1000 nodes 389 hashfull 0 pv c7c8
info depth 4 seldepth 7 time 218 score cp -847 upperbound nps 1000 nodes 418 hashfull 0 pv c7c8
info depth 4 seldepth 7 time 219 score cp -902 nps 2000 nodes 477 hashfull 0 pv c7c8 a6a7 c8d7 b6b7 d7c7
info depth 5 seldepth 9 time 222 score cp -892 nps 3000 nodes 711 hashfull 0 pv c7c8 a6a7 c8d7 b6b7 d7d6 b7b8q d6d5
info depth 6 seldepth 9 time 225 score cp -897 nps 4000 nodes 1123 hashfull 0 pv c7c8 a6a7 c8d7 b6b7 d7c6 a7a8 c6c7
info depth 7 seldepth 9 time 227 score cp -918 upperbound nps 6000 nodes 1433 hashfull 0 pv c7c8
info depth 7 seldepth 11 time 229 score cp -918 nps 7000 nodes 1746 hashfull 0 pv c7c8 a6a7 c8d7 b6b7 d7c6 b7b8q c6c5 a7a6
info depth 8 seldepth 13 time 234 score cp -933 nps 13000 nodes 3118 hashfull 0 pv c7c8 a6a7 c8d7 b6b7 d7c6 b7b8q c6c5 b8c8 c5d5 a7b6
info depth 9 seldepth 14 time 251 score cp -935 nps 33000 nodes 8469 hashfull 0 pv c7c8 a6a7 c8d7 b6b7 d7c6 b7b8q c6c5 b8e5 c5c6 a7a6 c6d7
info depth 10 seldepth 15 time 269 score cp -953 nps 77000 nodes 20903 hashfull 0 pv c7c8 a6a7 c8d7 b6b7 d7c6 b7b8q c6d5 a7b6 d5d4
info depth 11 seldepth 17 time 310 score cp -958 nps 153000 nodes 47712 hashfull 1 pv c7c8 a6a7 c8d7 b6b7 d7c6 b7b8q c6d5 a7b6
info depth 12 seldepth 19 time 399 score cp -963 nps 515000 nodes 205623 hashfull 2 pv c7c8 a6a7 c8d7 b6b7 d7c6 b7b8q c6d5 a7b6
info depth 13 seldepth 21 time 479 score cp -975 nps 737000 nodes 353090 hashfull 4 pv c7c8 a6a7 c8d7 b6b7 d7c6 b7b8q c6d5
info depth 14 seldepth 23 time 599 score cp -980 nps 914000 nodes 547616 hashfull 6 pv c7c8 a6a7 c8d7 b6b7 d7c6 b7b8q c6d5 a7b6
info depth 15 seldepth 23 time 778 score cp -989 nps 1171000 nodes 911606 hashfull 10 pv c7c8 a6a7 c8d7 b6b7 d7c6 b7b8q c6d5
info depth 16 seldepth 25 time 1501 score cp -993 nps 1633000 nodes 2451834 hashfull 13 pv c7c8 a6a7 c8d7 b6b7 d7c6 b7b8q c6d5
info depth 17 seldepth 27 time 1890 score cp -1009 nps 2350000 nodes 4443147 hashfull 20 pv c7c8 a6a7 c8d7 b6b7 d7c6 b7b8q c6d5 b8g8 d5e4 g8g4 e4e3 a7b6 e3f2 g4f4 f2e2 b6c5 e2d3 f4f3 d3d2
info depth 18 seldepth 29 time 2589 score cp -1029 upperbound nps 3243000 nodes 8397791 hashfull 28 pv c7c8
info depth 18 seldepth 29 time 4937 score cp -1029 nps 4543000 nodes 22433422 hashfull 32 pv c7c8 a6a7 c8d7 b6b7 d7e6 a7b6 e6f5
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412741 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412742 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412743 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412744 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412745 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412746 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412747 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412748 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412749 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412750 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412751 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412752 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412753 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412754 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412755 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412756 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412757 hashfull 34 pv c7d6
info depth 19 seldepth 33 time 773295 score cp -32743 nps 6276000 nodes 4853293564 hashfull 56 pv c7c8 a6a7 c8d7 b6b7 d7e6 b7b8q e6f5 b8g3 f5e4 a7a6
Time        773295ms
Bestmove    c7c8 a6a7 c8d7 b6b7 d7e6 b7b8q e6f5 b8g3 f5e4 a7a6
Score       -32743
NPS         6276k
AB-nodes    4864944909
See-nodes   53849
Evaluated   3124013564
Q-Checks    272
Moves       4853293564/3766679367
TT          1680090250/1680725261 &#40;99%)
TT-usage    5%
Evalcache   -1555820907/-1170953732 &#40;132%)
Usage       100%
PEvalcache  384867148/384867175 &#40;99%)
Usage       0%
Depth       19/33
TT-best       564
TT-upper-best 67090565
TT-lower-best 1110965694
Promo-best    448
Win-cap-best  45973
Killer1-best  4951102
Killer2-best  3147489
Other-best    96600191
Los-cap-best  0
Null-move    6849/6841795 &#40;0%)
LMR-move     45097460/45196795 &#40;99%)
PVS-move     3520581287/3525293096 &#40;99%)
Stalemate,CM 155250, 3028
Repetitions  56788659&#40;63960564&#41;
Draw-by-mtrl 55860795
Bad bishop   0
Extensions   1030159951
IID          5
bestmove c7c8
DISABLED FEATURES

Code: Select all

info depth 1 seldepth 1 time 177 score cp -245 nps 0 nodes 7 hashfull 0 pv c7d6
info depth 2 seldepth 3 time 178 score cp -305 nps 0 nodes 41 hashfull 0 pv c7b8 b6b7
info depth 3 seldepth 3 time 179 score cp -305 nps 0 nodes 100 hashfull 0 pv c7c8 b6b7 c8b8
info depth 4 seldepth 5 time 179 score cp -390 nps 0 nodes 162 hashfull 0 pv c7c8 a6a7 c8d7 b6b7
info depth 5 seldepth 7 time 181 score cp -895 nps 1000 nodes 286 hashfull 0 pv c7c8 a6a7 c8d7 b6b7 d7c7
info depth 6 seldepth 9 time 183 score cp -885 nps 2000 nodes 513 hashfull 0 pv c7c8 a6a7 c8d7 b6b7 d7d6 b7b8q
info depth 7 seldepth 9 time 187 score cp -890 nps 4000 nodes 899 hashfull 0 pv c7c8 a6a7 c8d7 b6b7 d7c6 a7a8 c6c7
info depth 8 seldepth 11 time 191 score cp -910 nps 7000 nodes 1372 hashfull 0 pv c7c8 a6a7 c8d7 b6b7 d7c6 b7b8q c6c5 a7b7
info depth 9 seldepth 11 time 194 score cp -905 nps 10000 nodes 2066 hashfull 0 pv c7c8 a6a7 c8d7 b6b7 d7c6 b7b8q c6c5 a7b7 c5d5
info depth 10 seldepth 11 time 200 score cp -925 nps 19000 nodes 3871 hashfull 0 pv c7c8 a6a7 c8d7 b6b7 d7c6 b7b8q c6c5 a7b7 c5d5 b7c7
info depth 11 seldepth 11 time 205 score cp -925 nps 26000 nodes 5437 hashfull 0 pv c7c8 a6a7 c8d7 b6b7 d7c6 b7b8q c6c5 a7b7 c5d5 b7c7 d5e5
info depth 12 seldepth 13 time 222 score cp -945 nps 72000 nodes 16113 hashfull 0 pv c7c8 a6a7 c8d7 b6b7 d7c6 b7b8q c6c5 b8e5 c5c6 a7a6 c6d7 a6b5
info depth 13 seldepth 13 time 240 score cp -950 nps 134000 nodes 32372 hashfull 0 pv c7c8 a6a7 c8d7 b6b7 d7c6 b7b8q c6c5 b8f4 c5b5 f4c7 b5b4 a7b6 b4b3
info depth 14 seldepth 15 time 406 score cp -960 nps 454000 nodes 184569 hashfull 3 pv c7c8 a6a7 c8d7 b6b7 d7e6 b7b8q e6f5 a7b6 f5e4 b6c5 e4e3 c5d5 e3f3 d5e5
info depth 15 seldepth 15 time 448 score cp -970 nps 542000 nodes 242984 hashfull 4 pv c7c8 a6a7 c8d7 b6b7 d7e6 b7b8q e6f5 a7b6 f5e4 b6c5 e4e3 c5d5 e3d3 b8g3 d3d2
info depth 16 seldepth 17 time 536 score cp -975 nps 690000 nodes 370231 hashfull 5 pv c7c8 a6a7 c8d7 b6b7 d7e6 b7b8q e6f5 a7b6 f5e4 b6c5 e4e3 b8e8 e3f4 c5d5 f4f5 e8f8
info depth 17 seldepth 17 time 642 score cp -975 nps 812000 nodes 521459 hashfull 7 pv c7c8 a6a7 c8d7 b6b7 d7e6 b7b8q e6f5 a7b6 f5e4 b6c5 e4e3 b8e8 e3f4 c5d5 f4f5 e8f8
info depth 18 seldepth 19 time 1018 score cp -995 nps 1160000 nodes 1181121 hashfull 11 pv c7c8 a6a7 c8d7 b6b7 d7e6 b7b8q e6f5 a7b6 f5e4 b6c5 e4e3 b8e5 e3f3 c5d4 f3g4 d4e3 g4h4 e3d4
info depth 19 seldepth 19 time 1150 score cp -995 nps 1297000 nodes 1492173 hashfull 13 pv c7c8 a6a7 c8d7 b6b7 d7e6 b7b8q e6f5 a7b6 f5e4 b6c5 e4e3 b8e5 e3f3 c5d4 f3g4 d4e4 g4h4 e5g7 h4h5
info depth 20 seldepth 21 time 1388 score cp -995 nps 1690000 nodes 2346189 hashfull 18 pv c7c8 a6a7 c8d7 b6b7 d7e6 b7b8q e6f5 a7b6 f5e4 b6c5 e4f5 c5d5 f5g6 d5c6
info depth 21 seldepth 21 time 2849 score cp -32733 nps 3676000 nodes 10474655 hashfull 35 pv c7c8 a6a7 c8d7 b6b7 d7e6 b7b8q e6f5 b8b4 f5g6 b4g4 g6h6 a7b7 h6h7 b7a6 h7h8 g4d7
info depth 22 seldepth 23 time 3484 score cp -32741 nps 3992000 nodes 13913453 hashfull 37 pv c7c8 a6a7 c8d7 b6b7 d7e6 b7b8q e6f5 b8g3 f5e4 a7a6
info depth 23 seldepth 25 time 3934 score cp -32741 nps 4147000 nodes 16316345 hashfull 39 pv c7c8 a6a7 c8d7 b6b7 d7e6 b7b8q e6f5 b8g3 f5e4 a7a6
info depth 24 seldepth 25 time 4716 score cp -32741 nps 4330000 nodes 20421658 hashfull 42 pv c7c8 a6a7 c8d7 b6b7 d7e6 b7b8q e6f5 b8g3 f5e4 a7a6
info depth 25 seldepth 25 time 5697 score cp -32743 nps 4506000 nodes 25672831 hashfull 50 pv c7c8 a6a7 c8d7 b6b7 d7e6 b7b8q e6f5 b8g3 f5e4 a7b6 e4f5 g3h4 f5e5 b6c5 e5f5 c5d5 f5g6 d5e6 g6g7 h4g4 g7f8 g4g5
info depth 26 seldepth 25 time 6735 score cp -32743 nps 4623000 nodes 31137611 hashfull 57 pv c7c8 a6a7 c8d7 b6b7 d7e6 b7b8q e6f5 b8g3 f5e4 a7b6 e4f5 g3h4 f5e5 b6c5 e5f5 c5d5 f5g6 d5e6 g6g7 h4g4 g7f8 g4g5
Time        6735ms
Bestmove    c7c8 a6a7 c8d7 b6b7 d7e6 b7b8q e6f5 b8g3 f5e4 a7b6 e4f5 g3h4 f5e5 b6c5 e5f5 c5d5 f5g6 d5e6 g6g7 h4g4 g7f8 g4g5
Score       -32743
NPS         4622k
AB-nodes    27869885
See-nodes   29247
Evaluated   12914449
Q-Checks    3391571
Moves       31137611/40120000
TT          14196525/14496932 &#40;97%)
TT-usage    5%
Evalcache   10372137/12914449 &#40;80%)
Usage       100%
PEvalcache  2542285/2542312 &#40;99%)
Usage       0%
Depth       26/25
TT-best       637
TT-upper-best 1095825
TT-lower-best 1063228
Promo-best    723
Win-cap-best  17295
Killer1-best  158502
Killer2-best  40796
Other-best    721057
Los-cap-best  0
Null-move    0/0 &#40;0%)
LMR-move     3457912/3480533 &#40;99%)
PVS-move     21064596/21166619 &#40;99%)
Stalemate,CM 34006, 3796
Repetitions  248910&#40;254990&#41;
Draw-by-mtrl 317469
Bad bishop   0
Extensions   0
IID          0
bestmove c7c8
Top
Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: High branching factor when mate score is found

Post by Sven »

sandermvdb wrote:Why is the branching factor suddenly so high?
Due to a bug?
sandermvdb wrote:Should I disable certain features under certain conditions? If only 3 pieces left for instance. This sounds a bit artificial...
No, better identify the problem and fix it. But to identify the problem it might of course help to temporarily disable certain features. Starting from the "restricted" version I would re-enable those five features step by step until you (hopefully) find the one that causes the trouble. Of course it is not normal to search about 5000 million nodes for finding a forced mate from the given position. The solution is "mated in 24 plies" and my engine Jumbo (not the strongest) finds it in about 7 seconds in iteration 20 after having searched about 15 million nodes. There are various possible reasons why something could go wrong.
sandermvdb wrote:If the aspiration window is enabled, is it normal to have mate-in-40 scores (-32685)? In other words, what is the actual score, the boundary or the bestscore (which is outside the boundary)?
Such scores might indicate a problem in transforming TT mate scores (which should always be relative to the node where they are stored) to mate scores within search (which usually are relative to the root node). But they could also be caused by some other bug.
I do not understand the second part of your question, could you please rephrase it?
sandermvdb wrote:

Code: Select all

info depth 18 seldepth 29 time 2589 score cp -1029 upperbound nps 3243000 nodes 8397791 hashfull 28 pv c7c8
info depth 18 seldepth 29 time 4937 score cp -1029 nps 4543000 nodes 22433422 hashfull 32 pv c7c8 a6a7 c8d7 b6b7 d7e6 a7b6 e6f5
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412741 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412742 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412743 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412744 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412745 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412746 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412747 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412748 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412749 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412750 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412751 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412752 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412753 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412754 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412755 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412756 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412757 hashfull 34 pv c7d6
info depth 19 seldepth 33 time 773295 score cp -32743 nps 6276000 nodes 4853293564 hashfull 56 pv c7c8 a6a7 c8d7 b6b7 d7e6 b7b8q e6f5 b8g3 f5e4 a7a6
Something is unusual in your search. At the root node Black has five legal moves but your engine prints 18 "info depth 19" lines, of which the first 17 are identical apart from the minor differences in time (1 ms) and nodes (one node more has been searched between printing two consecutive lines). So what is your engine doing there? And why does it not start iteration 19 by searching the PV move Kc8 of iteration 18? Do you have a general move ordering problem?

The main problem itself is some sort of search explosion. Maybe you have a bug in your implementation of check extensions? Since there is no way to get a search explosion during qsearch from this position (the longest move sequence that could happen during qsearch would be two plies: a promotion followed by capturing the queen with the black king) it is very likely related to giving many checks somehow.

Or do you have a draw detection problem (king vs. king)?
Top
sandermvdb
Posts: 160
Joined: Sat Jan 28, 2017 1:29 pm
Location: The Netherlands

Re: High branching factor when mate score is found

Post by sandermvdb »

Sven Schüle wrote:
sandermvdb wrote:Should I disable certain features under certain conditions? If only 3 pieces left for instance. This sounds a bit artificial...
No, better identify the problem and fix it. But to identify the problem it might of course help to temporarily disable certain features. Starting from the "restricted" version I would re-enable those five features step by step until you (hopefully) find the one that causes the trouble.
All the features that I have disabled influence the number of nodes it searches befores it finds the mate-in-12.
Sven Schüle wrote:
sandermvdb wrote:

Code: Select all

info depth 18 seldepth 29 time 2589 score cp -1029 upperbound nps 3243000 nodes 8397791 hashfull 28 pv c7c8
info depth 18 seldepth 29 time 4937 score cp -1029 nps 4543000 nodes 22433422 hashfull 32 pv c7c8 a6a7 c8d7 b6b7 d7e6 a7b6 e6f5
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412741 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412742 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412743 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412744 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412745 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412746 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412747 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412748 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412749 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412750 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412751 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412752 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412753 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412754 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412755 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412756 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412757 hashfull 34 pv c7d6
info depth 19 seldepth 33 time 773295 score cp -32743 nps 6276000 nodes 4853293564 hashfull 56 pv c7c8 a6a7 c8d7 b6b7 d7e6 b7b8q e6f5 b8g3 f5e4 a7a6
Something is unusual in your search. At the root node Black has five legal moves but your engine prints 18 "info depth 19" lines, of which the first 17 are identical apart from the minor differences in time (1 ms) and nodes (one node more has been searched between printing two consecutive lines). So what is your engine doing there? And why does it not start iteration 19 by searching the PV move Kc8 of iteration 18? Do you have a general move ordering problem?
This is caused by the aspiration window: the score is outside the window, so the window is increased and the search is performed again. The score is again outside of window, etc...
Sven Schüle wrote: The main problem itself is some sort of search explosion. Maybe you have a bug in your implementation of check extensions? Since there is no way to get a search explosion during qsearch from this position (the longest move sequence that could happen during qsearch would be two plies: a promotion followed by capturing the queen with the black king) it is very likely related to giving many checks somehow.
Disabling extensions helps, but as I said, the other disabled features also help in finding the mate faster.
Sven Schüle wrote: Or do you have a draw detection problem (king vs. king)?
This could be it!! I only check for draw-by-material in my evaluation function :)
I'll check right away!
Top
Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: High branching factor when mate score is found

Post by Sven »

sandermvdb wrote:
Sven Schüle wrote:
sandermvdb wrote:

Code: Select all

info depth 18 seldepth 29 time 2589 score cp -1029 upperbound nps 3243000 nodes 8397791 hashfull 28 pv c7c8
info depth 18 seldepth 29 time 4937 score cp -1029 nps 4543000 nodes 22433422 hashfull 32 pv c7c8 a6a7 c8d7 b6b7 d7e6 a7b6 e6f5
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412741 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412742 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412743 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412744 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412745 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5262 score cp -32685 upperbound nps 4639000 nodes 24412746 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412747 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412748 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412749 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412750 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412751 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412752 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412753 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412754 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412755 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412756 hashfull 34 pv c7d6
info depth 19 seldepth 29 time 5263 score cp -32685 upperbound nps 4638000 nodes 24412757 hashfull 34 pv c7d6
info depth 19 seldepth 33 time 773295 score cp -32743 nps 6276000 nodes 4853293564 hashfull 56 pv c7c8 a6a7 c8d7 b6b7 d7e6 b7b8q e6f5 b8g3 f5e4 a7a6
Something is unusual in your search. At the root node Black has five legal moves but your engine prints 18 "info depth 19" lines, of which the first 17 are identical apart from the minor differences in time (1 ms) and nodes (one node more has been searched between printing two consecutive lines). So what is your engine doing there? And why does it not start iteration 19 by searching the PV move Kc8 of iteration 18? Do you have a general move ordering problem?
This is caused by the aspiration window: the score is outside the window, so the window is increased and the search is performed again. The score is again outside of window, etc...
So you probe the TT at the root and return the TT move as best move if there is one, right? That would explain why each iteration only burns one single node in that phase. I do not do this in my engine (probing at the root), and I'm not sure whether it is ok to do so, but it is certainly possible.
sandermvdb wrote:
Sven Schüle wrote:The main problem itself is some sort of search explosion. Maybe you have a bug in your implementation of check extensions? Since there is no way to get a search explosion during qsearch from this position (the longest move sequence that could happen during qsearch would be two plies: a promotion followed by capturing the queen with the black king) it is very likely related to giving many checks somehow.
Disabling extensions helps, but as I said, the other disabled features also help in finding the mate faster.
So none of these five features has an obviously much bigger influence on the problem than the other four?
sandermvdb wrote:
Sven Schüle wrote:Or do you have a draw detection problem (king vs. king)?
This could be it!! I only check for draw-by-material in my evaluation function :)
I'll check right away!
Not checking for a draw-by-material during search is indeed a possible source for that kind of behaviour when testing a KPK position. For instance promoting to a knight or bishop is an immediate draw in the given case but if you continue to search and have check extension enabled then it will take quite a while ...
Top
Ras
Posts: 2487
Joined: Tue Aug 30, 2016 8:19 pm
Full name: Rasmus Althoff

Re: High branching factor when mate score is found

Post by Ras »

Sven Schüle wrote:check extension enabled
I noticed that check extension in itself can make the search tree explode. That's why I activate the extension only when the remaining depth is 4 or less plies.
Top
User avatar
hgm
Posts: 27787
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: High branching factor when mate score is found

Post by hgm »

A large score drop of the PV move often causes a very long search time for the iteration on which it occurs. Because the refutation trees for all the other moves left over from the previous iteration are totally inadequate to push the score lower tha the dropped PV score; they were picked because they could push the score marginally below the previous, much higher PV score. So all hash moves will be wrong, and the search will have to find better moves, (often the very best, to show they lead to an even faster mate), that lead to sub-trees consisting of positions never searched before. And null moves will certainly not help to get a fast mate, so they will all fail low.

So it depends very much on how robust your search is. E.g. whether you do Internal Iterative Deepeing, in every node.

Fairy-Max does it like this:

Code: Select all

dep	score	nodes	time	&#40;not shown&#58;  tbhits	knps	seldep&#41;
 23	 #-12 	62.6M  	1&#58;01.85	c7c8 a6a7 c8d7 b6b7 d7e6 b7b8 e6f5 a7b6 f5g5 b6c6 g5g4 c6c5
 22	 #-15 	36.1M  	0&#58;33.75	c7c8 a6a7 c8d7 b6b7 d7e6 b7b8 e6f5 a7b6 f5e4 b6c5 e4f3 c5d5 f3e3
 21	 -8.58 	21.9M  	0&#58;20.34	c7c8 a6a7 c8d7 b6b7 d7e6 b7b8 e6f5 a7b6 f5e4 b6c6 e4f5 c6d5 f5g4 d5e4 g4g5 b8f4 g5g6 f4f5 g6g7 f5e6 g7f8
 20	 -8.56 	11.2M  	0&#58;10.50	c7c8 a6a7 c8d7 b6b7 d7e6 b7b8 e6f5 a7b6 f5e4 b6c5 e4f5 c5d4 f5g5 b8e5 g5g4 d4e4 g4h4 e5f4 h4h5 f4g3
 19	 -8.56 	3.37M  	0&#58;02.93	c7c8 a6a7 c8d7 b6b7 d7e6 b7b8 e6f5 a7b6 f5e4 b6c5 e4f5 c5d5 f5g4 d5e4 g4g5 b8f4 g5g6 f4f5 g6g7
 18	 -8.54 	1.60M  	0&#58;01.39	c7c8 a6a7 c8d7 b6b7 d7e6 b7b8 e6f5 a7b6 f5e4 b6c5 e4f5 c5d5 f5g4 d5e4 g4g5 b8f4 g5g6 e4d4
 17	 -8.53 	897602	0&#58;00.76	c7c8 a6a7 c8d7 b6b7 d7e6 b7b8 e6f5 a7b6 f5e4
 16	 -8.53 	343672	0&#58;00.28	c7c8 a6a7 c8d7 b6b7 d7c6 b7b8 c6d5 a7b6 d5d4 b8f4 d4d5 b6b5 d5e6 b5c5 e6e7 c5d5
 15	 -8.50 	179583	0&#58;00.14	c7c8 a6a7 c8d7 b6b7 d7c6 b7b8 c6d5 a7b6 d5d4 b6b5 d4e4 b5c4 e4e3 c4d5 e3f3
 14	 -8.49 	89632  	0&#58;00.06	c7c8 a6a7 c8d7 b6b7 d7c6 b7b8 c6d5 a7b6 d5d4 b6c6 d4e4 c6c5 e4f5 c5d5
 13	 -8.47 	58103  	0&#58;00.04	c7c8 a6a7 c8d7 b6b7 d7c6 b7b8 c6d5 a7b6 d5d4 b6c6 d4e4 c6d6 e4f4
 12	 -8.47 	25836  	0&#58;00.01	c7c8 a6a7 c8d7 b6b7 d7c6 b7b8 c6d5 a7b6 d5d4 b6c6 d4e4 c6d6
 11	 -8.41 	12897  	0&#58;00.01	c7c8 a6a7 c8d7 b6b7 d7c6 b7b8 c6c5 a7b7 c5d5 b7c7 d5e5
 10	 -8.42 	7163    	0&#58;00.01	c7c8 a6a7 c8d7 b6b7 d7c6 b7b8 c6c5 a7b7 c5d5 b7c7
  9	 -8.38 	4706    	0&#58;00.00	c7c8 a6a7 c8d7 b6b7 d7c6 b7b8 c6c5 a7b7 c5d5
  8	 -8.41 	2487    	0&#58;00.00	c7c8 a6a7 c8d7 b6b7 d7d6 a7b6 d6e5 b7b8
  7	 -8.32 	1700    	0&#58;00.00	c7c8 a6a7 c8d7 b6b7 d7e6 b7b8 e6d5
  6	 -8.33 	1334    	0&#58;00.00	c7c8 a6a7 c8d7 b6b7 d7e6 b7b8
  6	 -8.34 	966      	0&#58;00.00	c7d6 b6b7 d6c7 a6a7 c7d6 b7b8
  5	 -1.88 	490      	0&#58;00.00	c7d6 b6b7 d6c7 a6a7 c7d6
  4	 -1.94 	191      	0&#58;00.00	c7d6 b6b7 d6c7 a6a7
  3	 -1.88 	89        	0&#58;00.00	c7d6 b6b7 d6e5
  2	 -1.91 	17        	0&#58;00.00	c7d6 b6b7
  1	 -1.31 	11        	0&#58;00.00	c7d6
Top
JVMerlino
Posts: 1357
Joined: Wed Mar 08, 2006 10:15 pm
Location: San Francisco, California

Re: High branching factor when mate score is found

Post by JVMerlino »

Ok, this may or not be helpful. But Myrddin has always had a similar problem, or at least a problem that looks similar. Sometimes when it reports a mate score, on a subsequent ply it will fail low multiple times and then report a silly mate score like "Mate in 51". Your post led me to investigate this again and I've determined that if I disable the zero-width window search, and just search every node at [Alpha, Beta], then the problem goes away.

Your position demonstrates this problem.

Output with PVS enabled:

Code: Select all

 1    100      0            2 c7b8 
 1     90      0            6 c7d7 &#40;0 KNPS&#41;
 1     87      1            9 c7d6 &#40;0 KNPS&#41;
 2     97      1           19 c7d6 a6b5 &#40;1 KNPS&#41;
 3    100      1           54 c7d6 a6b5 d6d7 &#40;3 KNPS&#41;
 4    109      2          173 c7d6 a6b5 d6d7 b6b7 &#40;8 KNPS&#41;
 4    106      2          282 c7d7 a6b5 d7d6 b6b7 &#40;11 KNPS&#41;
 4    105      2          332 c7c6 a6a5 c6b7 a5b5 &#40;11 KNPS&#41;
 5    121      3          443 c7c6? b6b7 c6d7 a5b5 d7c7 &#40;13 KNPS&#41;
 5    110      3          624 c7c8 a6b5 c8b8 b5c5 b8b7 &#40;16 KNPS&#41;
 6    126      4          913 c7c8? a6a7 c8d7 &#40;21 KNPS&#41;
 6    142      4          979 c7c8? a6a7 &#40;20 KNPS&#41;
 6    174      5         1045 c7c8? a6a7 &#40;20 KNPS&#41;
 6    222      5         1111 c7c8? a6a7 &#40;19 KNPS&#41;
 6    286      6         1192 c7c8? a6a7 &#40;19 KNPS&#41;
 6    366      6         1341 c7c8? a6a7 &#40;20 KNPS&#41;
 6    462      7         1469 c7c8? a6a7 &#40;20 KNPS&#41;
 6    574      7         1618 c7c8? a6a7 &#40;21 KNPS&#41;
 6    702      7         1756 c7c8? a6a7 &#40;22 KNPS&#41;
 6    846      8         1893 c7c8? a6a7 &#40;22 KNPS&#41;
 6    928      9         2065 c7c8 a6a7 c8d7 b6b7 d7c7 b7b8Q c7d7 &#40;22 KNPS&#41;
 6    921      9         2185 c7d6 a6a7 d6c6 b6b7 c6d6 b7b8Q d6e6 &#40;22 KNPS&#41;
 7    937     10         2586 c7d6? a6a7 &#40;24 KNPS&#41;
 7    938     10         3186 c7d6 a6a7 d6c6 b6b7 c6d6 b7b8Q d6d5 b8b4 &#40;29 KNPS&#41;
 8    942     11         5329 c7d6 a6a7 d6c6 b6b7 c6d6 b7b8Q d6e6 b8g8 e6e5 g8c4 &#40;45 KNPS&#41;
 9    946     12        11025 c7d6 a6a7 d6c6 b6b7 c6d6 b7b8Q d6d5 b8b5 d5d4 b5b4 d4d5 a7b6 &#40;86 KNPS&#41;
10    950     17        67153 c7d6 b6b7 d6c7 a6a7 c7d6 &#40;388 KNPS&#41;
11    956     19       102921 c7d6 b6b7 d6c7 a6a7 c7d6 b7b8Q d6d5 b8b5 d5e4 b5c4 e4e5 a7b6 e5d6 c4d4 d6e6 &#40;522 KNPS&#41;
12    961     25       223534 c7d6 b6b7 d6c7 a6a7 c7d6 b7b8Q d6d5 b8b5 d5e4 b5c4 e4e5 a7b6 e5f6 c4d4 f6f5 b6c5 &#40;880 KNPS&#41;
13    963     35       508734 c7d6 b6b7 d6c7 a6a7 c7d6 b7b8Q d6d5 b8d8 d5e5 a7b6 e5e6 b6c5 e6e5 d8d4 e5f5 c5d5 &#40;1429 KNPS&#41;
14    967     62      1291862 c7d6 b6b7 d6c7 a6a7 c7d6 b7b8Q d6d5 a7b6 d5d4 b8f4 d4d5 f4f5 d5d4 b6b5 d4e3 f5e5 e3d2 e5d4 d2e2 &#40;2070 KNPS&#41;
15    970    103      2638210 c7d6 b6b7 d6c7 a6a7 c7d6 b7b8Q d6d5 a7b6 d5e4 b6c5 e4f5 c5d5 f5f6 b8e5 f6f7 d5e4 f7g8 &#40;2544 KNPS&#41;
16    970    149      4310312 c7d6 b6b7 d6c7 a6a7 c7d6 b7b8Q d6d5 a7b6 d5e4 b6c5 e4f5 c5d5 f5f6 b8e5 f6f7 d5e4 f7g8 e4d4 &#40;2888 KNPS&#41;
17    973    253      8064655 c7d6 b6b7 d6c7 a6a7 c7d6 b7b8Q d6d5 a7b6 d5e4 b6c6 e4d4 b8f4 d4c3 f4e4 c3b3 e4d5 b3b2 c6d6 b2c2 d6e5 &#40;3180 KNPS&#41;
18    989    358     11865590 c7d6? b6b7 &#40;3312 KNPS&#41;
18   1005    431     14523169 c7d6? b6b7 &#40;3369 KNPS&#41;
18   1037    487     16584320 c7d6? b6b7 &#40;3404 KNPS&#41;
18   1085    495     16893913 c7d6? b6b7 &#40;3408 KNPS&#41;
18   1149    530     18102990 c7d6? b6b7 &#40;3415 KNPS&#41;
18   1229    633     21832539 c7d6? b6b7 &#40;3444 KNPS&#41;
18   1325    707     24429216 c7d6? b6b7 &#40;3454 KNPS&#41;
18   1437    791     27384461 c7d6? b6b7 &#40;3459 KNPS&#41;
18   1565    823     28533174 c7d6? b6b7 &#40;3464 KNPS&#41;
18   1709    907     31434564 c7d6? b6b7 &#40;3463 KNPS&#41;
18  32661   1295     43942012 c7d6 b6b7 d6d5 b7b8Q d5e4 b8g3 e4f5 a6b5 f5e6 g3g4 e6e7 g4e4 e7f6 e4g4 f6e5 &#40;3391 KNPS&#41;&#40;Mate in 53&#41; 
18  32655   1347     45408506 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 b8g3 f5f6 a7b6 f6f7 g3g4 f7f6 g4f3 f6e5 &#40;3370 KNPS&#41;&#40;Mate in 56&#41; 
19  32651   1380     46258242 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 b8g3 f5e4 a7a6 e4f5 g3f3 f5e5 a6b6 &#40;3352 KNPS&#41;&#40;Mate in 58&#41; 
20  32651   1421     47429955 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 b8g3 f5e4 a7a6 e4f5 g3f3 f5e5 a6b6 &#40;3336 KNPS&#41;&#40;Mate in 58&#41; 
21  32655   1481     49243523 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 b8g3 f5e4 a7a6 e4f5 g3f3 f5e5 a6b5 e5d6 f3f4 d6e7 f4e4 &#40;3324 KNPS&#41;&#40;Mate in 56&#41; 
22  32639   1711     57059012 c7c8! &#40;3334 KNPS&#41;&#40;Mate in 64&#41; 
22  32623   1892     63011199 c7c8! &#40;3330 KNPS&#41;&#40;Mate in 72&#41; 
22  32591   2081     69516752 c7c8! &#40;3340 KNPS&#41;&#40;Mate in 88&#41; 
22  32651   2100     70027912 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 b8g3 f5e4 a7b6 e4f5 g3f3 f5e5 f3f2 &#40;3334 KNPS&#41;&#40;Mate in 58&#41; 
23  32651   2235     74581515 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 b8g3 f5e4 a7b6 e4f5 g3h4 f5e5 h4f2 &#40;3335 KNPS&#41;&#40;Mate in 58&#41; 
24  32645   2549     85276986 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 b8g3 f5e4 g3g4 e4e5 g4f3 e5e6 f3f4 e6e7 a7b6 e7e6 f4f1 &#40;3344 KNPS&#41;&#40;Mate in 61&#41; 
25  32661   3679    125899541 c7c8? a6a7 &#40;3422 KNPS&#41;&#40;Mate in 53&#41; 
25  32629   5585    197199458 c7c8! &#40;3530 KNPS&#41;&#40;Mate in 69&#41; 
25  32597   6475    229613160 c7c8! &#40;3545 KNPS&#41;&#40;Mate in 85&#41; 
25  32677   7062    250723913 c7c8? a6a7 &#40;3550 KNPS&#41;&#40;Mate in 45&#41; 
25  32715   9296    334464443 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 b8b5 f5e4 a7b6 e4d4 b5a4 d4e3 b6c5 e3f3 a4b5 f3e4 &#40;3597 KNPS&#41;&#40;Mate in 26&#41; 
26  32731   9989    359494487 c7c8? a6a7 &#40;3598 KNPS&#41;&#40;Mate in 18&#41; 
26  32699  12797    465708489 c7c8! &#40;3639 KNPS&#41;&#40;Mate in 34&#41; 
26  32725  13656    498128406 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 b8b4 f5e5 b4g4 e5d5 g4f4 d5e6 f4e4 e6f6 e4f4 &#40;3647 KNPS&#41;&#40;Mate in 21&#41; 
27  32725  14167    517875572 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 b8b4 f5e5 b4g4 e5d5 g4f4 d5e6 f4g5 e6f7 g5f5 f7g7 a7b7 g7h6 f5g4 h6h7 g4g5 &#40;3655 KNPS&#41;&#40;Mate in 21&#41; 
28  32741  19080    702994062 c7c8? a6a7 &#40;3684 KNPS&#41;&#40;Mate in 13&#41; 
28  32737  59958   2208144090 c7d7 a6a7 d7d6 b6b7 d6e6 b7b8Q e6f5 a7b6 f5g4 b8a8 g4g5 b6c5 g5f4 c5d4 f4f5 &#40;3682 KNPS&#41;&#40;Mate in 15&#41; 
29  32737  75549   2812016938 c7d7 a6a7 d7d6 b6b7 d6e6 b7b8Q e6f5 a7b6 f5g5 b6c6 g5g4 c6c5 &#40;3722 KNPS&#41;&#40;Mate in 15&#41; 
29  32733  87352   3263525112 c7d6 b6b7 d6d5 b7b8Q d5e4 b8c7 e4e3 c7g3 e3e4 a6b6 &#40;3736 KNPS&#41;&#40;Mate in 17&#41; 
30  32739 110201   4139038044 c7d6 b6b7 d6d5 b7b8Q d5e4 a6b5 e4f5 b8c7 f5f6 c7d6 f6g7 d6e6 g7h7 e6f6 h7g8 b5c4 g8h7 c4d5 h7g8 d5e5 g8h7 f6f8 h7g6 f8g8 g6h5 e5f5 h5h4 g8g4 &#40;3755 KNPS&#41;&#40;Mate in 14&#41; 
30  32737 131010   4904398407 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 b8c7 f5g4 a7b6 g4g5 b6c5 g5f5 c7f7 f5e4 f7e7 e4f4 e7h4 f4e5 c5c6 e5f5 c6d6 f5g6 d6e6 g6g7 h4g5 g7h7 e6f6 h7h8 g5g7 &#40;3743 KNPS&#41;&#40;Mate in 15&#41; 
31  32739 146366   5486621925 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 a7b6 f5f6 b6c6 f6f5 c6d5 f5g4 d5e4 g4g5 b8e5 g5g6 e5e6 g6g7 e4e5 &#40;3748 KNPS&#41;&#40;Mate in 14&#41; 
32  32729 172665   6499867848 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 b8c8 f5f4 c8h3 f4e4 h3g3 &#40;3764 KNPS&#41;&#40;Mate in 19&#41; 
33  32741 182150   6852820490 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 b8g3 f5e4 a7b6 e4f5 g3h4 f5g6 h4g4 g6f6 b6c6 f6e5 c6c5 e5f6 c5d6 f6f7 g4g5 f7f8 d6e6 &#40;3762 KNPS&#41;&#40;Mate in 13&#41; 
34  32729 206784   7798172656 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 b8f8 f5g4 f8f2 g4g5 f2f3 g5g6 f3f4 g6g7 f4g5 g7f7 g5f5 f7g7 a7b6 &#40;3771 KNPS&#41;&#40;Mate in 19&#41; 
35  32737 395313  14952753877 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 b8f8 f5g4 f8g7 g4f3 g7e7 f3f4 a7b6 f4f3 b6c5 f3f4 c5d4 f4f3 e7f7 f3g4 d4e3 g4g5 f7e6 g5h4 e3f4 h4h5 e6d6 h5h4 d6h6 &#40;3782 KNPS&#41;&#40;Mate in 15&#41;
Output with PVS disabled:

Code: Select all

 1    100      0            2 c7b8 
 1     90      0            5 c7d7 &#40;2 KNPS&#41;
 1     87      0            7 c7d6 &#40;1 KNPS&#41;
 2     97      0           15 c7d6 a6b5 &#40;3 KNPS&#41;
 3    100      0           45 c7d6 a6b5 d6d7 &#40;6 KNPS&#41;
 4    109      1          151 c7d6 a6b5 d6d7 b6b7 &#40;15 KNPS&#41;
 4    106      1          219 c7d7 a6b5 d7d6 b6b7 &#40;16 KNPS&#41;
 4    105      1          247 c7c6 a6a5 c6b7 a5b5 &#40;15 KNPS&#41;
 5    121      1          321 c7c6? b6b7 c6d7 a5b5 &#40;17 KNPS&#41;
 5    137      2          621 c7c6? b6b7 &#40;29 KNPS&#41;
 5    169      2          743 c7c6? b6b7 &#40;32 KNPS&#41;
 5    217      2          865 c7c6? b6b7 &#40;34 KNPS&#41;
 5    281      2          987 c7c6? b6b7 &#40;35 KNPS&#41;
 5    361      3         1109 c7c6? b6b7 &#40;34 KNPS&#41;
 5    457      3         1231 c7c6? b6b7 &#40;35 KNPS&#41;
 5    569      3         1353 c7c6? b6b7 &#40;36 KNPS&#41;
 5    697      4         1475 c7c6? b6b7 &#40;36 KNPS&#41;
 5    841      4         1597 c7c6? b6b7 &#40;37 KNPS&#41;
 5    928      4         1757 c7c6 b6b7 c6d7 a6a7 d7c7 b7b8Q c7d7 &#40;37 KNPS&#41;
 6    921      5         2257 c7c6 b6b7 c6c7 a6a7 c7d6 b7b8Q &#40;44 KNPS&#41;
 7    923      5         2688 c7c6 b6b7 c6c7 a6a7 c7c6 b7b8Q c6d5 &#40;49 KNPS&#41;
 8    938      5         3527 c7c6 b6b7 c6c7 a6a7 c7c6 b7b8Q c6d5 b8b4 &#40;60 KNPS&#41;
 9    942      6         6063 c7c6 b6b7 c6c7 a6a7 c7c6 b7b8Q c6d5 b8b5 d5e4 a7b6 &#40;91 KNPS&#41;
10    946      7        10977 c7c6 b6b7 c6c7 a6a7 c7c6 b7b8Q c6d5 b8b5 d5d4 b5b4 d4d5 &#40;148 KNPS&#41;
11    950      8        24094 c7c6 b6b7 c6c7 a6a7 c7c6 b7b8Q c6d5 b8b5 d5d4 a7b6 d4e4 b5c4 e4e5 &#40;270 KNPS&#41;
12    956     11        51297 c7c6 b6b7 c6c7 a6a7 c7c6 b7b8Q c6d5 b8b5 d5d4 a7b6 d4e4 b5c4 e4e5 b6c5 &#40;449 KNPS&#41;
13    958     18       154780 c7c6 b6b7 c6c7 a6a7 c7c6 b7b8Q c6d5 b8b3 d5d4 b3e6 d4d5 &#40;855 KNPS&#41;
14    967     38       502170 c7c6 b6b7 c6c7 a6a7 c7c6 b7b8Q c6d5 b8f4 d5e6 a7b6 e6e7 f4e5 e7f8 b6c5 f8g8 &#40;1321 KNPS&#41;
14    965     40       535490 c7c8 a6a7 c8d7 &#40;1312 KNPS&#41;
15    967     46       640616 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 a7b6 f5e4 b8a8 e4d4 a8a4 d4d5 a4f4 d5e6 b6a6 &#40;1365 KNPS&#41;
16    970     78      1203516 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 a7b6 f5e4 b6c5 e4f5 c5d5 f5g5 b8e5 g5g6 d5d4 g6f7 &#40;1525 KNPS&#41;
17    971    130      2113053 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 a7b6 f5e4 b6c5 e4f5 b8d6 f5e4 d6f6 &#40;1621 KNPS&#41;
18    987    235      4026406 c7c8? a6a7 &#40;1707 KNPS&#41;
18   1003    382      6696748 c7c8? a6a7 &#40;1748 KNPS&#41;
18   1035    465      8241049 c7c8? a6a7 &#40;1771 KNPS&#41;
18   1083    540      9654600 c7c8? a6a7 &#40;1785 KNPS&#41;
18   1147    598     10727061 c7c8? a6a7 &#40;1792 KNPS&#41;
18   1227    626     11236878 c7c8? a6a7 &#40;1794 KNPS&#41;
18   1323    630     11285737 c7c8? a6a7 &#40;1791 KNPS&#41;
18   1435    635     11357041 c7c8? a6a7 &#40;1788 KNPS&#41;
18   1563    636     11365660 c7c8? a6a7 &#40;1785 KNPS&#41;
18   1707    638     11374080 c7c8? a6a7 &#40;1782 KNPS&#41;
18    981    682     12287356 c7c8 a6a7 c8d7 b6b7 d7d6 b7b8Q d6e6 b8g3 e6e7 a7a6 e7e6 g3f4 e6e7 a6b6 e7e6 f4g5 e6e5 b6b7 e5d6 b7b8 &#40;1800 KNPS&#41;
19    997    697     12560928 c7c8? a6a7 &#40;1800 KNPS&#41;
19   1013    725     13084794 c7c8? a6a7 &#40;1803 KNPS&#41;
19   1045    760     13722372 c7c8? a6a7 &#40;1804 KNPS&#41;
19    981    780     14094392 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 b8g3 &#40;1804 KNPS&#41;
20    997    785     14181412 c7c8? a6a7 &#40;1804 KNPS&#41;
20   1013    797     14365952 c7c8? a6a7 &#40;1802 KNPS&#41;
20   1045    811     14590053 c7c8? a6a7 &#40;1797 KNPS&#41;
20   1093    834     14986022 c7c8? a6a7 &#40;1795 KNPS&#41;
20    981    870     15679635 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 b8g3 &#40;1800 KNPS&#41;
21    997    872     15692372 c7c8? a6a7 &#40;1799 KNPS&#41;
21   1013    898     16142428 c7c8? a6a7 &#40;1796 KNPS&#41;
21   1045    918     16456962 c7c8? a6a7 &#40;1791 KNPS&#41;
21   1093    944     16885830 c7c8? a6a7 &#40;1788 KNPS&#41;
21   1157    967     17293264 c7c8? a6a7 &#40;1786 KNPS&#41;
21   1237    991     17710518 c7c8? a6a7 &#40;1786 KNPS&#41;
21   1333   1017     18172581 c7c8? a6a7 &#40;1786 KNPS&#41;
21   1445   1056     18867738 c7c8? a6a7 &#40;1786 KNPS&#41;
21   1573   1098     19621965 c7c8? a6a7 &#40;1787 KNPS&#41;
21   1717   1120     20007488 c7c8? a6a7 &#40;1785 KNPS&#41;
21  32725   1940     36559598 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 b8b4 f5g5 b4e4 g5f6 e4f4 &#40;1884 KNPS&#41;&#40;Mate in 21&#41; 
21  32723   8804    175861973 c7d6 b6b7 d6e6 b7b8Q e6f5 b8b4 f5g5 a6b6 g5f5 b6a7 f5e4 &#40;1997 KNPS&#41;&#40;Mate in 22&#41; 
22  32739  17262    346533862 c7d6? b6b7 &#40;2007 KNPS&#41;&#40;Mate in 14&#41; 
22  32739  22545    452124642 c7d6 b6b7 d6c7 a6a7 c7d6 b7b8Q d6d5 b8f4 d5c5 a7b7 c5d5 b7b6 d5e6 b6c6 e6e7 f4f5 &#40;2005 KNPS&#41;&#40;Mate in 14&#41; 
23  32741  32772    659023374 c7d6 b6b7 d6e6 a6b5 e6f5 b5c5 f5e5 b7b8Q e5f5 b8a8 &#40;2010 KNPS&#41;&#40;Mate in 13&#41; 
23  32739  34922    702830623 c7c8 a6a7 c8d7 b6b7 d7e6 &#40;2012 KNPS&#41;&#40;Mate in 14&#41; 
24  32739  35691    718754346 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 a7b6 f5e4 b6c5 e4e3 c5c4 e3e4 b8g3 e4f5 c4d5 &#40;2013 KNPS&#41;&#40;Mate in 14&#41; 
25  32741  44727    899972382 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 a7b6 f5e4 b6c5 e4f5 c5d4 f5f6 b8d6 f6f7 d4e5 f7e8 e5f5 e8f7 d6d8 &#40;2012 KNPS&#41;&#40;Mate in 13&#41; 
26  32741  74248   1501525620 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 a7b6 f5g5 b6c6 g5g4 c6d5 g4f3 d5d4 f3g4 d4e4 g4h3 b8f4 &#40;2022 KNPS&#41;&#40;Mate in 13&#41; 
27  32741 101003   2029087974 c7c8 a6a7 c8d7 b6b7 d7e6 b7b8Q e6f5 a7b6 f5e4 b6c5 e4e3 b8e8 e3f4 c5d4 f4f3 d4d3 f3f4 e8h5 f4g3 d3e3 g3g2 h5g6 g2f1 g6g8 f1e1 g8g1 &#40;2008 KNPS&#41;&#40;Mate in 13&#41;
As far as I'm aware, this behavior shouldn't happen. Maybe I'm wrong, but does this mean that there's a bug in my PVS implementation?

jm
Top
sandermvdb
Posts: 160
Joined: Sat Jan 28, 2017 1:29 pm
Location: The Netherlands

Re: High branching factor when mate score is found

Post by sandermvdb »

sandermvdb wrote:
Sven Schüle wrote: Or do you have a draw detection problem (king vs. king)?
This could be it!! I only check for draw-by-material in my evaluation function :)
I'll check right away!
Unfortunately this did not improve the situation :(

Out of the 5 features I disabled, the nullmove and check-extensions seem to have the highest impact.

Investigation continues...
Top
User avatar
hgm
Posts: 27787
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: High branching factor when mate score is found

Post by hgm »

Rather than just trying random things to see if they have an effect, you could try to learn how the engine actually burns this large number of nodes: let it print node counts for every move it searches in the root, or on every pair of moves in the first two ply levels, etc.
Top
Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: High branching factor when mate score is found

Post by Sven »

hgm wrote:Rather than just trying random things to see if they have an effect, you could try to learn how the engine actually burns this large number of nodes: let it print node counts for every move it searches in the root, or on every pair of moves in the first two ply levels, etc.
I would even suggest to do this for the first four plies in the given position since that would already include pawn promotion on b8. If one specific variation shows up that consumes many nodes then use the position after these four plies as new subject of test, and repeat the same process from there, etc. If no specific variation shows up, i.e. node burning looks almost evenly distributed, then select any arbitrary line and proceed as above as if this were the "one specific variation".
Top

Return to “Computer Chess Club: Programming and Technical Discussions”