PVS

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
diep
Posts: 1780
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: PVS

Post by diep » Fri Mar 13, 2009 11:53 pm

CThinker wrote:
Gian-Carlo Pascutto wrote:
Zach Wegner wrote:
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
Posts: 388
Joined: Wed Mar 08, 2006 9:08 pm
Contact:

Re: PVS

Post by CThinker » Sat Mar 14, 2009 12:12 am

diep wrote:
CThinker wrote:
Gian-Carlo Pascutto wrote:
Zach Wegner wrote:
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
Posts: 1780
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: PVS

Post by diep » Sat Mar 14, 2009 1:08 am

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
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
Posts: 1120
Joined: Sat Dec 13, 2008 6:00 pm
Contact:

Re: PVS

Post by Gian-Carlo Pascutto » Sun Mar 15, 2009 9:16 am

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
Posts: 2111
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: PVS

Post by Gerd Isenberg » Sun Mar 15, 2009 10:43 am

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

Gian-Carlo Pascutto
Posts: 1120
Joined: Sat Dec 13, 2008 6:00 pm
Contact:

Re: PVS

Post by Gian-Carlo Pascutto » Sun Mar 15, 2009 11:53 am

Gerd Isenberg wrote: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
Posts: 2111
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: PVS

Post by Gerd Isenberg » Sun Mar 15, 2009 1:30 pm

Gian-Carlo Pascutto wrote:
Gerd Isenberg wrote: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
Posts: 3743
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: PVS

Post by Sven » Mon Mar 16, 2009 2:57 pm

diep wrote:

Code: Select all

// ...
     if&#40; score > bestscore ) &#123;
       if&#40; bestscore >= beta )
         return score;
       bestscore = score;
     &#125;
  &#125;
  return bestscore;
&#125;
May I assume that the following is correct:

Code: Select all

// ...
     if&#40; score > bestscore ) &#123;
       if&#40; score >= beta )
         return score;
       bestscore = score;
     &#125;
  &#125;
  return bestscore;
&#125;
i.e., "if( score >= beta )" instead of "if (bestscore >= beta)" ?

Sven

Gian-Carlo Pascutto
Posts: 1120
Joined: Sat Dec 13, 2008 6:00 pm
Contact:

Re: PVS

Post by Gian-Carlo Pascutto » Mon Mar 16, 2009 4:48 pm

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

Sven
Posts: 3743
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: PVS

Post by Sven » Mon Mar 16, 2009 5:23 pm

Gian-Carlo Pascutto wrote:Yes. Maybe we should repost the code with the 2 bugfixes :)

Code: Select all

Call from root&#58;
    rootscore = PVS&#40;-infinite,infinite,depthleft&#41;;


int PVS&#40;alfa,beta,depthleft&#41; &#123;
  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

Post Reply