Computer Chess Club Archives




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


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 will locate it for you.


This page took 0.07 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.