fixing the null move search "bug"

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
syzygy
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: fixing the null move search "bug"

Post by syzygy » Wed Feb 05, 2014 9:44 am

Uri Blass wrote:The maximal depth that stockfish can get is 100 and null move verification does not help because of huge reduction that stockfish is using today
so if we use time control that is long enough for stockfish to get depth 100 in every move then it is clear that stockfish without null move pruning at depth that is bigger than 50 is going to be better than default stockfish.
Sure. But I know a better one: if we use time control that is long enough for stockfish to get depth 100 in every move then it is clear that stockfish without any reductions and pruning at all (and still reaching depth 100) is going to be better than default stockfish.

Maybe we should reduce maximal depth to 10, because then it is safe to get rid of all reductions and pruning.

Uri Blass
Posts: 8586
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: fixing the null move search "bug"

Post by Uri Blass » Wed Feb 05, 2014 12:49 pm

syzygy wrote:
Uri Blass wrote:The maximal depth that stockfish can get is 100 and null move verification does not help because of huge reduction that stockfish is using today
so if we use time control that is long enough for stockfish to get depth 100 in every move then it is clear that stockfish without null move pruning at depth that is bigger than 50 is going to be better than default stockfish.
Sure. But I know a better one: if we use time control that is long enough for stockfish to get depth 100 in every move then it is clear that stockfish without any reductions and pruning at all (and still reaching depth 100) is going to be better than default stockfish.

Maybe we should reduce maximal depth to 10, because then it is safe to get rid of all reductions and pruning.
I have no problem with pther type of pruning because they are not basically unsound pruning.

The main problem with null move pruning is that the program may miss the best move even at infinite depth.

stockfish use today verification search but I do not think that it is the right solution to the problem because after stockfish increased the super crazy reductions that it used even verification search cannot help in a reasonable depth.

The super crazy reductions of stockfish is expressed by the following code:

Depth R = 3 * ONE_PLY
+ depth / 4
+ int(eval - beta) / PawnValueMg * ONE_PLY;

This code practically means that stockfish can reduce many plies for example in case that eval>beta+10 pawns and practically never solve positions when there is a zugzwang in some moves inspite of verification search.

With this super crazy reduction stockfish cannot solve the following position even with depth 1000(and it can get depth 1000 if I change the code) and when this position cannot happen in games I will be surprised if there are no position from games that stockfish can practically get depth 100 without solving them because of null move pruning and the conclusion is that it may be better to limit null move pruning after some depth to prevent stockfish to get depth 100 very fast and always prune the right move.

[D]8/8/8/2p5/1pp5/brpp4/1pprp2P/qnkbK3 w - - 0 1

User avatar
lucasart
Posts: 3040
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: fixing the null move search "bug"

Post by lucasart » Wed Feb 05, 2014 1:34 pm

Uri Blass wrote: [D]8/8/8/2p5/1pp5/brpp4/1pprp2P/qnkbK3 w - - 0 1
What is the move you expect in this position that SF cannot find ?
DiscoCheck immediately understands that h4 is the best move and leads to a draw. I'm not a good chess player myself, bu I don't see why this is wrong:

Code: Select all

info score cp -25 depth 7 nodes 353 time 0 pv h2h4 a1a2 h4h5 a2a1 h5h6 a1a2 h6h7 a2a1 h7h8q a1a2 h8e5 a2a1 e5h8
DiscoCheck uses aggressive null move, similar to Stockfish (R = a + b*depth, altough with different (a,b) tuned by CLOP). And it performs no verification search. No matter how you implement verif search the cure is always worse than the disease. Verification search is worse than useless.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

Uri Blass
Posts: 8586
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: fixing the null move search "bug"

Post by Uri Blass » Wed Feb 05, 2014 1:39 pm

lucasart wrote:
Uri Blass wrote: [D]8/8/8/2p5/1pp5/brpp4/1pprp2P/qnkbK3 w - - 0 1
What is the move you expect in this position that SF cannot find ?
DiscoCheck immediately understands that h4 is the best move and leads to a draw. I'm not a good chess player myself, bu I don't see why this is wrong:

Code: Select all

info score cp -25 depth 7 nodes 353 time 0 pv h2h4 a1a2 h4h5 a2a1 h5h6 a1a2 h6h7 a2a1 h7h8q a1a2 h8e5 a2a1 e5h8
DiscoCheck uses aggressive null move, similar to Stockfish (R = a + b*depth, altough with different (a,b) tuned by CLOP). And it performs no verification search. No matter how you implement verif search the cure is always worse than the disease. Verification search is worse than useless.
The right move is h3 with the plan h8=N when white is winning

Here is a possible line when all black moves are forced

The reason h4 does not work is that the knight cannot lose a tempo so h4 with h8=N means that the knight will never be able to capture b3 in the right time when the black queen is at a1 and not at a2

