Null Move

[smcracraft]

My null move is only giving me about 1/2 extra ply
in the non-quiescence search and about the same
for the quiescence search as compared to not using it
across a moderately long test suite on 5 second
per position tests.

What should be expected for null move in terms
of ply improvement?

I had heard one ply... but I only get half that.

--Stuart

[Bill Rogers]

You got what is expected. It allows you to see what you might gain if you moved twice and nothing more. one halp ply that is all.
Bill

[Uri Blass]

My null move is only giving me about 1/2 extra ply
in the non-quiescence search and about the same
for the quiescence search as compared to not using it
across a moderately long test suite on 5 second
per position tests.

What should be expected for null move in terms
of ply improvement?

I had heard one ply... but I only get half that.

--Stuart

My experience was that you get more than one ply by null mve pruning in 5 seconds search.
I do not have non q-search and I never tried it

Here is analysis by Toga in the opening position(second analysis is without null move pruning)

You can see that toga earns more than one ply by null move pruning in the opening position.

nbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

Analysis by Toga II 1.3 Beta1:

1.Nb1-a3
= (0.06) Depth: 1/1 00:00:00
1.Nb1-c3
² (0.34) Depth: 1/1 00:00:00
1.d2-d4
² (0.40) Depth: 1/1 00:00:00
1.d2-d4 d7-d5
= (0.20) Depth: 2/2 00:00:00
1.d2-d4 d7-d5 2.Ng1-f3
² (0.34) Depth: 3/8 00:00:00
1.d2-d4 d7-d5 2.Ng1-f3 Ng8-f6
= (0.20) Depth: 4/8 00:00:00
1.d2-d4 d7-d5 2.Ng1-f3 Ng8-f6 3.Nb1-c3
² (0.30) Depth: 5/12 00:00:00
1.d2-d4 d7-d5 2.Ng1-f3 Ng8-f6 3.Nb1-c3 Nb8-c6
= (0.20) Depth: 6/12 00:00:00 9kN
1.d2-d4 d7-d5 2.Ng1-f3 Ng8-f6 3.Nb1-c3 Nb8-c6 4.Bc1-f4
= (0.20) Depth: 7/14 00:00:00 27kN
1.d2-d4 d7-d5 2.Ng1-f3 Ng8-f6 3.Nb1-c3 Nb8-c6 4.Bc1-f4 Bc8-f5
= (0.20) Depth: 8/16 00:00:00 58kN
1.d2-d4 Ng8-f6 2.Ng1-f3 d7-d5 3.c2-c4 Bc8-f5 4.c4xd5 Nf6xd5 5.Qd1-b3 b7-b6
= (0.15) Depth: 9/22 00:00:01 165kN
1.d2-d4 Ng8-f6 2.Ng1-f3 d7-d5 3.c2-c4 d5xc4 4.Nb1-c3 Bc8-f5 5.e2-e3 Nb8-c6 6.Bf1xc4
² (0.27) Depth: 10/24 00:00:01 322kN
1.d2-d4 Ng8-f6 2.Ng1-f3 e7-e6 3.Nb1-c3 Bf8-b4 4.e2-e3 Nb8-c6 5.Bf1-d3 0-0 6.0-0
= (0.21) Depth: 11/24 00:00:01 656kN
1.d2-d4 Ng8-f6 2.Ng1-f3 d7-d5 3.c2-c4 e7-e6 4.Nb1-c3 Bf8-b4 5.Qd1-b3 Nb8-c6 6.c4xd5 Nf6xd5 7.e2-e4
= (0.16) Depth: 12/26 00:00:02 1380kN
1.e2-e4 Ng8-f6 2.e4-e5 Nf6-d5 3.d2-d4 Nb8-c6 4.Ng1-f3 d7-d6 5.Bf1-b5 a7-a6 6.Bb5xc6+ b7xc6 7.0-0 Bc8-f5
= (0.22) Depth: 12/30 00:00:03 2798kN
1.e2-e4 Ng8-f6 2.e4-e5 Nf6-d5 3.d2-d4 Nb8-c6 4.Ng1-f3 d7-d6 5.Bf1-c4 e7-e6 6.Bc1-g5 f7-f6 7.Bc4xd5 e6xd5
² (0.27) Depth: 13/33 00:00:06 4933kN

