Less null move pruning by trans map

[Onno Garms]

There seems to have been some improvement of Onno by using the trans
map to skip null move pruning on certain moves.

After I made a move, I check the trans map before doing null move
pruning. There might be no trans cutoff because the depth found in the
trans map is smaller that current search depth (trans.max_depth <
p_depth). However it is still possible that trans_max_depth >= p_depth
- SearchInnerRc::null_reduction.

So I do the following:

Code: Select all

    // Even with a move opponent is not so well off.
    // So null move pruning is unlikely to be successful.
    if &#40;SearchInnerRc&#58;&#58;null_skip_by_trans && trans.max_value <= p_alpha && trans.max_depth >= p_depth - SearchInnerRc&#58;&#58;null_reduction&#41;
      *v_no_nmp = true;

[bob]

There seems to have been some improvement of Onno by using the trans
map to skip null move pruning on certain moves.

After I made a move, I check the trans map before doing null move
pruning. There might be no trans cutoff because the depth found in the
trans map is smaller that current search depth (trans.max_depth <
p_depth). However it is still possible that trans_max_depth >= p_depth
- SearchInnerRc::null_reduction.

So I do the following:

Code: Select all

    // Even with a move opponent is not so well off.
    // So null move pruning is unlikely to be successful.
    if &#40;SearchInnerRc&#58;&#58;null_skip_by_trans && trans.max_value <= p_alpha && trans.max_depth >= p_depth - SearchInnerRc&#58;&#58;null_reduction&#41;
      *v_no_nmp = true;

Hasn't this been known and used for 20 years now???

[Mincho Georgiev]

We had a discussion on this some time ago and I've posted some results.Unfortunately, I cannot find the thread, I'll keep trying.
If I understand correctly, it's exactly the null move trick that we had discussed then.
It gave me around 5 elo as far as I remember. I'll keep trying to find it.

[Mincho Georgiev]

Found it:
http://www.talkchess.com/forum/viewtopi ... ht=#340398

[Onno Garms]

Hasn't this been known and used for 20 years now???

In deed fairly obvious, so not surprising that it is known. Though not worth too much, it is certainly an improvement.

By code inspection I thought that this feature is missing in Stockfish. That's why I posted it.

[mjlef]

A refinement is that if the depth is less than whatever the null reduction value, you can safely store with the depth reduction value. For example if depth=2, and you would reduce a null move by 4 (R=3 plus the normal 1 ply you would reduce) then you can save it with depth=4. I only save though if the has entry has no move in it. Not well tested but it seems to keep move ordering better, since a null move search returns no real "move" for the current since two moves in a row could lead to illegal moves for the current side in the regular search.

[Sergei S. Markoff]

Code: Select all

    // Even with a move opponent is not so well off.
    // So null move pruning is unlikely to be successful.
    if &#40;SearchInnerRc&#58;&#58;null_skip_by_trans && trans.max_value <= p_alpha && trans.max_depth >= p_depth - SearchInnerRc&#58;&#58;null_reduction&#41;
      *v_no_nmp = true;

SmarThink declines null move more aggressively. Probably you don't need "trans.max_depth >= p_depth - SearchInnerRc::null_reduction" because if at any depth you're failed with null move, it looks to be too dangerous.
Moreover, I'm using some case of IID with null move — trying to search it with depth = 0, 1, 2 ... till (depth – null_reduction). Only if every search (including simple static eval) returns value >= beta then make cutoff.
This approach is combined with relatively larger reduction comparing to other programs.

I think null-move subtree is very specific and probably it's a good idea to make more reductions here. Because it's relatively safe to falsely decline reduction — you will just search more, but if it will be compensated by enought pruned nodes in subtree — it will be clear advantage.

I think it's worth to try something like flags for search to indicate, if there was null move for each side. If we're in subtree where white null move was done we can prune more white moves despite these cutoffs will be completely incorrect (for example, just exclude moves with SEE < 0, more than 8 quiet white moves, moves that can't return value >= beta with very reduced depth and so on). Moreover, resulting score can be more valuable, because it will exclude some non-obvious refutations of answers to null move; if null move answers are hard to refute, probably it's better to make full search to explore this position.
I think it's possible to tune this framework very well.

[Rein Halbersma]

Hasn't this been known and used for 20 years now???

In deed fairly obvious, so not surprising that it is known. Though not worth too much, it is certainly an improvement.

By code inspection I thought that this feature is missing in Stockfish. That's why I posted it.

I think I asked the same question about Stockfish 3 years ago http://www.talkchess.com/forum/viewtopi ... highlight=

The answer is that it interacts in a subtle way with LMR (at least at the time, not sure if that is still the case).

Funny that Bob's reaction then was the same as now. Why continue with this hobby if everything was already solved 20 years ago

[Daniel Shawul]

Code: Select all

    // Even with a move opponent is not so well off.
    // So null move pruning is unlikely to be successful.
    if &#40;SearchInnerRc&#58;&#58;null_skip_by_trans && trans.max_value <= p_alpha && trans.max_depth >= p_depth - SearchInnerRc&#58;&#58;null_reduction&#41;
      *v_no_nmp = true;

SmarThink declines null move more aggressively. Probably you don't need "trans.max_depth >= p_depth - SearchInnerRc::null_reduction" because if at any depth you're failed with null move, it looks to be too dangerous.
Moreover, I'm using some case of IID with null move — trying to search it with depth = 0, 1, 2 ... till (depth – null_reduction). Only if every search (including simple static eval) returns value >= beta then make cutoff.
This approach is combined with relatively larger reduction comparing to other programs.

Do you mean that you try null move iteratively starting from the lowest say from depth=1 to depth=d-3 until all of fail high, implemented like IID or via an explicitly for-loop over the depths? I think that the current top programs use depths big enough to make null move searches negligible, using depth reductions function of depth itself say R=depth/4. From my limited perft-analysis of null move trees, even a constant reductions of 3 makes the cost negligible when you factor in the thing is applied recursively.

[Ralph Stoesser]

Hasn't this been known and used for 20 years now???

In deed fairly obvious, so not surprising that it is known. Though not worth too much, it is certainly an improvement.

By code inspection I thought that this feature is missing in Stockfish. That's why I posted it.

It was tried about three month ago by Lucas Braesch, but it failed at stage 2 (60+0.05) rather convincingly.