Null move pruning = lottery?

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
OliverBr
Posts: 563
Joined: Tue Dec 18, 2007 8:38 pm
Location: Munich, Germany
Full name: Dr. Oliver Brausch
Contact:

Null move pruning = lottery?

Post by OliverBr » Sat Jul 18, 2020 3:48 pm

Null move pruning is a very effective way to prune the search tree. But in some positions OliThink behave very unpredictable.

The following position has one clear best move: Kc3!



1) I disabled Null move pruning in 5.5.6. At depth 6 the correct move is found. The correct score is found at depth 12.

Code: Select all

5.5.6 disabled nullmove pruning
 1    11      0        36  f7c7 
 2   -13      0       230  f7e7 b6d6 d3c3 
 3     2      0       771  d3c3 b6d6 c3b4 
 4    39      0      3293  f7e7 b6d6 d3c3 d6d7 e7e5 
 5    62      0      7220  f7e7 b6d6 d3e2 d6d7 e7e5 d7b7 
 6    77      0     17243  d3c3 b5b4 a3b4 b6c6 c3d2 c6d6 d2e1 d6b6 e1e2 
 7    90      1     29429  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 f7e7 a6d6 d3c3 d6c6 c3d3 
 8   125      1     56287  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 f7e7 a6d6 d3e2 d6d4 g5f7 h6g7 
 9   146      5    167588  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 d3c4 a6b6 f7c7 b6b8 g5f7 h6g7 
10   176     16    572765  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 d3c4 a6c6 c4b5 c6d6 b5a5 d6c6 a5a4 
11   174     36   1430663  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 f7b7 b5b4 c5b4 a6a8 g5f7 h6g7 
12   278     89   3848011  d3c3 b5b4 c3c4 b4a3 b2a3 b6c6 c4b4 c6b6 b4c5 b6b3 f7f6 b3a3 c5b4 a3g3 b4a4 
13   308    222  10337074  d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4a5 h6g7 f6f7 g7g8 f7b7 b2b3 b7b5 b3g3 b5b8 g8g7 
14   261    556  27625016  d3c3 b6c6 c3b4 c6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 b2b4 b6c6 a4b3 c6d6 a3a4 
15   259   1638  85168279  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 f7b7 a6a8 c5b5 a8f8 b5a4 f8g8 g5f7 h6h7 f7e5 g8g7 b7b4 
16   275   3999 212077081  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 b2b3 b6c6 a4b5 c6d6 f7h7 f6h7 g5f7 h6g7 
move d3c3
2) 5.5.6 with enabled null move pruning yields results that were expected. At depth 13 Kc3 is found, correct score at depth 15. A much deeper search is possible thanks to pruning.

Code: Select all

5.5.6 With Nullmove Pruning
 1    11      0        36  f7c7 
 2   -13      0       230  f7e7 b6d6 d3c3 
 3    -5      0       609  f7e7 b6d6 d3c3 f6g4 
 4    39      0      2079  f7e7 b6d6 d3c3 d6d1 e7e5 
 5    50      0      3748  f7e7 b6d6 d3c3 d6c6 c3b4 c6c2 g5f7 h6g7 
 6    50      0      6265  f7e7 b6d6 d3c3 d6c6 c3b4 c6c2 g5f7 h6g7 f7e5 g7h6 
 7    89      0     11473  f7e7 b6d6 d3c3 d6c6 c3b4 c6c2 g5f7 h6g7 f7e5 g7g8 e5g6 
 8    88      1     41074  f7e7 b5b4 e7a7 b4a3 g5f7 h6g7 f7e5 g7g8 a7a8 g8h7 b2a3 
 9    70      3    104224  f7e7 b5b4 a3b4 b6b4 g5f7 h6g7 f7e5 g7g8 e5g6 b4b3 d3c2 b3g3 
10    86     14    513848  f7c7 b6d6 d3c3 d6d1 c7b7 d1g1 g5f7 h6g7 f7e5 g7g8 c3b4 g1g3 b4b5 
11    87     16    596867  f7c7 b6d6 d3c3 d6d1 c7b7 d1g1 g5f7 h6g7 f7e5 g7g8 b7b5 g1g3 c3b4 g6g5 h4g5 
12    98     31   1195751  f7c7 b5b4 g5f7 h6g7 f7e5 g7g8 c7c8 g8g7 e5c4 b6e6 e4e5 f6g4 a3b4 g4e5 c4e5 e6e5 
13   166     52   2072045  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 b4b5 a6b6 d3c3 b6d6 f7a7 d6b6 g5f7 h6g7 f7e5 g7h6 e5f7 h6g7 
14   199     57   2274945  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 b4b5 a6b6 d3c3 b6d6 f7a7 d6b6 g5f7 h6g7 f7e5 g7h6 e5f7 h6h7 e4e5 
15   313     93   3742879  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 b4b5 a4a3 b2a3 a6a3 d3c4 a3a4 c4b3 a4e4 f7f6 e4e3 b3c4 e3g3 c4d5 g3b3 
16   303    128   5293126  d3c3 b5b4 a3b4 b6a6 b4b5 a6d6 c3b4 d6d4 b4a3 d4d6 a3a4 d6b6 f7a7 b6b8 g5f7 h6g7 f7e5 g7h6 e5d7 f6d7 
17   332    280  12302831  d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4a5 h6g7 f6f7 g7g8 f7b7 b2b3 b7b5 b3g3 a5a4 g3g4 a4b3 g4h4 b5e5 
18   323    362  16360282  d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4a5 h6g7 f6f7 g7g8 f7b7 b2b3 b7b5 b3a3 b5e5 a3g3 e5e6 g8g7 a5a4 g3g4 
19   316    461  21320116  d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4a5 h6g7 f6f7 g7g8 f7b7 b2b3 b7b5 b3a3 b5e5 a3g3 a5a4 g3g4 e5e8 g8g7 e8e7 g7h8 e7e6 
20   291    634  29819407  d3c3 b6d6 c3b4 d6b6 b4a5 b6c6 a5b5 c6d6 b5a4 d6b6 a4a5 b6d6 f7e7 d6d7 e7e5 d7a7 a5b6 a7a4 b6b5 a4d4 e5e7 
move d3c3
3) With 5.5.6a I changed pawn evaluation a little. This alteration is not supposed to change anything for null move pruning, but it does: Now Kc3 is found only at depth 16. Other changes do not find Kc3 at all (like example 5).

Code: Select all

5.5.6a Little change in pawn evaluation
 1    11      0        36  f7c7 
 2   -13      0       230  f7e7 b6d6 d3c3 
 3    -5      0       609  f7e7 b6d6 d3c3 f6g4 
 4    47      0      2065  f7e7 b6d6 d3c3 d6d1 e7e5 
 5    58      0      3680  f7e7 b6d6 d3c3 d6c6 c3b4 c6c2 g5f7 h6g7 
 6    58      0      6199  f7e7 b6d6 d3c3 d6c6 c3b4 c6c2 g5f7 h6g7 f7e5 g7h6 
 7    81      0     14324  f7e7 b6d6 d3c3 d6c6 c3b4 c6c2 g5f7 h6g7 f7e5 g7g8 e5g6 
 8    95      1     51449  f7e7 b6d6 d3c3 d6d7 e7d7 f6d7 c3b4 d7f6 b4b5 
 9    67      4    169685  f7a7 b6d6 d3e3 d6d7 a7d7 f6d7 g5f7 h6g7 f7d6 d7c5 d6b5 
