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 wrote: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).Gian-Carlo Pascutto wrote: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.Zach Wegner wrote:That was my first thought too. I don't think either method is fundamentally better, each has its advantages.Gerd Isenberg wrote:see also
http://www.talkchess.com/forum/viewtopic.php?t=24883
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...
PVS
Moderators: hgm, Rebel, chrisw
-
- Posts: 1822
- Joined: Thu Mar 09, 2006 11:54 pm
- Location: The Netherlands
Re: PVS
-
- Posts: 388
- Joined: Wed Mar 08, 2006 10:08 pm
Re: PVS
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 wrote: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 wrote: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).Gian-Carlo Pascutto wrote: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.Zach Wegner wrote:That was my first thought too. I don't think either method is fundamentally better, each has its advantages.Gerd Isenberg wrote:see also
http://www.talkchess.com/forum/viewtopic.php?t=24883
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...
-
- Posts: 1822
- Joined: Thu Mar 09, 2006 11:54 pm
- Location: The Netherlands
Re: PVS
I feel what is needed is showing what PVS is, let's quickly write down something: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
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( depthleft <= 0 ) return qsearch(alfa,beta);
using fail soft with negamax:
bestscore = -alfabeta(-beta,-alfa,depthleft-1);
if( bestscore > alfa ) {
if( bestscore >= beta )
return bestscore;
alfa = bestscore;
}
for( all remaining moves ) {
score = -alfabeta(-alfa-1,-alfa,depthleft-1);
if( score > alfa && score < beta ) {
// research with window [alfa;beta]
score = -alfabeta(-beta,-alfa,depthleft-1);
if( score > alfa )
alfa = score;
}
if( score > bestscore ) {
if( bestscore >= beta )
return score;
bestscore = score;
}
}
return bestscore;
}
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).
-
- Posts: 1243
- Joined: Sat Dec 13, 2008 7:00 pm
Re: PVS
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.
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.
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: PVS
I guess at some places, you call PVS instead of alphabeta recursively.
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: PVS
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.Gian-Carlo Pascutto wrote:You're right. In fact, you would call PVS everywhere. Just replace alphabeta by PVS in Vincents post.Gerd Isenberg wrote:I guess at some places, you call PVS instead of alphabeta recursively.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: PVS
May I assume that the following is correct:diep wrote:Code: Select all
// ... if( score > bestscore ) { if( bestscore >= beta ) return score; bestscore = score; } } return bestscore; }
Code: Select all
// ...
if( score > bestscore ) {
if( score >= beta )
return score;
bestscore = score;
}
}
return bestscore;
}
Sven
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: PVS
Gian-Carlo Pascutto wrote: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( depthleft <= 0 ) return qsearch(alfa,beta);
// using fail soft with negamax:
bestscore = -PVS(-beta,-alfa,depthleft-1);
if( bestscore > alfa ) {
if( bestscore >= beta )
return bestscore;
alfa = bestscore;
}
for( all remaining moves ) {
score = -PVS(-alfa-1,-alfa,depthleft-1);
if( score > alfa && score < beta ) {
// research with window [alfa;beta]
score = -PVS(-beta,-alfa,depthleft-1);
if( score > alfa )
alfa = score;
}
if( score > bestscore ) {
if( score >= beta )
return score;
bestscore = score;
}
}
return bestscore;
}