I wonder if more programmers have experimented with this? I know it is not in Glaurung and not in Stockfish, it is not in Fruit either. Crafty does it perhaps?
Part of the implemention question; of how to go about it, is, if the null move search can be limited, can it be limited safely or should it not be limited in the capture search at all. A shorter q-search like one does in the normal search would be nice, but is it still safe, or alternatively if you do not limit the depth of the null move in q-search then are you still saving nodes or are you making the q-search a bit more accurate, but actually longer?
The first try I did was with a normal unlimited null move search. In Tord's program it comes down to a very simple block of code, everything already exists elsewhere and no verification seems necessary especially if there is no depth limitation. As far as I can see, the search is not shortened, may actually be slightly longer but the main difference seems to be the search shows a bit lower evaluations It is less optimistic? Something not entirely obvious from the outset
This is with normal seach in a test-position from a very recent game:
1rr5/1b2k2p/pq1p1bpP/n1n1pP2/3NP3/2N4R/1PP1Q1B1/1KBR4 w - -
Engine: Ancalagon 1.3 WS180BC5050 Build 192 (256 MB)
by Romstad, Costalba, Kiiski, de Groot
2.01 0:06 +1.26 29.Nf3 gxf5 (13.603) 1
3.01 0:17 +0.39 29.Nf3 gxf5 30.exf5 Kf8 31.Rg3 (191.829) 11
3.02 0:17 +0.39 29.Nd5+ (199.046) 11
3.31 0:24 +0.40 29.fxg6 (430.118) 17
4.01 0:25 -1.31 29.fxg6 exd4 30.Nd5+ Bxd5 31.exd5+ Be5
32.gxh7 d3 33.cxd3 Rh8 34.Bg5+ Ke8 (629.163) 24
4.02 0:25 -0.05 29.Nd5+ Bxd5 30.exd5 Kf8 31.Rf3 gxf5
32.Nxf5 (633.724) 24
4.03 0:25 +0.39 29.Nf3 gxf5 30.exf5 Kf8 31.Rg3 (646.564) 25
4.31 0:27 +0.78 29.Ne6 gxf5 30.Ng7 fxe4 31.Nf5+ Kf8
32.Rxd6 Rc6 (1.166.828) 42
5.01 0:27 +0.78 29.Ne6 gxf5 30.Ng7 fxe4 31.Nf5+ Kf8
32.Rxd6 Rc6 (1.367.064) 49
6.01 0:42 +1.16 29.Ne6 (6.425.828) 152
7.01 0:44 +2.69 29.Ne6 (7.220.402) 161
8.01 0:47 +2.52 29.Ne6 gxf5 30.exf5 Nxe6 31.Bxb7 Rxc3
32.Rxc3 Nd4 33.Rxd4 Qxd4 34.Rd3 Qxd3
35.Qxd3 Rxb7 36.Qxa6 (8.173.920) 173
9.01 2:11 +2.56 29.Ne6 gxf5 30.exf5 Nxe6 31.Bxb7 Rxc3
32.Rxc3 Nd4 33.Rxd4 Qxd4 34.Rd3 Qxd3
35.Qxd3 Nxb7 36.Qxa6 (38.882.718) 294
10.01 7:04 +3.15 29.Ne6 Qb4 30.Nxc5 Rxc5 31.fxg6 Nc4
32.Nd5+ Bxd5 33.Rxd5 Na3+ 34.Rxa3 Qxa3
35.g7 Rxd5 36.g8Q Rxg8 37.bxa3 Rb5+
38.Ka2 Bg5 39.Bxg5+ Rxg5 40.Bh3 (140.193.421) 330
11.01 15:45 +3.72 29.Ne6 Qb4 30.Nxc5 Rxc5 31.fxg6 Nc4
32.Nd5+ Bxd5 33.Rxd5 Qb5 34.Rxc5 dxc5
35.Bf1 Nd2+ 36.Qxd2 Qxf1 37.Rd3 Kf8
38.gxh7 Ke8 (334.115.566) 353
12.01 100:53 +4.05 29.Ne6 Nxe6 30.fxe6 Nc4 31.b3 Na5
32.Nd5+ Bxd5 33.exd5 Qc5 34.Rf1 e4
35.Rxf6 Nxb3 36.Bb2 Nd4 37.Rf7+ Ke8
38.Qxe4 Qxc2+ 39.Qxc2 Rxc2 (2.133.250.203) 352
13.01 350:19 +3.78 29.Ne6 Nxe6 30.fxe6 Nc4 31.b3 Na5
32.Na4 Qb4 33.Rf1 Nxb3 34.cxb3 Qxa4
35.bxa4 Bxe4+ 36.Ka1 Rb1+ 37.Ka2 Rc2+
38.Qxc2 Bxc2 39.Rc3 Rxc1 40.Rxc1 Bxa4 (6.672.110.890) 317
best move: Nd4-e6 time: 595:12.969 min n/s: 331.872 nodes: 11.852.130.363
And this is with Null Move implemented in quiescence search:
[D]1rr5/1b2k2p/pq1p1bpP/n1n1pP2/3NP3/2N4R/1PP1Q1B1/1KBR4 w - -
Engine: Ancalagon 1.3 Weak Squares 180 Board Control middle game 50 endgame 50 Null move in quiescence search, of unlimited depth, Build 236 (Athlon 2009 Mhz, 256 MB)
by Romstad, Costalba, Kiiski, de Groot
2.00 0:00 +1.26 29.Nf3 gxf5 (17.928) 40
3.00 0:00 +0.39 29.Nf3 gxf5 30.exf5 Kf8 31.Rg3 (226.915) 241
3.33 0:01 +0.39 29.fxg6 (520.946) 311
4.01 0:02 +0.66 29.fxg6 exd4 30.Nd5+ Bxd5 31.exd5+ Kd8
32.Qf2 Nd7 33.g7 Ke7 (695.005) 336
4.31 0:04 +2.88 29.Ne6 Nxe6 30.fxe6 Kxe6 31.Rf3 Rxc3
32.Bh3+ Kf7 33.Rxc3 Kg8 34.Be6+ Kf8 (1.596.475) 370
5.01 0:05 +0.78 29.Ne6 gxf5 30.Ng7 fxe4 31.Nf5+ Kf8
32.Rxd6 Rc6 (1.980.867) 378
6.01 0:12 +2.43 29.Ne6 gxf5 30.Ng7 fxe4 31.Nf5+ Kf8
32.Rxd6 Rc6 33.Nd5 Rxd6 34.Nxb6 Rxb6 (5.159.405) 412
7.01 0:52 +2.25 29.Ne6 gxf5 30.Ng7 f4 31.Nf5+ Kf8
32.Rxd6 Rc6 33.Nd5 Rxd6 34.Nxb6 Rxb6 (21.686.439) 411
8.01 1:03 +2.25 29.Ne6 gxf5 30.Ng7 f4 31.Nf5+ Kf8
32.Rxd6 Rc6 33.Nd5 Rxd6 34.Nxb6 Rxb6 (26.780.510) 419
9.01 1:47 +2.45 29.Ne6 (46.637.299) 435
10.01 4:00 +2.54 29.Ne6 Qb4 30.Nxc5 Rxc5 31.fxg6 Nc4
32.Nd5+ Bxd5 33.Rxd5 Qb5 34.Qg4 Nxb2
35.Rxc5 dxc5 36.Rb3 (100.234.636) 416
11.01 14:06 +3.13 29.Ne6 (362.287.841) 428
12.01 26:40 +3.94 29.Ne6 Nxe6 30.fxe6 Nc4 31.b3 Na5
32.Nd5+ Bxd5 33.exd5 Rxc2 34.Qxc2 Nxb3
35.Bb2 Nc5 36.Rf1 Qxb2+ 37.Qxb2 Rxb2+
38.Kxb2 e4+ 39.Kc2 g5 (672.560.513) 420
best move: Nd4-e6 time: 58:36.812 min n/s: 415.764 nodes: 1.462.140.299
Slightly lower eval it seems and especially a highlight is that the bad score for fxg6 is gone, from very early in the search, this now follows the actual game between a 56 core Cluster Rybka and a Skulltrail 8 core HIARCS for 9 plies in the 4 ply deep variation! Not too bad a result for source-code from 1986
Without null move qsearch():
4.01 0:25 -1.31 29.fxg6 exd4 30.Nd5+ Bxd5 31.exd5+ Be5
32.gxh7 d3 33.cxd3 Rh8 34.Bg5+ Ke8 (629.163) 24
With null move quiescence search this has become:
4.01 0:02 +0.66 29.fxg6 exd4 30.Nd5+ Bxd5 31.exd5+ Kd8 32.Qf2 Nd7 33.g7 Ke7 (695.005) 336
This was the game I borrowed the position from:
[Event "ICS unrated standard match"]
[Site "chessclub.com"]
[Date "2009.08.15"]
[Round "-"]
[White "Rybka"]
[Black "Hiarcs8x"]
[WhiteElo "2813"]
[BlackElo "2789"]
[Result "1-0"]
1. e4 c5 2. Nf3 d6 3. d4 cxd4 4. Nxd4 Nf6 5. Nc3 a6 6. h3
e6 7. g4 b5 8. Bg2 Bb7 9. a3 Be7 10. Be3 O-O 11. f4 Nfd7
12. Qf3 Nb6 13. O-O-O N8d7 14. Kb1 Nc4 15. Bc1 Qc7 16. h4
Rfc8 17. Rh3 b4 18. axb4 Qb6 19. g5 Qxb4 20. Na2 Qb6
21. Qg4 Nc5 22. Qe2 Na5 23. h5 Rab8 24. g6 Bf6 25. gxf7+
Kxf7 26. h6 g6 27. f5 Ke7 28. Nc3 e5 29. fxg6 exd4 30. Nd5+
Bxd5 31. exd5+ Kd8 32. Qf2 Nd7 33. g7 Kc7 34. Be4 Qb4
35. Rhd3 Nc4 36. Rb3 Qa4 37. Rdd3 Ncb6 38. Rf3 Be5 39. Rf7
Rd8 40. Bg5 Rg8 41. Bxh7 Bxg7 42. hxg7 Rge8 43. Bf5 Rb7
44. Qg3 d3 45. Be3 Rxe3 46. Rc3+ Nc4 47. Rxc4+ Qxc4
48. Rxd7+ Kb6 49. Qxe3+ Ka5 50. Qd2+ Qb4 51. c3 Qxb2+
52. Qxb2 Rxb2+ 53. Kxb2 d2 54. g8=Q d1=Q 55. Bc2 Qd4
56. cxd4 Kb5 57. Kc3 a5 58. Rb7+ Ka6 59. Qa8# {Hiarcs8x
checkmated} 1-0
I also now have a version that does limit the null move search in depth, but this post is maybe getting a bit long so I'll save that for later. A new parameter is added to the call to qsearch, bool limitDepth
Code: Select all
// qsearch() is the quiescence search function, which is called by the main
// search function when the remaining depth is zero (or, to be more precise,
// less than OnePly).
Value qsearch(Position &pos, SearchStack ss[], Value alpha, Value beta,
Depth depth, int ply, bool limitDepth, int threadID) {
I should note for certain critics that every building block for this "new" code was already there
Code: Select all
// Initialize "stand pat score", and return it immediately if it is
// at least beta.
Value bestValue = staticValue;
if (bestValue >= beta)
{
// Store the score to avoid a future costly evaluation() call
if (!isCheck && !tte && ei.futilityMargin == 0)
TT.store(pos, value_to_tt(bestValue, ply), VALUE_TYPE_EVAL, Depth(-127*OnePly), MOVE_NONE);
return bestValue;
}
if (bestValue > alpha)
alpha = bestValue;
Code: Select all
Value nullValue;
bool disableNull = false;
Code: Select all
// Null move in quiescence search
if ( !disableNull
&& !isCheck
&& !value_is_mate(beta)
&& ok_to_do_nullmove(pos)
&& bestValue >= beta - NullMoveMargin)
{
ss[ply].currentMove = MOVE_NULL;
StateInfo st;
pos.do_null_move(st);
nullValue = -qsearch(pos, ss, -beta, -alpha, depth-OnePly, ply+1, true, threadID);
pos.undo_null_move();
if (value_is_mate(nullValue))
{
/* Do not return unproven mates */
}
else if (nullValue >= beta)
{
return beta;
}
}
Code: Select all
// Initialize a MovePicker object for the current position, and prepare
// to search the moves. Because the depth is <= 0 here, only captures,
// queen promotions and checks (only if depth == 0) will be generated.
MovePicker mp = MovePicker(pos, pvNode, ttMove, EmptySearchStack, depth);
Move move;