bob wrote:It appears to be a moot issue to me anyway. If you don't use aspiration search at the root, so that you always start with (-inf, +inf) then either algorithm works _exactly_ the same way, because the first move will _always_ improve on -inf.
That's not true. Without an aspiration window, the first line searched (all the way up the left side) has an infinite window. Once there is a PV research though, every node below it will have an open but finite window. If this was true then we wouldn't even be discussing it.
That was my first thought too. I don't think either method is fundamentally better, each has its advantages.
I don't think so. If the first move doesn't give alpha or better, you'd expect no other move to give alpha or better in more than 95% of the cases.
Even in those 5% of cases, your gain will be minimal, because you will only do one zero-window search (which has to be followed by a bigger window) less.
With the other method, in 95% of the cases you're being grossly inefficient.
If these assumptions didn't hold, PVS wouldn't work to begin with.
It makes no sense to use PVS and then search moves other than the first with an open window. None at all...
I agree with Zach. At expected PV-nodes, you really expect to raise alpha. Expected PV-Nodes are either the most left nodes in the tree, or nodes where you need to re-search a null-window search. Thus, an expected PV-Node only degenerates to an All-Node, if your aspiration window was too optimistic, or if you have to deal with search instability issues, that is a NWS needs to be re-searched, but the re-search didn't confirm the alpha raise as indicated by the former NWS.
I would not call Bruce's approach wrong per se. You are right with the initial PVS implementation by Marsland though.
Here's the issue. First assumption is an aspiration window at the root, otherwise this can't happen in the first place. Next assumption is that the first move you search at each ply, except for the last, is a hash move. Because the previous iteration should have left those laying around for the next iteration, or if you do as I do, I guarantee this by re-installing all the PV moves just to be sure the ordering goes well.
If that move fails low, it is likely that the root aspiration window is too narrow. I can try to instrument Crafty to see how often the first move fails to improve alpha while a subsequent move does, to see what percent of the time this will pay off or lose in terms of efficiency.
I can probably simply test both ways since it just involves (in my case) setting "first_move = 0" at a slightly different place than where it is currently set.
One may argue PV-nodes are usually not singular - there are more often many moves which would raise alpha, but of course the first move should most often be the best one. In rare cases, the first move didn't raise alpha at PV-nodes, which is indeed an indication the node starts to behave unexpected, the second move may still have potential most often with some care to pick the right move. An available Killer (after the failed Hash move) or "winning" or "equal" captures might still raise alpha, or one may look for a counter against the refutation of the first move. I think Zach's idea to switch to NWS without PV after N moves (N == 2 or 3) is worth a try.
I found Bruce's implementation an argument to distinguish PVS per definition from NegaScout (even if historically unsound): PVS uses alpha-beta until it founds a principle variation, no matter when - and then switches to ZWS. NegaScout always after first move. Of course with -oo/+oo we always raise alpha with the first move, but if we re-search, it also depends on trusting the score from ZWS. Do you use -alpha or the narrower -score as re-search beta?
That was my first thought too. I don't think either method is fundamentally better, each has its advantages.
I don't think so. If the first move doesn't give alpha or better, you'd expect no other move to give alpha or better in more than 95% of the cases.
Even in those 5% of cases, your gain will be minimal, because you will only do one zero-window search (which has to be followed by a bigger window) less.
With the other method, in 95% of the cases you're being grossly inefficient.
If these assumptions didn't hold, PVS wouldn't work to begin with.
It makes no sense to use PVS and then search moves other than the first with an open window. None at all...
I agree with Zach. At expected PV-nodes, you really expect to raise alpha. Expected PV-Nodes are either the most left nodes in the tree, or nodes where you need to re-search a null-window search. Thus, an expected PV-Node only degenerates to an All-Node, if your aspiration window was too optimistic, or if you have to deal with search instability issues, that is a NWS needs to be re-searched, but the re-search didn't confirm the alpha raise as indicated by the former NWS.
I would not call Bruce's approach wrong per se. You are right with the initial PVS implementation by Marsland though.
Here's the issue. First assumption is an aspiration window at the root, otherwise this can't happen in the first place. Next assumption is that the first move you search at each ply, except for the last, is a hash move. Because the previous iteration should have left those laying around for the next iteration, or if you do as I do, I guarantee this by re-installing all the PV moves just to be sure the ordering goes well.
If that move fails low, it is likely that the root aspiration window is too narrow. I can try to instrument Crafty to see how often the first move fails to improve alpha while a subsequent move does, to see what percent of the time this will pay off or lose in terms of efficiency.
I can probably simply test both ways since it just involves (in my case) setting "first_move = 0" at a slightly different place than where it is currently set.
One may argue PV-nodes are usually not singular - there are more often many moves which would raise alpha, but of course the first move should most often be the best one. In rare cases, the first move didn't raise alpha at PV-nodes, which is indeed an indication the node starts to behave unexpected, the second move may still have potential most often with some care to pick the right move. An available Killer (after the failed Hash move) or "winning" or "equal" captures might still raise alpha, or one may look for a counter against the refutation of the first move. I think Zach's idea to switch to NWS without PV after N moves (N == 2 or 3) is worth a try.
I found Bruce's implementation an argument to distinguish PVS per definition from NegaScout (even if historically unsound): PVS uses alpha-beta until it founds a principle variation, no matter when - and then switches to ZWS. NegaScout always after first move. Of course with -oo/+oo we always raise alpha with the first move, but if we re-search, it also depends on trusting the score from ZWS. Do you use -alpha or the narrower -score as re-search beta?
int pvSearchA( int alpha, int beta, int depth ) {
...
score = -pvSearch(-alpha-1, -alpha, depth - 1);
if ( score > alpha && score < beta )
score = -pvSearch(-beta, -alpha, depth - 1); // re-search
versus
int pvSearchB( int alpha, int beta, int depth ) {
...
score = -pvSearch(-alpha-1, -alpha, depth - 1);
if ( score > alpha && score < beta )
score = -pvSearch(-beta, -score, depth - 1); // re-search
I've never seen PVS defined like that, although that is a bit beside the point. My thinking is as follows:
If the first mvoe does not raise alpha, what convinces one that the second move will do so? This then boils down to which do you prefer and think is more efficient:
(1) search every move with a full window until one returns a score > alpha; or,
(2) since the first move was no good, scout the remainder of the moves with a null-window search to find one that will raise alpha, and then search it with the original bound.
Searching moves and avoiding the savings of the null-window search seems pointless since that is _exactly_ what it is designed to do, That is do minimal effort searches unless we find one where the next ply fails low (so that this move fails high) and then research that specific move with a wider window and expend more effort than normal.
bob wrote:It appears to be a moot issue to me anyway. If you don't use aspiration search at the root, so that you always start with (-inf, +inf) then either algorithm works _exactly_ the same way, because the first move will _always_ improve on -inf.
That's not true. Without an aspiration window, the first line searched (all the way up the left side) has an infinite window. Once there is a PV research though, every node below it will have an open but finite window. If this was true then we wouldn't even be discussing it.
How is that not true. If I do a normal search from the root with (-inf, +inf) then how can _any_ node below that point fail low (or high for that matter). So all scores returned will be within the window for the first move down the left-hand side of the tree. Which means that every node down the left-hand side (assuming left-to-right traversal of course) will search one move, get a value > alpha back, and the rest of the searches will be null-window searches. Any of which might fail high and trigger a re-search since we can never lower alpha at a node, but we can most certainly raise it.
Without aspiration search at the root, how can you possibly not get a score >= alpha and <= beta backed up down the left-hand edge of the tree? Unless you have a bug and lose your king, of course...
bob wrote:How is that not true. If I do a normal search from the root with (-inf, +inf) then how can _any_ node below that point fail low (or high for that matter). So all scores returned will be within the window for the first move down the left-hand side of the tree. Which means that every node down the left-hand side (assuming left-to-right traversal of course) will search one move, get a value > alpha back, and the rest of the searches will be null-window searches. Any of which might fail high and trigger a re-search since we can never lower alpha at a node, but we can most certainly raise it.
Without aspiration search at the root, how can you possibly not get a score >= alpha and <= beta backed up down the left-hand edge of the tree? Unless you have a bug and lose your king, of course...
I'm not sure exactly what you're talking about. The root doesn't have anything to do with it. We're talking about PVS/NegaScout on all PV nodes. It's just replacing the PVS condition with
if (moves > 2 || pv_found)
search(-alpha-1, -alpha, depth-1);
Anyways, I did a very brief test (just a set of some test positions to fixed depth) with this and my idea turned out to be worse, so I guess we can all carry on...
This thread is very interesting for me but it is also close to creating some confusion in my mind about the "correct" PVS algorithm.
In his original posting Edmund refers to CPW. The algorithm that is shown there (and partially quoted by Edmund) is explicitly restricted to the case of not using an aspiration window at the root, and it also relies on the fail-hard framework. Other postings in this thread partially refer to PVS with aspiration window, and also using fail-soft has been mentioned. I think I have followed the discussion carefully but I still miss a commonly agreed listing of a correct and "state of the art" PVS algorithm for each of these three different approaches:
a) no aspiration window, fail-hard
b) aspiration window (at the root), fail-hard
c) aspiration window (at the root), fail-soft
From reading this thread, up to now I have not been able to derive whether the doubts that have been expressed about the CPW algorithm are legitimate or not, and if they are, whether this means that the CPW algorithm is not appropriate for approach a), or only that it needs modifications for approaches b) and c) - which has been known in advance.
I would really appreciate some clarification here.
Sven
Last edited by Sven on Fri Mar 13, 2009 3:24 pm, edited 1 time in total.
Gerd Isenberg wrote: Of course with -oo/+oo we always raise alpha with the first move, but if we re-search, it also depends on trusting the score from ZWS. Do you use -alpha or the narrower -score as re-search beta?
I use -alpha. If you use -score, and flip-flop, your PV will be truncated.
Sven Schüle wrote:This thread is very interesting for me but it is also close to creating some confusion in my mind about the "correct" PVS algorithm.
In his original posting Edmund refers to CPW. The algorithm that is shown there (and partially quoted by Edmund) is explicitly restricted to the case of not using an aspiration window at the root, and it also relies on the fail-hard framework. Other postings in this thread partially refer to PVS with aspiration window, and also using fail-soft has been mentioned. I think I have followed the discussion carefully but I still miss a commonly agreed listing of a correct and "state of the art" PVS algorithm for each of these three different approaches:
a) no aspiration window, fail-hard
b) aspiration window (at the root), fail-hard
c) aspiration window (at the root), fail-soft
From reading this thread, up to now I have not been able to derive whether the doubts that have been expressed about the CPW algorithm are legitimate or not, and if they are, whether this means that the CPW algorithm is not appropriate for approach a), or only that it needs modifications for approaches b) and c) - which has been known in advance.
I would really appreciate some clarification here.
Sven
As pointed out by Edmund, Gian-Carlo and Bob, and tried by Zach, it seems consensus now, to only search the first move with an open window, no matter whether you use a b or c. This was the initial implementation by Marsland and Campbell. One can assume CPW's and Bruce Moreland's implementation is inefficient, specially with aspiration from the root. I will address this topic in CPW briefly, but I am still looking for a reason to have separate pages for NegaScout and Scout
An interesting PVS-modification is shown in Mark Winand's paper on Enhanced Forward Pruning, to apply multi-cut at expected All-Nodes, returning beta!
Sven Schüle wrote:This thread is very interesting for me but it is also close to creating some confusion in my mind about the "correct" PVS algorithm.
In his original posting Edmund refers to CPW. The algorithm that is shown there (and partially quoted by Edmund) is explicitly restricted to the case of not using an aspiration window at the root, and it also relies on the fail-hard framework. Other postings in this thread partially refer to PVS with aspiration window, and also using fail-soft has been mentioned. I think I have followed the discussion carefully but I still miss a commonly agreed listing of a correct and "state of the art" PVS algorithm for each of these three different approaches:
a) no aspiration window, fail-hard
b) aspiration window (at the root), fail-hard
c) aspiration window (at the root), fail-soft
From reading this thread, up to now I have not been able to derive whether the doubts that have been expressed about the CPW algorithm are legitimate or not, and if they are, whether this means that the CPW algorithm is not appropriate for approach a), or only that it needs modifications for approaches b) and c) - which has been known in advance.
I would really appreciate some clarification here.
Sven
The PVS search I did in 1978, with Murray Campbell sitting beside me at the terminal as I made the changes, was as I described. Search the first move with a normal window (with aspiration at the root as we were all doing that in 1978 already) and then the rest of the moves with a null-window. Whether the first move improved alpha or not. And I have always done it that way since...
I believe that this is the most logical approach and is in keeping with the "scout" concept of doing the least work possible to identify those moves that need more effort (fail high on null-window) to deal with.
bob wrote:How is that not true. If I do a normal search from the root with (-inf, +inf) then how can _any_ node below that point fail low (or high for that matter). So all scores returned will be within the window for the first move down the left-hand side of the tree. Which means that every node down the left-hand side (assuming left-to-right traversal of course) will search one move, get a value > alpha back, and the rest of the searches will be null-window searches. Any of which might fail high and trigger a re-search since we can never lower alpha at a node, but we can most certainly raise it.
Without aspiration search at the root, how can you possibly not get a score >= alpha and <= beta backed up down the left-hand edge of the tree? Unless you have a bug and lose your king, of course...
I'm not sure exactly what you're talking about. The root doesn't have anything to do with it. We're talking about PVS/NegaScout on all PV nodes. It's just replacing the PVS condition with
if (moves > 2 || pv_found)
search(-alpha-1, -alpha, depth-1);
Anyways, I did a very brief test (just a set of some test positions to fixed depth) with this and my idea turned out to be worse, so I guess we can all carry on...
But it does affect things, because at the root, you either start with (-inf, +inf) as your initial alpha/beta window, which _guarantees_ that your leftmost edge searches will _always_ improve alpha, since all scores have to be above -inf or below +inf down that edge. This issue only happens (first move on a PV node fails to improve alpha) if you use aspiration at the root so that scores can lie outside the a-b window.
