Improvement from PVS

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.
matthewlai
Posts: 791
Joined: Sun Aug 03, 2014 2:48 am
Location: London, UK
Contact:

Improvement from PVS

Post by matthewlai » Tue Sep 09, 2014 9:56 am

What kind of improvements are people getting with PVS compared to good old alpha-beta (with aspiration window)?

I am working on a new engine. It already has good move ordering (hash, winning/equal captures sorted by SEE, killers, other moves, losing captures), aspiration window, transposition table, null move.

I can get about 15 plies on average at 5 seconds on WAC, with an average branching factor of about 2.5. No forward pruning except null-move.

With PVS, it seems to be getting slower for some reason. The tree seems to be growing by about 10-15% on average.

Not a lot of information I know... but any guesses? :D

Here is the source if anyone wants to take a look -
https://bitbucket.org/waterreaction/gir ... at=default
Disclosure: I work for DeepMind on the AlphaZero project, but everything I say here is personal opinion and does not reflect the views of DeepMind / Alphabet.

User avatar
lucasart
Posts: 3036
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Improvement from PVS

Post by lucasart » Tue Sep 09, 2014 11:15 am

PVS is only useful if you're pretty sure that the first move you search has a good chance of being best (for PV or Cut node). Perhaps you're forgetting IID (if you have no hash move, and the depth is sufficient)?

But do not measure anythihng using WAC. It's useless and counter productive. These test positions are not representative of the average case. Rather a collection of abnormal cases.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

matthewlai
Posts: 791
Joined: Sun Aug 03, 2014 2:48 am
Location: London, UK
Contact:

Re: Improvement from PVS

Post by matthewlai » Tue Sep 09, 2014 11:26 am

lucasart wrote:PVS is only useful if you're pretty sure that the first move you search has a good chance of being best (for PV or Cut node). Perhaps you're forgetting IID (if you have no hash move, and the depth is sufficient)?

But do not measure anythihng using WAC. It's useless and counter productive. These test positions are not representative of the average case. Rather a collection of abnormal cases.
That's a good point. I am not doing IID yet. Though the result is still the same even if I only do PVS on nodes with a hash move.

I am measuring against many test suites. For average cases I use mlmfl, and I also see significant reduction in average plies reached with PVS (on nodes with a hash move only).

EDIT: Actually, it looks like I made a mistake in testing. With mlmfl I am now getting a slight reduction in branching factor (and a slight increase in average plies reached from 9.14 to 9.35). So I guess that's working. I just need IID to make it work better.
Disclosure: I work for DeepMind on the AlphaZero project, but everything I say here is personal opinion and does not reflect the views of DeepMind / Alphabet.

User avatar
hgm
Posts: 23474
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Improvement from PVS

Post by hgm » Tue Sep 09, 2014 11:43 am

PVS gets worse than vanilla alpha-beta when the move ordering sucks, and you have to do too many re-searches. For this reason people often don't do it if the remaining depth is below some limit (like 2), as you are very unlikely to have a good hash move there.

matthewlai
Posts: 791
Joined: Sun Aug 03, 2014 2:48 am
Location: London, UK
Contact:

Re: Improvement from PVS

Post by matthewlai » Tue Sep 09, 2014 11:55 am

hgm wrote:PVS gets worse than vanilla alpha-beta when the move ordering sucks, and you have to do too many re-searches. For this reason people often don't do it if the remaining depth is below some limit (like 2), as you are very unlikely to have a good hash move there.
Thanks. Will definitely give that a try once I have IID.
Disclosure: I work for DeepMind on the AlphaZero project, but everything I say here is personal opinion and does not reflect the views of DeepMind / Alphabet.

matthewlai
Posts: 791
Joined: Sun Aug 03, 2014 2:48 am
Location: London, UK
Contact:

Re: Improvement from PVS

Post by matthewlai » Tue Sep 09, 2014 12:35 pm

mlmfl suite, 5 seconds search -

No PVS, No IID - 9.143 plies (4.28 EBF)
PVS, No IID - 9.429 plies (4.26 EBF)
No PVS, IID - 9.286 plies (4.22 EBF)
PVS, IID - 9.571 plies (4.15 EBF)

