Null move in quiescence search idea from Don Beal, 1986

[Eelco de Groot]

Ed mentioned this in his post here, that BCP already in 1986 was experimenting with null move in the quiescence search. Thanks for the tip Ed! I am trying it out in Ancalagon now Ed I don't think you ever mentioned whether Rebel does this though, but I suspect it does not? On the other hand it is possible and Rebel does mysterious things there in its q-search, it is possible to do up to 4 checks in quiescence with some of the hidden parameters of Pro Deo and it still does not slow down very much!

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) {

The added code fragment to do null move in quiescence search is, thanks to Tord's fabulous codebase very short, this only I added to Stockfish 1.3 based Ancalagon after the stand-pat investigation in qsearch().

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;

Two new variables

Code: Select all

    Value nullValue;
    bool disableNull = false;

New block:

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 &#40;only if depth == 0&#41; will be generated.
    MovePicker mp = MovePicker&#40;pos, pvNode, ttMove, EmptySearchStack, depth&#41;;
    Move move;

Eelco

[zamar]

My intuition says that null move in qsearch is way too expensive to be of any good. I could very well be wrong though

Looking through the code you posted, it looks like that you are doing null move also in PV nodes. That must be very wrong.

[mcostalba]

I would think that pruning captures with negative SEE and captures that in any case cannot reach beta because the captured piece value is not enough (see the qsearch futility pruning) is more effective, simpler to understund and faster and should not miss any move that a possible null move would catch.

But admittely I have not tought a lot on this: null move in qsearch is not immediatily evident what stands for, what is its 'meaning' given that we are talking of just captures here.

[bob]

Ed mentioned this in his post here, that BCP already in 1986 was experimenting with null move in the quiescence search. Thanks for the tip Ed! I am trying it out in Ancalagon now Ed I don't think you ever mentioned whether Rebel does this though, but I suspect it does not? On the other hand it is possible and Rebel does mysterious things there in its q-search, it is possible to do up to 4 checks in quiescence with some of the hidden parameters of Pro Deo and it still does not slow down very much!

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) {

The added code fragment to do null move in quiescence search is, thanks to Tord's fabulous codebase very short, this only I added to Stockfish 1.3 based Ancalagon after the stand-pat investigation in qsearch().

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;

Two new variables

Code: Select all

    Value nullValue;
    bool disableNull = false;

New block:

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 &#40;only if depth == 0&#41; will be generated.
    MovePicker mp = MovePicker&#40;pos, pvNode, ttMove, EmptySearchStack, depth&#41;;
    Move move;

Eelco

No, I don't. The current stand/pat stuff with pruning bad captures effectively eliminates the benefit of this. But of course we all do it in the normal search in a somewhat different form.

[bob]

My intuition says that null move in qsearch is way too expensive to be of any good. I could very well be wrong though

Looking through the code you posted, it looks like that you are doing null move also in PV nodes. That must be very wrong.

I do, and always have, done null moves _everywhere_. Testing has shown that is better than trying to avoid them in PV nodes. I do use the hash table trick to turn null moves off when it appears a null move will not fail high in the current position based on hash table info.

[adieguez]

I have not tried this very much in the past but I will try better this time. This is very interesting. Afair the focus is to resolve threats. Im getting tired of amyan not seeing almost nothing in the qsearch, I want it to see some longer tactical lines now. I think it is more entertaining.

[rebel777]

Ed mentioned this in his post here, that BCP already in 1986 was experimenting with null move in the quiescence search. Thanks for the tip Ed! I am trying it out in Ancalagon now Ed I don't think you ever mentioned whether Rebel does this though, but I suspect it does not? On the other hand it is possible and Rebel does mysterious things there in its q-search, it is possible to do up to 4 checks in quiescence with some of the hidden parameters of Pro Deo and it still does not slow down very much!

Hi Eelco,

I never tried null-move in QS as I could not come up with an idea that probably could be useful. Instead my focus has always been on a very fast QS. The "mysterious" things you talk about are fully documented on my pages.

The number of checks in QS is controlled by the below parameter:

[Checks Depth = 2]

Default is 2. I tested with various values, but 2 seems to work best in games.

Ed

[bob]

I have not tried this very much in the past but I will try better this time. This is very interesting. Afair the focus is to resolve threats. Im getting tired of amyan not seeing almost nothing in the qsearch, I want it to see some longer tactical lines now. I think it is more entertaining.

There is a pretty easy way to see long tactical lines. A couple in fact.

1. When any position fails high in the tree, stop and do a null-move search with a lowered window. If this fails low, this means doing nothing is bad and your opponent has some sort of threat. Since you failed high here, you may well be in one of those positions where there is only one way to hold off your opponent's threat, and those kinds of positions are dangerous. So if you want to fail high, but the null-move (offset downward by say 1/2 pawn or more) fails low, then you extend by one ply and search again and use this result rather then the original fail-high result.

2. You can use an el-cheapo singular extension approach. At the beginning of a node, first search the first move with the normal window, but with a 2-3-4 ply reduced depth. Now search the remainder of the moves with the same reduced depth, but offset the A-B window down by a pawn or so. If all the other moves fail low, then they are a pawn or more worse than the best move you found. Now start the normal search but when you get to this "singularly good move" extend it by one ply. Note the original singular test can be complex. For example, the first move gives a score, the next 3 fail low, but the 4th fails high. This 4th move might be singularly better than the original best move. You have to re-test this hypothesis. Until you complete and either prove that one move is significantly better than the rest, or that there are two or more moves that are pretty close (in which case nothing is extended).

The drawback? These cost some depth overall, but gain some depth on tactical lines. Your task is to make the cost hurt you less than the gain helps. I've not done so yet.

[Eelco de Groot]

Back to the future of 1986 again, some reexploring of the idea from Don Beal's BCP, more than 25 years ago now. Old thread but I just wanted to mention in that the old new idea has become a little more attractive perhaps, because there may be a way to avoid a costly static evaluation call in quiescence search as suggested by Honzhi Cheng on GitHub. If we do nullmove in quiescence search it should profit from the same trick

The speedup is already in the quiescence search code, we just have to add null move in there too. I don't have any hard measurements, it may still be too costly as Bob and Joona expected. I just wanted to share the above fragment that I have just converted to the code as it is now in recent Stockfish 2.3.1 (Stockfish Master is different again from this and Marco also has a slightly different implementation of avoiding the evaluate call after nullmove than Rainbow Serpent).

In search.cpp, quiescence search, starting with line 1162 in Rainbow Serpent's version of the file:

Code: Select all

    // Evaluate the position statically
    if (inCheck)
    {
        bestValue = futilityBase = -VALUE_INFINITE;
        ss->eval = evalMargin = VALUE_NONE;
        enoughMaterial = false;
    }
    else
    {
        if (tte)
        {
            assert(tte->static_value() != VALUE_NONE);

            evalMargin = tte->static_value_margin();
            ss->eval = bestValue = tte->static_value();
        }
        else
        {
            if ((ss)->skipNullMove && ((ss-1)->currentMove == MOVE_NULL))
            {
                 ss->eval = bestValue = -(ss-1)->eval;
                 evalMargin = -(ss-1)->evalMargin;
             }
             else
             {
                ss->eval = bestValue = evaluate(pos, evalMargin);
                if (bestValue >= beta)
                {   // Stand pat
                     TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin);
                     return bestValue;
                 }
              }
        }

        // Stand pat. Return immediately if static value is at least beta
        if (bestValue >= beta)
            return bestValue;

        if (PvNode && bestValue > alpha)
            alpha = bestValue;

        futilityBase = ss->eval + evalMargin + FutilityMarginQS;
        enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMg;
		
        Value nullValue;
        bool disableNull = false;
		
        // Null move in quiescence search
        if (   !disableNull	// !inCheck is already tested
            && !PvNode
            && !ss->skipNullMove
            &&  enoughMaterial
            &&  abs&#40;beta&#41; < VALUE_MATE_IN_MAX_PLY
            &&  bestValue >= beta - futility_margin&#40;depth, 0&#41;)
         &#123;
             ss->currentMove = MOVE_NULL;
			
             pos.do_null_move<true>&#40;st&#41;;
             &#40;ss+1&#41;->skipNullMove = true;
             nullValue = -qsearch<NonPV>&#40;pos, ss+1, -beta, -alpha, DEPTH_ZERO&#41;;
             &#40;ss+1&#41;->skipNullMove = false;
             pos.do_null_move<false>&#40;st&#41;;
			
             if &#40;nullValue >= VALUE_MATE_IN_MAX_PLY&#41;
             &#123;
                 /* Do not return unproven mates */
                 nullValue = beta;
             &#125;
             if &#40;nullValue >= beta&#41;
                 return beta;
         &#125;
    &#125;

The "Do not return" line is more for comparison's sake with regular nullmove. We are saying that, if with an extra move the opponent still does not have any capture to reach his beta, we think/gamble we can with either a capture or a regular move, even though the static eval is not yet enough to reach beta in the stand pat.

Don Dailey once mentioned in passing something about nullmove and quiescence search too so maybe I'm not the only one who has retried BCP's idea

Eelco

[diep]

hi Eelco,

Don't let yourself get fooled by engines that extend their mainline by a few plies and others which in reality search a minimum of 3 plies even if you set them at 1 ply or something and others like the original rybka which is diong a n ply search meanwhile showing n-3 at its display as iteration depth.

Note that diep is doing giving checks in qsearch at *every* ply of the qsearch up to 32 plies deep or so. I explicitly put the word 'giving' to it as we otherwise get yet another discussion where 'doing checks' to most means 'check evasions' and for others it means as well 'giving check'.

It is very difficult to limit it.

I do that by using a bunch of chessknowledge rules. For fast beancounters that would already slow down too much in nps to apply those rules as i conveniently make also use of the fact that Diep has incremental attacktables.

The combination of those rules really limit it - yet if i would remove the evaluation function you cannot search more than 1.5 million nps single core with this at a modern core, which is duck slow ofcourse from beancounter viewpoint, as it doesn't even include evaluation yet.

Rebel has much simpler attacktables than Diep, which we can explain. What Ed has been designing all works great at 8 bits CPU's as well and what i designed only works well at 32 bits CPU's and up and even in the days that i designed the 32 bits datastructure of Diep, 8 bits code was fantastic faster than 32 bits code. Just like 32 bits code executes a lot faster nowadays than 64 bits code.

So i assume this is why Ed gets a high nps in combination with lazy eval and can get away with doing several checks.

There is however a big price to pay for doing checks in qsearch in terms of overhead. For example you have 2 options.

Either you forward prune iin a hard manner (be it futility or razoring or whatever you show up with) last few plies, OR you also stores the qsearch positions into the transpositiontable. Without 1 of those 2, doing lots of giving check moves in qsearch is total impossible.

In general spoken, if you have simple evaluation function that's not more extensive than ivanhoe/rybka/houdini (not to mention glaurung), i would not consider doing what i do in Diep as what Diep is doing is gonna explode if you do not have incremental attacktables.

And those are simply too expensive if you want 3+ million nps a core.