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?
Null move pruning on PV nodes.
Moderators: hgm, Rebel, chrisw
-
- Posts: 18
- Joined: Thu Jun 19, 2014 5:07 am
- Location: Minnesota, USA
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Null move pruning on PV nodes.
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
https://chessprogramming.wikispaces.com ... ion+Search
-
- Posts: 18
- Joined: Thu Jun 19, 2014 5:07 am
- Location: Minnesota, USA
Re: Null move pruning on PV nodes.
Thanks Ronald, that was the reason for the confusion all right.
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Null move pruning on PV nodes.
Implementing PVS should be a source of at least some Elo gain
-
- Posts: 18
- Joined: Thu Jun 19, 2014 5:07 am
- Location: Minnesota, USA
Re: Null move pruning on PV nodes.
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.
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.