Null-move pruning and the hash table

[bob]

Ok, The jury is back, and the verdict is "don't do this." It is only worth about 2-3 Elo to not do back-to-back nulls, and the reason seems to be efficiency. After the cluster test showed the idea to be slightly worse, I ran some test positions with some additional statistics gathered. A null after a null does not fail high very often. And when it doesn't, it is a total waste of time. If you disallow a null right after a null, you gain just a bit of zugzwang protection, but you lose a little more in efficiency due to the extra null-move searches that fail low and don't refute the previous null-move.

I'm sticking with the current approach. I will test both of these versions by adding verification, for completeness, but it seems like a very slightly worse way of doing null-move searches, although it is not very significant overall. But as I have often said, give away a couple of Elo here, a couple there, and soon you are working on a patzer.

Code: Select all

    Crafty-23.2R08       2653    6    6  6974   61%  2569   23% 
    Crafty-23.2R01-1     2651    3    3 30000   61%  2570   23% 
    Crafty-23.2R07-1     2648    3    3 30000   60%  2570   23% 

R08 is the version with double-nulls allowed, and nulls can be done even in pawn-only endings. It always looks a bit better until the 15-20,000 game point where it has dropped back to about the same.

Note that R01 does win one more game out of every 100 than R07 (the double-null version).. I'll post the complete results in a couple of hours when I get out of class... Test should have finished by then.

Final results:

Code: Select all

    Crafty-23.2R01-1     2645    3    3 30000   61%  2564   23% 
    Crafty-23.2R08-1     2644    3    3 30000   60%  2564   23% 
    Crafty-23.2R07-1     2643    3    3 30000   60%  2564   23% 

[hgm]

As to error bars: 30,000 games gives sigma = 40%/sqrt(30,000) = 0.23%, which is about 1.6 Elo, (7 Elo per %), right? And the 95% confidence intervals are +/- 3.2 Elo.

So the verdict should actually be: "no difference could be detected at the current resolution".

[Mincho Georgiev]

As to error bars: 30,000 games gives sigma = 40%/sqrt(30,000) = 0.23%, which is about 1.6 Elo, (7 Elo per %), right? And the 95% confidence intervals are +/- 3.2 Elo.

So the verdict should actually be: "no difference could be detected at the current resolution".

Sounds right to me.

I'll continue my test, and post the results which off course will not be with the above resolution. The reason to continue it is not that after seeing the Bob's results i'm not confident. No, I am, it's just might be engine or implementation specific, since my results so far are quite different regarding
null_rows vs ordinary_recursive.

[micron]

[1] if (tt_depth >= depth - R - 1 && tt_score < beta && tt_type & UPPER) skip_null(); // If a plain reduced search without nullmove won't produce a cutoff...

[2] You have a bug.

[1] Ah, thank you, that seems to predict reliably that null-move won't cutoff and therefore should not be attempted. In my program, though, it turns out to save a negligible number of attempts.
Without skip_null: 45366 null-moves 36240 cutoffs (79%)
With skip_null: 45304 null moves 36240 cutoffs (79%)

Search deeper. Those should be in the millions, not tens of thousands. The deeper you go, the more hash hits you will see (particularly when draft < depth).

[2] Good, if I can fix the bug in the TT save, null-move pruning should produce even better results...

Found the bug; I forgot to subtract R from the stored draft.
With a sufficiently deep search (13 plies), the combination of skip_null hint from the TT, and correctly hashing the result of null-move, gives about 5% speedup. Thanks to all for the help.

My first chess program was written in the pre-internet era, with 'Chess Skill in Man and Machine' as almost the only resource. It's a very different experience now!

[bob]

Code: Select all

    Crafty-23.2R01-2     2639    3    3 30000   61%  2557   23% 
    Crafty-23.2R01-1     2637    3    3 30000   61%  2557   23% 
    Crafty-23.2R08       2636    5    5 15073   60%  2557   23% 
    Crafty-23.2R08-1     2636    3    3 30000   60%  2557   23% 
    Crafty-23.2R07-1     2635    3    3 30000   60%  2557   23% 
    Crafty-23.2R07-2     2633    3    3 30000   60%  2557   23% 

Second run is not quite complete. Above are results tagged with -1 and -2. These represent two different sets of 3,000 starting positions, played against the same 5 opponents alternating colors for each position, total = 30,000 games.

So far, fairly consistent. I will combine them when all 120,000 games per version has completed. Here is LOS data from BayesElo however:

Code: Select all

