Stockfish search: bug or feature?

[Jouni]

When running testsuites (my favourite use of engines ) I have noticed, that sometimes Stockfish don't solve position, that others solve fast. When looking at main line I see, that there is first 4 ply "null moves"
= repeat and after that the solution! As seen here:

[d]4k3/7p/1pr1np2/p1p1pNpP/P1P1K1P1/1P2P3/3R1P2/8 w - - bm Rd6

Analysis by Stockfish 1.6.3 JA 64bit:

...
1.Nd6+ Kd7 2.Nf5+ Ke8 3.Rd6 Rxd6 4.Nxd6+ Kd7 5.Nb5 Ke7 6.Nc3 Ng7 7.Kd5 Kd7 8.h6 Ne8 9.Nb5 f5 10.Kxe5 fxg4 11.Kf5 Ke7 12.Kxg5 Nf6 13.Nc7 Ne4+ 14.Kxg4 Nxf2+ 15.Kf5 Nh1 16.Ke5 Kd7
+- (2.74) Depth: 24 00:00:13 43429kN

Is this Stockfish speciality?

Jouni

[BBauer]

I could not see this behavior.
stockfish plays Rd6 at depth 20 after 8.5 sec

Code: Select all

18 +133 515 8875971 Nd6+ Ke7 Nf5+ Ke8 Rd3 Nd8 Nh6 Ne6 Ng8 Nc7 Rd1
19 +133 547 9657504 Nd6+ Ke7 Nf5+ Ke8 Rd3 Nd8 Nh6 Ne6 Ng8 Nc7 Rd1
20 +129 728 13682798 Nd6+ Ke7 Nf5+ Ke8 Rd3 Nd8 Nh6 Ne6 Ng8 Nc7 Rd1
20 +153 843 16776437 Rd6 Rxd6 Nxd6+ Kd7 Nb5 Ke7 Nc3 Ng7 Kd5 Kd7 h6
21 +177 893 18259436 Rd6 Rxd6 Nxd6+ Kd7 Nb5 Ng7 h6 Ne8 Kd5 e4 Kxe4
22 +226 1038 21857944 Rd6 Nd8 Kd5 Rxd6+ Kxd6 Nb7+ Ke6
23 +250 1257 27183379 Rd6 Rxd6 Nxd6+ Kd7 Nb5 Ng7 h6 Ne8 Kd5 f5 Kxe5
24 +270 1711 39156488 Rd6 Rxd6 Nxd6+ Kd7 Nb5 Ng7 h6 Ne8 Kd5 f5 Kxe5
25 +335 2654 63003700 Rd6 Rxd6 Nxd6+ Kd7 Nb5 Ng7 h6 Ne8 Kd5 f5 Kxe5
26 +331 2951 70907676 Rd6 Rxd6 Nxd6+ Kd7 Nb5 Ng7 h6 Ne8 Kd5 f5 Kxe5
27 +355 5509 141166739 Rd6 Rxd6 Nxd6+ Kd7 Nb5 Ke7 Nc3 Nf8 Nd5+ Kf7 
28 +355 8071 194215009 Rd6 Rxd6 Nxd6+ Kd7 Nb5 Ke7 Nc3 Ng7 Kd5 Kd7 
29 +331 9744 234871141 Rd6 Rxd6 Nxd6+ Kd7 Nb5 Ke7 Nc3 Ng7 Kd5 Kd7

kind regards
Bernhard

[BBauer]

Sorry, my stockfish version was modified. In search.cpp I have changed
the line 1412 from
Value v = search(pos, ss, beta, depth-5*OnePly, ply, false, threadID);
to
Value v = search(pos, ss, beta, depth-6*OnePly, ply, false, threadID);


The unmodified version gives the following. So you are right.
kind regards
Bernhard

Code: Select all