10   102     11    393704  f7a7 b6d6 d3c3 d6d1 c3b4 d1b1 g5f7 h6g7 f7e5 g7g8 e5d3 f6e4 b4b5 
11   110     13    459908  f7a7 b6d6 d3c3 d6d1 c3b4 d1b1 b4b5 b1b2 b5a4 b2b1 g5f7 h6g7 f7e5 g7h6 a7a6 
12   132     17    617814  f7a7 b6d6 d3c3 d6d1 c3b4 d1b1 b4b5 b1b2 b5a4 b2b1 g5f7 h6g7 f7e5 g7g8 e5g6 f6e4 
13   130     33   1203465  f7a7 b6d6 d3c3 d6d1 c3b4 d1b1 b4b5 b1b2 b5a4 b2b1 g5f7 h6g7 f7e5 g7g8 a7a6 g8g7 a4a5 
14   138     61   2368859  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2b1 a7c7 b1b8 g5f7 h6g7 f7e5 g7g8 c7c4 g8g7 a4a5 
15   130     80   3138944  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2b1 a7c7 b1b8 g5f7 h6g7 f7e5 g7g8 c7c6 g8g7 c6d6 b8b2 
16   284    215   9192639  d3c3 b5b4 a3b4 b6c6 c3d3 a4a3 b2a3 c6b6 d3c3 b6d6 f7e7 d6d7 e7e5 d7a7 e5a5 a7a5 b4a5 h6g7 
17   320    318  14039565  d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4a5 h6g7 f6f7 g7g8 f7b7 b2b3 b7b5 b3g3 a5a4 g3g4 b5e5 g4h4 a4b3 
18   331    464  20964341  d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4a5 h6g7 f6f7 g7g8 f7b7 b2b3 b7b5 b3a3 b5e5 a3g3 a5a4 g3g4 e5e6 g8g7 
19   349    729  33882006  d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4c3 b2b3 c3c2 h6g7 f6f3 b5b4 f3b3 a4b3 c2b2 b4a3 b2a3 g7f6 a3b3 f6e7 g5f3 e7d6 b3c4 
20   341   1557  73859694  d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4c3 b2b3 c3c2 b3g3 f6f7 g3g5 h4g5 h6g5 c2c3 h5h4 c3b4 g5h6 f7b7 h4h3 b7b8 h6g7 b4b5 
move d3c3
4) To investigate further I start the iterative search with the same engine of 3) at depth 13 (where Kc3 was found in 2) and suprisingly, Kc3 is found directly, but: the score is wrong! Should be about 300 and not 170.
Kc3 b4 is not the correct line, it's Kc3 Rd6. So it got the answer wrong, even at depth 20.

Code: Select all

5.5.6a Starting with d = 13
13   124     68   2957058  d3c3 b5b4 a3b4 b6c6 c3d2 c6d6 d2c1 d6c6 c1d1 c6b6 d1e1 b6c6 f7e7 c6c2 g5f7 h6g7 f7e5 g7h6 e5d3 
14   176     83   3551479  d3c3 b5b4 a3b4 b6c6 c3d2 c6d6 d2e1 d6b6 b4b5 b6d6 f7a7 d6d4 g5f7 h6g7 f7e5 g7g8 e5g6 f6e4 a7a8 g8f7 
15   167     90   3872293  d3c3 b5b4 a3b4 b6c6 c3d2 c6d6 d2e1 d6b6 b4b5 b6d6 f7a7 d6b6 e1e2 b6b8 g5f7 h6g7 f7e5 g7g8 e5g6 b8b5 
16   174    114   4884385  d3c3 b5b4 a3b4 b6c6 c3d2 c6d6 d2e1 d6c6 b4b5 c6b6 f7a7 b6b8 e1d2 b8b6 g5f7 h6g7 f7e5 g7g8 a7a4 b6b5 a4a8 g8h7 
17   177    158   6879948  d3c3 b5b4 a3b4 b6c6 c3d2 c6d6 d2e1 d6c6 b4b5 c6d6 f7a7 d6b6 e1d2 b6b8 d2c3 a4a3 g5f7 h6g7 f7e5 g7g8 b2a3 b8b5 
18   180    197   8637382  d3c3 b5b4 a3b4 b6c6 c3d2 c6d6 d2e1 d6c6 b4b5 c6d6 f7a7 d6b6 g5f7 h6g7 f7e5 g7g8 a7a4 b6b5 e5g6 b5b2 e4e5 b2b1 e1f2 f6g4 f2f3 
19   195    297  13439382  d3c3 b5b4 a3b4 b6c6 c3d2 c6d6 d2e1 d6c6 b4b5 c6b6 f7a7 b6b8 g5f7 h6h7 f7e5 h7g8 a7a4 b8e8 e5g6 f6e4 e1d1 g8f7 g6f4 e4g3 
20   200    464  21402445  d3c3 b5b4 a3b4 b6c6 c3d2 c6d6 d2e1 d6c6 b4b5 c6b6 f7a7 b6b8 g5f7 h6h7 f7e5 h7g8 a7a4 b8e8 e5g6 f6e4 e1d1 e4g3 g6f4 e8d8 d1c2 g8f7 
5) Doing the same search, but starting with d = 14, Kc3 is not found at all...the move and the score are just wrong.

Code: Select all

5.5.6a Starting with d = 14
14   133     31   1223814  f7a7 b6b8 g5f7 h6g7 f7e5 g7h6 e5f7 h6g7 e4e5 f6g4 f7g5 g7g8 e5e6 g4e5 d3c2 b8c8 c2b1 e5d3 e6e7 g8h8 
15   140     68   2778230  f7a7 b6b8 g5f7 h6g7 f7e5 g7h6 e5f7 h6g7 e4e5 f6g4 f7g5 g7g8 e5e6 g4e5 d3c2 e5c6 a7c7 c6d4 c2d3 d4f5 g5e4 
16   151    211   9551297  f7a7 b5b4 g5f7 h6g7 f7e5 g7h6 e5f7 h6g7 f7g5 g7g8 a7a4 b4a3 a4a3 b6b2 a3a6 g8g7 a6a7 g7h8 e4e5 f6g4 e5e6 
17   138    488  22332872  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2d2 a4b5 d2g2 a7f7 g2b2 b5a6 b2f2 f7e7 f2g2 g5f7 h6g7 f7e5 g7h6 e5f7 h6g7 
18   146    708  32181264  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 a7f7 c2b2 b4a5 b2f2 a5b5 f2b2 b5a4 b2b6 f7e7 b6b8 g5f7 h6g7 f7e5 g7h6 e5f7 h6g7 f7g5 g7h6 e7c7 b8b1 
19   144   1340  61087770  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2f2 a4a5 f2b2 g5f7 h6g7 f7e5 g7g8 a7a6 g8g7 e5g6 b2b3 g6f4 b3a3 a5b5 a3a6 b5a6 
20   166   3389 155239904  f7a7 b6b8 g5f7 h6g7 f7e5 g7h6 e5f7 h6g7 f7g5 g7h8 e4e5 f6g4 e5e6 g4e5 d3e4 e5c4 g5f7 h8g8 f7e5 b8b6 e5c4 b5c4 e6e7 g8f7 e4d4 b6b2 
So does anyone have an explanation for this? How can such inconsistency be avoided? What's special with the position?

What are your engines doing in this position?
Glaurung 2.1 find this move no sooner than at depth 15, so it's clear it's a difficult one, but why is the outcome so unpredictable?


EDIT: Something special about the position is that the black knight is "pseudo-pinned". Black can't move it without being checkmated. This may play an important role.
Last edited by OliverBr on Sat Jul 18, 2020 4:05 pm, edited 2 times in total.
Chess Engine OliThink: http://brausch.org/home/chess
OliThink GitHub:https://github.com/olithink

brianr
Posts: 451
Joined: Thu Mar 09, 2006 2:01 pm

Re: Null move pruning = lottery?

Post by brianr » Sat Jul 18, 2020 4:02 pm

Yup, null move is a gamble.
On balance, for most engines it is a 100-150 Elo improvement (in fact, typically the biggest single improvement).

Yes, there are some pathological cases for null move.
Many null move "verification" approaches have been tried if the inconsistency is bothersome.

