Less null move pruning by trans map

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

User avatar
Onno Garms
Posts: 224
Joined: Mon Mar 12, 2007 6:31 pm
Location: Bonn, Germany

Less null move pruning by trans map

Post by Onno Garms » Sun Mar 13, 2011 7:38 pm

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
Posts: 20340
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Less null move pruning by trans map

Post by bob » Fri Mar 18, 2011 2:29 pm

Onno Garms wrote: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
Posts: 454
Joined: Sat Apr 04, 2009 4:44 pm
Location: Bulgaria
Contact:

Re: Less null move pruning by trans map

Post by Mincho Georgiev » Sat Mar 19, 2011 9:58 am

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.


User avatar
Onno Garms
Posts: 224
Joined: Mon Mar 12, 2007 6:31 pm
Location: Bonn, Germany

Re: Less null move pruning by trans map

Post by Onno Garms » Sat Mar 19, 2011 2:17 pm

bob wrote: 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
Posts: 1308
Joined: Thu Mar 30, 2006 12:08 pm
Contact:

Re: Less null move pruning by trans map

Post by mjlef » Mon Mar 21, 2011 12:01 am

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
Posts: 202
Joined: Mon Sep 12, 2011 9:27 pm
Location: Moscow, Russia
Contact:

Re: Less null move pruning by trans map

Post by Sergei S. Markoff » Tue Dec 10, 2013 9:13 am

Onno Garms wrote:

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.
The Force Be With You!

Rein Halbersma
Posts: 672
Joined: Tue May 22, 2007 9:13 am

Re: Less null move pruning by trans map

Post by Rein Halbersma » Tue Dec 10, 2013 9:28 am

Onno Garms wrote:
bob wrote: 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 :roll:

Daniel Shawul
Posts: 3436
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Less null move pruning by trans map

Post by Daniel Shawul » Tue Dec 10, 2013 3:56 pm

Sergei S. Markoff wrote:
Onno Garms wrote:

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
Posts: 408
Joined: Sat Mar 06, 2010 8:28 am

Re: Less null move pruning by trans map

Post by Ralph Stoesser » Tue Dec 10, 2013 8:20 pm

Onno Garms wrote:
bob wrote: 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.

Post Reply