Author: Christophe Theron
Date: 23:39:43 06/09/01
Go up one level in this thread
On June 09, 2001 at 22:03:24, Cheok Yan Cheng wrote:
>I just read "scalable search in computer chess" by Heinz, I have some doubt with
>PVS explained by his book. Since I don't see PVS by using minimal window will
>produce more cutoff than original alpha beta search. Consider the case for
>origial alpha beta search
>
>------- beta level
>
>
>------- alpha level
>
>1. If value<=alpha level, ignore value
>2. If value>alpha level and value<beta level, increase the alpha level line to
>value
>3. If value>=beta, happily return the value.
>
>
>For PVS search case,
>------- beta level
>
>******* alpha+1 level
>------- alpha level
>
>@call using [-INFINITY, INFINITY]
>@score := - INFINITY
>
>@start search the rest child node using [alpha, alpha+1] when score is updated
>1. If value<=alpha level, ignore value
>2. If value>alpha level and value<beta level, increase the alpha level line to
>(alpha+1). re-search using original alpha beta search.
>3. If value>=beta, happily return the value.
>
>The book says a good move ordering is needed to make this PVS work well. Then I
>draw a search tree :
> 7 (max)
> 7 4 1 (min)
> 789 456 321 (max)
>
>This the best move ordering. I use original alpha beta search, node "5, 6, 2, 1"
>will not be search due to beta cutoff.
>Then I use PVS search, also node "5, 6, 2, 1" will be cutoff, but more work done
>since it always meet rules 2 (re-search).
>
>Oh man.....I spend the whole mid night to convinct my PVS is GOOD. But I don't
>get the key.
>
>Please help me with this by providing me some tree example to show PVS will tend
>to be FASTER than original alpha beta search.
>
>thank you in advance
>
>regards
>yccheok
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.
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.