Nodes type clarification.

[mathmoi]

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

[hgm]

I use IID in any node. It makes no sense to do it only in cut-nodes, as you cannot really prevent it from happening in an all node: the node after the all-node is a cut-node. So if you try to search full-depth at once in the all node, the tree is still deepened level by level from the nodes immediately after it. So you don't gain anything compared to doing IID in the all-node as well.

And there always is the risk that a predicted all node becomes a cut-node on deeper search. And if you would have committed yourself to searching each move at full depth before starting with the next move, you would have wasted an enormous amount of search effort before you notice the switch.

[Pradu]

What am I not understanding? Can someone give me some explanation on nodes types and how to recognize/predict them?

Thanks

This is how I do it:

Let me state my definitions up front:
An OPEN node is a node where you expect alpha<return_score<beta for the next move being searched.
An ALL node is a node where you expect return_score<=alpha for the next move being searched.
A CUT node is a node where you expect the return_score>=beta for the next move being searched.

The root node starts off an OPEN node.
All children of OPEN nodes are OPEN nodes.

After the first move of an OPEN node is searched, it becomes an ALL node (you expect that the rest of the moves to fail low because you assume good move ordering). And you do zero-window searches to try to prove that they fail low.

If any of the zero-window searches on the "OPEN turned ALL" node fail high, then the node turns back into an OPEN node and you do the research assuming that the current node is an OPEN node. After this move is researched, the OPEN node becomes an ALL node again because one move was searched and you expect the rest of the moves to fail low.

All children of ALL nodes are CUT nodes. (ALL node is expected to fail low, so children CUT nodes are expected to fail high)

All children of CUT nodes are ALL nodes. (CUT node is expected to fail high, so children CUT nodes are expected to fail low)

Now lets say you search the first move of a CUT node and it fails low. What does it turn into? If you assume good move ordering, you can turn it into an ALL node. But say you had some other well ordered moves for the CUT node (like killer moves or captures or something), you could search them as a CUT node, then search the rest as an ALL node.

[xsadar]

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

Another definition of PV node is any node in PVS that does not have a null window. This is because it is expected to be a PV node by the other definition, which you gave above (and would have to be either a PV node or a cut node by that definition if there were no search instability). If you are doing standard alpha-beta instead of PVS then to me, it seems impossible to predict which nodes are PV nodes beyond the left side of the tree.

[Pradu]

Another definition of PV node is any node in PVS that does not have a null window. This is because it is expected to be a PV node by the other definition, which you gave above (and would have to be either a PV node or a cut node by that definition if there were no search instability). If you are doing standard alpha-beta instead of PVS then to me, it seems impossible to predict which nodes are PV nodes beyond the left side of the tree.

It is possible when you make the assumption that you have reasonably good move ordering on OPEN and CUT nodes (this is the assumption made when using PVS anyways).

[Harald]

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:

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":

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

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

[Pradu]

All children of ALL nodes are CUT nodes. (ALL node is expected to fail low, so children CUT nodes are expected to fail high)

I can't edit the post anymore... but I meant to say

(ALL node is expected to fail low, so children of ALL nodes are expected to fail high)

[Pradu]

This seems to be similar to Bob's method, but I am too tired to examine or draw it.

Yes, it looks similar. Perhaps it's the same for Bob's method as well, but ALL nodes can change to OPEN nodes when alpha is expected to improve (for example PVS zero-window search fails high).

[bob]

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

Here is the easiest way to deal with this, although this applies to a normal alpha-beta search (PVS changes this a bit).

The root node is always an ALL node. The first node searched below an ALL node is also an ALL node. Except for this first node below an ALL node, all other nodes immediately below an ALL node are CUT nodes. It is simple after that. If a node follows an ALL node, it is a CUT node. If a node follows a CUT node, it is an ALL node.

If you want to factor in PV nodes, then we can change that to this:

The root node is a PV node. The first successor of a PV node is always a PV node. Other successors of a PV node are CUT nodes. And as before, any successor of an ALL node is a CUT node and vice-versa. If you traverse the tree in the usual left-to-right graph, the left edge of the graph contains the PV nodes. There are no others unless move ordering is incorrect...

For parallel search, you want to split only at ALL nodes, never at CUT nodes. YBW is a methodology that approaches that goal since if you search a branch from any node and do not get a cutoff, then that node must be an ALL node (again assuming good move ordering).

[bob]

I use IID in any node. It makes no sense to do it only in cut-nodes, as you cannot really prevent it from happening in an all node: the node after the all-node is a cut-node. So if you try to search full-depth at once in the all node, the tree is still deepened level by level from the nodes immediately after it. So you don't gain anything compared to doing IID in the all-node as well.

And there always is the risk that a predicted all node becomes a cut-node on deeper search. And if you would have committed yourself to searching each move at full depth before starting with the next move, you would have wasted an enormous amount of search effort before you notice the switch.

The reason to not do it at ALL nodes is that move ordering is completely irrelevant there, and trying to improve on something that is irrelevant ends up just wasting time...