Null Move

[bob]

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

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.

You got a different result because you didn't do it correctly, is my guess.

Can you post the log file? I would almost guess you used sel=0 which does _not_ disable null-move completely, it only disables it in part of the tree...

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

That is _not_ a slow computer if that is correct. Here is a run on my core-2 laptop which is about as fast as they come today:

9-> 11.24 0.20 1. e4 Nc6 2. d4 Nf6 3. d5 Ne5 4. Nf3
d6 5. Nxe5 dxe5

There is no way your "slow computer" can get 2 plies deeper than my core-2 unless you made some sort of mistake... so now it becomes an issue of trying to figure out what you did that I didn't do...

[bob]

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

There is a _TON_ of paranoia about hashing. I've never quite seen the likes of it either... You can find posted here from time to time:

(1) don't store mate scores in the hash;

(2) don't store draw scores in the hash;

(3) don't store null-move scores in the hash;

(4) don't store reduced-depth scores in the hash;

If you trust the original result, and you are hashing properly, then why not trust the scores when hashing them as well? Beyond me... yes draw scores are a problem, but they are a problem if you don't store them as well...

[Rob]

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

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.

You got a different result because you didn't do it correctly, is my guess.

Can you post the log file? I would almost guess you used sel=0 which does _not_ disable null-move completely, it only disables it in part of the tree...

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

That is _not_ a slow computer if that is correct. Here is a run on my core-2 laptop which is about as fast as they come today:

9-> 11.24 0.20 1. e4 Nc6 2. d4 Nf6 3. d5 Ne5 4. Nf3
d6 5. Nxe5 dxe5

There is no way your "slow computer" can get 2 plies deeper than my core-2 unless you made some sort of mistake... so now it becomes an issue of trying to figure out what you did that I didn't do...

It's a VIA C3 700MHz, I use it because it requires only passive cooling.

I got the executable from P. Skinner's site, the blended build.
http://www.webkikr.net/files/crafty21-6xp3.zip

Here's the logfile:


noise level set to 0.
pondering disabled.

Crafty v21.6 (1 cpus)

White(1): sel=0/0
null move disabled.
White(1): st 300
search time set to 300.00.
White(1): go
time surplus 0.00 time limit 5:00 (+0.00) (5:00)
depth time score variation (1)
1 0.00 0.36 1. Nf3
1-> 0.01 0.36 1. Nf3
2 0.01 0.05 1. Nf3 Nc6
2-> 0.02 0.05 1. Nf3 Nc6
3 0.02 0.36 1. Nf3 Nc6 2. Nc3
3-> 0.04 0.36 1. Nf3 Nc6 2. Nc3
4 0.04 0.05 1. Nf3 Nc6 2. Nc3 Nf6
4-> 0.06 0.05 1. Nf3 Nc6 2. Nc3 Nf6
5 0.09 0.29 1. Nf3 Nc6 2. Nc3 Nf6 3. e4
5-> 0.12 0.29 1. Nf3 Nc6 2. Nc3 Nf6 3. e4
6 0.15 0.05 1. Nf3 Nc6 2. Nc3 Nf6 3. e4 e5
6 0.21 0.11 1. e4 Nc6 2. Nc3 Nf6 3. d4 e5
6-> 0.34 0.11 1. e4 Nc6 2. Nc3 Nf6 3. d4 e5
7 0.45 0.17 1. e4 Nc6 2. Nc3 Nf6 3. Nf3 d5 4. Qe2
Nxe4 5. Nxe4 dxe4 6. Qxe4
7 0.69 0.20 1. d4 Nf6 2. Nc3 d5 3. Nf3 Nc6 4. Bf4
7-> 0.88 0.20 1. d4 Nf6 2. Nc3 d5 3. Nf3 Nc6 4. Bf4
8 1.18 0.07 1. d4 Nf6 2. Nc3 d5 3. Bf4 Nbd7 4.
Nb5 c5
8 1.74 0.15 1. e4 Nc6 2. Nc3 Nf6 3. Nf3 d5 4. e5
Ne4 5. Nxe4 dxe4
8-> 2.24 0.15 1. e4 Nc6 2. Nc3 Nf6 3. Nf3 d5 4. e5
Ne4 5. Nxe4 dxe4
9 3.00 0.15 1. e4 Nc6 2. Nc3 Nf6 3. Nf3 d5 4. e5
Ne4 5. Nxe4 dxe4
9-> 9.02 0.15 1. e4 Nc6 2. Nc3 Nf6 3. Nf3 d5 4. e5
Ne4 5. Nxe4 dxe4
10 10.07 0.15 1. e4 Nc6 2. Nc3 Nf6 3. Nf3 d5 4. e5
Ne4 5. Nxe4 dxe4
10-> 13.05 0.15 1. e4 Nc6 2. Nc3 Nf6 3. Nf3 d5 4. e5
Ne4 5. Nxe4 dxe4
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