(, 23.11.2007)

,a - Glaurung Lodz 2007, Friend mode
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

Analysis by Toga II 1.3 Beta1:

1.Nb1-a3
= (0.06) Depth: 1/1 00:00:00
1.Nb1-c3
² (0.34) Depth: 1/1 00:00:00
1.d2-d4
² (0.40) Depth: 1/1 00:00:00
1.d2-d4 d7-d5
= (0.20) Depth: 2/2 00:00:00
1.d2-d4 d7-d5 2.Ng1-f3
² (0.34) Depth: 3/8 00:00:00
1.d2-d4 d7-d5 2.Ng1-f3 Ng8-f6
= (0.20) Depth: 4/8 00:00:00
1.d2-d4 d7-d5 2.Ng1-f3 Ng8-f6 3.Nb1-c3
² (0.30) Depth: 5/12 00:00:00
1.d2-d4 d7-d5 2.Ng1-f3 Ng8-f6 3.Nb1-c3 Nb8-c6
= (0.20) Depth: 6/12 00:00:00 17kN
1.d2-d4 d7-d5 2.Ng1-f3 Ng8-f6 3.Nb1-c3 Nb8-c6 4.Bc1-f4
= (0.20) Depth: 7/15 00:00:00 53kN
1.d2-d4 d7-d5 2.Ng1-f3 Ng8-f6 3.Nb1-c3 Nb8-c6 4.Bc1-f4 Bc8-f5
= (0.20) Depth: 8/16 00:00:00 108kN
1.d2-d4 d7-d5 2.Nb1-c3 Ng8-f6 3.Bc1-f4 Nf6-h5 4.Bf4-e5 Nb8-c6 5.Ng1-f3 Nc6xe5 6.Nf3xe5
= (0.16) Depth: 9/22 00:00:01 299kN
1.d2-d4 Ng8-f6 2.Nb1-c3 e7-e6 3.Ng1-f3 Nb8-c6 4.Bc1-f4 Bf8-b4 5.a2-a3 Bb4xc3+ 6.b2xc3 0-0
= (0.20) Depth: 10/24 00:00:01 1012kN
1.d2-d4 Ng8-f6 2.Ng1-f3 e7-e6 3.Nb1-c3 Nb8-c6 4.e2-e4 Bf8-b4 5.Bf1-d3 0-0 6.0-0
² (0.27) Depth: 11/26 00:00:04 3133kN
1.d2-d4 Ng8-f6 2.Ng1-f3 e7-e6 3.Nb1-c3 d7-d5 4.e2-e3 Nb8-c6 5.Bf1-d3 Bf8-d6 6.0-0 0-0
= (0.20) Depth: 12/29 00:00:13 8473kN

(, 23.11.2007)


Uri

[bob]

You got what is expected. It allows you to see what you might gain if you moved twice and nothing more. one halp ply that is all.
Bill

no no no no no... you need to try this before answering. Here is a position searched to depth=12 with null move on and off:

in fact, I can't even get it to search to depth=12 with null=off. It is _way_ more than "a half ply".

here's a paultry 8 ply search:

with null move:

