PVS

[diep]

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

Actually IID gets used differently: if you don't have a move from hashtable, do an IID (with some additional conditions which are different from program to program, some might not want to try IID at expected allnodes for example).

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

Actually IID gets used differently: if you don't have a move from hashtable, do an IID (with some additional conditions which are different from program to program, some might not want to try IID at expected allnodes for example).

All I am saying is that if you are in a PV node, you expect your moves to be ordered. Not having an entry in a hash table is an example of detecting an unordered condition (for those that use hash tables; some programs don't), and IID is on way of getting the moves ordered.

[diep]

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

I feel what is needed is showing what PVS is, let's quickly write down something:

You start with root window -infinite,infinite
First move window keeps unchanged.
After that you search with alfa,alfa+1 and in case of a fail high and beta != alfa+1 then you research with open window:

Code: Select all

Call from root:
    rootscore = PVS(-infinite,infinite,depthleft);

int PVS(alfa,beta,depthleft) {
  if&#40; depthleft <= 0 ) return qsearch&#40;alfa,beta&#41;;

  using fail soft with negamax&#58;
  bestscore = -alfabeta&#40;-beta,-alfa,depthleft-1&#41;;
  if&#40; bestscore > alfa ) &#123; 
    if&#40; bestscore >= beta ) 
      return bestscore;
    alfa = bestscore;    
  &#125;

  for&#40; all remaining moves ) &#123;
    score = -alfabeta&#40;-alfa-1,-alfa,depthleft-1&#41;;
    if&#40; score > alfa && score < beta ) &#123;
      // research with window &#91;alfa;beta&#93;
      score = -alfabeta&#40;-beta,-alfa,depthleft-1&#41;;
      if&#40; score > alfa ) 
        alfa = score;      
    &#125;

     if&#40; score > bestscore ) &#123;
       if&#40; bestscore >= beta )
         return score;
       bestscore = score;
     &#125;
  &#125;
  return bestscore;
&#125;

The above is exactly how i'm using PVS in Diep and it works great.

Note that YBW for parallel search uses the same assumption and over time it has proven to have the best speedup of all algorithms (note that deciding WHERE to split in the tree is another issue that's independant from not splitting the first move).

[Gian-Carlo Pascutto]

Thanks for posting this.

If after reading this thread, you're still now sure what fail-soft vs fail-hard is or which PVS implementation is the best, I'd strongly recommend to use exactly the version Vincent posted: fail-soft PVS without aspiration search.

[Gerd Isenberg]

I guess at some places, you call PVS instead of alphabeta recursively.

[Gian-Carlo Pascutto]

I guess at some places, you call PVS instead of alphabeta recursively.

You're right. In fact, you would call PVS everywhere. Just replace alphabeta by PVS in Vincents post.

[Gerd Isenberg]

I guess at some places, you call PVS instead of alphabeta recursively.

You're right. In fact, you would call PVS everywhere. Just replace alphabeta by PVS in Vincents post.

Yes, while it is quite "modern" to use a distinct routine for the zero window search, which covers the vast majority of the Cut- and All-nodes.

[Sven]

Code: Select all

// ...
     if( score > bestscore ) {
       if( bestscore >= beta )
         return score;
       bestscore = score;
     }
  }
  return bestscore;
}

May I assume that the following is correct:

Code: Select all

// ...
     if( score > bestscore ) {
       if( score >= beta )
         return score;
       bestscore = score;
     }
  }
  return bestscore;
}

i.e., "if( score >= beta )" instead of "if (bestscore >= beta)" ?

Sven

[Gian-Carlo Pascutto]

Yes. Maybe we should repost the code with the 2 bugfixes

[Sven]

Yes. Maybe we should repost the code with the 2 bugfixes

Code: Select all

Call from root:
    rootscore = PVS(-infinite,infinite,depthleft);


int PVS(alfa,beta,depthleft) {
  if&#40; depthleft <= 0 ) return qsearch&#40;alfa,beta&#41;;

  // using fail soft with negamax&#58;
  bestscore = -PVS&#40;-beta,-alfa,depthleft-1&#41;;
  if&#40; bestscore > alfa ) &#123;
    if&#40; bestscore >= beta )
      return bestscore;
    alfa = bestscore;
  &#125;

  for&#40; all remaining moves ) &#123;
    score = -PVS&#40;-alfa-1,-alfa,depthleft-1&#41;;
    if&#40; score > alfa && score < beta ) &#123;
      // research with window &#91;alfa;beta&#93;
      score = -PVS&#40;-beta,-alfa,depthleft-1&#41;;
      if&#40; score > alfa )
        alfa = score;
    &#125;

    if&#40; score > bestscore ) &#123;
      if&#40; score >= beta )
        return score;
      bestscore = score;
    &#125;
  &#125;
  return bestscore;
&#125;

Sven