Improvement from PVS

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

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?

Think about this: You search N plies deep and start iteration N+1. You search the first move and get a score and now search the remainder using a null-window. If you fail high, you JUST found a better move at reduced cost, compared to what it would have taken you to just search with original aspiration beta value as the upper bound. But when you get lots of "mind changes" PVS falls a bit flat. It just doesn't happen that frequently, except in positions that are highly tactical where every new iteration exposes some new tactic and screws up move ordering for those branches at the same time...

[matthewlai]

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

But isn't getting to the solution quicker (ie. being able to find a change of mind quicker) the goal?

I am seeing similar result with ECM (also tactical positions). PVS takes longer to find solutions and finds less solutions at fixed time.

[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?

Think about this: You search N plies deep and start iteration N+1. You search the first move and get a score and now search the remainder using a null-window. If you fail high, you JUST found a better move at reduced cost, compared to what it would have taken you to just search with original aspiration beta value as the upper bound. But when you get lots of "mind changes" PVS falls a bit flat. It just doesn't happen that frequently, except in positions that are highly tactical where every new iteration exposes some new tactic and screws up move ordering for those branches at the same time...

I guess that means I have to start using results from incomplete plies. Right now I only use the result of a ply if it actually finishes.

Otherwise, it doesn't really matter that we get to the fail high faster in iteration N + 1, since iteration N + 1 will take longer to complete anyways due to the re-search.

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

But isn't getting to the solution quicker (ie. being able to find a change of mind quicker) the goal?

I am seeing similar result with ECM (also tactical positions). PVS takes longer to find solutions and finds less solutions at fixed time.

You ought to pick a single solution and look at the output to see what is happening. If you see several fail highs at each new iteration, PVS is probably going to be a little slower.

And to be careful here, I assume you are doing something like this:

v = -Search(-alpha-1, -alpha, ...)
if (v > alpha && v < beta)
v = -Search(-beta, -alpha, ...)

???

So that I am sure we are talking about the same PVS idea. At the start of the search, before calling search, I also use aspiration:

alpha = old - 16;
beta = old + 16;

and pass those to the ply=1 search.

[JVMerlino]

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

But isn't getting to the solution quicker (ie. being able to find a change of mind quicker) the goal?

I am seeing similar result with ECM (also tactical positions). PVS takes longer to find solutions and finds less solutions at fixed time.

You ought to pick a single solution and look at the output to see what is happening. If you see several fail highs at each new iteration, PVS is probably going to be a little slower.

And to be careful here, I assume you are doing something like this:

v = -Search(-alpha-1, -alpha, ...)
if (v > alpha && v < beta)
v = -Search(-beta, -alpha, ...)

???

So that I am sure we are talking about the same PVS idea. At the start of the search, before calling search, I also use aspiration:

alpha = old - 16;
beta = old + 16;

and pass those to the ply=1 search.

I thought most engines only decreased alpha on a fail low and only increased beta on a fail high, and this appears to be what Crafty 24.0 does as well in iterate.c. Or am I mistaken?

jm

[elcabesa]

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.

today I just tried to look how many times pvs failed in my search at various depth.
it looks like that the % of research at high depth node and low depth ones is near 2-3%.
I'll have to further investigate, but i'll let you know the results of my search

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

But isn't getting to the solution quicker (ie. being able to find a change of mind quicker) the goal?

I am seeing similar result with ECM (also tactical positions). PVS takes longer to find solutions and finds less solutions at fixed time.

You ought to pick a single solution and look at the output to see what is happening. If you see several fail highs at each new iteration, PVS is probably going to be a little slower.

And to be careful here, I assume you are doing something like this:

v = -Search(-alpha-1, -alpha, ...)
if (v > alpha && v < beta)
v = -Search(-beta, -alpha, ...)

???

So that I am sure we are talking about the same PVS idea. At the start of the search, before calling search, I also use aspiration:

alpha = old - 16;
beta = old + 16;

and pass those to the ply=1 search.

I thought most engines only decreased alpha on a fail low and only increased beta on a fail high, and this appears to be what Crafty 24.0 does as well in iterate.c. Or am I mistaken?

jm

The +/- 16 is the aspiration window set before Search() is called for a specific iteration. If Search() returns a value <= alpha or >= beta, that specific bound is relaxed and we do it again.

The search code I gave above is the PVS search /fail-high-research code to show how it should look in general.

[matthewlai]

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

But isn't getting to the solution quicker (ie. being able to find a change of mind quicker) the goal?

I am seeing similar result with ECM (also tactical positions). PVS takes longer to find solutions and finds less solutions at fixed time.

You ought to pick a single solution and look at the output to see what is happening. If you see several fail highs at each new iteration, PVS is probably going to be a little slower.

And to be careful here, I assume you are doing something like this:

v = -Search(-alpha-1, -alpha, ...)
if (v > alpha && v < beta)
v = -Search(-beta, -alpha, ...)

???

So that I am sure we are talking about the same PVS idea. At the start of the search, before calling search, I also use aspiration:

alpha = old - 16;
beta = old + 16;

and pass those to the ply=1 search.

It's very similar to what I am doing, except I am only checking for alpha. Didn't occur to me that I can also get a fail high (on the parent node) from a null window node. Will give that a try.

I am doing aspiration as well, but with a little bigger bounds (25 on either side).

[matthewlai]

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

But isn't getting to the solution quicker (ie. being able to find a change of mind quicker) the goal?

I am seeing similar result with ECM (also tactical positions). PVS takes longer to find solutions and finds less solutions at fixed time.

You ought to pick a single solution and look at the output to see what is happening. If you see several fail highs at each new iteration, PVS is probably going to be a little slower.

And to be careful here, I assume you are doing something like this:

v = -Search(-alpha-1, -alpha, ...)
if (v > alpha && v < beta)
v = -Search(-beta, -alpha, ...)

???

So that I am sure we are talking about the same PVS idea. At the start of the search, before calling search, I also use aspiration:

alpha = old - 16;
beta = old + 16;

and pass those to the ply=1 search.

It's very similar to what I am doing, except I am only checking for alpha. Didn't occur to me that I can also get a fail high (on the parent node) from a null window node. Will give that a try.

I am doing aspiration as well, but with a little bigger bounds (25 on either side).

Actually, never mind. I AM checking beta as well. I just didn't recall adding that.

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

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?

Think about this: You search N plies deep and start iteration N+1. You search the first move and get a score and now search the remainder using a null-window. If you fail high, you JUST found a better move at reduced cost, compared to what it would have taken you to just search with original aspiration beta value as the upper bound. But when you get lots of "mind changes" PVS falls a bit flat. It just doesn't happen that frequently, except in positions that are highly tactical where every new iteration exposes some new tactic and screws up move ordering for those branches at the same time...

I guess that means I have to start using results from incomplete plies. Right now I only use the result of a ply if it actually finishes.

Otherwise, it doesn't really matter that we get to the fail high faster in iteration N + 1, since iteration N + 1 will take longer to complete anyways due to the re-search.

Depends on your definition of "incomplete plies". If you mean a ply where you terminated due to a search time-out, you NEVER store those results, lest you plant the seeds from which a blunder will eventually grow. If you mean a ply where you fail high, that is not "incomplete". You searched all that was required to prove that the previous move (previous ply) was a mistake that is refuted by at least this move if not others. That is a complete ply also, just like a ply where you search everything and discover alpha was unchanged after you finished.