[pgn][Event "Computer chess game"]
[Site "URI-PC"]
[Date "2014.02.05"]
[Round "?"]
[White "Uri"]
[Black "Uri"]
[Result "1-0"]
[BlackElo "2400"]
[Time "15:39:58"]
[WhiteElo "2400"]
[TimeControl "40/300:40/300:40/300"]
[SetUp "1"]
[FEN "8/8/8/2p5/1pp5/brpp4/1pprp2P/qnkbK3 w - - 0 1"]
[Termination "normal"]
[PlyCount "29"]
[WhiteType "human"]
[BlackType "human"]

1. h3 Qa2 2. h4 Qa1 3. h5 Qa2 4. h6 Qa1 5. h7 Qa2 6. h8=N Qa1 7. Ng6 Qa2 8.
Ne5 Qa1 9. Nd7 Qa2 10. Nxc5 Qa1 11. Nd7 Qa2 12. Ne5 Qa1 13. Nxc4 Qa2 14.
Na5 Qa1 15. Nxb3# 1-0
[/pgn]
Last edited by Uri Blass on Wed Feb 05, 2014 1:46 pm, edited 3 times in total.

Michel
Posts: 2046
Joined: Sun Sep 28, 2008 11:50 pm

Re: fixing the null move search "bug"

Post by Michel » Wed Feb 05, 2014 1:41 pm

Best move is h3. And the fact that it wins depends essentially on zugzwang. So without verification search (or a similar device) an engine can never solve this position even with infinite time.

One may say this position is not important but that is a different issue.

syzygy
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: fixing the null move search "bug"

Post by syzygy » Wed Feb 05, 2014 2:23 pm

Michel wrote:One may say this position is not important but that is a different issue.
This position is not important, and I don't think that is a different issue (but you're probably responding to Lucas' h4 post). I understand Uri to be talking in terms of overall engine strength. Contrived positions are not important for engine strength.

Of course it would be nice if an engine would not have problems with any position, but simply disabling nullmove when depth is high is very very likely going to cost Elo (even though there are non-contrived positions where nullmove hurts). Uri's argument based on SF's maximal depth is obviously not going anywhere and hopefully does not need further discussion.
Last edited by syzygy on Wed Feb 05, 2014 2:25 pm, edited 1 time in total.

User avatar
lucasart
Posts: 3040
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: fixing the null move search "bug"

Post by lucasart » Wed Feb 05, 2014 2:24 pm

Uri Blass wrote:
lucasart wrote:
Uri Blass wrote: [D]8/8/8/2p5/1pp5/brpp4/1pprp2P/qnkbK3 w - - 0 1
What is the move you expect in this position that SF cannot find ?
DiscoCheck immediately understands that h4 is the best move and leads to a draw. I'm not a good chess player myself, bu I don't see why this is wrong:

Code: Select all

info score cp -25 depth 7 nodes 353 time 0 pv h2h4 a1a2 h4h5 a2a1 h5h6 a1a2 h6h7 a2a1 h7h8q a1a2 h8e5 a2a1 e5h8
DiscoCheck uses aggressive null move, similar to Stockfish (R = a + b*depth, altough with different (a,b) tuned by CLOP). And it performs no verification search. No matter how you implement verif search the cure is always worse than the disease. Verification search is worse than useless.
The right move is h3 with the plan h8=N when white is winning

Here is a possible line when all black moves are forced

The reason h4 does not work is that the knight cannot lose a tempo so h4 with h8=N means that the knight will never be able to capture b3 in the right time when the black queen is at a1 and not at a2

[pgn][Event "Computer chess game"]
[Site "URI-PC"]
[Date "2014.02.05"]
[Round "?"]
[White "Uri"]
[Black "Uri"]
[Result "1-0"]
[BlackElo "2400"]
[Time "15:39:58"]
[WhiteElo "2400"]
[TimeControl "40/300:40/300:40/300"]
[SetUp "1"]
[FEN "8/8/8/2p5/1pp5/brpp4/1pprp2P/qnkbK3 w - - 0 1"]
[Termination "normal"]
[PlyCount "29"]
[WhiteType "human"]
[BlackType "human"]

1. h3 Qa2 2. h4 Qa1 3. h5 Qa2 4. h6 Qa1 5. h7 Qa2 6. h8=N Qa1 7. Ng6 Qa2 8.
Ne5 Qa1 9. Nd7 Qa2 10. Nxc5 Qa1 11. Nd7 Qa2 12. Ne5 Qa1 13. Nxc4 Qa2 14.
Na5 Qa1 15. Nxb3# 1-0
[/pgn]
I must admit, the h3 and knight promotion which forces mate are really beautiful. I totally missed that.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: fixing the null move search "bug"

