mathmoi wrote:Hi,
I'm thinking about implementing IID (Internal Iterative Deepening) for the first time. From what I red, I should only use IID in PV-nodes and "predicted Cut-Nodes".
I've been reading about nodes types on CPW (
http://chessprogramming.wikispaces.com/Node+Types) and I must say, I'm confused.
It says :
PV-nodes (Knuth's Type 1) are nodes that have a score that ends up being inside the window. So if the bounds passed are [a,b], with the score returned s, a . These nodes have all moves searched, and the value returned is exact (i.e., not a bound), which may propagate down (up?) to the root.
But how can I know that a node will not fail high or low before I search it (my engine use aspiration window)?
But even if I consider that the root node and leftmost nodes (first child of a PV-Node) are always PV-Node, the CPW is still confusing me. It says that all siblings nodes of a PV-Node are Cut-Nodes (nodes where a Fail-High occurs). That seems false to me. If we knew that all siblings of a PV-nodes are gonna fail-high we wouldn't need to search them.
What am I not understanding? Can someone give me some explanation on nodes types and how to recognize/predict them?
Thanks
You are right. The definition is useless when it is based on a search that
is done and the show is over. What is needed is a prediction or a guess
of the node type. Here are some methods:
Gerd Isenberg wrote:
Hmm, is it worth to update node types incrementally during search?
I guess with a counter of played pv-moves (0..N) in the top of the current path
and ply index one may determine the minimal tree node type as well...
So we have distance D of the current node to the last pv node in the current
path.
If D == zero we have a pv-node.
If D is odd we have a cut node.
If D is even and greater zero we have an all node.
Gerd's trees look like this:
Code: Select all
P
/ | \
/ | \
/ | \
/ | \
/ | \
P C C
/ | \ / | \ / | \
/ | \ / | \ / | \
P C C A A A A A A
/|\ /|\ /|\ /|\ /|\ /|\ /|\ /|\ /|\
PCC AAA AAA CCC CCC CCC CCC CCC CCC
From the Paper "The DTS high-performance parallel tree search algorithm":
Robert Hyatt wrote:
3.1 Node types PV, CUT and ALL.
Knuth and Moore clearly defined three node classes of nodes within the alpha/beta minimax tree [Knut75]. While their analysis was centered on a minimal game-tree with perfect move ordering, the concepts they presented also apply to "real" alpha/beta trees, even though it is impossible to produce perfect move ordering [Hyatt89]. In this context we use the terminology developed in [Marsland85], which uses the terms PV, CUT and ALL instead of type one, two and three.
Type one (PV) nodes. The root position is a type one node. The first successor of a PV node is also a PV node while all other successors of a PV node are CUT nodes. PV nodes require examination of all their successors. A PV node is easy to recognize, because both alpha and beta are at their original values since nothing has yet been searched.
Type two (CUT) nodes. A CUT node is a successor of either a PV node (as given above) or an ALL node. A CUT node only requires examination of one successor (for perfectly ordered game trees.) This is the node type that we must recognize and avoid selecting as a split-point, because with best move ordering, only one branch needs to be searched, which leaves no work for additional processors, other than work that is completely unnecessary.
Type three (ALL) nodes. An ALL node is a successor of a CUT node and requires examination of all its successor branches. Even more interesting, move ordering within a type three node is completely unimportant and has no effect on the total nodes searched. This is an important node type in a parallel search because every move must be searched, offering plenty of work that can be done in parallel.
From these definitions, several things become apparent. (1) Type three (ALL) nodes are perfect candidates for parallel searching since all successors must be searched, and the order of traversal for these successors is unimportant. (2) Type two (CUT) nodes must be avoided as split points since only one successor must be examined. If such a node is chosen as a split point, extra branches will be searched, resulting in wasted work. (3) Type one (PV) nodes appear to be good candidates for parallel search until careful study uncovers the fact that the first successor of a type one node must be completely examined before any of the other successors. This is required since the first branch establishes a search bound for the remainder of the successors, and if they are searched before this bound is known, extra work might be done.
3.2 Classifying node types.
When a processor generates a HELP command, and obtains tree-state data from busy processors, it must (if possible) establish a split point so that it (and other idle processors) can "join in" and help. From section 3.1, it becomes obvious that type ALL nodes make desirable split points, type PV nodes make desirable split points AFTER the first successor of the node has been completely searched, and type CUT nodes must be avoided at all costs.
Cray Blitz contains a function TypeNode(), that types any node from ply one to the current ply. this function is called by function Split() to make an initial "guess" of the node types for each ply in the current processor's search space.
It makes the following assumptions. If, for the current node being tested, the values of alpha and beta are equal to the initial search window, then this node is a PV node. Otherwise, if the current node is at an odd ply and alpha is equal to the lower initial search bound, or the current node is at an even ply and beta is equal to the upper initial search bound, then the node type is CUT. For all other cases, it is type ALL.
Split() uses the above algorithm to set its initial guess for each node type from ply 1 through the current ply. Next it enters an "override" phase. Split() starts at ply=2 and checks the number of moves that have been zeroed by the search (the number of moves that have actually been searched.) For an ALL node, many moves already searched increases the "confidence" that this is truly an ALL node. For CUT nodes, if more than one move has been searched, then the confidence for this CUT node is lowered, since it should not be necessary to search more than one move at a real CUT node. In fact, if more than some limit of moves has been examined (currently=3) then the type for this node is overridden and set to ALL, since it appears that move ordering has somehow failed to search the best move first at some previous ply.
After this override phase, a final simple check is made since it is now possible to have two ALL nodes on successive plies. If this happens, the second ALL node probably means that the successor to this node is really a CUT node and we are resetting the upper/lower search bounds after searching a wrong first move somewhere. The final override phase will note the second ALL node, and then force the successor of this node to be type CUT since yet another ALL node can't follow this one unless move ordering is hopelessly bad. This phase of the override code simply allows only two ALL nodes to be consecutive in the tree. After the second ALL node, the next node must be CUT, the next ALL, etc. For all of these overrides the confidence is very "low" and, again, the number of moves searched at each ply is used to improve this confidence.
Bob's trees look like this:
Code: Select all
P
/ | \
/ | \
/ | \
/ | \
/ | \
P C C
/ | \ / : / :
/ | \ / /
P C C A A
/|\ /: /: /|\ /|\
PCC A A CCC CCC
But they can change into something like this if the cut nodes become
all nodes at the places indicated by : in the tree above.
Code: Select all
P
/ | \
/ | \
/ | \
/ | \
/ | \
P CA CA
/ | \ / | / |
/ | \ / /|\ / /|\
P CA CA A CCC A CCC
/|\ /| /| /|\ ||| /|\ |||
PCC AC AC CCC AAA CCC AAA
Pradyumna Kannan wrote:
Here's a small analysis of zero window searches and perhaps a slight enhancment to PVS as well. Here's a slightly unconventional node type classification I use for imperfectly ordered trees:
Code:
OPEN Nodes
----------
The root node is an OPEN node.
All children of OPEN nodes are an OPEN nodes.
An OPEN node changes to an ALL node when alpha is raised.
ALL Nodes
---------
All children of ALL nodes are CUT nodes.
An ALL node changes an OPEN node when the scout search fails high.
(will define "scout search" later)
CUT Nodes
---------
The first child of a CUT node is an ALL node.
A CUT node changes to an ALL node when the first move fails low.
Notes:
======
Parallelism isn't good on OPEN nodes because there is too much search overhead for the current window. It is very likely that the window will be smaller at a later time and that parallel search should wait until the window is smaller.
Parallelism isn't good on CUT nodes because there is too much search overhead because one of the moves will cutoff the search.
Parallelism is possible only on ALL nodes.
Basically from the definitions, on OPEN nodes we know that a move will at a later time will likely increase alpha. On CUT nodes we know that the first move will likely cause a cutoff. On ALL nodes it is likely that all the moves will fail low. So basically just like in PVS we can do a "scout search" that tests only for the fail high or fail low and does a research of the move as an OPEN node if it doesn't:
This seems to be similar to Bob's method, but I am too tired to
examine or draw it.
Harald