Every engine is different.
I gave up on "fancy" null move with Tinker and just use R=3 (except at depth < 5), FWIW.

OliverBr
Posts: 563
Joined: Tue Dec 18, 2007 8:38 pm
Location: Munich, Germany
Full name: Dr. Oliver Brausch
Contact:

Re: Null move pruning = lottery?

Post by OliverBr » Sat Jul 18, 2020 5:04 pm

brianr wrote:
Sat Jul 18, 2020 4:02 pm
I gave up on "fancy" null move with Tinker and just use R=3 (except at depth < 5), FWIW.
There may be a point where and odd R makes sense in order to not repeat the same mistake.

FYI, another little change within the pawn evaluation with 5.5.6 yields:

Code: Select all

 1    43      0        31  f7c7 
 2    19      0       226  f7e7 b6d6 d3c3 
 3    66      0       572  d3c3 b6d6 c3b4 
 4    78      0      1076  d3c3 b6d6 c3b4 d6b6 
 5    94      0      2440  d3c3 b6d6 c3b4 d6d4 b4b5 f6e4 
 6   118      0      5513  d3c3 b5b4 a3b4 b6c6 c3d3 c6d6 d3e2 d6b6 e2d3 
 7   134      0     10378  d3c3 b5b4 a3b4 b6c6 c3d3 c6d6 d3c4 d6b6 f7a7 b6c6 c4d3 
 8   137      0     16711  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 f7c7 a6d6 d3c2 d6d4 g5f7 h6g7 
 9   137      0     26095  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 f7c7 a6d6 d3c2 d6d4 g5f7 h6g7 f7e5 g7h6 
10   149      1     45087  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 f7c7 a6d6 d3c2 d6d4 g5f7 h6g7 f7e5 g7h6 e5f7 h6g7 
11   202      3    105951  d3c3 b5b4 a3b4 b6c6 c3d3 c6d6 d3c4 d6d7 f7d7 f6d7 c4b5 d7f6 b5a4 f6g4 
12   218      4    165923  d3c3 b5b4 a3b4 b6c6 c3d3 c6d6 d3c4 d6d7 f7d7 f6d7 c4b5 d7f6 b5a4 f6g4 b4b5 
13   313     13    529057  d3c3 b5b4 a3b4 b6c6 c3d3 a4a3 b2a3 c6b6 a3a4 b6a6 d3c4 a6c6 c4b3 c6b6 f7e7 f6g4 
14   319     21    872301  d3c3 b5b4 a3b4 b6c6 c3d3 a4a3 b2a3 c6b6 a3a4 b6a6 d3c4 a6c6 c4b3 c6d6 f7h7 f6h7 g5f7 h6g7 f7d6 
15   332     48   2025197  d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4a5 h6g7 f6f7 g7h8 f7h7 h8g8 h7e7 b2b3 e7e5 b3g3 e5e8 g8g7 a5b5 
16   344     68   2953871  d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4a5 h6g7 f6f7 g7h8 f7b7 b2b3 b7b5 b3g3 a5a4 g3g4 a4b3 g4h4 
17   344    106   4414836  d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4a5 h6g7 f6f7 g7h8 f7b7 b2b3 b7b5 b3g3 a5a4 g3g4 a4b3 g4h4 b5e5 
18   331    159   7075141  d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4a5 h6g7 f6f7 g7h8 f7h7 h8g8 h7e7 b2b3 e7e5 b3g3 e5b5 g3a3 b5b4 g8g7 b4a4 
19   332    256  11942791  d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4a5 h6g7 f6f7 g7g8 f7e7 b2b3 e7e5 b3a3 e5b5 a3g3 b5b8 g8g7 b8b7 g7g8 a5a4 g3g4 b7b6 
20   309    422  20257926  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 a4a5 b6d6 f7e7 d6d7 e7e5 d7d3 e5e6 f6g4 e6b6 d3g3 
Chess Engine OliThink: http://brausch.org/home/chess
OliThink GitHub:https://github.com/olithink

chrisw
Posts: 3841
Joined: Tue Apr 03, 2012 2:28 pm

Re: Null move pruning = lottery?

Post by chrisw » Sat Jul 18, 2020 5:12 pm

OliverBr wrote:
Sat Jul 18, 2020 3:48 pm
Null move pruning is a very effective way to prune the search tree. But in some positions OliThink behave very unpredictable.

The following position has one clear best move: Kc3!



1) I disabled Null move pruning in 5.5.6. At depth 6 the correct move is found. The correct score is found at depth 12.

Code: Select all

5.5.6 disabled nullmove pruning
 1    11      0        36  f7c7 
 2   -13      0       230  f7e7 b6d6 d3c3 
 3     2      0       771  d3c3 b6d6 c3b4 
 4    39      0      3293  f7e7 b6d6 d3c3 d6d7 e7e5 
 5    62      0      7220  f7e7 b6d6 d3e2 d6d7 e7e5 d7b7 
 6    77      0     17243  d3c3 b5b4 a3b4 b6c6 c3d2 c6d6 d2e1 d6b6 e1e2 
 7    90      1     29429  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 f7e7 a6d6 d3c3 d6c6 c3d3 
 8   125      1     56287  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 f7e7 a6d6 d3e2 d6d4 g5f7 h6g7 
 9   146      5    167588  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 d3c4 a6b6 f7c7 b6b8 g5f7 h6g7 
10   176     16    572765  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 d3c4 a6c6 c4b5 c6d6 b5a5 d6c6 a5a4 
11   174     36   1430663  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 f7b7 b5b4 c5b4 a6a8 g5f7 h6g7 
12   278     89   3848011  d3c3 b5b4 c3c4 b4a3 b2a3 b6c6 c4b4 c6b6 b4c5 b6b3 f7f6 b3a3 c5b4 a3g3 b4a4 
13   308    222  10337074  d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4a5 h6g7 f6f7 g7g8 f7b7 b2b3 b7b5 b3g3 b5b8 g8g7 
14   261    556  27625016  d3c3 b6c6 c3b4 c6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 b2b4 b6c6 a4b3 c6d6 a3a4 
15   259   1638  85168279  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 f7b7 a6a8 c5b5 a8f8 b5a4 f8g8 g5f7 h6h7 f7e5 g8g7 b7b4 
16   275   3999 212077081  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 b2b3 b6c6 a4b5 c6d6 f7h7 f6h7 g5f7 h6g7 
move d3c3
2) 5.5.6 with enabled null move pruning yields results that were expected. At depth 13 Kc3 is found, correct score at depth 15. A much deeper search is possible thanks to pruning.

Code: Select all

5.5.6 With Nullmove Pruning
 1    11      0        36  f7c7 
 2   -13      0       230  f7e7 b6d6 d3c3 
 3    -5      0       609  f7e7 b6d6 d3c3 f6g4 
 4    39      0      2079  f7e7 b6d6 d3c3 d6d1 e7e5 
 5    50      0      3748  f7e7 b6d6 d3c3 d6c6 c3b4 c6c2 g5f7 h6g7 
 6    50      0      6265  f7e7 b6d6 d3c3 d6c6 c3b4 c6c2 g5f7 h6g7 f7e5 g7h6 
 7    89      0     11473  f7e7 b6d6 d3c3 d6c6 c3b4 c6c2 g5f7 h6g7 f7e5 g7g8 e5g6 
 8    88      1     41074  f7e7 b5b4 e7a7 b4a3 g5f7 h6g7 f7e5 g7g8 a7a8 g8h7 b2a3 
 9    70      3    104224  f7e7 b5b4 a3b4 b6b4 g5f7 h6g7 f7e5 g7g8 e5g6 b4b3 d3c2 b3g3 