18 +129 454 5998102 Nd6+ Ke7 Nf5+ Ke8 Rd5 Nd8 Rd1 Nb7 f4 exf4 exf4 gxf4
19 +149 702 13326857 Nd6+ Kd7 Nf5+ Ke8 Rd3 Nd8 Nh6 Ne6 Rd1 Nc7 Nf5 Ne6
20 +145 801 15647153 Nd6+ Kd7 Nf5+ Ke8 Rd3 Nd8 Nh6 Ne6 Rd1 Nc7 Nf5 Ne6
21 +141 1079 23463508 Nd6+ Kd7 Nf5+ Ke8 Rd3 Nd8 Nh6 Ne6 Rd1 Nc7 Nf5 Ne6
22 +173 1310 29725336 Nd6+ Ke7 Nf5+ Ke8 Rd6 Rxd6 Nxd6+ Kd7 Nb5 Ke8 Nc3
23 +262 1802 43786383 Nd6+ Ke7 Nf5+ Ke8 Rd6 Rxd6 Nxd6+ Kd7 Nb5 Ke8 Nc3
24 +242 2262 55784651 Nd6+ Ke7 Nf5+ Ke8 Rd6 Rxd6 Nxd6+ Kd7 Nb5 Ke7 Nc3
25 +258 3113 76810417 Nd6+ Ke7 Nf5+ Ke8 Rd6 Rxd6 Nxd6+ Kd7 Nb5 Ke7 Nc3
26 +266 3819 96126252 Nd6+ Ke7 Nf5+ Ke8 Rd6 Rxd6 Nxd6+ Kd7 Nb5 Ke7 Nc3
27 +282 5627 144104544 Nd6+ Ke7 Nf5+ Ke8 Rd6 Rxd6 Nxd6+ Kd7 Nb5 Ke7 Nc3

[Aaron Becker]

I suspect this phenomenon is due to the way that Stockfish handles the PV. Non-PV nodes are pruned and reduced much more aggressively than the PV, so it may be that it's easier for Stockfish to find a solution that doesn't involve replacing the PV at the root, even though the resulting solution contains some pointless filler moves.

[Jouni]

Another example:

[d]1r4r1/1Q4Bk/6p1/6K1/8/8/8/n7 w - - bm Qc7

Analysis by Stockfish 1.6.3 JA 64bit:

...
1.Qa7 Ra8 2.Qb7 Rab8 3.Qc7 Rbc8 4.Qh2+ Kxg7 5.Qb2+ Kh7 6.Qb7+ Rg7 7.Qxc8 Re7 8.Qb8 Rf7 9.Qh2+ Kg8 10.Kxg6 Rg7+ 11.Kf5 Rf7+ 12.Ke6 Rg7 13.Qb8+ Kh7 14.Qb1+ Rg6+ 15.Kd5
+- (6.22) Depth: 27 00:00:57 318mN

Jouni

[Pablo Vazquez]

Maybe this solves it: in position.cpp line 1671 change "<" to "<=".

[Eelco de Groot]

Code: Select all

 // Draw by repetition?
 for (int i = 2; i < Min(Min(gamePly, st->rule50), st->pliesFromNull); i += 2) // Change < to <=? Bugfix suggested by Pablo Vasquez
     if (history[gamePly - i] == st->key)
         return true;

 return false;
}

Maybe this solves it: in position.cpp line 1671 change "<" to "<=".

Thanks Pablo for reporting a bug! At least I think it may be but I can't say I competely follow all of the code in position.cpp. Complication is if you do not want to count first time repetitions in analysis mode, I think this no longer is a bug but, as Jouni correctly surmised in the thread title, an important feature At least part of it, it only works for repetitions of the startposition.

Bernhard's suggestion is also interesting, because null move may be partly to blame for not correcting this in time in the Non-PV nodes, and if you use adaptive null move pruning of for instance Dann's version of adaptive null move, there is something to say for also making the verification search adaptive. I tried

Code: Select all

         // Do zugzwang verification search
         Value v = search(pos, ss, beta, depth - (R + 1)*OnePly, ply, false, threadID);
         if (v >= beta)
             return beta;

as a variation on what Bernhard suggested, this should make the verification search a bit deeper but also a bit safer if R+1 < 5

Regards, Eelco

[Eelco de Groot]

Another example:

[d]1r4r1/1Q4Bk/6p1/6K1/8/8/8/n7 w - - bm Qc7

Analysis by Stockfish 1.6.3 JA 64bit:

...
1.Qa7 Ra8 2.Qb7 Rab8 3.Qc7 Rbc8 4.Qh2+ Kxg7 5.Qb2+ Kh7 6.Qb7+ Rg7 7.Qxc8 Re7 8.Qb8 Rf7 9.Qh2+ Kg8 10.Kxg6 Rg7+ 11.Kf5 Rf7+ 12.Ke6 Rg7 13.Qb8+ Kh7 14.Qb1+ Rg6+ 15.Kd5
+- (6.22) Depth: 27 00:00:57 318mN

Jouni

Here the "bugfix" of a deeper verification search did not work, with the standard version it is solved faster by Rainbow Serpent, but not terribly fast.


[d]1r4r1/1Q4Bk/6p1/6K1/8/8/8/n7 w - -

