Computer Chess Club Archives

Messages

Subject: Re: "ALL node" definition

Author: Tom Likens

Date: 14:17:46 02/21/03

Go up one level in this thread

```On February 21, 2003 at 13:26:34, Alvaro Jose Povoa Cardoso wrote:

>Could someone please define what "ALL node" is and axplain how do we process
>these type of nodes?
>
>Best regards,
>Alvaro Cardoso

Alvaro,

The node types were first defined by Knuth.  They basically refer
to the nature of the nodes in a perfectly ordered tree that is
searched with the alpha-beta algorithm.  He defined the nodes into
three types (called appropriately enough type 1, 2, and 3 ;)

Type 1
------
1. The principal variation consists of Type 1 nodes.
2. All the moves at type 1 nodes have to be searched, and
move ordering is *very* important.
3. The first child of a type 1 node is also a type 1 node
4. All other children of a type 1 node are type 2 nodes

Type 2
------
1. Only the first child of a type 2 node needs to be search since
it will (again, remember this is a "perfectly" ordered tree)
cause a beta cutoff and return.
2. All children of a type 2 node are type 3 nodes

Type 3
------
1. All children of type 3 nodes are type 2 nodes
2. All children of type 3 nodes must be searched and move
ordering is *irrelevant*.
3. This is an ALL node, since all the moves need to be searched
and the order will not help in achieving a quick cutoff.

Knuth's original paper has just been recently re-released in
the new book "Selected Papers on the Analysis of Algorithms".
A quick search on Amazon.com will locate it for you.

regards,
--tom

```