Null Move

[Roman Hartmann]

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.

I thought only Rebel (ProDeo) wouly usually rely on something else than null move although null move can be enabled. Someone posted some zugzwang positions in the old CCC forum and one of the engines having problems with some of the positions was junior. Usually those kind of problems are related to null move.

Roman

[Tony]

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

[Uri Blass]

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

[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

I ran the _same_ program, with sel=0/0 to disable null move. Nothing else was changed, hash size or anything, and no parallel search either.

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

[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

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 */[/quote]

Why that restriction???  That really hurts null-move search efficiency.  I don't use that at all...

[quote]
         !INCHECK(pg,stm) &&    /* Side to move not in check */
         !(MATESCORE (alpha)) && /* Score is not a mate score */


[/quote]

Don't use that either in my code,..

[quote]
         (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
:
}

[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

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

[Tony]

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

[Uri Blass]

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

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