Page 1 of 5

Null Move

Posted: Fri Nov 23, 2007 2:11 am
by 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

Re: Null Move

Posted: Fri Nov 23, 2007 3:33 am
by 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

Re: Null Move

Posted: Fri Nov 23, 2007 7:01 am
by Uri Blass
smcracraft wrote: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

Re: Null Move

Posted: Fri Nov 23, 2007 4:58 pm
by bob
Bill Rogers wrote: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.

Re: Null Move

Posted: Fri Nov 23, 2007 6:44 pm
by Uri Blass
<snipped>
bob wrote:
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

Re: Null Move

Posted: Fri Nov 23, 2007 7:22 pm
by 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.

Re: Null Move

Posted: Fri Nov 23, 2007 9:06 pm
by Michael Sherwin
Uri Blass wrote:<snipped>
bob wrote:
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.

Re: Null Move

Posted: Sat Nov 24, 2007 3:00 am
by 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&#40;...)
&#123;
&#58;
#define R 3
#define NULLMOVE
#ifdef NULLMOVE
    /* null move  */

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

Re: Null Move

Posted: Sat Nov 24, 2007 4:29 am
by Zach Wegner
smcracraft wrote:

Code: Select all

         !&#40;MATESCORE &#40;alpha&#41;) && /* 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.

Re: Null Move

Posted: Sat Nov 24, 2007 7:41 am
by Vempele
smcracraft wrote: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).