Post by Evert » Wed Feb 05, 2014 2:37 pm

Michel wrote:Best move is h3. And the fact that it wins depends essentially on zugzwang. So without verification search (or a similar device) an engine can never solve this position even with infinite time.
I was going to say that finding the solution to this problem at all would be an interesting project, because it involves underpromotion to knight and then a fairly precise sequence of moves that I would imagine are hard to find if you don't notice the goal is Nxb3#.

However, before saying that, I fed the position into Jazz, which to my astonishment came back with this:

Code: Select all

  1 -4947     0         3 1. h3   
  2 -4909     0         8 1. h4    Qa2   
  3 -4834     0        25 1. h4    Qa2   2. h5    
  4 -4838     0        44 1. h4    Qa2   2. h5    Qa1   
  5 -4763     0        65 1. h4    Qa2   2. h5    Qa1   3. h6    
  6 -4759     0        90 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   
  7 -4653     0       131 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    
  8 -3822     0       174 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   
  9 -3822     0       222 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   
 10 -3818     0       279 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   
 11 -3682     0       401 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   
 12 -3467     0       553 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qxc4  
 13    0     0       824 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qh8   
 14    0     0      1476 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qh8   
 15    0     0      2272 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qh8   
 16    0     0      3880 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qh8   Qa2   
 17    0     1      6123 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qh8   Qa2   
 18    0     1     12589 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qh8   Qa2   
 19    0     1     20024 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qh8   
 20    0     2     36118 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qh8   
 21    0     3     53674 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qh8   
 22    0     4     80661 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qh8   
 23    0     6    112308 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qh8   
 24    0     9    172269 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qh8   
 25    0    13    257874 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qh8   
 26    0    18    374425 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qh8   
 27    0    24    513327 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qh8   
 28    0    33    721958 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qh8   
 29    0    45    994873 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qh8   
 30    0    62   1437696 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qh8   
 31    0    84   1985484 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qh8   
 32    0   118   2827111 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qh8   
 33    0   164   3935752 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qh8   
 34    0   246   5674567 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qh8   
 35    0   357   8142404 1. h4    Qa2   2. h5    Qa1   3. h6    Qa2   4. h7    Qa1   5. h8Q   Qa2   6. Qh4   Qa1   7. Qh8   
 36  15972   544  12029848 1. h3    Qa2   2. h4    Qa1   3. h5    Qa2   4. h6    Qa1   5. h7    Qa2   6. h8N   Qa1   7. Nf7   Qa2   8. Ne5   Qa1   9. Nd7   Qa2   10. Nxc5  Qa1   11. Nd7   Qa2   12. Ne5   Qa1   13. Nxc4  Qa2   14. Na5   Qa1   15. Nxb3  
Now, Jazz' condition for disabling null move for the side to move is "is not able to lose a tempo", which is simply based on the material on the board (more than one piece that can do a triangulation, ie, a king+non-knight, non-pawn). Still, I wouldn't have expected it to find the mate here.

EDIT: in retrospect, the fact that you can easily win some material probably helps get the relevant moves reasonably high up in the move list.

Sergei S. Markoff
Posts: 224
Joined: Mon Sep 12, 2011 9:27 pm
Location: Moscow, Russia
Contact:

Re: fixing the null move search "bug"

Post by Sergei S. Markoff » Wed Feb 05, 2014 8:27 pm

Uri, I think we can do some research. At first we need to analyse, how often and under which conditions null move goes bad. To accomplish that we need sample data.

To do it you should produce sampling verision of SF with such modifications:
1. At random node (let say if rand() % 10000 == 0) with null search instead of pruning node do verification search with full depth and then store result in log file.
2. Log file should be plain csv with (I suppose) such list of columns:
— side to move;
— alpha;
— static eval;
— depth;
— material signature;
— null-move reduction (plies);
— number of white passers;
— number of black passers;
— number of legal non-losing captures for white;
— number of legal non-losing captures for black;
— number of legal quiet moves with see >= 0 for white;
— number of legal quiet moves with see >= 0 for black;
— number of nodes searched inside null-move subtree;
— number of nodes searched inside full verification search;
— fail flag (1 — for the case of verification search returned < beta, otherwise — 0).

I think that's enogh for the beginning. Let's collect sample of 100 000 positions (for the beginning) and I will perform clustering analysis for this set and let's see — if there are any significant cluster for which it's a good idea to disable null move/add verification search.
The Force Be With You!

Michel
Posts: 2046
Joined: Sun Sep 28, 2008 11:50 pm

Re: fixing the null move search "bug"

Post by Michel » Thu Feb 06, 2014 6:59 am

I did a quick check with GNU Chess 5.5. It solves the position very quickly. If I disable verification search then it cannot solve the position at all. As expected of course.

Post Reply