PVS

[Zach Wegner]

see also
http://www.talkchess.com/forum/viewtopic.php?t=24883

That was my first thought too. I don't think either method is fundamentally better, each has its advantages.

I don't think anyone tried my idea ("What you might try is searching with a zero window if either moves>N or best_score>alpha.") though. Bob!! Your cluster beckons!! It wants to test this idea!

[Gian-Carlo Pascutto]

see also
http://www.talkchess.com/forum/viewtopic.php?t=24883

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

[diep]

For Diep, PVS is far superior over any other method, especially MTD.

Vincent

[Zach Wegner]

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.

I certainly can't expect that. My PV nodes typically get the best move searched first around 60%, assuming alpha is raised. I can only sometimes get that number for CUT nodes. And I don't think my move ordering is that bad...

With the other method, in 95% of the cases you're being grossly inefficient.

But that's only in the x% of cases that a PV node turns out to be an all node (don't have a number on me, but I'd expect it to be low).

Anyways, I remember last time I tried the difference was very small. It is at least worth a shot to combine them, since if you search 2 or 3 or so nodes at a PV node, then you might really be 95% sure it's an ALL node.

[Gerd Isenberg]

see also
http://www.talkchess.com/forum/viewtopic.php?t=24883

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.

[CThinker]

see also
http://www.talkchess.com/forum/viewtopic.php?t=24883

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

In fact, the fundamental assumption with PVS is that the moves are well ordered - the first move is already the best. And if it isn't, then you do a shallow search to order the moves (IID).

[bob]

Fixed:

Code: Select all

   for ( all moves)  {
      make
      if ( bSearchPv ) {
         score = -pvSearch(-beta, -alpha, depth - 1);
      } else {
         score = -pvSearch(-alpha-1, -alpha, depth - 1);
         if ( score > alpha && score < beta ) 
            score = -pvSearch&#40;-beta, -alpha, depth - 1&#41;; // re-search
      &#125;
      unmake
      if&#40; score >= beta )
         return score;  
      if&#40; score > alpha )
         alpha = score; // alpha acts like max in MiniMax      
      bSearchPv = false;
   &#125; 

I thought this was the difference between PVS and NegaScout

PVS waits until a move is found that improves alpha, and then searches every move after that with a zero window around alpha. NegaScout just searches the first move, and then searches every move after that with the same zero window.

The PseudoCode mentioned is almost identical with Bruce Moreland's PVS code.

If no PV move has been found, "AlphaBeta()" is recursed normally. If one has been found, everything changes. Rather than searching with a normal (alpha, beta) window, we search with (alpha, alpha + 1). The premise is that all of the searches are going to come back with a score less than or equal to alpha, and if this is going to happen, the elimination of the top end of the window results in more cutoffs. Of course, if the premise is wrong, the score comes back at alpha + 1 or higher, and the search must be re-done with the wider window.

Code: Select all

int AlphaBeta(int depth, int alpha, int beta)
{
    BOOL fFoundPv = FALSE;

    if (depth == 0)
        return Evaluate();

    GenerateLegalMoves();
    while (MovesLeft()) {
        MakeNextMove();
        if (fFoundPv) {
            val = -AlphaBeta(depth - 1, -alpha - 1, -alpha);
            if (&#40;val > alpha&#41; && &#40;val < beta&#41;) // Check for failure.
                val = -AlphaBeta&#40;depth - 1, -beta, -alpha&#41;;
        &#125; else
            val = -AlphaBeta&#40;depth - 1, -beta, -alpha&#41;;
        UnmakeMove&#40;);
        if &#40;val >= beta&#41;
            return beta;
        if &#40;val > alpha&#41; &#123;
            alpha = val;
            fFoundPv = TRUE;
        &#125;
    &#125;
    return alpha;
&#125;

see also
http://www.talkchess.com/forum/viewtopic.php?t=24883

Gerd

I've never seen PVS limited (search until alpha is improved prior to starting null-window searches.) PVS will, by definition, get a value for alpha on the first search from a PV node. Because PVS does not explicitly require any sort of aspiration window at the root. That is a different animal completely, and aspiration search and PVS can be used independently or together.

[bob]

see also
http://www.talkchess.com/forum/viewtopic.php?t=24883

That was my first thought too. I don't think either method is fundamentally better, each has its advantages.

I don't think anyone tried my idea ("What you might try is searching with a zero window if either moves>N or best_score>alpha.") though. Bob!! Your cluster beckons!! It wants to test this idea!

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.

If you use aspiration search at the window, why would you want to defer starting null-window searches? If the first move fails low (leaves alpha intact) why not do a null-window search on the rest in case they fail low as well because the aspiration window is wrong? By searching the null-window, you will discover this faster, and it is the way my code has always worked.

I first used PVS in 1978, quite by accident. Murray Campbell and I were discussing this idea at the ACM event in Washington, DC. We were running on a Univac, and I suggested that we dial up my local Vax box and make the changes and see how it works. It looked pretty good, with the only odd thing being fail highs on very minor score changes, which was OK. The next round, our Univac developed a memory problem and I switched back to the vax and had a few exciting moments when we came out with a Nxf7!! sort of output, only to see the score rise by 2 or 3 millipawns. Even in 1978 we just searched the first move with normal alpha/beta and then went into the null-window search, just as the code exactly does in Crafty...

[bob]

see also
http://www.talkchess.com/forum/viewtopic.php?t=24883

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

[bob]

see also
http://www.talkchess.com/forum/viewtopic.php?t=24883

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.