Engine: Rainbow Serpent 1.6.3s(dc) Build 126 (Athlon 2009 MHz, 128 MB)
by Tord Romstad, Marco Costalba, Joona Kiiski Modifications: Dann Corbit

1.00 0:00 -0.32 1.Qc7 (262) 2

2.00 0:00 -0.16 1.Qc7 Rgc8 (378) 3

3.00 0:00 -0.36 1.Qc7 Rgc8 2.Qe5 (2.435) 19

4.00 0:00 -0.08 1.Qc7 Rbc8 2.Qb7 Rb8 3.Qc7 (4.331) 34

5.00 0:00 0.00 1.Qc7 Rbc8 2.Qb7 Rb8 3.Qc7 (5.604) 44

6.00 0:00 0.00 1.Qc7 Rbc8 2.Qb7 Rb8 3.Qc7 (6.735) 48

7.00 0:00 0.00 1.Qc7 Rbc8 2.Qb7 Rb8 3.Qc7 (9.144) 65

8.00 0:00 0.00 1.Qc7 Rbc8 2.Qb7 Rb8 3.Qc7 (14.340) 102

9.00 0:00 +0.20++ 1.Qc7 Rbc8 2.Qd7 Rgd8 3.Qf7 (22.136) 141

10.00 0:00 +0.36 1.Qc7 Rbc8 2.Qd7 Rcd8 3.Qe7 Rxg7
4.Qxd8 Rb7 5.Qd5 Ra7 6.Qh1+ Kg8
7.Kxg6 (35.802) 208

10.00 0:00 +1.01++ 1.Qh1+ Kxg7 2.Qxa1+ Kh7 3.Qa7+ Kh8
4.Kh6 (46.172) 246

11.00 0:00 +4.24++ 1.Qh1+ Kxg7 2.Qxa1+ Kh7 3.Qa7+ Kh8
4.Kh6 (47.594) 254

12.00 0:00 +5.29 1.Qh1+ Kxg7 2.Qxa1+ Kh7 3.Qa7+ Rg7
4.Qxb8 Rf7 5.Qh2+ Kg7 6.Qh6+ Kg8
7.Qh1 Kg7 8.Qa1+ Kh7 9.Kg4 Kg8
10.Qd4 Kf8 (124.758) 443

13.00 0:00 +5.29 1.Qh1+ Kxg7 2.Qxa1+ Kh7 3.Qa7+ Rg7
4.Qxb8 Rf7 5.Qh2+ Kg7 6.Qh6+ Kg8
7.Qh1 Kg7 8.Qa1+ Kh7 9.Kg4 Kg8
10.Qd4 Kh7 11.Qb2 Kg8 12.Qe5 Kf8 (620.764) 811

14.00 0:00 +5.13 1.Qh1+ Kxg7 2.Qxa1+ Kh7 3.Qa7+ Rg7
4.Qxb8 Rf7 5.Qh2+ Kg7 6.Qh6+ Kg8
7.Qh1 Kg7 8.Qa1+ Kh7 9.Kg4 Kg8
10.Qd4 Kh7 11.Qe5 Rf5 12.Qc7+ Kh6
13.Qc3 Kh7 14.Qb4 (789.414) 828

15.00 0:01 +5.17 1.Qh1+ Kxg7 2.Qxa1+ Kh7 3.Qa7+ Rg7
4.Qxb8 Rf7 5.Qh2+ Kg7 6.Qh6+ Kg8
7.Qh1 Kg7 8.Qa1+ Kh7 9.Kg4 Kg8
10.Qd4 Kh7 11.Qe5 Rf5 12.Qc7+ Kh6
13.Qh2+ Kg7 14.Qb2+ (918.230) 851

16.01 0:03 +5.17 1.Qh1+ Kxg7 2.Qxa1+ Kh7 3.Qa7+ Rg7
4.Qxb8 Rf7 5.Qh2+ Kg7 6.Qh6+ Kg8
7.Qh1 Kg7 8.Qa1+ Kh7 9.Kg4 Kg8
10.Qd4 Kh7 11.Qe5 Rf5 12.Qc7+ Kh6
13.Qh2+ Kg7 14.Qb2+ (3.719.799) 1004

17.01 0:04 +5.17 1.Qh1+ Kxg7 2.Qxa1+ Kh7 3.Qa7+ Rg7
4.Qxb8 Rf7 5.Qh2+ Kg7 6.Qh6+ Kg8
7.Qh1 Kg7 8.Qa1+ Kh7 9.Kg4 Kg8
10.Qd4 Kh7 11.Qe5 Rf5 12.Qc7+ Kh6
13.Qe7 Rh5 14.Qf6 (4.055.583) 1006