White(1): e4
time used: 5:00

[bob]

OK, I found the problem and it was mine, not yours. I have rewritten the search code to clean it up, since it is not changing much and I wanted to get search.c, searchmp.c and searchr.c to look as much alike as possible. When doing so, I made the decision that I would not allow anyone to turn off null-move completely as it is really pointless to do so.

The effect was that null=0/0 still did null-move searches, but with a reduction factor of zero, which had a huge cost and very little benefit. It just made the trees impossibly large. your values look reasonable and the 1-2 plies is what I would expect with the default null-move setting.

So sorry for the confusion, I simply forgot that the current version was different. When I ran the test on 21.6 rather than 21.7, I got exactly what you got, just faster due to the hardware...

[hristo]

OK, I found the problem and it was mine, not yours. I have rewritten the search code to clean it up, since it is not changing much and I wanted to get search.c, searchmp.c and searchr.c to look as much alike as possible. When doing so, I made the decision that I would not allow anyone to turn off null-move completely as it is really pointless to do so.

The effect was that null=0/0 still did null-move searches, but with a reduction factor of zero, which had a huge cost and very little benefit. It just made the trees impossibly large. your values look reasonable and the 1-2 plies is what I would expect with the default null-move setting.

So sorry for the confusion, I simply forgot that the current version was different. When I ran the test on 21.6 rather than 21.7, I got exactly what you got, just faster due to the hardware...

Does this close the issue about getting 6-8 plys with null-move 'on' compared to null-move 'off'?
I'm just trying to be clear on the subject -- you gain 2-3 plys and not 6-8, when using null-move?

When using null-move +1 ply is great, +2 is excellent, +3 is fantastic, +4 is miraculous, +5 makes ones eyes go in opposite directions, and +6 means you have gotten gawd by the gonads and made him scream 'uncle'.
(I hope you are not torturing the old guy, too much, with this 'uncle' stuff)

Regards,
Hristo

p.s.
I just tried compiling crafty 21.6 and got nothing but errors

Code: Select all

 make darwin
make target=FreeBSD \
		CC=gcc CXX=g++ \
		CFLAGS=' -Wall -pipe -O3' \
		CXFLAGS= \
		LDFLAGS= \
		LIBS='-lstdc++' \
		opt='' \
		crafty-make
gcc -Wall -pipe -O3  -DFreeBSD -c crafty.c
In file included from searchr.c:4,
                 from crafty.c:1:
chess.h:30:17: warning: missing whitespace after the macro name
In file included from chess.h:129,
                 from searchr.c:4,
                 from crafty.c:1:
lock.h:1:6: error: token "=" is not valid in preprocessor expressions
In file included from searchr.c:4,
                 from crafty.c:1:
chess.h:392: error: syntax error before ‘=’ token
chess.h:392: warning: no semicolon at end of struct or union
chess.h:402: error: syntax error before ‘}’ token
chess.h:428: error: syntax error before ‘=’ token
chess.h:428: warning: no semicolon at end of struct or union
chess.h:429: error: syntax error before ‘=’ token
chess.h:475: error: syntax error before ‘}’ token
chess.h:475: warning: type defaults to ‘int’ in declaration of ‘SHARED’
chess.h:475: warning: data definition has no type or storage class
In file included from searchr.c:5,
                 from crafty.c:1:
data.h:3: error: syntax error before ‘*’ token
.........

[bob]

OK, I found the problem and it was mine, not yours. I have rewritten the search code to clean it up, since it is not changing much and I wanted to get search.c, searchmp.c and searchr.c to look as much alike as possible. When doing so, I made the decision that I would not allow anyone to turn off null-move completely as it is really pointless to do so.

The effect was that null=0/0 still did null-move searches, but with a reduction factor of zero, which had a huge cost and very little benefit. It just made the trees impossibly large. your values look reasonable and the 1-2 plies is what I would expect with the default null-move setting.

So sorry for the confusion, I simply forgot that the current version was different. When I ran the test on 21.6 rather than 21.7, I got exactly what you got, just faster due to the hardware...

Does this close the issue about getting 6-8 plys with null-move 'on' compared to null-move 'off'?
I'm just trying to be clear on the subject -- you gain 2-3 plys and not 6-8, when using null-move?