depth time score variation (1)
1 0.00 -0.04 1. ... Kh8
1-> 0.00 -0.04 1. ... Kh8
2 0.00 0.02 1. ... Kh8 2. Bd4
2 0.00 -0.04 1. ... e5 2. Bc3
2-> 0.00 -0.04 1. ... e5 2. Bc3
3 0.00 0.02 1. ... e5 2. Bc3 Kh8
3-> 0.00 0.02 1. ... e5 2. Bc3 Kh8
4 0.00 -0.03 1. ... e5 2. Bc3 Kh8 3. Nb2
4-> 0.00 -0.03 1. ... e5 2. Bc3 Kh8 3. Nb2
5 0.00 0.03 1. ... e5 2. Bc3 Kh8 3. Rac1 Rfe8
5 0.01 -0.04 1. ... Rfd8 2. Bd4 e5 3. Bc3
5-> 0.01 -0.04 1. ... Rfd8 2. Bd4 e5 3. Bc3
6 0.02 -0.03 1. ... Rfd8 2. Bd4 e5 3. Bc3 Kh8 4.
Nb2
6 0.04 -0.05 1. ... Ne5 2. Nxe5 dxe5 3. Qe3 Nd7
6-> 0.04 -0.05 1. ... Ne5 2. Nxe5 dxe5 3. Qe3 Nd7
7 0.06 -0.20 1. ... Ne5 2. Nxe5 dxe5 3. Rd2 Rfd8
4. Rad1 Qd6
7-> 0.07 -0.20 1. ... Ne5 2. Nxe5 dxe5 3. Rd2 Rfd8
4. Rad1 Qd6
8 0.11 -0.21 1. ... Ne5 2. Nxe5 dxe5 3. Rd2 Rfd8
4. Rad1 Qd6 5. Bc2
8 0.15 -1 1. ... Bxe4!!
8 0.17 -0.64 1. ... Bxe4 2. Bxe4 Qxc4 3. Qxc4 Rxc4
4. Nxb6 Rxe4 5. Nxd7 Nxd7
8-> 0.17 -0.64 1. ... Bxe4 2. Bxe4 Qxc4 3. Qxc4 Rxc4
4. Nxb6 Rxe4 5. Nxd7 Nxd7
time=0.17 mat=0 n=232818 fh=93% nps=1.4M
ext-> check=750 1rep=16 mate=0 pp=0 reduce=74K/11K
predicted=0 evals=206K 50move=0 EGTBprobes=0 hits=0
SMP-> splits=0 aborts=0 data=0/128 elap=0.17

and then without:

depth time score variation (1)
1 0.00 -0.04 1. ... Kh8
1-> 0.00 -0.04 1. ... Kh8
2 0.00 0.02 1. ... Kh8 2. Bd4
2 0.01 -0.04 1. ... e5 2. Bc3
2-> 0.01 -0.04 1. ... e5 2. Bc3
3 0.01 0.02 1. ... e5 2. Bc3 Kh8
3-> 0.01 0.02 1. ... e5 2. Bc3 Kh8
4 0.01 -0.03 1. ... e5 2. Bc3 Kh8 3. Nb2
4-> 0.04 -0.03 1. ... e5 2. Bc3 Kh8 3. Nb2
5 0.07 -0.02 1. ... e5 2. Bc3 Kh8 3. Ra2 Rfe8
5 0.17 -0.05 1. ... Nh5 2. Qe3 Bf6 3. Bd4
5-> 0.18 -0.05 1. ... Nh5 2. Qe3 Bf6 3. Bd4
6 0.29 -0.05 1. ... Nh5 2. Qe3 e5 3. Nc3 Nf4 4.
Nd5 Bxd5 5. cxd5 Nxd3 6. Qxd3
6-> 0.87 -0.05 1. ... Nh5 2. Qe3 e5 3. Nc3 Nf4 4.
Nd5 Bxd5 5. cxd5 Nxd3 6. Qxd3
7 1.63 -0.13 1. ... Nh5 2. Qe3 Bf6 3. Bc3 Nc5 4.
Bxf6 Nxf6 5. Nxc5 Qxc5
7-> 3.76 -0.13 1. ... Nh5 2. Qe3 Bf6 3. Bc3 Nc5 4.
Bxf6 Nxf6 5. Nxc5 Qxc5
8 6.56 -0.12 1. ... Nh5 2. Qe3 Bf6 3. Bd4 Bxd4 4.
Qxd4 Nf4 5. Nc3
8 11.51 -1 1. ... Bxe4!!
8 12.14 -0.64 1. ... Bxe4 2. Bxe4 Qxc4 3. Qxc4 Rxc4
4. Nxb6 Rxe4 5. Nxd7 Nxd7
8-> 18.79 -0.64 1. ... Bxe4 2. Bxe4 Qxc4 3. Qxc4 Rxc4
4. Nxb6 Rxe4 5. Nxd7 Nxd7
time=18.79 mat=0 n=29537909 fh=89% nps=1.6M
ext-> check=248K 1rep=17K mate=5K pp=0 reduce=16.6M/255K
predicted=0 evals=27.5M 50move=0 EGTBprobes=0 hits=0
SMP-> splits=0 aborts=0 data=0/128 elap=18.79


