Improvement from PVS

[matthewlai]

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?

Here is the source if anyone wants to take a look -
https://bitbucket.org/waterreaction/gir ... at=default

[lucasart]

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.

[matthewlai]

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.

[hgm]

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]

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.

[matthewlai]

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!

[bob]

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]

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]

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?

[bob]

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...