Null move pruning on PV nodes.

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
eric.oldre
Posts: 18
Joined: Thu Jun 19, 2014 3:07 am
Location: Minnesota, USA
Contact:

Null move pruning on PV nodes.

Post by eric.oldre » Tue Jul 22, 2014 7:35 pm

Looking through the source of other open source engines I've noticed that nearly every program will only attempt to use null move pruning on non-pv nodes.

It appears non-PV nodes are usually defined as nodes where beta == alpha + 1.

Noticing that my program does NOT put such a limitation on the use of null move pruning, I thought that I might have found a source of a big elo gain. So I went ahead and added that condition and did some testing. I found that just by restricting null-move-pruning to non-pv nodes my average search tree size exploded by 250%. I went ahead and ran a 2000 game test at 1min/game and found my program lost about 100 elo with this restriction in place.

What is the rational for only using null-move-pruning at non-pv nodes? My my thinking, if the position is above beta, it should be above beta regardless of what alpha is (search instability aside). So why do most restrict it's use?

Also, anyone have any advice on if my drastic explosion of the search tree size might be indicating something else going wrong in my search? perhaps inspiration windows too large?

syzygy
Posts: 4450
Joined: Tue Feb 28, 2012 10:56 pm

Re: Null move pruning on PV nodes.

Post by syzygy » Tue Jul 22, 2014 7:59 pm

Distinguishing between PV and non-PV nodes only makes sense if you use PVS. If you do not use PVS, the condition "beta == alpha + 1" has little meaning.

https://chessprogramming.wikispaces.com ... ion+Search

eric.oldre
Posts: 18
Joined: Thu Jun 19, 2014 3:07 am
Location: Minnesota, USA
Contact:

Re: Null move pruning on PV nodes.

Post by eric.oldre » Tue Jul 22, 2014 10:00 pm

Thanks Ronald, that was the reason for the confusion all right.

syzygy
Posts: 4450
Joined: Tue Feb 28, 2012 10:56 pm

Re: Null move pruning on PV nodes.

Post by syzygy » Tue Jul 22, 2014 11:42 pm

Implementing PVS should be a source of at least some Elo gain :-)

eric.oldre
Posts: 18
Joined: Thu Jun 19, 2014 3:07 am
Location: Minnesota, USA
Contact:

Re: Null move pruning on PV nodes.

Post by eric.oldre » Wed Jul 23, 2014 2:07 am

Ronald, yes I decided to try implementing PVS and in my "nodes to depth" tests it cut the size of the search tree by about 25%!

I'm running 2000 games right now and it's too early to tell how much of a gain I got but the test has run long enough that I'm pretty certain it's a non-trivial amount. Thanks for your help.

Post Reply