10    86     14    513848  f7c7 b6d6 d3c3 d6d1 c7b7 d1g1 g5f7 h6g7 f7e5 g7g8 c3b4 g1g3 b4b5 
11    87     16    596867  f7c7 b6d6 d3c3 d6d1 c7b7 d1g1 g5f7 h6g7 f7e5 g7g8 b7b5 g1g3 c3b4 g6g5 h4g5 
12    98     31   1195751  f7c7 b5b4 g5f7 h6g7 f7e5 g7g8 c7c8 g8g7 e5c4 b6e6 e4e5 f6g4 a3b4 g4e5 c4e5 e6e5 
13   166     52   2072045  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 b4b5 a6b6 d3c3 b6d6 f7a7 d6b6 g5f7 h6g7 f7e5 g7h6 e5f7 h6g7 
14   199     57   2274945  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 b4b5 a6b6 d3c3 b6d6 f7a7 d6b6 g5f7 h6g7 f7e5 g7h6 e5f7 h6h7 e4e5 
15   313     93   3742879  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 b4b5 a4a3 b2a3 a6a3 d3c4 a3a4 c4b3 a4e4 f7f6 e4e3 b3c4 e3g3 c4d5 g3b3 
16   303    128   5293126  d3c3 b5b4 a3b4 b6a6 b4b5 a6d6 c3b4 d6d4 b4a3 d4d6 a3a4 d6b6 f7a7 b6b8 g5f7 h6g7 f7e5 g7h6 e5d7 f6d7 
17   332    280  12302831  d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4a5 h6g7 f6f7 g7g8 f7b7 b2b3 b7b5 b3g3 a5a4 g3g4 a4b3 g4h4 b5e5 
18   323    362  16360282  d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4a5 h6g7 f6f7 g7g8 f7b7 b2b3 b7b5 b3a3 b5e5 a3g3 e5e6 g8g7 a5a4 g3g4 
19   316    461  21320116  d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4a5 h6g7 f6f7 g7g8 f7b7 b2b3 b7b5 b3a3 b5e5 a3g3 a5a4 g3g4 e5e8 g8g7 e8e7 g7h8 e7e6 
20   291    634  29819407  d3c3 b6d6 c3b4 d6b6 b4a5 b6c6 a5b5 c6d6 b5a4 d6b6 a4a5 b6d6 f7e7 d6d7 e7e5 d7a7 a5b6 a7a4 b6b5 a4d4 e5e7 
move d3c3
3) With 5.5.6a I changed pawn evaluation a little. This alteration is not supposed to change anything for null move pruning, but it does: Now Kc3 is found only at depth 16. Other changes do not find Kc3 at all (like example 5).

Code: Select all

5.5.6a Little change in pawn evaluation
 1    11      0        36  f7c7 
 2   -13      0       230  f7e7 b6d6 d3c3 
 3    -5      0       609  f7e7 b6d6 d3c3 f6g4 
 4    47      0      2065  f7e7 b6d6 d3c3 d6d1 e7e5 
 5    58      0      3680  f7e7 b6d6 d3c3 d6c6 c3b4 c6c2 g5f7 h6g7 
 6    58      0      6199  f7e7 b6d6 d3c3 d6c6 c3b4 c6c2 g5f7 h6g7 f7e5 g7h6 
 7    81      0     14324  f7e7 b6d6 d3c3 d6c6 c3b4 c6c2 g5f7 h6g7 f7e5 g7g8 e5g6 
 8    95      1     51449  f7e7 b6d6 d3c3 d6d7 e7d7 f6d7 c3b4 d7f6 b4b5 
 9    67      4    169685  f7a7 b6d6 d3e3 d6d7 a7d7 f6d7 g5f7 h6g7 f7d6 d7c5 d6b5 
10   102     11    393704  f7a7 b6d6 d3c3 d6d1 c3b4 d1b1 g5f7 h6g7 f7e5 g7g8 e5d3 f6e4 b4b5 
11   110     13    459908  f7a7 b6d6 d3c3 d6d1 c3b4 d1b1 b4b5 b1b2 b5a4 b2b1 g5f7 h6g7 f7e5 g7h6 a7a6 
12   132     17    617814  f7a7 b6d6 d3c3 d6d1 c3b4 d1b1 b4b5 b1b2 b5a4 b2b1 g5f7 h6g7 f7e5 g7g8 e5g6 f6e4 
13   130     33   1203465  f7a7 b6d6 d3c3 d6d1 c3b4 d1b1 b4b5 b1b2 b5a4 b2b1 g5f7 h6g7 f7e5 g7g8 a7a6 g8g7 a4a5 
14   138     61   2368859  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2b1 a7c7 b1b8 g5f7 h6g7 f7e5 g7g8 c7c4 g8g7 a4a5 
15   130     80   3138944  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2b1 a7c7 b1b8 g5f7 h6g7 f7e5 g7g8 c7c6 g8g7 c6d6 b8b2 
16   284    215   9192639  d3c3 b5b4 a3b4 b6c6 c3d3 a4a3 b2a3 c6b6 d3c3 b6d6 f7e7 d6d7 e7e5 d7a7 e5a5 a7a5 b4a5 h6g7 
17   320    318  14039565  d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4a5 h6g7 f6f7 g7g8 f7b7 b2b3 b7b5 b3g3 a5a4 g3g4 b5e5 g4h4 a4b3 
18   331    464  20964341  d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4a5 h6g7 f6f7 g7g8 f7b7 b2b3 b7b5 b3a3 b5e5 a3g3 a5a4 g3g4 e5e6 g8g7 
19   349    729  33882006  d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4c3 b2b3 c3c2 h6g7 f6f3 b5b4 f3b3 a4b3 c2b2 b4a3 b2a3 g7f6 a3b3 f6e7 g5f3 e7d6 b3c4 
20   341   1557  73859694  d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4c3 b2b3 c3c2 b3g3 f6f7 g3g5 h4g5 h6g5 c2c3 h5h4 c3b4 g5h6 f7b7 h4h3 b7b8 h6g7 b4b5 
move d3c3
4) To investigate further I start the iterative search with the same engine of 3) at depth 13 (where Kc3 was found in 2) and suprisingly, Kc3 is found directly, but: the score is wrong! Should be about 300 and not 170.
Kc3 b4 is not the correct line, it's Kc3 Rd6. So it got the answer wrong, even at depth 20.

Code: Select all

5.5.6a Starting with d = 13
13   124     68   2957058  d3c3 b5b4 a3b4 b6c6 c3d2 c6d6 d2c1 d6c6 c1d1 c6b6 d1e1 b6c6 f7e7 c6c2 g5f7 h6g7 f7e5 g7h6 e5d3 
14   176     83   3551479  d3c3 b5b4 a3b4 b6c6 c3d2 c6d6 d2e1 d6b6 b4b5 b6d6 f7a7 d6d4 g5f7 h6g7 f7e5 g7g8 e5g6 f6e4 a7a8 g8f7 
15   167     90   3872293  d3c3 b5b4 a3b4 b6c6 c3d2 c6d6 d2e1 d6b6 b4b5 b6d6 f7a7 d6b6 e1e2 b6b8 g5f7 h6g7 f7e5 g7g8 e5g6 b8b5 
16   174    114   4884385  d3c3 b5b4 a3b4 b6c6 c3d2 c6d6 d2e1 d6c6 b4b5 c6b6 f7a7 b6b8 e1d2 b8b6 g5f7 h6g7 f7e5 g7g8 a7a4 b6b5 a4a8 g8h7 
17   177    158   6879948  d3c3 b5b4 a3b4 b6c6 c3d2 c6d6 d2e1 d6c6 b4b5 c6d6 f7a7 d6b6 e1d2 b6b8 d2c3 a4a3 g5f7 h6g7 f7e5 g7g8 b2a3 b8b5 
18   180    197   8637382  d3c3 b5b4 a3b4 b6c6 c3d2 c6d6 d2e1 d6c6 b4b5 c6d6 f7a7 d6b6 g5f7 h6g7 f7e5 g7g8 a7a4 b6b5 e5g6 b5b2 e4e5 b2b1 e1f2 f6g4 f2f3 
19   195    297  13439382  d3c3 b5b4 a3b4 b6c6 c3d2 c6d6 d2e1 d6c6 b4b5 c6b6 f7a7 b6b8 g5f7 h6h7 f7e5 h7g8 a7a4 b8e8 e5g6 f6e4 e1d1 g8f7 g6f4 e4g3 
20   200    464  21402445  d3c3 b5b4 a3b4 b6c6 c3d2 c6d6 d2e1 d6c6 b4b5 c6b6 f7a7 b6b8 g5f7 h6h7 f7e5 h7g8 a7a4 b8e8 e5g6 f6e4 e1d1 e4g3 g6f4 e8d8 d1c2 g8f7 
5) Doing the same search, but starting with d = 14, Kc3 is not found at all...the move and the score are just wrong.