18.01 0:08 +5.21 1.Qh1+ Kxg7 2.Qxa1+ Kh7 3.Qa7+ Rg7
4.Qxb8 Rf7 5.Qh2+ Kg7 6.Qh6+ Kg8
7.Qh1 Kg7 8.Qa1+ Kh7 9.Kg4 Kg8
10.Qd4 Kh7 11.Qe5 Rf5 12.Qc7+ Kh6
13.Qe7 Rh5 14.Kf4 (8.868.040) 1097

19.01 0:15 +5.21 1.Qh1+ Kxg7 2.Qxa1+ Kh7 3.Qa7+ Rg7
4.Qxb8 Rf7 5.Qh2+ Kg7 6.Qh6+ Kg8
7.Qh1 Kg7 8.Qa1+ Kh7 9.Kg4 Kg8
10.Qd4 Kh7 11.Qe5 Rf5 12.Qc7+ Kh6
13.Qe7 Rh5 14.Kf4 (18.045.074) 1173

20.01 0:16 +5.21 1.Qh1+ Kxg7 2.Qxa1+ Kh7 3.Qa7+ Rg7
4.Qxb8 Rf7 5.Qh2+ Kg7 6.Qh6+ Kg8
7.Qh1 Kg7 8.Qa1+ Kh7 9.Kg4 Kg8
10.Qd4 Kh7 11.Qe5 Rf5 12.Qc7+ Kg8
13.Qb7 Kf8 14.Qh7 (19.435.552) 1172

21.01 0:31 +5.21 1.Qh1+ Kxg7 2.Qxa1+ Kh7 3.Qa7+ Rg7
4.Qxb8 Rf7 5.Qh2+ Kg7 6.Qh6+ Kg8
7.Qh1 Kg7 8.Qa1+ Kh7 9.Kg4 Kg8
10.Qd4 Kh7 11.Qe5 Rf5 12.Qc7+ Kh6
13.Qe7 Rb5 14.Qd6 (39.408.272) 1236

21.02 0:37 +5.41++ 1.Qc7 Rbc8 2.Qh2+ Kxg7 3.Qb2+ Kh7
4.Qb7+ Rg7 5.Qxc8 Ra7 6.Kf6 g5
7.Qf5+ Kh8 8.Kxg5 Kg7 9.Qf6+ Kg8
10.Kg6 (44.292.129) 1188

22.01 0:38 +6.22++ 1.Qc7 Rbc8 2.Qh2+ Kxg7 3.Qb2+ Kh7
4.Qb7+ Rg7 5.Qxc8 Ra7 6.Kf6 g5
7.Qf5+ Kh8 8.Kxg5 Kg7 9.Qf6+ Kg8
10.Kg6 (45.150.999) 1180

23.01 0:57 +7.37 1.Qc7 Rbc8 2.Qh2+ Kxg7 3.Qb2+ Kf7
4.Qf6+ Ke8 5.Qe6+ Kd8 6.Qxg8+ Kc7
7.Qg7+ Kd8 8.Qd4+ Ke7 9.Qxa1 Rc6
10.Qa7+ Kd6 11.Kxg6 Rc5 12.Kf6 Kd5
13.Qa4 Rc6+ 14.Kf5 (65.255.661) 1135

24.01 1:41 +7.37 1.Qc7 Rbc8 2.Qh2+ Kxg7 3.Qb2+ Kf7
4.Qf6+ Ke8 5.Qe6+ Kd8 6.Qxg8+ Kc7
7.Qg7+ Kd8 8.Qd4+ Ke7 9.Qxa1 Rc6
10.Qa7+ Kd6 11.Kxg6 Rc5 12.Kf6 Kd5
13.Qa4 Rc6+ 14.Kf5 (117.263.355) 1152

best move: Qb7-c7 time: 1:58.672 min n/s: 1.150.892 nodes: 136.560.342

With standard way of doing verification:

Code: Select all

            // Do zugzwang verification search
            Value v = search(pos, ss, beta, depth-5*OnePly, ply, false, threadID);
            if (v >= beta)
                return beta;

[zamar]

Indeed! This is a bug in Stockfish!

Thanks Jouni for reporting the issue and Pablo for the fix!

I'll forward the fix to Marco and it will be included in current development branch of Stockfish.

[Togga]

how much elo improvement would it be? and will the next stockfish version have smoothscaling support?