Author: Cheok Yan Cheng
Date: 01:55:37 06/10/01
Go up one level in this thread
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. 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.