fixing the null move search "bug"

[syzygy]

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]

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

[lucasart]

[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.

[Uri Blass]

[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]

[Michel]

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]

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.

[lucasart]

[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.

[Evert]

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]

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.

[Michel]

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.