Yes it does. The problem was that my non-null-move search had a _HUGE_ overhead because the null-move was being searched to a normal (non-reduced) depth... So that deflated the normal search depth without null move dramatically...

I had just forgotten about the recent clean-up changes since this version is not yet out, and it was a huge boo-boo...

When using null-move +1 ply is great, +2 is excellent, +3 is fantastic, +4 is miraculous, +5 makes ones eyes go in opposite directions, and +6 means you have gotten gawd by the gonads and made him scream 'uncle'.
(I hope you are not torturing the old guy, too much, with this 'uncle' stuff)

Regards,
Hristo

p.s.
I just tried compiling crafty 21.6 and got nothing but errors

Code: Select all

 make darwin
make target=FreeBSD \
		CC=gcc CXX=g++ \
		CFLAGS=' -Wall -pipe -O3' \
		CXFLAGS= \
		LDFLAGS= \
		LIBS='-lstdc++' \
		opt='' \
		crafty-make
gcc -Wall -pipe -O3  -DFreeBSD -c crafty.c
In file included from searchr.c:4,
                 from crafty.c:1:
chess.h:30:17: warning: missing whitespace after the macro name
In file included from chess.h:129,
                 from searchr.c:4,
                 from crafty.c:1:
lock.h:1:6: error: token "=" is not valid in preprocessor expressions
In file included from searchr.c:4,
                 from crafty.c:1:
chess.h:392: error: syntax error before ‘=’ token
chess.h:392: warning: no semicolon at end of struct or union
chess.h:402: error: syntax error before ‘}’ token
chess.h:428: error: syntax error before ‘=’ token
chess.h:428: warning: no semicolon at end of struct or union
chess.h:429: error: syntax error before ‘=’ token
chess.h:475: error: syntax error before ‘}’ token
chess.h:475: warning: type defaults to ‘int’ in declaration of ‘SHARED’
chess.h:475: warning: data definition has no type or storage class
In file included from searchr.c:5,
                 from crafty.c:1:
data.h:3: error: syntax error before ‘*’ token
.........

Not sure what would cause that. First thought is to just try "make linux" instead, as that makes cleanly on my linux boxes...

Bob

[hristo]

OK, I found the problem and it was mine, not yours. I have rewritten the search code to clean it up, since it is not changing much and I wanted to get search.c, searchmp.c and searchr.c to look as much alike as possible. When doing so, I made the decision that I would not allow anyone to turn off null-move completely as it is really pointless to do so.

The effect was that null=0/0 still did null-move searches, but with a reduction factor of zero, which had a huge cost and very little benefit. It just made the trees impossibly large. your values look reasonable and the 1-2 plies is what I would expect with the default null-move setting.

So sorry for the confusion, I simply forgot that the current version was different. When I ran the test on 21.6 rather than 21.7, I got exactly what you got, just faster due to the hardware...

Does this close the issue about getting 6-8 plys with null-move 'on' compared to null-move 'off'?
I'm just trying to be clear on the subject -- you gain 2-3 plys and not 6-8, when using null-move?

Yes it does. The problem was that my non-null-move search had a _HUGE_ overhead because the null-move was being searched to a normal (non-reduced) depth... So that deflated the normal search depth without null move dramatically...

I had just forgotten about the recent clean-up changes since this version is not yet out, and it was a huge boo-boo...

I know the feeling!
BTW,
what is going on with the Darwin target in 21.6? It seems slightly busted to me.

I looked at the Makefile and saw "Alpha" targets (??) -- does anyone still use those things?

Cheers,
Hristo

[hristo]

Not sure what would cause that. First thought is to just try "make linux" instead, as that makes cleanly on my linux boxes...

Bob

"make linux" compiled ... damn linux is better than FreeBSD. (your Makefile proves it)
However when running the application

Code: Select all

hristo$ ./crafty 
unable to open book file [./book.bin].
book is disabled
unable to open book file [./books.bin].
ERROR.  shmget() failed, unable to allocate a shared memory segment.
        Please verify that your /proc/sys/kernel/shmmax value is
        large enough to allow allocating the amount of memory you
        are requesting.  "echo 1000000000 > /proc/sys/kernel/shmmax"
        will allow a segment up to one billion bytes.

Cheers,
Hristo

[Dann Corbit]

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

Do you check to see if you just executed a null move? (Double null move)

[Zach Wegner]

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

Do you check to see if you just executed a null move? (Double null move)

I don't. I removed that condition too, because it didn't really matter. So now I allow triple, quadruple, etc. nullmoves. One less parameter to my search function...