It is _way_ more than 1/2 ply...

for 10 seconds, with null gets 16 plies in a test position, without gets 8. You can test this by using "sel=0/0" as a command to turn null-move off in Crafty...

for a 10 second limit, with null=16 plies, without = 8.

[Uri Blass]

<snipped>

for 10 seconds, with null gets 16 plies in a test position, without gets 8. You can test this by using "sel=0/0" as a command to turn null-move off in Crafty...

for a 10 second limit, with null=16 plies, without = 8.

I agree that the difference is more than one ply but
16 plies against 8 plies seem to me too big difference.
I wonder if you use the same late move reductions in both versions.

Uri

[pedrox]

I believe that in blitz games, null move will give an average between 2 and 3 plys more deep, in ELO between 100 and 200 points.

The only program strong that I have heard that it does not use is Junior.

[Michael Sherwin]

<snipped>

for 10 seconds, with null gets 16 plies in a test position, without gets 8. You can test this by using "sel=0/0" as a command to turn null-move off in Crafty...

for a 10 second limit, with null=16 plies, without = 8.

I agree that the difference is more than one ply but
16 plies against 8 plies seem to me too big difference.
I wonder if you use the same late move reductions in both versions.

Uri

Bob just gave the results for one extreem example to show that there are positions that benifit hugely from the null move huristic. He was not indicating an average expectation.

[smcracraft]

To further the critique from this board, enclosed is the section in
the search that does the null move. Anything wrong with this basic
implementation, let me know...

Thanks -- Stuart

Code: Select all

search(...)
{
:
#define R 3
#define NULLMOVE
#ifdef NULLMOVE
    /* null move  */

    if (use_null_move) {
      if(
         pg->ply != 0 &&        /* Not first ply of search*/
         pg ->nmoves > 0 &&     /* Not first move of game */
         pg->game[pg->nmoves -1 ] != 0 && /* Previous move was not null */
         depth >= 2 &&          /* Depth remaining in search >= 2 */
         !INCHECK(pg,stm) &&    /* Side to move not in check */
         !(MATESCORE (alpha)) && /* Score is not a mate score */
         (pg->p[stm][knight] | pg->p[stm][bishop] |pg->p[stm][rook] | pg->p[stm][queen]) != NULLBITBOARD
         )                      /* At least one or more major and/or minor pieces left */
        {
          MakeNullMove(pg);
          score = -search(pg,  -beta,  -beta+1,  depth - R - 1, "");
          UnMakeNullMove(pg);
          if(score >= beta){
            return score;
          }
        }
    }
#endif
:
}

[Zach Wegner]

Code: Select all

         !(MATESCORE (alpha)) && /* Score is not a mate score */

Usually this condition is just checking if beta equals infinity, i.e. it is possible to fail high at all. Alpha does not have anything to do with it, and if you check for negative mate scores this will weed out some possible cutoffs (not sure how many). If it only tests for positive mate scores, then it probably won't matter: it's hard to mate an opponent by null moving.

[Vempele]

To further the critique from this board, enclosed is the section in
the search that does the null move. Anything wrong with this basic
implementation, let me know...

Thanks -- Stuart

If you use a hashtable, I see no reason not to store the result, with max(depth,R+1).