Code: Select all

5.5.6a Starting with d = 14
14   133     31   1223814  f7a7 b6b8 g5f7 h6g7 f7e5 g7h6 e5f7 h6g7 e4e5 f6g4 f7g5 g7g8 e5e6 g4e5 d3c2 b8c8 c2b1 e5d3 e6e7 g8h8 
15   140     68   2778230  f7a7 b6b8 g5f7 h6g7 f7e5 g7h6 e5f7 h6g7 e4e5 f6g4 f7g5 g7g8 e5e6 g4e5 d3c2 e5c6 a7c7 c6d4 c2d3 d4f5 g5e4 
16   151    211   9551297  f7a7 b5b4 g5f7 h6g7 f7e5 g7h6 e5f7 h6g7 f7g5 g7g8 a7a4 b4a3 a4a3 b6b2 a3a6 g8g7 a6a7 g7h8 e4e5 f6g4 e5e6 
17   138    488  22332872  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2d2 a4b5 d2g2 a7f7 g2b2 b5a6 b2f2 f7e7 f2g2 g5f7 h6g7 f7e5 g7h6 e5f7 h6g7 
18   146    708  32181264  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 a7f7 c2b2 b4a5 b2f2 a5b5 f2b2 b5a4 b2b6 f7e7 b6b8 g5f7 h6g7 f7e5 g7h6 e5f7 h6g7 f7g5 g7h6 e7c7 b8b1 
19   144   1340  61087770  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2f2 a4a5 f2b2 g5f7 h6g7 f7e5 g7g8 a7a6 g8g7 e5g6 b2b3 g6f4 b3a3 a5b5 a3a6 b5a6 
20   166   3389 155239904  f7a7 b6b8 g5f7 h6g7 f7e5 g7h6 e5f7 h6g7 f7g5 g7h8 e4e5 f6g4 e5e6 g4e5 d3e4 e5c4 g5f7 h8g8 f7e5 b8b6 e5c4 b5c4 e6e7 g8f7 e4d4 b6b2 
So does anyone have an explanation for this? How can such inconsistency be avoided? What's special with the position?

What are your engines doing in this position?
Glaurung 2.1 find this move no sooner than at depth 15, so it's clear it's a difficult one, but why is the outcome so unpredictable?


EDIT: Something special about the position is that the black knight is "pseudo-pinned". Black can't move it without being checkmated. This may play an important role.

Mine has nullmove, and took 8000 nodes to get this one
score cp 308 nodes 8075 pv d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4a5 b2b3 f6a6 b3g3 a5b5 g3a3

OliverBr
Posts: 563
Joined: Tue Dec 18, 2007 8:38 pm
Location: Munich, Germany
Full name: Dr. Oliver Brausch
Contact:

Re: Null move pruning = lottery?

Post by OliverBr » Sat Jul 18, 2020 5:41 pm

chrisw wrote:
Sat Jul 18, 2020 5:12 pm
Mine has nullmove, and took 8000 nodes to get this one
score cp 308 nodes 8075 pv d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4a5 b2b3 f6a6 b3g3 a5b5 g3a3
This is not the point, one version of mine with a slightly different pawn evualuation gets it with 500 nodes (see post before, or the log down here).

It's the reliability, does it get it always this quickly and constantly? Even after some changes in evaluation or starting depth?
And what about other Zugzwang critical positions. Does your engine always get the right move very quick?

If yes, you are doing something different and it would be interesting to know what.

Version 5.5.6b:

Code: Select all

 1    43      0        31  f7c7 
 2    19      0       226  f7e7 b6d6 d3c3 
 3    66      0       572  d3c3 b6d6 c3b4 
 4    78      0      1076  d3c3 b6d6 c3b4 d6b6 
 5    94      0      2440  d3c3 b6d6 c3b4 d6d4 b4b5 f6e4 
 6   118      0      5513  d3c3 b5b4 a3b4 b6c6 c3d3 c6d6 d3e2 d6b6 e2d3 
 7   134      0     10378  d3c3 b5b4 a3b4 b6c6 c3d3 c6d6 d3c4 d6b6 f7a7 b6c6 c4d3 
 8   137      0     16711  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 f7c7 a6d6 d3c2 d6d4 g5f7 h6g7 
 9   137      0     26095  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 f7c7 a6d6 d3c2 d6d4 g5f7 h6g7 f7e5 g7h6 
10   149      1     45087  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 f7c7 a6d6 d3c2 d6d4 g5f7 h6g7 f7e5 g7h6 e5f7 h6g7 
Chess Engine OliThink: http://brausch.org/home/chess
OliThink GitHub:https://github.com/olithink

chrisw
Posts: 3841
Joined: Tue Apr 03, 2012 2:28 pm

Re: Null move pruning = lottery?

Post by chrisw » Sat Jul 18, 2020 6:13 pm

OliverBr wrote:
Sat Jul 18, 2020 5:41 pm
chrisw wrote:
Sat Jul 18, 2020 5:12 pm
Mine has nullmove, and took 8000 nodes to get this one
score cp 308 nodes 8075 pv d3c3 b6d6 c3b4 d6d2 f7f6 d2b2 b4a5 b2b3 f6a6 b3g3 a5b5 g3a3
This is not the point, one version of mine with a slightly different pawn evualuation gets it with 500 nodes (see post before, or the log down here).
sorry about that, I’ll remember to stick to your agenda only next time.

It's the reliability, does it get it always this quickly and constantly? Even after some changes in evaluation or starting depth?
And what about other Zugzwang critical positions. Does your engine always get the right move very quick?
no idea, I only took a look at this because of the king issues.

Obviously most null move implementions are going to tend to post the critical factors of this position over the horizon. Zugswang works that way. I don’t think it’s a question of pawn values, other to encourage black to give his knight up as expensively as possible, but is lost whatever, white has a spare manoeuvring piece, black doesn’t. If you remove whites mobility (via null move) he’s probably not going to so easily solve this kind of position.

If yes, you are doing something different and it would be interesting to know what.

not looked at it that recently, but doesn’t Stockfish do some sort of reduced depth null move verification search? That might pick this up *if* the rest of the engine is geared to see the ensuing problems

Version 5.5.6b:

Code: Select all

 1    43      0        31  f7c7 
 2    19      0       226  f7e7 b6d6 d3c3 
 3    66      0       572  d3c3 b6d6 c3b4 
 4    78      0      1076  d3c3 b6d6 c3b4 d6b6 
 5    94      0      2440  d3c3 b6d6 c3b4 d6d4 b4b5 f6e4 
 6   118      0      5513  d3c3 b5b4 a3b4 b6c6 c3d3 c6d6 d3e2 d6b6 e2d3 
 7   134      0     10378  d3c3 b5b4 a3b4 b6c6 c3d3 c6d6 d3c4 d6b6 f7a7 b6c6 c4d3 
 8   137      0     16711  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 f7c7 a6d6 d3c2 d6d4 g5f7 h6g7 
 9   137      0     26095  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 f7c7 a6d6 d3c2 d6d4 g5f7 h6g7 f7e5 g7h6 
