Author: Cheok Yan Cheng
Date: 19:03:24 06/09/01
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
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.