Null Move

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
smcracraft
Posts: 671
Joined: Wed Mar 08, 2006 7:08 pm
Location: Orange County California
Full name: Stuart Cracraft
Contact:

Null Move

Post by smcracraft » Fri Nov 23, 2007 2:11 am

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

User avatar
Bill Rogers
Posts: 3562
Joined: Thu Mar 09, 2006 2:54 am
Location: San Jose, California

Re: Null Move

Post by Bill Rogers » Fri Nov 23, 2007 3:33 am

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
Posts: 8593
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Null Move

Post by Uri Blass » Fri Nov 23, 2007 7:01 am

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

bob
Posts: 20562
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Null Move

Post by bob » Fri Nov 23, 2007 4:58 pm

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.

Uri Blass
Posts: 8593
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Null Move

Post by Uri Blass » Fri Nov 23, 2007 6:44 pm

<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

User avatar
pedrox
Posts: 992
Joined: Fri Mar 10, 2006 5:07 am
Location: Basque Country (Spain)
Contact:

Re: Null Move

Post by pedrox » Fri Nov 23, 2007 7:22 pm

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
Posts: 3041
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Null Move

Post by Michael Sherwin » Fri Nov 23, 2007 9:06 pm

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.
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

smcracraft
Posts: 671
Joined: Wed Mar 08, 2006 7:08 pm
Location: Orange County California
Full name: Stuart Cracraft
Contact:

Re: Null Move

Post by smcracraft » Sat Nov 24, 2007 3:00 am

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;

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: Null Move

Post by Zach Wegner » Sat Nov 24, 2007 4:29 am

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.

Vempele

Re: Null Move

Post by Vempele » Sat Nov 24, 2007 7:41 am

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

Post Reply