10   149      1     45087  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 f7c7 a6d6 d3c2 d6d4 g5f7 h6g7 f7e5 g7h6 e5f7 h6g7 

OliverBr
Posts: 563
Joined: Tue Dec 18, 2007 8:38 pm
Location: Munich, Germany
Full name: Dr. Oliver Brausch
Contact:

Re: Null move pruning = lottery?

Post by OliverBr » Sat Jul 18, 2020 6:50 pm

chrisw wrote:
Sat Jul 18, 2020 6:13 pm
I don’t think it’s a question of pawn values, other to encourage black to give his knight up as expensively as possible, but is lost whatever, white has a spare manoeuvring piece, black doesn’t.
Very true. There are 6 non-pawn pieces on board, but only one can be manoeuvred freely. My engine tests a Zugzwang situation by counting non-pinned (quite easily calculated) non-pawn pieces and gets 3 here for each site, while practically it's rather 0 resp. 1.

Obviously, sometimes it's not enough to check for pinned-pieces, threading and defending pieces can be limited, too. But those are expensive to calculate.
Last edited by OliverBr on Sat Jul 18, 2020 7:20 pm, edited 1 time in total.
Chess Engine OliThink: http://brausch.org/home/chess
OliThink GitHub:https://github.com/olithink

OliverBr
Posts: 563
Joined: Tue Dec 18, 2007 8:38 pm
Location: Munich, Germany
Full name: Dr. Oliver Brausch
Contact:

Re: Null move pruning = lottery?

Post by OliverBr » Sat Jul 18, 2020 7:19 pm

It's really too strange.
If I change the mobility bonus for pawns in OiThink 5.5.6 Line 1049 to 13:

Code: Select all

if (m) ppos += 13; else ppos -= 13;
The result is horrible. It changes to Re7 at depth 4 and never finds back to Kc3. It does change the best move to Ka7 at depth 10 though:

Code: Select all

 1    21      0        31  f7c7 
 2    -3      0       225  f7e7 b6d6 d3c3 
 3    22      0       610  d3c3 b6d6 c3b4 
 4    37      0      2430  f7e7 b5b4 g5f7 h6g7 f7e5 g7h6 
 5    50      0      4393  f7e7 b6d6 d3c3 d6c6 c3b4 c6c2 g5f7 h6g7 
 6    50      0      6384  f7e7 b6d6 d3c3 d6c6 c3b4 c6c2 g5f7 h6g7 f7e5 g7h6 
 7    99      0     14111  f7e7 b6d6 d3c3 d6c6 c3b4 c6c2 g5f7 h6g7 f7e5 g7g8 e5g6 
 8    93      1     36276  f7e7 b5b4 g5f7 h6g7 f7e5 g7g8 e5c4 b6b8 a3b4 b8b4 
 9   113      2     79697  f7e7 b5b4 g5f7 h6g7 f7e5 g7g8 d3e3 b4a3 b2a3 b6b3 e3f4 g6g5 h4g5 
10   106      8    266710  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2b1 g5f7 h6g7 f7e5 g7h6 e5f7 h6g7 
11   119      9    327932  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2b1 g5f7 h6g7 f7e5 g7g8 e5g6 f6e4 
12   122     13    478071  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2b1 g5f7 h6g7 f7e5 g7g8 a7a6 f6e4 a6g6 g8f8 
13   147     34   1273952  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2b1 g5f7 h6g7 f7e5 g7g8 a7a6 b1f1 a4a5 g8h7 
14   108     49   1874210  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2g2 g5f7 h6g7 f7e5 g7g8 e5g6 f6e4 a7a8 g8f7 g6e5 f7f6 e5d7 f6f5 
15   108    119   4874385  f7a7 b6d6 d3c3 d6d1 c3b4 d1b1 b4b5 b1b2 b5a4 b2g2 g5f7 h6g7 f7e5 g7g8 e5g6 f6e4 a7a8 g8f7 g6e5 f7f6 e5d7 f6f5 
16   135    184   7304995  f7a7 b6d6 d3c3 d6d1 c3b4 d1b1 b4b5 b1b2 b5a4 b2b1 a7f7 b1b6 a4a5 b6c6 a5b5 c6d6 f7h7 f6h7 g5f7 h6g7 
17   140    284  11536439  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2g2 g5f7 h6g7 f7e5 g7g8 a7a6 g8g7 e5g6 g7g6 e4e5 g6f5 a6f6 f5e5 f6f3 
18   146    581  24319441  f7a7 b6d6 d3c3 d6d1 c3b4 d1b1 b4b5 b1b2 b5a4 b2b1 a4a5 b1c1 a5b4 c1b1 b4c4 b1c1 c4d3 c1d1 d3c2 d1d7 a7d7 f6d7 a3a4 
19   148    886  37432828  f7a7 b6d6 d3c3 d6d1 c3b4 d1b1 b4b5 b1b2 b5a4 b2f2 a4b4 f2b2 b4c5 b2e2 c5c4 e2c2 c4b5 c2b2 b5c6 b2b3 g5f7 h6g7 f7e5 g7g8 e5g6 b3c3 c6b5 
20   161   2213  97227066  f7a7 b6d6 d3c3 d6d1 c3b4 d1b1 b4b5 b1b2 b5a4 b2b1 a4a5 b1c1 a3a4 c1c2 a5b4 c2g2 g5f7 h6g7 f7e5 g7g8 e5g6 f6e4 a7a8 g8h7 g6f8 h7h6 
But, if I increase this bonus from 13 to 14:

Code: Select all

if (m) ppos += 14; else ppos -= 14;
I get a very good result with finding Kc3 after 600 nodes:

Code: Select all

 1    23      0        31  f7c7 
 2    -1      0       225  f7e7 b6d6 d3c3 
 3    26      0       608  d3c3 b6d6 c3b4 
 4    38      0      2087  d3c3 b6a6 c3b4 a6b6 
 5    58      0      3018  d3c3 b6a6 c3b4 a6b6 f7c7 
 6    98      0      5629  d3c3 b5b4 a3b4 b6c6 c3d3 c6d6 d3c2 d6c6 c2d2 c6d6 d2c3 
 7   102      0      9794  d3c3 b5b4 a3b4 b6c6 c3d3 c6d6 d3e3 d6b6 e3f3 b6d6 
 8   102      0     16131  d3c3 b5b4 a3b4 b6c6 c3d3 c6b6 d3e3 f6g4 e3e2 g4f6 e2d3 
 9   142      1     35502  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 f7c7 a6d6 d3e3 d6d7 c7d7 f6d7 
10   158      1     53378  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 f7c7 a6d6 d3e3 d6d7 c7d7 f6d7 b4b5 
11   198      5    196239  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6d4 a4a5 f6e4 
12   230      8    307470  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 a4a5 b6c6 
13   256     14    509773  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 a4a5 b6c6 b2b3 
14   256     20    745688  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 a4a5 b6c6 b2b3 c6d6 
15   275     30   1154737  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6c6 a4b5 c6d6 f7e7 d6d4 g5f7 h6g7 
16   274     49   2028087  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 a4a5 b6d6 f7e7 d6d4 g5f7 h6g7 f7e5 g7h6 
17   289     82   3551611  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 a4a5 b6d6 f7e7 d6d7 e7d7 f6d7 b2b3 
18   318    161   7339738  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 a4a5 b6c6 f7b7 c6c2 g5f7 h6g7 f7e5 g7g8 e5g6 f6e4 
19   318    309  14893387  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 a4a5 b6d6 f7e7 d6d4 g5f7 h6g7 f7e5 g7g8 e5g6 f6e4 e7e8 g8h7 
20   291    578  28602804  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5c5 d6a6 c5b4 a6c6 b4a4 c6b6 a4a5 b6c6 b2b3 c6d6 f7h7 f6h7 g5f7 h6g7 
Of course using 14 only helps in this very position. In other positions it may worsen things.

