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

Re: Null Move

Post by Tony » Sun Nov 25, 2007 5:18 pm

Uri Blass wrote:
Tony wrote:
Uri Blass wrote:
Tony wrote:
Zach Wegner wrote:
smcracraft wrote:

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.
In addition, a lot of people started doing this since it was used in Fruit, but only a few realize that Fruit did it wrong (or rather, the way it was implemented, it didn't do it).

There is no reason to do it either. Nullmove always helps move ordering.

Tony
I do not understand how null move can help move ordering when every move fail high.

Suppose that you search from the opening position
1.e4 Nf6 2.Qh5 Nxh5 3.null black move

of course you are going to find that black has a threat but every move is going to have a threat so the fact that you started from null is not going to help you to get better move ordering.

Uri
Did you test it ?

First test something and then try to understand it is the correct order.


Tony
I do not use null move pruning if the evaluation is above beta.
Unfortunately it is hard to test changes when the difference is small and in test positions I do not have consistent results(sometimes I need to search more nodes to get the same depth and sometimes I need to search less nodes espacially when there are other factors that are different because if the tree is different the order of pieces in the piece list is also different and the order of moves is different)

searching null move first may change the order of moves but I see no reason to assume that it is going to improve the order of moves.

When I rewrite movei I may change things and have order of pieces in the piece list that is not dependent on the tree that I searched so things may be different.

Uri
Yes, if you already limit nullmove it might be harder to test because of the possible different combinations.

I always nullmove, since it always gives me something. Killer moves, threaths, hash moves (iid) etc.

Tony

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

Re: Null Move

Post by Uri Blass » Sun Nov 25, 2007 7:02 pm

bob wrote:
Uri Blass wrote:
bob wrote:
Michael Sherwin wrote:
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.
wasn't extreme at all. Here's an opening position searched for 20 seconds:

If you have a favorite position for me to run, post it, or you can do it yourself using the "sel=0/0" command to turn null move off...

15 9.58 0.32 1. e4 e6 2. Nf3 Nc6 3. d4 Nf6 4. Bd3
Bb4+ 5. c3 Be7 6. O-O O-O 7. e5 Nd5
8. Qc2 f5
15-> 10.39 0.32 1. e4 e6 2. Nf3 Nc6 3. d4 Nf6 4. Bd3
Bb4+ 5. c3 Be7 6. O-O O-O 7. e5 Nd5
8. Qc2 f5
time=20.20 mat=0 n=32392436 fh=89% nps=1.6M

9 9.13 0.20 1. e4 Nc6 2. d4 Nf6 3. d5 Ne5 4. Nf3
d6 5. Nxe5 dxe5
9-> 11.59 0.20 1. e4 Nc6 2. d4 Nf6 3. d5 Ne5 4. Nf3
d6 5. Nxe5 dxe5
time=20.33 mat=0 n=27355629 fh=84% nps=1.3M


So 9 plies to 15 plies in the same time, from the initial opening position...
I suspect that something is wrong if you get only 9 plies without null move pruning when you use late move reductions(I assume that the 15 plies in the opening position are with late move reductions)

Maybe in your code you disable both null move pruning and late move reductions in the same time when you have sel=0/0.

Uri
No I don't. Null-move is a huge savings.

I'd suggest that you try it for yourself to see. I do null-move _everywhere_ in the search, as I do for reductions as well... disabling reductions requires something completely different in Crafty (setting reduction depth to zero).

9 plies in a few seconds seems perfectly reasonable to me...
9 plies in a few seconds without reductions is reasonable but 9 plies when you do late move reductions seem to be wrong to me.

I agree that null move give more than 1 ply.
2 plies or 3 plies in few seconds may make sense in the opening position but 6 plies difference seem to me too much unless for some reason you disable late move reductions together with null move pruning.

Uri

Alessandro Scotti

Re: Null Move

Post by Alessandro Scotti » Sun Nov 25, 2007 7:34 pm

Uri Blass wrote:I agree that null move give more than 1 ply.
2 plies or 3 plies in few seconds may make sense in the opening position but 6 plies difference seem to me too much unless for some reason you disable late move reductions together with null move pruning.
Indeed, null move gives Hamsters between 2 and 3 plies in the start position.

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

Re: Null Move

Post by Zach Wegner » Sun Nov 25, 2007 10:48 pm

Tony wrote:I always nullmove, since it always gives me something. Killer moves, threaths, hash moves (iid) etc.
Indeed. The _only_ condition I use right now is whether I am in check.

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

Re: Null Move

Post by bob » Sun Nov 25, 2007 11:45 pm

Alessandro Scotti wrote:
Uri Blass wrote:I agree that null move give more than 1 ply.
2 plies or 3 plies in few seconds may make sense in the opening position but 6 plies difference seem to me too much unless for some reason you disable late move reductions together with null move pruning.
Indeed, null move gives Hamsters between 2 and 3 plies in the start position.
feel free to test with crafty.

sel=0/0 disables null move and nothing else...

Apparently null-move + search reductions is a huge win... Much more so than just null-move by itself. But it is easy enough to test with Crafty for those so interested... sel=0/0 has absolutely no effect on search reductions. They are controlled by different commands and variables...

hristo

Re: Null Move

Post by hristo » Mon Nov 26, 2007 2:25 am

bob wrote:
Alessandro Scotti wrote:
Uri Blass wrote:I agree that null move give more than 1 ply.
2 plies or 3 plies in few seconds may make sense in the opening position but 6 plies difference seem to me too much unless for some reason you disable late move reductions together with null move pruning.
Indeed, null move gives Hamsters between 2 and 3 plies in the start position.
feel free to test with crafty.

sel=0/0 disables null move and nothing else...

Apparently null-move + search reductions is a huge win... Much more so than just null-move by itself. But it is easy enough to test with Crafty for those so interested... sel=0/0 has absolutely no effect on search reductions. They are controlled by different commands and variables...
It is possible that in your case the NULL-move is helping the LMR and when disabled (null-move) the LMR becomes counter productive, hence the large (6 ply!) difference.

What happens if you disable LMR for all cases and then try the NULL-move on/off test?
(this is not that important, though, since if you are using the LMR with NULL-move then thats all that matters and disjointed tests are probably meaningless.)

IME (in my experience) 'raw' NULL-move doesn't offer 6 ply advantage over a few seconds of run time, without factoring in other parts of the program (evaluation, search, etc.).

Regards,
Hristo

Tony

Re: Null Move

Post by Tony » Mon Nov 26, 2007 8:37 am

Zach Wegner wrote:
Tony wrote:I always nullmove, since it always gives me something. Killer moves, threaths, hash moves (iid) etc.
Indeed. The _only_ condition I use right now is whether I am in check.
Yes, you are right. I have 1 condition.

Tony

Tony

Re: Null Move

Post by Tony » Mon Nov 26, 2007 8:47 am

hristo wrote:
bob wrote:
Alessandro Scotti wrote:
Uri Blass wrote:I agree that null move give more than 1 ply.
2 plies or 3 plies in few seconds may make sense in the opening position but 6 plies difference seem to me too much unless for some reason you disable late move reductions together with null move pruning.
Indeed, null move gives Hamsters between 2 and 3 plies in the start position.
feel free to test with crafty.

sel=0/0 disables null move and nothing else...

Apparently null-move + search reductions is a huge win... Much more so than just null-move by itself. But it is easy enough to test with Crafty for those so interested... sel=0/0 has absolutely no effect on search reductions. They are controlled by different commands and variables...
It is possible that in your case the NULL-move is helping the LMR and when disabled (null-move) the LMR becomes counter productive, hence the large (6 ply!) difference.

What happens if you disable LMR for all cases and then try the NULL-move on/off test?
(this is not that important, though, since if you are using the LMR with NULL-move then thats all that matters and disjointed tests are probably meaningless.)

IME (in my experience) 'raw' NULL-move doesn't offer 6 ply advantage over a few seconds of run time, without factoring in other parts of the program (evaluation, search, etc.).

Regards,
Hristo
You might be right that they influence each other.

Late move reduction results in a super nullmove (or a super late move reduction). We reduce a move because it's crappy, then nullmove it because it doesn't threathen anything.

This makes the latemove more likely to succeed ( to see the move wasn't crappy, we have to search deeper, but because of nullmove it is hidden even longer) and late move reduction can do what it does best : Hide fail high moves. ( and save a lot of nodes because move ordering is so "good")

Tony

Rob

Re: Null Move

Post by Rob » Mon Nov 26, 2007 6:15 pm

bob wrote:
Michael Sherwin wrote:
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.
wasn't extreme at all. Here's an opening position searched for 20 seconds:

If you have a favorite position for me to run, post it, or you can do it yourself using the "sel=0/0" command to turn null move off...

15 9.58 0.32 1. e4 e6 2. Nf3 Nc6 3. d4 Nf6 4. Bd3
Bb4+ 5. c3 Be7 6. O-O O-O 7. e5 Nd5
8. Qc2 f5
15-> 10.39 0.32 1. e4 e6 2. Nf3 Nc6 3. d4 Nf6 4. Bd3
Bb4+ 5. c3 Be7 6. O-O O-O 7. e5 Nd5
8. Qc2 f5
time=20.20 mat=0 n=32392436 fh=89% nps=1.6M

9 9.13 0.20 1. e4 Nc6 2. d4 Nf6 3. d5 Ne5 4. Nf3
d6 5. Nxe5 dxe5
9-> 11.59 0.20 1. e4 Nc6 2. d4 Nf6 3. d5 Ne5 4. Nf3
d6 5. Nxe5 dxe5
time=20.33 mat=0 n=27355629 fh=84% nps=1.3M


So 9 plies to 15 plies in the same time, from the initial opening position...
I get a different result.
Crafty 21.6

On slow computer without null move:

11 18.71 0.23 1. e4 Nc6 2. Nc3 Nf6 3. Nf3 e6 4. d4
d5 5. Qd3 Bb4 6. e5
11-> 33.96 0.23 1. e4 Nc6 2. Nc3 Nf6 3. Nf3 e6 4. d4
d5 5. Qd3 Bb4 6. e5
12 48.56 0.20 1. e4 Nc6 2. Nc3 Nf6 3. Nf3 e6 4. d4
Bb4 5. Qd3 d5 6. e5 Ne4 <HT>
12-> 1:26 0.20 1. e4 Nc6 2. Nc3 Nf6 3. Nf3 e6 4. d4
Bb4 5. Qd3 d5 6. e5 Ne4 <HT>
13 4:01 0.23 1. e4 e6 2. Nf3 Nc6 3. Nc3 d5 4. exd5
exd5 5. Bb5 Qe7+ <HT>
time=5:00 mat=0 n=31563160 fh=94% nps=104K
ext-> check=718K 1rep=44K mate=0 pp=0 reduce=22.0M/2.2M
predicted=0 evals=24.4M 50move=0 EGTBprobes=0 hits=0
hashing-> 25%(raw) 24%(draftOK) 99%(saturation)
hashing-> 0%(exact) 21%(lower) 0%(upper)
SMP-> splits=0 aborts=0 data=0/256 elap=5:00

With nullmove:

13-> 53.32 0.37 1. e4 e5 2. Nc3 Nc6 3. Nf3 Nf6 4. d4
exd4 5. Nxd4 Bb4 6. Nxc6 <HT>
14 1:23 0.31 1. e4 e5 2. Nc3 Nc6 3. Nf3 Bb4 4. Bc4
Nf6 5. O-O d6 6. d3 O-O 7. Be3 Be6
8. Bxe6 fxe6
14-> 1:37 0.31 1. e4 e5 2. Nc3 Nc6 3. Nf3 Bb4 4. Bc4
Nf6 5. O-O d6 6. d3 O-O 7. Be3 Be6
8. Bxe6 fxe6
time=5:00 mat=0 n=35164765 fh=90% nps=117K
ext-> check=1.5M 1rep=96K mate=530 pp=0 reduce=20.8M/2.3M
predicted=0 evals=28.2M 50move=0 EGTBprobes=0 hits=0
hashing-> 21%(raw) 20%(draftOK) 99%(saturation)
hashing-> 0%(exact) 15%(lower) 0%(upper)
SMP-> splits=0 aborts=0 data=0/256 elap=5:00


So it's only a two ply difference, 12 vs 14.

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

Re: Null Move

Post by bob » Mon Nov 26, 2007 7:00 pm

Here's the tests... run at 20 seconds per position.

three positions, null-move off, LMR off. Four lines per position, first is with both LMR and null disabled. Second is null on, LMR off. Third is Null off, LMR on, fourth is both on. The PV given represents the max depth for 20 seconds on my laptop. I repeated it for three positions, the first is kopec22, the second is the starting position, the third is for a quiet middlegame position...

Kopec22:

6 5.40 -0.05 1. ... Nh5 2. Qe3 e5 3. Nc3 Nf4 4.
Nd5 Bxd5 5. cxd5 Nxd3 6. Qxd3
13-> 17.22 -0.45 1. ... Bxe4 2. Bxe4 Qxc4 3. Qxc4 Rxc4
4. Nxb6 Rxe4 5. Nxd7 Nxd7 6. Rac1 Re2
7. Rd2 Rxd2 8. Nxd2
8-> 18.44 -0.64 1. ... Bxe4 2. Bxe4 Qxc4 3. Qxc4 Rxc4
4. Nxb6 Rxe4 5. Nxd7 Nxd7
17 18.10 -0.61 1. ... Bxe4 2. Bxe4 Qxc4 3. Qxc4 Rxc4
4. Nxb6 Rxe4 5. Nxd7 Nxd7 6. Rac1 Re2
7. Bd4 Rd8 8. Rc7 d5 9. Kf1 Bd6 10.
Kxe2 Bxc7

Opening initial position:

7 3.91 0.23 1. Nf3 Nc6 2. d4 d5 3. Bf4 Nf6 4. Nbd2
12-> 11.88 0.32 1. e4 e6 2. Nf3 Nf6 3. e5 Nd5 4. Nc3
Bb4 5. a3 Bxc3 6. dxc3 O-O
9-> 11.41 0.20 1. e4 Nc6 2. d4 Nf6 3. d5 Ne5 4. Nf3
d6 5. Nxe5 dxe5
15-> 10.12 0.32 1. e4 e6 2. Nf3 Nc6 3. d4 Nf6 4. Bd3
Bb4+ 5. c3 Be7 6. O-O O-O 7. e5 Nd5
8. Qc2 f5

quiet middlegame position:

6 5.20 -0.21 1. ... Bf5 2. Rf2 O-O 3. Rd2 Re8 4.
Rad1
12-> 9.23 -0.22 1. ... Bf5 2. Qd2 O-O 3. Ne2 Bh4 4.
Bf2 Re8 5. Bxh4 Qxh4 6. Nd4 Be4 7.
Qe3
8-> 8.71 -0.23 1. ... Bf5 2. Rf2 O-O 3. Rd2 Re8 4.
Rad1 Qd7 5. a5
15-> 14.96 -0.24 1. ... Bf5 2. Qd2 Qa5 3. Qf2 O-O 4.
h3 Qb4 5. g4 d4 6. Bxd4 Bxc2 7. Qxc2
Qxd4+ 8. Qf2 Qd3 9. Kh2

Now, as the old saying goes, "it is what it is..." Null-move is a huge win. I am using adaptive null-move R=3~2 (3 at early plies, 2 all the way out to the tips)...

Again, I will be happy to test any particular position you want. Here's the proper way to disable null-move:

sel=0/0

Note that sel=0 will _not_ do the trick. The 0/0 is critical.

To disable LMR,

reduce/val=0

and it is turned off.

Do both commands and both are turned off...

Post Reply