Author: Tony Werten
Date: 02:41:25 06/10/01
Go up one level in this thread
On June 10, 2001 at 04:55:37, Cheok Yan Cheng wrote: >On June 10, 2001 at 04:18:49, Tony Werten wrote: > >>On June 10, 2001 at 03:46:02, Cheok Yan Cheng wrote: >> >>>On June 10, 2001 at 02:39:43, Christophe Theron wrote: >>>>The trick is that you do no re-search in the first branches, because the first >>>>branch in the PVS algorithm is searched with the FULL alphabeta window, not a >>>>"null" window (where beta=alpha+1). >>>> >>>>In any position, the first move is searched with an ]alpha;beta[ window, the >>>>returned score becomes the new alpha value (unless there is a cutoff in which >>>>case you quit), and you search the rest of the moves with an ]alpha;alpha+1[ >>>>window. If you get a fail high in any of these moves (and only in this case), >>>>you need to re-search the move with an ]alpha+1;beta[ window. >>> >>>What is the advantages of using ]alpha, alpha+1[ in the 2nd and the rest of the >>>child node? I don't see any point it will produce more cutoff than original >>>alpha beta search. Compare the two windows is >>> >>>]7, 8[ //Null Window search >>>]7, 100[ //original alpha beta search >>> >>>If value<=7, ignore the value. (both windows) >>>If value>=100, return the value (both windows) >>>If value>7 AND value<100, re-search arghhhh...... (only Null windows) >> >>The point is that this 3rd one should not occur very often. > >But both searching can perform 1 and 2. Why we need PVS which will perform 3 >(The bad situation). > >>suppose you search with -100,100 window, 4 ply deep. At ply 4 the score of the >>first move=10. PVS will search the remaining moves with (10,11) and alfabeta >>will search with (10,100). That's why PVS has more cutoffs. >Yes. There will be more cutoff but ... > >Consider the node child value with 9 12 101. You don't get the point. If your moveordering is ok you should have 101,12 and 9. First move is the best, no need for researching. But because pvs searches with a smaller window you should get more cutoffs. Tony >In "9", BOTH will have alpha cutoff (may I conclude that PVS and Original Alpha >beta have same times of alpha cutoff ?) > >In "12", PVS will found that the value exceed 11 and re-search again. (In this >case, I don't consider it as beta cutoff since this cutoff didn't bring any >meaning. It need to re-search it again and only then it will shift up alpha >level to 12.) >But for original alpha beta, it just shift up the alpha level to 12 without >re-searching. > >Same case for "101", PVS search with ]12,13[ and need to do re-search. >alpha beta will immediately return the 100 value. > >number of alpha cutoff (I think they will always be the same) >====================== >1 times for PVS (during "9") >1 times for alpha beta (during "9") > >numbers of beta cutoff >====================== >1 times for PVS (during "101") >(I don't condesider the "cutoff" at (alpha+1) is a real cutoff since it don't >give any meaning) > >1 times for alpha beta (during "101") > >Same cutoff produced by PVS compare with Alpha beta. Instead, it waste time on >re-searching. > >PLEASE SHOW ME SOME TREES EXAMPLE TO SHOW THAT PVS REALLY PRODUCED MORE CUT OFF. >>But the important thing is that researches shouldn't happen very often. I you >>have a not so good moveordering then a-b is a better choice. >> >>Tony >> >>> >>>See! No advantages gain from NULL WINDOWS. This confused me a lot! >>>Please help me with this by providing me some example. >>> >>>>This is a rough explanation of the principle, but I think it highlights a point >>>>you had missed. >>>> >>>>If the move ordering is perfect, you never need to do a re-search, so you have >>>>saved some work because many nodes have been searched with a smaller window. >>>> >>>> >>>> >>>> Christophe
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.