So there a serious bug or is this the price for null move pruning?
Chess Engine OliThink: http://brausch.org/home/chess
OliThink GitHub:https://github.com/olithink

mhouppin
Posts: 67
Joined: Wed Feb 12, 2020 4:00 pm
Full name: Morgan Houppin

Re: Null move pruning = lottery?

Post by mhouppin » Sat Jul 18, 2020 9:11 pm

OliverBr wrote:
Sat Jul 18, 2020 7:19 pm
It's really too strange.
If I change the mobility bonus for pawns in OiThink 5.5.6 Line 1049 to 13:

Code: Select all

if (m) ppos += 13; else ppos -= 13;
The result is horrible. It changes to Re7 at depth 4 and never finds back to Kc3. It does change the best move to Ka7 at depth 10 though:

Code: Select all

 1    21      0        31  f7c7 
 2    -3      0       225  f7e7 b6d6 d3c3 
 3    22      0       610  d3c3 b6d6 c3b4 
 4    37      0      2430  f7e7 b5b4 g5f7 h6g7 f7e5 g7h6 
 5    50      0      4393  f7e7 b6d6 d3c3 d6c6 c3b4 c6c2 g5f7 h6g7 
 6    50      0      6384  f7e7 b6d6 d3c3 d6c6 c3b4 c6c2 g5f7 h6g7 f7e5 g7h6 
 7    99      0     14111  f7e7 b6d6 d3c3 d6c6 c3b4 c6c2 g5f7 h6g7 f7e5 g7g8 e5g6 
 8    93      1     36276  f7e7 b5b4 g5f7 h6g7 f7e5 g7g8 e5c4 b6b8 a3b4 b8b4 
 9   113      2     79697  f7e7 b5b4 g5f7 h6g7 f7e5 g7g8 d3e3 b4a3 b2a3 b6b3 e3f4 g6g5 h4g5 
10   106      8    266710  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2b1 g5f7 h6g7 f7e5 g7h6 e5f7 h6g7 
11   119      9    327932  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2b1 g5f7 h6g7 f7e5 g7g8 e5g6 f6e4 
12   122     13    478071  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2b1 g5f7 h6g7 f7e5 g7g8 a7a6 f6e4 a6g6 g8f8 
13   147     34   1273952  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2b1 g5f7 h6g7 f7e5 g7g8 a7a6 b1f1 a4a5 g8h7 
14   108     49   1874210  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2g2 g5f7 h6g7 f7e5 g7g8 e5g6 f6e4 a7a8 g8f7 g6e5 f7f6 e5d7 f6f5 
15   108    119   4874385  f7a7 b6d6 d3c3 d6d1 c3b4 d1b1 b4b5 b1b2 b5a4 b2g2 g5f7 h6g7 f7e5 g7g8 e5g6 f6e4 a7a8 g8f7 g6e5 f7f6 e5d7 f6f5 
16   135    184   7304995  f7a7 b6d6 d3c3 d6d1 c3b4 d1b1 b4b5 b1b2 b5a4 b2b1 a7f7 b1b6 a4a5 b6c6 a5b5 c6d6 f7h7 f6h7 g5f7 h6g7 
17   140    284  11536439  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2g2 g5f7 h6g7 f7e5 g7g8 a7a6 g8g7 e5g6 g7g6 e4e5 g6f5 a6f6 f5e5 f6f3 
18   146    581  24319441  f7a7 b6d6 d3c3 d6d1 c3b4 d1b1 b4b5 b1b2 b5a4 b2b1 a4a5 b1c1 a5b4 c1b1 b4c4 b1c1 c4d3 c1d1 d3c2 d1d7 a7d7 f6d7 a3a4 
19   148    886  37432828  f7a7 b6d6 d3c3 d6d1 c3b4 d1b1 b4b5 b1b2 b5a4 b2f2 a4b4 f2b2 b4c5 b2e2 c5c4 e2c2 c4b5 c2b2 b5c6 b2b3 g5f7 h6g7 f7e5 g7g8 e5g6 b3c3 c6b5 
20   161   2213  97227066  f7a7 b6d6 d3c3 d6d1 c3b4 d1b1 b4b5 b1b2 b5a4 b2b1 a4a5 b1c1 a3a4 c1c2 a5b4 c2g2 g5f7 h6g7 f7e5 g7g8 e5g6 f6e4 a7a8 g8h7 g6f8 h7h6 
But, if I increase this bonus from 13 to 14:

Code: Select all

if (m) ppos += 14; else ppos -= 14;
I get a very good result with finding Kc3 after 600 nodes:

Code: Select all

 1    23      0        31  f7c7 
 2    -1      0       225  f7e7 b6d6 d3c3 
 3    26      0       608  d3c3 b6d6 c3b4 
 4    38      0      2087  d3c3 b6a6 c3b4 a6b6 
 5    58      0      3018  d3c3 b6a6 c3b4 a6b6 f7c7 
 6    98      0      5629  d3c3 b5b4 a3b4 b6c6 c3d3 c6d6 d3c2 d6c6 c2d2 c6d6 d2c3 
 7   102      0      9794  d3c3 b5b4 a3b4 b6c6 c3d3 c6d6 d3e3 d6b6 e3f3 b6d6 
 8   102      0     16131  d3c3 b5b4 a3b4 b6c6 c3d3 c6b6 d3e3 f6g4 e3e2 g4f6 e2d3 
 9   142      1     35502  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 f7c7 a6d6 d3e3 d6d7 c7d7 f6d7 
10   158      1     53378  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 f7c7 a6d6 d3e3 d6d7 c7d7 f6d7 b4b5 
11   198      5    196239  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6d4 a4a5 f6e4 
12   230      8    307470  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 a4a5 b6c6 
13   256     14    509773  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 a4a5 b6c6 b2b3 
14   256     20    745688  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 a4a5 b6c6 b2b3 c6d6 
15   275     30   1154737  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6c6 a4b5 c6d6 f7e7 d6d4 g5f7 h6g7 
16   274     49   2028087  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 a4a5 b6d6 f7e7 d6d4 g5f7 h6g7 f7e5 g7h6 
17   289     82   3551611  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 a4a5 b6d6 f7e7 d6d7 e7d7 f6d7 b2b3 
18   318    161   7339738  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 a4a5 b6c6 f7b7 c6c2 g5f7 h6g7 f7e5 g7g8 e5g6 f6e4 
19   318    309  14893387  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 a4a5 b6d6 f7e7 d6d4 g5f7 h6g7 f7e5 g7g8 e5g6 f6e4 e7e8 g8h7 
20   291    578  28602804  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5c5 d6a6 c5b4 a6c6 b4a4 c6b6 a4a5 b6c6 b2b3 c6d6 f7h7 f6h7 g5f7 h6g7 
Of course using 14 only helps in this very position. In other positions it may worsen things.

So there a serious bug or is this the price for null move pruning?
FWIW, I tested the position on the latest 10 major releases of my engine, running them with default settings during one second and checking when they found the correct move and holded it for the rest of the search. Here's what I got:

Code: Select all

Stash 10: depth 7, 113 milliseconds
Stash 11: depth 7, 40 milliseconds
Stash 12: depth 5, 5 milliseconds
Stash 13: depth 7, 14 milliseconds
Stash 14: depth 12, 266 milliseconds
Stash 15: > 1 second
Stash 16: > 1 second
Stash 17: depth 16, 428 milliseconds
Stash 18: depth 16, 386 milliseconds
Stash 19: depth 16, 375 milliseconds
Should I conclude from this position that Stash 16 is worse than Stash 12, which found the move in only 5 milliseconds ? On this position, maybe, but Stash 16 is actually 320 Elo higher rated than Stash 12...