I guess that's mystery solved.

Thanks guys!
Disclosure: I work for DeepMind on the AlphaZero project, but everything I say here is personal opinion and does not reflect the views of DeepMind / Alphabet.

bob
Posts: 20406
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Improvement from PVS

Post by bob » Tue Sep 09, 2014 9:56 pm

First, you are testing incorrectly. PVS works when the first move is best and move ordering is working as expected. IE in the normal chess positions you encounter in games.

WAC is a bunch of positions where the goal is to find a non-obvious move that works by some tactical trick. By definition you are going to have to change your mind to the correct move, once you get deep enough, and that re-search when you get the null-window fail high, then the PVS fail high, and then finally reset the aspiration beta value and start again, is the thing that hurts. HERE. But PVS is about the average case, not about the worst case. And yet WAC is nothing but "worst cases".

PVS is a "calm water" algorithm. Don't try to sail it into a hurricane, it will sink. But in calm water it works flawlessly. As Gene Amdahl used to preach, "design for the common case, not the exceptional one" if you want to make something better.

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

Re: Improvement from PVS

Post by syzygy » Tue Sep 09, 2014 10:32 pm

PVS works better than normal alpha-beta not when all first moves are best, but when all first moves are "good enough". If all first moves are best, you can't do better than alpha-beta.

I agree that WAC positions aren't average positions and that it is dangerous to rely on WAC too much. However, it is utterly useless to do well only on positions where the best move never changes as you go deeper.

I'm reasonably sure PVS helps also on WAC. On those positions there is obviously a point where the search changes its mind and PVS will suffer a bit for that, but in most parts of those trees PVS should still help.

matthewlai
Posts: 791
Joined: Sun Aug 03, 2014 2:48 am
Location: London, UK
Contact:

Re: Improvement from PVS

Post by matthewlai » Tue Sep 09, 2014 10:55 pm

bob wrote:First, you are testing incorrectly. PVS works when the first move is best and move ordering is working as expected. IE in the normal chess positions you encounter in games.

WAC is a bunch of positions where the goal is to find a non-obvious move that works by some tactical trick. By definition you are going to have to change your mind to the correct move, once you get deep enough, and that re-search when you get the null-window fail high, then the PVS fail high, and then finally reset the aspiration beta value and start again, is the thing that hurts. HERE. But PVS is about the average case, not about the worst case. And yet WAC is nothing but "worst cases".

PVS is a "calm water" algorithm. Don't try to sail it into a hurricane, it will sink. But in calm water it works flawlessly. As Gene Amdahl used to preach, "design for the common case, not the exceptional one" if you want to make something better.
I did find out about that as well. It's an improvement for mlmfl (positions after common opening lines).

But that begs the question - if that's the case, does PVS actually help?

On positions where we don't change the PV, PVS allows us to search deeper, but if we aren't changing our mind anyways, searching deeper is just wasting time.

On positions where we do change the PV, PVS seems to be slower in my case, which means it will miss deeper tactical lines.

So it seems to me like PVS makes the search faster where it doesn't matter, and slower where it does matter?
Disclosure: I work for DeepMind on the AlphaZero project, but everything I say here is personal opinion and does not reflect the views of DeepMind / Alphabet.

bob
Posts: 20406
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Improvement from PVS

Post by bob » Wed Sep 10, 2014 1:28 am

syzygy wrote:PVS works better than normal alpha-beta not when all first moves are best, but when all first moves are "good enough". If all first moves are best, you can't do better than alpha-beta.

I agree that WAC positions aren't average positions and that it is dangerous to rely on WAC too much. However, it is utterly useless to do well only on positions where the best move never changes as you go deeper.

I'm reasonably sure PVS helps also on WAC. On those positions there is obviously a point where the search changes its mind and PVS will suffer a bit for that, but in most parts of those trees PVS should still help.
I'd bet the overall nodes searched goes up on WAC however, whether you get to the solution quicker is another thing. But the OP was concerned with nodes going up by 10%. That wouldn't surprise me at all although I have not tested that in years...

Post Reply