Crafty-23.2R01-2      0    77 83 91 94 99
Crafty-23.2R01-1      0 22    63 73 79 95
Crafty-23.2R08        0 16 36    57 63 86
Crafty-23.2R08-1      0  8 26 42    57 86
Crafty-23.2R07-1      0  5 20 36 42    82
Crafty-23.2R07-2      0  0  4 13 13 17   

So BayesElo seems pretty convinced that R01 is better than the others...

I'll combine all this into three versions when everything is done, to see what that does...

Again, R01 wins one more game out of every 100 than either of the other two, which while small is not insignificant.

[bob]

[1] if (tt_depth >= depth - R - 1 && tt_score < beta && tt_type & UPPER) skip_null(); // If a plain reduced search without nullmove won't produce a cutoff...

[2] You have a bug.

[1] Ah, thank you, that seems to predict reliably that null-move won't cutoff and therefore should not be attempted. In my program, though, it turns out to save a negligible number of attempts.
Without skip_null: 45366 null-moves 36240 cutoffs (79%)
With skip_null: 45304 null moves 36240 cutoffs (79%)

Search deeper. Those should be in the millions, not tens of thousands. The deeper you go, the more hash hits you will see (particularly when draft < depth).

[2] Good, if I can fix the bug in the TT save, null-move pruning should produce even better results...

Found the bug; I forgot to subtract R from the stored draft.
With a sufficiently deep search (13 plies), the combination of skip_null hint from the TT, and correctly hashing the result of null-move, gives about 5% speedup. Thanks to all for the help.

My first chess program was written in the pre-internet era, with 'Chess Skill in Man and Machine' as almost the only resource. It's a very different experience now!

I still have a copy of the original, plus the updated version that came out later. It was a "bible" when I started to work on "Blitz" version 6.0 and beyond...

[Mincho Georgiev]

Here it is:

Code: Select all

Rank Name               Elo    +    -  games score oppo. draws
   1 P_019_norestrict     0   12   12   600   50%     0   34%
   2 P_019_restricted     0   12   12   600   50%     0   34%

So my conclusion is: I was wrong, H.G. was right and the null rows restriction is worthless.
Handshake.


p.s. I have no idea why bayeselo is make it 50/50, so here is elostat, not that it make a difference:

Code: Select all

    Program                          Elo    +   -   Games   Score   Av.Op.  Draws

  1 P_019_norestrict               : 2400   23  23   600    50.1 %   2400   33.5 %
  2 P_019_restricted               : 2400   23  23   600    49.9 %   2400   33.5 %

[michiguel]

[1] if (tt_depth >= depth - R - 1 && tt_score < beta && tt_type & UPPER) skip_null(); // If a plain reduced search without nullmove won't produce a cutoff...

[2] You have a bug.

[1] Ah, thank you, that seems to predict reliably that null-move won't cutoff and therefore should not be attempted. In my program, though, it turns out to save a negligible number of attempts.
Without skip_null: 45366 null-moves 36240 cutoffs (79%)
With skip_null: 45304 null moves 36240 cutoffs (79%)

Search deeper. Those should be in the millions, not tens of thousands. The deeper you go, the more hash hits you will see (particularly when draft < depth).

[2] Good, if I can fix the bug in the TT save, null-move pruning should produce even better results...

Found the bug; I forgot to subtract R from the stored draft.

What do you mean exactly by that?

Miguel

With a sufficiently deep search (13 plies), the combination of skip_null hint from the TT, and correctly hashing the result of null-move, gives about 5% speedup. Thanks to all for the help.

My first chess program was written in the pre-internet era, with 'Chess Skill in Man and Machine' as almost the only resource. It's a very different experience now!

[micron]

[2] Good, if I can fix the bug in the TT save, null-move pruning should produce even better results...

Found the bug; I forgot to subtract R from the stored draft.

What do you mean exactly by that?

Nothing interesting. Just the difference between:
SaveInHashTable( alpha, ..., depth ); // oops
SaveInHashTable( alpha, ..., depth - R );

[michiguel]

[2] Good, if I can fix the bug in the TT save, null-move pruning should produce even better results...

Found the bug; I forgot to subtract R from the stored draft.

What do you mean exactly by that?

Nothing interesting. Just the difference between:
SaveInHashTable( alpha, ..., depth ); // oops
SaveInHashTable( alpha, ..., depth - R );

That is what I guessed. Unless I am confused about what you are doing, you should be saving SaveInHashTable( alpha, ..., depth );
You save in the hashtable the same conditions you faced when you entered search(). Otherwise, the next time you enter this node, you would not be able have a hash hit.

Miguel