Two conclusions from here: Null Move Pruning is not the factor in fault here (it was actually added in version 12!), it's risky, but an engine without it will struggle to break the 2000 Elo bar; and one should never test new search/eval features solely on position solving, but rather make the engine play a lot of matches with/without the feature, and draw conclusions from this. Test-positions are good for sanity checking, but not for measuring engine progress.

chrisw
Posts: 3841
Joined: Tue Apr 03, 2012 2:28 pm

Re: Null move pruning = lottery?

Post by chrisw » Sat Jul 18, 2020 9:28 pm

OliverBr wrote:
Sat Jul 18, 2020 7:19 pm
It's really too strange.
If I change the mobility bonus for pawns in OiThink 5.5.6 Line 1049 to 13:

Code: Select all

if (m) ppos += 13; else ppos -= 13;
The result is horrible. It changes to Re7 at depth 4 and never finds back to Kc3. It does change the best move to Ka7 at depth 10 though:

Code: Select all

 1    21      0        31  f7c7 
 2    -3      0       225  f7e7 b6d6 d3c3 
 3    22      0       610  d3c3 b6d6 c3b4 
 4    37      0      2430  f7e7 b5b4 g5f7 h6g7 f7e5 g7h6 
 5    50      0      4393  f7e7 b6d6 d3c3 d6c6 c3b4 c6c2 g5f7 h6g7 
 6    50      0      6384  f7e7 b6d6 d3c3 d6c6 c3b4 c6c2 g5f7 h6g7 f7e5 g7h6 
 7    99      0     14111  f7e7 b6d6 d3c3 d6c6 c3b4 c6c2 g5f7 h6g7 f7e5 g7g8 e5g6 
 8    93      1     36276  f7e7 b5b4 g5f7 h6g7 f7e5 g7g8 e5c4 b6b8 a3b4 b8b4 
 9   113      2     79697  f7e7 b5b4 g5f7 h6g7 f7e5 g7g8 d3e3 b4a3 b2a3 b6b3 e3f4 g6g5 h4g5 
10   106      8    266710  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2b1 g5f7 h6g7 f7e5 g7h6 e5f7 h6g7 
11   119      9    327932  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2b1 g5f7 h6g7 f7e5 g7g8 e5g6 f6e4 
12   122     13    478071  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2b1 g5f7 h6g7 f7e5 g7g8 a7a6 f6e4 a6g6 g8f8 
13   147     34   1273952  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2b1 g5f7 h6g7 f7e5 g7g8 a7a6 b1f1 a4a5 g8h7 
14   108     49   1874210  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2g2 g5f7 h6g7 f7e5 g7g8 e5g6 f6e4 a7a8 g8f7 g6e5 f7f6 e5d7 f6f5 
15   108    119   4874385  f7a7 b6d6 d3c3 d6d1 c3b4 d1b1 b4b5 b1b2 b5a4 b2g2 g5f7 h6g7 f7e5 g7g8 e5g6 f6e4 a7a8 g8f7 g6e5 f7f6 e5d7 f6f5 
16   135    184   7304995  f7a7 b6d6 d3c3 d6d1 c3b4 d1b1 b4b5 b1b2 b5a4 b2b1 a7f7 b1b6 a4a5 b6c6 a5b5 c6d6 f7h7 f6h7 g5f7 h6g7 
17   140    284  11536439  f7a7 b6d6 d3c3 d6c6 c3b4 c6c2 b4b5 c2b2 b5a4 b2g2 g5f7 h6g7 f7e5 g7g8 a7a6 g8g7 e5g6 g7g6 e4e5 g6f5 a6f6 f5e5 f6f3 
18   146    581  24319441  f7a7 b6d6 d3c3 d6d1 c3b4 d1b1 b4b5 b1b2 b5a4 b2b1 a4a5 b1c1 a5b4 c1b1 b4c4 b1c1 c4d3 c1d1 d3c2 d1d7 a7d7 f6d7 a3a4 
19   148    886  37432828  f7a7 b6d6 d3c3 d6d1 c3b4 d1b1 b4b5 b1b2 b5a4 b2f2 a4b4 f2b2 b4c5 b2e2 c5c4 e2c2 c4b5 c2b2 b5c6 b2b3 g5f7 h6g7 f7e5 g7g8 e5g6 b3c3 c6b5 
20   161   2213  97227066  f7a7 b6d6 d3c3 d6d1 c3b4 d1b1 b4b5 b1b2 b5a4 b2b1 a4a5 b1c1 a3a4 c1c2 a5b4 c2g2 g5f7 h6g7 f7e5 g7g8 e5g6 f6e4 a7a8 g8h7 g6f8 h7h6 
But, if I increase this bonus from 13 to 14:

Code: Select all

if (m) ppos += 14; else ppos -= 14;
I get a very good result with finding Kc3 after 600 nodes:

Code: Select all

 1    23      0        31  f7c7 
 2    -1      0       225  f7e7 b6d6 d3c3 
 3    26      0       608  d3c3 b6d6 c3b4 
 4    38      0      2087  d3c3 b6a6 c3b4 a6b6 
 5    58      0      3018  d3c3 b6a6 c3b4 a6b6 f7c7 
 6    98      0      5629  d3c3 b5b4 a3b4 b6c6 c3d3 c6d6 d3c2 d6c6 c2d2 c6d6 d2c3 
 7   102      0      9794  d3c3 b5b4 a3b4 b6c6 c3d3 c6d6 d3e3 d6b6 e3f3 b6d6 
 8   102      0     16131  d3c3 b5b4 a3b4 b6c6 c3d3 c6b6 d3e3 f6g4 e3e2 g4f6 e2d3 
 9   142      1     35502  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 f7c7 a6d6 d3e3 d6d7 c7d7 f6d7 
10   158      1     53378  d3c3 b5b4 a3b4 b6c6 c3d3 c6a6 f7c7 a6d6 d3e3 d6d7 c7d7 f6d7 b4b5 
11   198      5    196239  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6d4 a4a5 f6e4 
12   230      8    307470  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 a4a5 b6c6 
13   256     14    509773  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 a4a5 b6c6 b2b3 
14   256     20    745688  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 a4a5 b6c6 b2b3 c6d6 
15   275     30   1154737  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6c6 a4b5 c6d6 f7e7 d6d4 g5f7 h6g7 
16   274     49   2028087  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 a4a5 b6d6 f7e7 d6d4 g5f7 h6g7 f7e5 g7h6 
17   289     82   3551611  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 a4a5 b6d6 f7e7 d6d7 e7d7 f6d7 b2b3 
18   318    161   7339738  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 a4a5 b6c6 f7b7 c6c2 g5f7 h6g7 f7e5 g7g8 e5g6 f6e4 
19   318    309  14893387  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5a4 d6b6 a4a5 b6d6 f7e7 d6d4 g5f7 h6g7 f7e5 g7g8 e5g6 f6e4 e7e8 g8h7 
20   291    578  28602804  d3c3 b6d6 c3b4 d6b6 b4c5 b6a6 c5b5 a6d6 b5c5 d6a6 c5b4 a6c6 b4a4 c6b6 a4a5 b6c6 b2b3 c6d6 f7h7 f6h7 g5f7 h6g7 
Of course using 14 only helps in this very position. In other positions it may worsen things.

So there a serious bug or is this the price for null move pruning?
Tuning your pawn evaluation parameters on the basis of one position in one game is very last century. Null move is a very blunt instrument. Heavily pruned search is subject to butterflies flapping their wings in Outer Mongolia. Most programmers have given up really, probably wisely, and rely on statistical results and/or use a statistical process, NN or Texel to find some suitably balanced evaluator. Because it works, apparently. If you can extract some generalised useful knowledge out of the chosen position above and somehow find a way to encode it at less expense than any possible gain, then good, but it won’t be in adjusting pawn evaluation parameters. Personally speaking, I find it more attractive to to find the holes in other engines (due to general assumptions about what is right way) and work out how to exploit those, rather than plug holes in mine.

Post Reply